Shift/Reduce 银联冲突

Question

我正在尝试使用 JFlex 和 Cup 为 javascript-ish 语言编写解析器，但我遇到了一些致命的 shift/reduce 问题和 reduce/reduce问题。

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

我的语法如下：从输入开始；

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: 语法要复杂得多，但我认为如果我看到这些 shift/reduce 问题是如何解决的，我就能解决其余的问题。

感谢您的回答。

Answer 1

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

PROGRAM::= FUNCTION NEWLINE PROGRAM
       |   NEWLINE PROGRAM;

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

这是个问题——无用的非终端真的永远无法匹配任何东西，因此它们最终会导致解析错误——但这不是您报告的解析冲突。冲突来自同一个产品的另一个特征，这与你不能除以0有关。

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

所以这里我们没有算术，我们有符号串。不幸的是，不包含任何符号的字符串实际上是不可见的，就像 0 代表所有这些千年，直到一些阿拉伯数学家注意到什么都不写的价值。

这一切发生的地方是你有

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

但是NEWLINE允许什么都不生产。

NEWLINE ::= salto NEWLINE 
        |   ;

所以 PROGRAM 的第二个递归产生式可能什么都不加。而且它可能多次不添加任何东西，因为生产是递归的。但是解析器需要是确定性的：它需要确切地知道有多少个 nothings 存在，这样它就可以将每个 nothing 减少到一个 NEWLINE 非终结符，然后减少一个新的 PROGRAM 非终结符。而且真的不知道要加多少废话

简而言之，optional nothings和repeated nothings是有歧义的。如果你要在你的语言中插入一个空，你需要确保有一个固定的有限数量的空，因为这是解析器可以明确地剖析空的唯一方法。

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

PROGRAM ::= ...
        |   salto PROGRAM;

尽管它与您当前的问题无关，但我觉得有必要提及 CUP 是一个 LALR 解析器生成器以及您可能已经在 Internet 上学习或阅读的所有关于递归下降解析器无法处理左递归的内容不适用。（我删除了关于解析技术教授方式的咆哮，所以你必须尝试从我留下的提示中恢复它。）自下而上的解析器生成器，如 CUP 和 yacc/bison love 左递归。当然，他们也可以处理右递归，但不情愿，因为除了左递归之外，他们需要为每个递归浪费堆栈space。所以没有必要扭曲你的语法来处理这个缺陷；自然地写语法并开心。（所以你很少需要非终端代表 "the rest of" 东西。）

PD：Plenty of nothing 是对 1934 年歌剧 Porgy and Bess 中歌曲的特定文化引用。

Shift/Reduce 银联冲突

Shift/Reduce conflict in CUP

parsing

compiler-construction

grammar

shift-reduce-conflict

cup