无法消除野牛移位/减少冲突

Question

我正在尝试为此事情添加更多规则，并且它一直在给我这种转变/减少冲突的方式，我不知道为什么会这样做，并且在过去的24小时中我一直在尝试解决此问题

FuncDecl        : RetType ID LPAREN Formals {
                    //code here
                    function($1, $2, $4);

                } RPAREN LBRACE Statements RBRACE {
                    //some code here
                    function($1, $2, $4);
                }   
                | RetType ID LPAREN Formals RPAREN SC 
                {
                    // some code here
                    function($1, $2, $4);
                }
                ;

parser.ypp:94.45-100.17: warning: rule useless in parser due to conflicts [-Wother]
 FuncDecl        : RetType ID LPAREN Formals {
                                             ^
g++ -std=c++11 -o test *.c *.cpp -Wno-deprecated

有人可以向我解释发生了什么吗？以及如何解决此问题？注意：我需要在第一条规则中的RBRACE之前添加代码...

非常感谢你们

Answer 1

作为练习，让我们以此为基础制作一个minimal reproducible example，就像SO帮助总是建议的那样。确实不是那么困难。由于在处理带有野牛的代码段时遇到问题，因此在这种情况下，MRE不必实际编译或运行。

这里是文件（conan.c）：

%token ID
%token RetType Formals Statements
%%
FuncDecl: RetType ID '(' Formals { funcdecl($1, $2, $4); } ')' 
                     '{' Statements '}' { funcdef($1, $2, $4, $8); }
        | RetType ID '(' Formals ')' ';'  { funcdecl($1, $2, $4) }

我已经删除了与该问题无关的所有内容，但仍然有一个可以用野牛处理的文件：

• 不相关的非终端已转换为终端。 （第2行）（如果它们是相关的，将它们转换为终端将使问题消失。既然没有关系，我们知道它们是不相关的。）

• 自由使用单字符标记，以使语法更具可读性，并避免将其声明为标记。 （出于相同的原因，我将把T_FOR之类的多字符标记转换为带引号的字符串（"for"）。）

这样就给了我一个可读的六行代码片段，现在可以用bison处理（我需要添加bison调用以及由此产生的错误，以使此代码可重复且完整）。错误消息现在具有预期的行号：

$ bison -o conan.c conan.y
conan.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
conan.y:4.34-58: warning: rule useless in parser due to conflicts [-Wother]
 FuncDecl: RetType ID '(' Formals { funcdecl($1, $2, $4); } ')' 
                                  ^^^^^^^^^^^^^^^^^^^^^^^^^

现在，解决问题。确实存在转移/减少冲突，因为解析器到达后：

RetType ID ( Formals   )
                     ^
                     |------- lookahead

它必须决定是否执行中间规则动作（funcdecl($1, $2, $4);）。但它尚不知道两种替代产品中的哪一种都适用。第一个要求执行MRA；第二个没有。但是编译器直到看到紧跟在圆括号后的标记后才知道，到那时它将为时已晚（根据LALR（1）算法）。

如摘要所示，第一个替代方案中的MRA与第二个替代方案中的最终操作完全相同。如果确实如此，则解析器实际上不必决定。它可以更早地为第二个替代方案运行最终操作。但是，这种简单的解决方案并不像看起来那样简单，因为bison并未尝试查看两个MRA是否是相同的代码。它只是假设它们都是不同的，这将导致它仍然必须有所作为。

另一方面，有一个简单得多的解决方案，因为无论是在右括号之前还是之后调用MRA，实际上都没有任何区别。读取令牌不会发生任何事情（除了增加行计数器之外，如果这是一个问题，则应使用位置对象）。移动MRA将导致：

%token RetType Formals Statements
%token ID
%%
FuncDecl: RetType ID '(' Formals ')'  { funcdecl($1, $2, $4); }
                     '{' Statements '}' { funcdef($1, $2, $4, $8); }
        | RetType ID '(' Formals ')' ';'  { funcdecl($1, $2, $4) }

现在冲突消失了：

$ bison -o conan.c conan.y
$

这是因为MRA决定是在解析已到达的点做出的

RetType ID ( Formals )   {
                       ^
                       |----- lookahead

现在，前瞻足以确定。 （在另一种选择中，前行是;。）>