如何修复表达式语法中的 shift/reduce 冲突

Question

我正在尝试使用 C 中的 flex/bison 编写编程语言。但是，它报告说我的语法有 117 个 shift/reduce 冲突。其中，44 个来自表达式语法。我不明白为什么，因为我指定了优先级。

我已经尝试在我的 bison 语法文件中添加优先规则：

%token INTEGER DOUBLE IDENTIFIER STRING RUNE TUPLEID
%token BEGIN END WHILE IF CLASS METHOD

%nonassoc BLOCKSTMT
%nonassoc ELSE
%nonassoc IFX
%right '=' INC DEC ASSIGN INCN DECN MULN DIVN MODN
%nonassoc ASSIGNBLOCK
%right STOP
%left GE LE EQ NE
%left '+' '-'
%left '*' '/' '%'
%nonassoc UMINUS

这并没有解决问题。我在 Stack Overflow 上查看了这里的答案，但我发现 none 解决了我编写的语法类型（这几乎只是从 yacc 教程扩展而来）。

expr:
    INTEGER {
        node_t *newInt = initNode(line, LEAFINT);
        newInt->leaf.Integer = ;
        $$ = newInt;
    }
    | DOUBLE {
        node_t *newDouble = initNode(line, LEAFDOUBLE);
        newDouble->leaf.Double = ;
        $$ = newDouble;
    }
    | id { $$ = ; }
    | STRING {
        node_t *newStr = initNode(line, LEAFSTRING);
        newStr->leaf.String = ;
        $$ = newStr;
    }
    | RUNE {
        node_t *newRune = initNode(line, LEAFRUNE);
        if (strcmp(, "\n") == 0) {
            newRune->leaf.Rune = '\n';
        } else if (strcmp(, "\t") == 0) {
            newRune->leaf.Rune = '\t';
        } else if (strcmp(, "\\") == 0) {
            newRune->leaf.Rune = '\';
        } else if (strcmp(, "\'") == 0) {
            newRune->leaf.Rune = '\'';
        } else if (strlen() < 2) {
            newRune->leaf.Rune = *;
        } else {
            yyerror("Error: Invalid rune literal.", line);
        }
        $$ = newRune;
    }
    | list { $$ = ; }
    | '-' expr %prec UMINUS {
        node_t *negative = initNode(line, OPERATOR);
        negative->operation = "-";
        addOperand(negative, );
        $$ = negative;
    }
    | expr '=' expr { $$ = binOpr(line, "=", , ); }
    | expr '+' expr { $$ = binOpr(line, "+", , ); }
    | expr '-' expr { $$ = binOpr(line, "-", , ); }
    | expr '*' expr { $$ = binOpr(line, "*", , ); }
    | expr '/' expr { $$ = binOpr(line, "/", , ); }
    | expr '%' expr { $$ = binOpr(line, "%", , ); }
    | expr EQ expr { $$ = binOpr(line, "==", , ); }
    | expr NE expr { $$ = binOpr(line, "!=", , ); }
    | expr '<' expr { $$ = binOpr(line, "<", , ); }
    | expr '>' expr { $$ = binOpr(line, ">", , ); }
    | expr LE expr { $$ = binOpr(line, "<=", , ); }
    | expr GE expr { $$ = binOpr(line, ">=", , ); }
    | expr INC {
        node_t *increment = initNode(line, OPERATOR);
        increment->operation = "++";
        addOperand(increment, );
        $$ = increment;
    }
    | INC expr {
        node_t *increment = initNode(line, OPERATOR);
        increment->operation = "++";
        addOperand(increment, );
        $$ = increment;
    }
    | expr DEC {
        node_t *decrement = initNode(line, OPERATOR);
        decrement->operation = "--";
        addOperand(decrement, );
        $$ = decrement;
    }
    | DEC expr {
        node_t *decrement = initNode(line, OPERATOR);
        decrement->operation = "--";
        addOperand(decrement, );
        $$ = decrement;
    }
    | expr INCN expr { $$ = binOpr(line, "+=", , ); }
    | expr DECN expr { $$ = binOpr(line, "-=", , ); }
    | expr MULN expr { $$ = binOpr(line, "*=", , ); }
    | expr DIVN expr { $$ = binOpr(line, "/=", , ); }
    | expr MODN expr { $$ = binOpr(line, "%=", , ); }
    | '(' expr ')' { $$ =  }
    | expr STOP IDENTIFIER {
        node_t *newID = initNode(line, LEAFID);
        newID->leaf.Identifier = ;
        $$ = binOpr(line, ".", , newID);
    }
    | expr '[' expr ']' %prec STOP { $$ = binOpr(line, "index", , ); }
    | expr '(' expr ')' {
        node_t *newList = initNode(line, LIST);
        addOperand(newList, );
        node_t *newCall = initNode(line, CALL);
        addOperand(newCall, );
        addOperand(newCall, newList);
        $$ = newCall;
    }
    | expr parenlist {
        node_t *newCall = initNode(line, CALL);
        addOperand(newCall, );
        addOperand(newCall, );
        $$ = newCall;
    }

