转移/减少 CUP 中的冲突

Question

我正在尝试使用 JFlex 和 Cup 为 javascript 风格的语言编写一个解析器，但是我遇到了一些致命的移位/归约问题和归约/归约问题。

我已经彻底搜索并找到了大量示例，但我无法将它们推断为我的语法。到目前为止我的理解是，这些问题是因为解析器无法决定应该采取哪种方式，因为它无法区分。

我的语法如下：从 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 ::=  ;

我遇到了一些冲突，但这两个只是一个例子：

 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：语法要复杂得多，但我认为如果我看到这些移位/归约问题是如何解决的，我将能够解决其余问题。

感谢您的回答。

Answer 1

PROGRAM没有用（在技术意义上）。也就是说，它不能产生任何句子，因为

PROGRAM::= FUNCTION NEWLINE PROGRAM
       |   NEWLINE PROGRAM;

的两个产生式PROGRAM都是递归的。为了使非终结符有用，它需要能够最终产生一些终结符串，并且为了做到这一点，它必须至少有一个非递归产生式；否则，递归永远无法终止。我很惊讶 CUP 没有向您提及此事。或者也许确实如此，而您选择忽略该警告。

这是一个问题 - 无用的非终端实际上​​无法匹配任何内容，因此它们最终会导致解析错误 - 但这不是您报告的解析冲突。冲突来自同一产生式的另一个特征，这与不能除以 0 的事实有关。

关于“无”的问题是，任何数量的“无”仍然是“无”。因此，如果你有很多空东西，而有人过来问你到底有多少空东西，你就会遇到一些问题，因为要从“0 * 很多”返回“很多”，你必须计算“0 / 0”，这不是一个明确定义的值。（如果你有很多个二，有人问你有多少个二，那不会有问题：假设有很多二，结果是 40；你可以很容易地计算出 40 / 2 = 20，结果是完美，因为 20 * 2 = 40。）

所以这里我们没有算术，我们有符号串。不幸的是，不包含符号的字符串实际上是不可见的，就像 0 已经存在了几千年，直到一些阿拉伯数学家注意到无法写入任何内容的价值。

这一切都发生在你有

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

但NEWLINE不允许产生任何东西。

NEWLINE ::= salto NEWLINE 
        |   ;

因此，第二次递归生成PROGRAM可能不会添加任何内容。而且它可能多次不会添加任何内容，因为产生式是递归的。但解析器需要是确定性的：它需要确切地知道存在多少个无，以便它可以将每个无减少为非NEWLINE终结符，然后减少一个新的PROGRAM非终结符。而且它真的不知道要添加多少个虚无。

简而言之，可选的nothings和重复的nothings是有歧义的。如果要在语言中插入“无”，则需要确保“无”的数量是固定的、有限的，因为这是解析器能够明确剖析“无”的唯一方法。

现在，因为该特定递归的唯一点（据我所知）是允许空的换行符终止语句（由于换行符而可见，但不执行任何操作）。你可以通过改变递归来避免任何事情：

PROGRAM ::= ...
        |   salto PROGRAM;

虽然它与您当前的问题无关，但我觉得有必要提及 CUP 是一个 LALR 解析器生成器，并且您可能在互联网上学到或阅读的所有关于递归下降解析器无法处理左递归的内容都不适用。（我删除了关于解析技术教学方式的咆哮，所以你必须尝试从我留下的提示中恢复它。） 像 CUP 和 yacc/bison 这样的自下而上的解析器生成器喜欢左递归。当然，它们也可以处理右递归，但很不情愿，因为除了左递归之外，它们还需要为每个递归浪费堆栈空间。因此，没有必要为了弥补这个缺陷而扭曲你的语法。自然地写出语法并感到高兴。（所以你很少需要非终结符来代表某些东西的“其余部分”。）

PD：《Plenty of Nothing》是对 1934 年歌剧《波吉与贝丝》中一首歌曲的特定文化参考。