Bison 冲突转移/减少

Question

我是 bison\yacc 的新手，我正在尝试编写一个类似 pascal 的语法分析器，并且我得到了

analizorSintactic.y: conflicts: 1 shift/reduce 
analizorSintactic.y:65.13-23: warning: rule useless in parser due to conflicts: decllist: declaration

我收到有关以下语法规则的警告

program : PROGRAM IDENTIFIER SEMICOLON content; 
content : VAR decllist SEMICOLON cmpdstmt DOT ;

decllist :  declaration | declaration SEMICOLON decllist ;
declaration : IDENTIFIER COLON type 
        | IDENTIFIER COMMA declaration;

如何解决此冲突？ 谢谢!

Answer 1

首先，请发布一些内容是自给自足的。这并不难:将语法片段中不需要的非终结符转换为标记。对于您的情况:

%%
program : "PROGRAM" "IDENTIFIER" "SEMICOLON" content; 
content : "VAR" decllist "SEMICOLON" "cmpdstmt" "DOT" ;

decllist :  declaration | declaration "SEMICOLON" decllist ;
declaration : "IDENTIFIER" "COLON" "type" 
        | "IDENTIFIER" "COMMA" declaration;

然后，将其提供给 bison --report=all 并读取生成的 *.output 文件，其中包含:

State 10

    3 decllist: declaration .  ["SEMICOLON"]
    4         | declaration . "SEMICOLON" decllist

    "SEMICOLON"  shift, and go to state 14

    "SEMICOLON"  [reduce using rule 3 (decllist)]

换句话说，Bison 不知道如何读取声明后跟的;。这是因为由于 content< 规则，有一个“单个”声明(规则 3)可以后跟一个 ;/。这种冲突无法通过优先级/关联性来解决，因为在某些情况下，移位是正确的(如果在 ; 之后有一个 decllist)，在其他情况下，reduce 是正确的(因为;后面有一个cmpdstmt)。您必须重写语法以帮助解析器生成器“在规则中看得更远”。

例如，您可以将 ; 从 content 规则发送到 decllist 规则:

%%
program : "PROGRAM" "IDENTIFIER" "SEMICOLON" content; 
content : "VAR" decllist "cmpdstmt" "DOT" ;

decllist : declaration "SEMICOLON"
         | declaration "SEMICOLON" decllist ;
declaration : "IDENTIFIER" "COLON" "type" 
        | "IDENTIFIER" "COMMA" declaration;

应该可以了。