如何在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
      ;

我这样做了转换/减少冲突,我怎样才能改变语法来停止？基本上它需要在新行之后进行分支,并查看下一个是TERMINAL2还是TERMINAL3.

Answer 1

模糊语法,而不是LALR(1),默认为yacc模式不可解析

总而言之,您可以使用以下%glr-parser声明"修复"此问题:

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

长话故事有点中长......

Shift-reduce冲突通常不是错误.通过总是做你想要的转变来解决冲突.大多数或所有现实世界的语法都有移位减少冲突.如果您想要减少,您可以使用优先级声明来安排.

然而,在一个真正含糊不清的语法中,执行移位会将解析器发送到两个路径中的一个路径,其中只有一个最终会在语法中找到一个字符串.在这种情况下,S/R冲突是致命错误.

分析所述第一种,当解析器看到换行符的| rule2 NEWLINE rule3_list情况下,它可以或者转移到其将被预期rule3_list新的状态,或者它可以使用降低规则1 rule1: rule2.由于默认选择shift,它总是会查找rule3_list.

当它看到换行符时发生第二次冲突 rule3_list: rule3_list . NEWLINE rule3.现在,它可以任意转移,并开始寻找规则3或使用减少规则1 | rule2 NEWLINE rule3_list.

结果是写入时,假设终端为"2"和"3",则只能解析2行后跟3行.如果你摆弄优先级,你只能解析'2'行,而不是'3'行.

最后,我应该补充一点,使用yacc生成的GLR解析器是一个很好的解决方案.我想它会工作得很好,但它是纯粹的BFI,解析器分裂,保持两个堆栈,继续向下两个路径,直到找到语法中的字符串.可悲的是,其他修复也是kludges:1.将语法重新表述为LALR(1),2.在扫描仪中添加额外的前瞻并返回复合令牌,3.试验你所拥有的语法规则,也许yacc可以处理一种变化.

这就是为什么我实际上并不喜欢yacc,而更喜欢手写的递归下降或像PEG那样更现代的东西.(见树顶.)

我尝试了一些(首选的)左递归规则,它们简单地忽略了换行符(这会使你的语法变得复杂,制作空格标记......)..而且这个"有效",虽然我不确定它是否是你想要的. ..

%%
start:   stmtList
      ;

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

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