c - 无法修复 Bison 语法中的移位/减少冲突

Question

我有以下 Bison 语法:

%error-verbose
%{
#include "node.h"
NBlock *programBlock;

#define YYDEBUG 1

extern int yylex();
void yyerror(const char *s) { printf("Error: %s\n", s); }
%}

%union {
    Node *node;
    NBlock *block;
    NBody *body;
    NHeader *header;
    NExpression *expression;
    NStatement *statement;
    NIdentifier *identifier;
    NVariableDeclaration *variableDeclaration;
    NDoWhileStatement *doWhileStatement;
    NWhileStatement *whileStatement;
    NIfStatement *ifStatement;
    NForStatement *forStatement;
    std::vector<NVariableDeclaration*> *variableDeclarations;
    std::vector<NExpression*> *expressions;
    std::vector<NStatement*> *statements;
    std:string *string;
    int token;
}

/*
The %token directive is used to associate a type to a terminal symbol.
%token <type> 'terminal_list'
associates the specific type <type> to each terminal in 'terminal_list'.
The type <type> is the same used in the %union declaration
*/

%token <string> TIDENTIFIER TINTEGER TDOUBLE
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE

/*
The %type directive is used to associate a type to a nonterminal symbol.
%type <type> nonterminal_list
associates the specific type <type> to each nonterminal in 'nonterminal_list'.
The type <type> is the same used in the %union declaration
*/

%type <expression> expression term factor
%type <block> program body header tail statements
%type <statement> statement forStatement ifStatement doWhileStatement whileStatement variableDeclaration
%type <token> comparison
%type <string> identifier_type

/*
Operator precedence for mathematical operators
*/

%left TPLUS TMINUS
%left TMUL TDIV
%left TCEQ TCNE TCLT TCLE TCGT TCGE

/*
Start grammar symbol
*/

%start program

%%

program:                TLBRACE body TRBRACE { printf("Reduce body to program\n"); }
                        ;

body:                   header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); }
                        ;

header:                 TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to header\n"); }
                        ;

variableDeclarations:   variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); }
                        | variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); }
                        ;

tail:                   TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to tal\n"); }
                        ;                   

statements:             statement TSEMICOLON { printf("Reduce statement to statement list\n"); }
                        | statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); }
                        ;

statement:              ifStatement { printf("Reduce if to statement\n"); };
                        | forStatement { printf("Reduce for to statement\n"); };
                        | doWhileStatement { printf("Reduce doWhile to statement\n"); };
                        | whileStatement { printf("reduce while to statement\n"); }
                        | TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); }
                        ;

forStatement:           TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); }
                        ;


ifStatement:            TIF expression TTHEN block { printf("Reduce if to if statement\n"); }
                        | TIF expression block TELSE block { printf("Reduce ifelse to if statement\n"); }
                        ;

doWhileStatement:       TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); }
                        ;

whileStatement:         TWHILE block expression { printf("Reduce while to while statement\n"); }
                        ;

block:                  TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); }
                        | TLBRACE TRBRACE { printf("Reduce empty to block\n"); }
                        ;

variableDeclaration:    identifier_type TIDENTIFIER { printf("reduce uninitialized identifier to variable declaration\n"); }
                        | identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); }
                        ;

identifier_type:        TINT_TYPE { printf("Reduce int to identifier type\n"); }
                        | TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); }
                        | { printf("Reduce empty to identifier type\n"); }
                        ;



expression:             term { printf("Reduce term to expresson\n"); }
                        | expression comparison expression { printf("Reduce comparison to expression\n"); }
                        | expression TPLUS term { printf("Reduce addition to expression\n"); }
                        | expression  TMINUS term { printf("Reduce subtraction to expression\n"); }
                        ;

term:                   factor { printf("Reduce factor to term\n"); }
                        | term TMUL factor { printf("Reduce multiplication to term\n"); }
                        | term TDIV factor { printf("Reduce division to term\n"); }
                        ;

factor:                 TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); }
                        | TMINUS factor { printf("Reduce -factor to factor\n"); }
                        | TIDENTIFIER { printf("Reduce identifier to factor\n"); }
                        | TINTEGER { printf("Reduce integer to numeric\n"); }
                        | TDOUBLE { printf("Reduce double to numeric\n"); }
                        ;

comparison:             TCEQ { printf("Reduce eq to comparison\n"); }
                        | TCNE { printf("Reduce ne to comparison\n"); }
                        | TCLT { printf("Reduce lt to comparison\n"); }
                        | TCLE { printf("Reduce le to comparison\n"); }
                        | TCGT { printf("reduce gt to comparison\n"); }
                        | TCGE { printf("Reduce ge to comparison\n"); }
                        ; 

我遇到了 8 个我不知道如何解决的 shift/reduce 冲突。

以下是我使用 --report=all 参数生成的 parser.output 文件的一部分。这是受 8 个 shift/reduce 冲突影响的状态:

State 79

   29 expression: expression . comparison expression
   29           | expression comparison expression .  [TCEQ, TCNE, TCLT, TCLE, TCGT, TCGE, TRPAREN, TLBRACE, TPLUS, TMINUS, TSEMICOLON, TTHEN]
   30           | expression . TPLUS term
   31           | expression . TMINUS term
   40 comparison: . TCEQ
   41           | . TCNE
   42           | . TCLT
   43           | . TCLE
   44           | . TCGT
   45           | . TCGE

    TCEQ    shift and go to state 56
    TCNE    shift and go to state 57
    TCLT    shift and go to state 58
    TCLE    shift and go to state 59
    TCGT    shift and go to state 60
    TCGE    shift and go to state 61
    TPLUS   shift and go to state 62
    TMINUS  shift and go to state 63

    TCEQ      [reduction with rule 29 (expression)]
    TCNE      [reduction with rule 29 (expression)]
    TCLT      [reduction with rule 29 (expression)]
    TCLE      [reduction with rule 29 (expression)]
    TCGT      [reduction with rule 29 (expression)]
    TCGE      [reduction with rule 29 (expression)]
    TPLUS     [reduction with rule 29 (expression)]
    TMINUS    [reduction with rule 29 (expression)]
    $default  reduction with rule 29 (expression)

    comparison  go to state 64

如果我理解得很好，问题是解析器不知道是继续读取另一段文本还是立即减少规则表达式:表达式比较表达式。

我会说立即减少是正确的。但如果我这是正确的，那么我该如何强制立即减少而不是转移？

Answer 1

您的语法有歧义——像 1 < 2 < 3 这样的输入可以解析为 (1 < 2) < 3或 1 < (2 < 3) .

有两种方法可以解决这个问题——要么添加 %left/%right/%nonassoc指令使用 bison 的内部优先级处理，或引入额外级别的规则来处理它。

现在，对于您的其他运算符 ( * / + - )，您正在同时执行这两项操作——这通常是一个错误，您只想执行其中一项。但是，如果您同时执行这两项操作，附加规则将优先，优先指令将被忽略，有时会导致令人惊讶的问题。

像这样的关系的“正常”处理是说你不能有多个关系(1 < 2 < 3 是一个语法错误，不应该被左递归或右递归解析。)要用额外的规则来做到这一点，您会将表达式规则更改为:

expression:           add_expression
                    | add_expression comparison add_expression
                    ;
add_expression:       term
                    | add_expression TPLUS term
                    | add_expression TMINUS term
                    ;

要使用优先指令，去掉 term , factor , 和 comparison (将它们全部移动到 expression 并添加:

%nonassoc TCEQ TCNE TCLT TCLE TCGT TCGE
%left TPLUS TMINUS
%left TMUL TDIV