解决GnuWin32 Bison中的Shift/Reduce警告

Question

我有以下规则，当我用bison实现它们时，我得到5个shift/reduce警告。

规则的一部分是:

Type---->        BOOL   
    |   INT 
    |   CHAR    
    |   DOUBLE  
    |   ID  
    |   INT '['']'
;
rule:           VarDec rule
    |   VarDec
;
VarDec: Type ID ';'
;

和Parser.output在这种状态下给我警告:

**state 25**

4 rule: VarDec . rule
5     | VarDec .
BOOL        shift, and go to state 3
INT         shift, and go to state 4
CHAR        shift, and go to state 5
DOUBLE      shift, and go to state 6
ID          shift, and go to state 7
BOOL        [reduce using rule 5 (rule)]
INT         [reduce using rule 5 (rule)]
CHAR        [reduce using rule 5 (rule)]
DOUBLE      [reduce using rule 5 (rule)]
ID          [reduce using rule 5 (rule)]
$default    reduce using rule 5 (rule)
rule            go to state 28
VarDec          go to state 25
Type            go to state 27

谁能帮我解决这个问题，我已经读了很多文章，但我不能找出什么是错误的，并提前感谢每一个…:)

Answer 1

上面的例子不足以重现shift/reduce冲突。您可能在其他地方有一个rule的实例，后面跟着VarDec或它开头的令牌。

如果我添加以下规则，我可以重现冲突:

decl : rule VarDec;

Answer 2

冲突发生在这样的状态:在解析堆栈的顶部有一个VarDec，而下一个令牌是BOOL、INT、CHAR、DOUBLE或ID。然后，解析器需要至少提前查看两个令牌，以确定它是否正在查看另一个VarDec——在这种情况下，现在的正确操作是转移，以预期稍后将以下令牌减少为"规则"——或者它是否正在查看其他内容——在这种情况下，正确的操作是将当前位于堆栈顶部的VarDec减少为"规则"。

应该可以通过改变你的'rule'规则来解决这个特殊的冲突，像这样:

rule: rule VarDec
  | VarDec
;

使用左递归而不是右递归。这也很好，因为在Bison规则中，应该总是使用左递归而不是右递归。这确保您可以解析具有有限堆栈空间的任何输入。

Bison识别的实际状态可能会因该更改而有所不同，但在可能的情况下，堆栈顶部仍然有一个VarDec，下一个令牌是BOOL, INT, CHAR, DOUBLE或ID，只有一种可能的操作(仅提供规则):将堆栈上的VarDec减少为"规则"。没有其他可能的解析，即使后来发现即将到来的令牌没有减少到VarDec。