解决 yacc 冲突 - 由于冲突规则在解析器中无用

Question

我正在处理 yacc 文件以解析给定文件并将其转换为等效的 c++ 文件。我根据提供的语法图创建了以下语法：

program:    PROGRAMnumber id 'is' comp_stmt
            ;

comp_stmt:    BEGINnumber statement symbol ENDnumber
              ;

statement:    statement SEMInumber statement 
              | id EQnumber expression
              | PRINTnumber expression
              | declaration
              ;

declaration:    VARnumber id
                ;

expression:    term
               ;

term:    term as_op term
         | MINUSnumber term
         | factor
         ;

factor:    factor md_op factor
           | ICONSTnumber
           | id
           | RPARENnumber expression LPARENnumber
           ;

as_op:    PLUSnumber
          | MINUSnumber
          ;

md_op:    TIMESnumber
          | DIVnumber
          ;

symbol:    SEMInumber
           | COMMAnumber
           ;

id:    IDnumber
       | id symbol id
       ;

唯一剩下的问题是我在尝试使用 yacc 进行编译时收到此错误。

conflicts: 14 shift/reduce
calc.y:103.17-111.41: warning: rule useless in parser due to conflicts: declaration: VARnumber id

我已经解决了我遇到的唯一的其他冲突，但我不确定这个冲突的解决方案是什么。它应该匹配的行的格式为

var a, b, c, d;

或

var a;

Answer 1

您所有旨在派生列表的作品都是模棱两可的，因此会产生 reduce/reduce 冲突。例如：

 id: id symbol id

当有三个标识符时会明显有歧义：是先减去前两个，还是后两个？通常的列表习惯用法是左递归：

id_list: id | id_list `,` id

对于大多数语言来说，这对于以分号终止而不是分隔的语句来说是不正确的，但该模型适用于以逗号分隔的标识符列表，或适用于加法运算符的左关联序列。

对于语句，您可能需要更像这样的东西：

statement_list: | statement_list statement ';'

说到symbol，你真的相信,和;有相同的句法功能吗？这似乎不太可能，因为您写的是 var a, b, c, d; 而不是 var a; b, c; d,.

bison产生的"useless rule"警告正是因为你的语法允许id用分号分隔。当解析器看到 "var" ID 和 ; 作为 lookahead 时，它首先将 ID 减少到 id 然后需要决定是否将 var id 减少到 declaration 或移动 ; 以便稍后将其减少到 symbol，然后继续减少 id symbol id。在没有优先规则的情况下，bison 总是解决 shift/reduce 有利于移位的冲突，所以这就是它在这种情况下所做的。但结果是永远不可能将 "var" id 减少到 declaration，由于 shift-reduce 冲突解决的结果，生产变得无用，这或多或少是警告所说的。

解决 yacc 冲突 - 由于冲突规则在解析器中无用

Resolving yacc conflicts - rules useless in parser due to conflicts

c

yacc