在CUP中移位/减少冲突

我正在尝试为JFlex和Cup编写javascript-ish语言的解析器，但是我遇到了致命移位/减少问题以及减少/减少问题的一些问题。在CUP中移位/减少冲突

我已经彻底搜索并发现了大量的例子，但我无法将这些推断到我的语法。我迄今为止的理解是，这些问题是因为解析器无法确定它应该采用哪种方式，因为它无法区分。

我的语法如下：以INPUT开头;

INPUT::= PROGRAM; 

PROGRAM::= FUNCTION NEWLINE PROGRAM 
| NEWLINE PROGRAM; 

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der; 

    OPTIONAL ::= 
    | TYPE; 


    TYPE::= integer 
    | boolean 

    ARG ::= 
    | TYPE id MORE_ARGS; 

    MORE_ARGS ::= 
    | colon TYPE id MORE_ARGS; 


    NEWLINE ::= salto NEWLINE 
    | ; 

    BODY ::= ;

我得到一些冲突，但这些2仅仅是个例子：

Warning : *** Shift/Reduce conflict found in state #5 
between NEWLINE ::= (*) 
and  NEWLINE ::= (*) salto NEWLINE 
under symbol salto 
Resolved in favor of shifting. 

Warning : *** Shift/Reduce conflict found in state #0 
between NEWLINE ::= (*) 
and  FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
under symbol function 
Resolved in favor of shifting.

PS：语法要复杂得多，但我想，如果我看到这些移位/减少的问题已解决，我将能够解决其余问题。

感谢您的回答。

来源

2017-06-04 inidar

PROGRAM是无用的（in the technical sense）。也就是说，它不能产生任何句子，因为在

PROGRAM::= FUNCTION NEWLINE PROGRAM 
     | NEWLINE PROGRAM;

这两个产品的PROGRAM是递归的。为了使非终端有用，它需要能够最终生成一些终端串，为此它必须至少有一个非递归生产;否则，递归永远不能终止。我很惊讶银联没有提到你。或者它可以，而且你选择忽略警告。

这是一个问题 - 无用的非终端真的无法匹配任何东西，所以它们最终会导致解析错误 - 但这不是您报告的解析冲突。冲突来自同一生产的另一个特点，这与你不能以0分割的事实有关。

关于什么都不是，没有任何数量的东西仍然没有。所以，如果你有很多不知道的东西，并且有人过来问你究竟有多少个没有，你会有一些问题，因为要从“0 *很多”中获得“充足”，你必须计算“0/0”，这不是一个明确定义的值。（如果你有足够多的两个人，并且有人问你有多少个，那么这不会是一个问题：假设大量的二者达到40，你可以很容易地计算出40/2 = 20，这可以解决问题因为20 * 2 = 40。）

所以在这里我们没有算术，我们有一串符号。不幸的是，没有符号的字符串真的是看不见的，就像所有那些千年数字都是0，直到一些阿拉伯数学家发现不能写任何东西的价值。

如果这是所有在我身边的就是，你有

PROGRAM::= ... something ... 
     | NEWLINE PROGRAM;

但NEWLINE被允许生产什么。

NEWLINE ::= salto NEWLINE 
     | ;

因此，PROGRAM的第二次递归生产可能不会添加任何内容。而且它可能不会增加很多次，因为生产是递归的。但是解析器需要具有确定性：它需要确切地知道存在多少个nothings，这样它就可以将每个nothing减少到非终端，然后减少一个新的非终端PROGRAM。它真的不知道要添加多少空格。

总之，可选的记号和重复的记号是不明确的。如果您要在您的语言中插入任何内容，则需要确保有固定数量的nothings，因为这是解析器可以毫不含糊地解析虚无的唯一方法。

现在，由于该特定递归的唯一一点（据我所知）是允许空的换行符终止的语句（因为换行符而可见，但什么都不做）。你能做到这一点通过改变递归避免什么：

PROGRAM ::= ... 
     | salto PROGRAM;

虽然它不相关的当前的问题，我觉得有必要提一提，银联是一个LALR解析器生成和所有的东西你可能已经在互联网上了解或阅读了关于递归下降解析器不能处理左递归不适用。（我删除了关于解析技术的教学方式，所以您必须尝试从我留下的提示中恢复它。）自下而上的解析器生成器，如CUP和yacc/bison 爱左递归。当然，他们也可以处理右递归，但是很不情愿，因为除了左递归之外，他们需要浪费每个递归的堆栈空间。所以没有必要扭曲你的语法来对付这个缺陷。只是自然写语法而快乐。（所以你很少，如果需要代表什么“的其他”非终端）。

PD：没什么大量是从1934年歌剧Porgy and Bess一个特定的文化参考一首歌。

来源

2017-06-04 05:29:31 rici

@ rici非常感谢。终于有了你的帮助 – inidar

在CUP中移位/减少冲突

回答

相关问题