我希望它能正常编译我的编译器，但相反，当我这样做时 "bison -d -v parse.y" 它给了我警告 "parse.y: warning: 117 shift/reduce conflicts [-Wconflicts-sr]." y.output 文件说明如下：

State 122

   40 expr: expr . '=' expr
   41     | expr . '+' expr
   42     | expr . '-' expr
   43     | expr . '*' expr
   44     | expr . '/' expr
   45     | expr . '%' expr
   46     | expr . EQ expr
   47     | expr . NE expr
   48     | expr . '<' expr
   48     | expr '<' expr .
   49     | expr . '>' expr
   50     | expr . LE expr
   51     | expr . GE expr
   52     | expr . INC
   54     | expr . DEC
   56     | expr . INCN expr
   57     | expr . DECN expr
   58     | expr . MULN expr
   59     | expr . DIVN expr
   60     | expr . MODN expr
   62     | expr . STOP IDENTIFIER
   63     | expr . '[' expr ']'
   64     | expr . '(' expr ')'
   65     | expr . parenlist

    '='   shift, and go to state 60
    INC   shift, and go to state 61
    DEC   shift, and go to state 62
    INCN  shift, and go to state 63
    DECN  shift, and go to state 64
    MULN  shift, and go to state 65
    DIVN  shift, and go to state 66
    MODN  shift, and go to state 67
    STOP  shift, and go to state 68
    GE    shift, and go to state 69
    LE    shift, and go to state 70
    EQ    shift, and go to state 71
    NE    shift, and go to state 72
    '+'   shift, and go to state 73
    '-'   shift, and go to state 74
    '*'   shift, and go to state 75
    '/'   shift, and go to state 76
    '%'   shift, and go to state 77
    '('   shift, and go to state 79
    '<'   shift, and go to state 80
    '>'   shift, and go to state 81
    '['   shift, and go to state 82

    '='       [reduce using rule 48 (expr)]
    INC       [reduce using rule 48 (expr)]
    DEC       [reduce using rule 48 (expr)]
    INCN      [reduce using rule 48 (expr)]
    DECN      [reduce using rule 48 (expr)]
    MULN      [reduce using rule 48 (expr)]
    DIVN      [reduce using rule 48 (expr)]
    MODN      [reduce using rule 48 (expr)]
    STOP      [reduce using rule 48 (expr)]
    GE        [reduce using rule 48 (expr)]
    LE        [reduce using rule 48 (expr)]
    EQ        [reduce using rule 48 (expr)]
    NE        [reduce using rule 48 (expr)]
    '+'       [reduce using rule 48 (expr)]
    '-'       [reduce using rule 48 (expr)]
    '*'       [reduce using rule 48 (expr)]
    '/'       [reduce using rule 48 (expr)]
    '%'       [reduce using rule 48 (expr)]
    '('       [reduce using rule 48 (expr)]
    '<'       [reduce using rule 48 (expr)]
    '>'       [reduce using rule 48 (expr)]
    '['       [reduce using rule 48 (expr)]
    $default  reduce using rule 48 (expr)

    parenlist  go to state 83
    arglist    go to state 84

下一个状态，状态 123，似乎是相同的。状态 124 也相同但没有冲突。

Answer 1

令牌 '<' 没有优先级，因此规则 48 没有优先级，所有 "E < E op E" 形式的表达式都是不明确的，导致您在此处看到的 shift/reduce 冲突状态。添加优先级 '<' 其他有冲突的状态可能与其他规则相似。

如何修复表达式语法中的 shift/reduce 冲突

How to fix shift/reduce conflicts in expression grammar

bison