c++ - 如何解决 YACC 中的 Shift/Reduce 冲突

Question

我有这样的语法:

“匹配一个或多个 rule1，其中 rule1 是一个或多个 rule2，其中 rule2 是一个或多个 rule3，等等，每个由换行符分隔”。看下面的例子。

start:   rule1_list
      ;

rule1_list:   rule1
           |  rule1_list NEWLINE rule1
            ;

rule1:   rule2
     |   rule2 NEWLINE rule3_list
      ;

rule2:   TERMINAL2
      ;

rule3_list:   rule3
          |   rule3_list NEWLINE rule3
          ;

rule3 :  TERMINAL3
      ;

我在执行此操作时遇到 shift/reduce 冲突，如何更改语法以停止？本质上它需要在新行之后分支并查看下一个是 TERMINAL2 还是 TERMINAL3。

Answer 1

语法不明确，不是 LALR(1)，默认 yacc 模式无法解析

长话短说，您可以使用 %glr-parser 声明“修复”此问题，如下所示:

%glr-parser
%%
start: rule1_list
. . .
. . .

---

把长篇故事变成中等长度的...

Shift-reduce 冲突通常不是错误。通过始终进行通常是您想要的转变来解决冲突。大多数或所有现实世界的语法都有移位减少冲突。如果你想要减少，你可以通过优先声明来安排。

然而，在一个真正有歧义的语法中，进行移位会将解析器发送到两条路径之一，其中只有一条最终会在语法中找到一个字符串。在这种情况下，S/R 冲突是一个 fatal error 。

分析第一个，当解析器看到 | 中的换行符时rule2 NEWLINE rule3_list 情况下，它可以要么转移到一个新的状态，在那里它会期望一个 rule3_list，或者它可以使用 rule1: rule2 减少一个 rule1。由于默认选择 shift，它将始终寻找 rule3_list。

第二个冲突发生在它在 rule3_list: rule3_list 中看到换行符时。换行规则 3。现在它可以要么转移并开始寻找 rule3 或使用 | 减少 rule1 rule2 NEWLINE rule3_list.

结果如所写，假设终端为“2”和“3”，您只能解析 2 行后跟 3 行。如果您摆弄优先级，则只能解析“2”行而不能解析“3”行。

最后，我要补充一点，使用 yacc 生成的 GLR 解析器有点麻烦。我想它会工作得很好，但它是纯 BFI，解析器拆分，保留两个堆栈，继续沿着两条路径前进，直到在语法中找到一个字符串。遗憾的是，其他修复也很麻烦:1. 将语法重新表述为 LALR(1)，2.在扫描器中添加额外的前瞻性并返回复合标记，3。试验您拥有的语法规则，也许 yacc 可以处理变体。

这就是为什么我实际上不喜欢 yacc 而更喜欢手写递归下降或更现代的东西，如 PEG。 (See Treetop.)

我尝试了一些带有(首选)左递归规则的东西，这些规则只是忽略了换行符(这会使你的语法复杂化，制作空白标记......)......并且这个“有效”，虽然我不确定它是否是什么你想要...

%%
start:   stmtList
      ;

stmtList: /* nothing */ 
      | stmtList '2' threeList;
      ;

threeList: /* nothing */
      | threeList '3'
      ;
%%
int yylex() { int c; do {  c = getchar (); } while (c == '\n'); return c; }