YACC程序中的移位减少冲突

我已经写了这个YACC程序来验证字符串w.r.t语法{c^kaⁿb^m: n ≠ m ∧ k,m,n > 0}。 NL代表换行符。令牌通过已经在那里的lex传递。但是，这个错误是给出的。我认为，产生式规则都OK，但我收到此消息：YACC程序中的移位减少冲突

[[email protected] wali1]$ yacc -d assign1.y 
yacc: 2 shift/reduce conflicts, 1 reduce/reduce conflict.

这里是我的语法文件：

%{ 
#include<stdio.h> 
%} 
%token NL A B C 
%% 
stmt : C stmt 
| X NL 
| Y NL 
; 
X : A X B 
| X B 
| B 
; 
Y : A Y B 
| A Y 
| A 
; 
%% 
int yyerror(char *msg) 
{ 
printf("Invalid String!\n"); 
exit(0); 
}

来源

2017-10-05 Hailey

你的语法正确无误的，据我所看到的。但它不是有限的前瞻，更不是LR（1）。

LR（k）解析器必须能够根据对下一个令牌的检查，预测非终端完成时输入点处的缩减。

现在考虑输入包含A令牌的大数字（相对于k），后面跟着B。如果输入最终匹配Y，那么解析器现在必须减少Y → A，然后可能会减少Y → A Y的一个或多个实例，LR解析的从左到右的性质意味着这些减少必须立即发生。

但是没有看到整个输入的其余部分并计算B s的数量，无法知道要减少多少个实例。此外，输入完全可能与X匹配，在这种情况下，B必须移位，因为减少到Y不正确。再次，没有足够的信息来做出这个决定，直到输入结束。

通过将-v选项传递给yacc/bison生成的状态表中显示了这些难题。例如，我们可以看到：

State 1 

    4 X: A . X B 
    7 Y: A . Y B 
    8 | A . Y 
    9 | A . 

    A shift, and go to state 1 
    B shift, and go to state 2 

    B   [reduce using rule 9 (Y)] 
    $default reduce using rule 9 (Y) 

    X go to state 7 
    Y go to state 8

表达的是否最后A降低到Y假设的问题，有更多的A总比B S，或到第一B准备转变为将其减少到X，假设有更多B s比A s。

（冲突由前瞻B的两种不同动作表示，减号动作包含在括号内（[reduce using rule 9 (Y)]），表明野牛通过选择总是移动来解决冲突。当然，这不是总是正确的分辨率，所以你的解析器将不能正确识别需要缩减操作的输入。）

该语言确实有LR（1）语法。诀窍是首先识别A s和B的内部平衡序列，而不强制解析器确定它遇到的句子类型。如果遇到B与A不匹配，或者在某些A尚未匹配时发现句子结尾，则可以作出该决定。

这里，AB是As和Bs的平衡序列。AAB一个或多个A，然后是AB;而ABB是AB后跟一个或多个B s。

stmt: tail NL 
    | C tail NL 
tail: AAB 
    | ABB 
AAB : A AB 
    | A AAB 
ABB : AB B 
    | ABB B 
AB : /* empty */ 
    | A AB B

人们很容易写

AAB : AA AB 
AA : A 
    | A AA

，但它不会工作，因为它需要解析器来决定的A是否为AA的一部分，它曾经看到一个B前。如上所述，A总是移入堆栈，并且在解析器堆栈展开时作出决定。

在另一方面，它会因为解析器到达第一无与伦比B所有相关决定已经作出的时间是不可能有书面的生产ABB以这种方式（ABB: AB BB; BB: B | BB B）。我选择像上面那样做对称。

来源

2017-10-05 15:23:04 rici

对不起，我没有得到它，请你提供解决方案。 – Hailey

@海利：好的，增加了解决方案。如果叙述不能使这个过程足够明显，我建议你使用[野牛的追踪功能]（https://www.gnu.org/software/bison/manual/bison.html#Tracing），这可能会有所帮助你可以看到解析器在做什么。 LR解析的一个很好的参考也可能是有用的。 – rici

YACC程序中的移位减少冲突

回答

相关问题