c++ - Bison 移位/减少冲突无法解决

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) }

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

无关的非终端已转换为终端。 (第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；第二个没有。但是编译器直到看到紧跟在圆括号之后的 token 时才知道，到那时它将为时已晚(根据LALR(1)算法)。

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

另一方面，有一个简单得多的解决方案，因为无论在右括号之前还是之后调用MRA，实际上都没有任何区别。读取 token 不会发生任何事情(除了增加行计数器之外，如果这是一个问题，则应使用位置对象)。移动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

现在，前瞻足以决定。 (在另一种选择中，前瞻是;)。