解决野牛语法中的 reduce/reduce 和 shift/reduce 冲突

Question

我正在尝试解决以下野牛语法中的 r/r 和 s/r 冲突

%right TOK_IF TOK_ELSE
%right '='
%left  TOK_EQ TOK_NE '<' TOK_LE '>' TOK_GE
%left  '+' '-'
%left  '*' '/' '%'
%right TOK_POS TOK_NEG '!' TOK_NEW
%left  TOK_BLK '.' TOK_CALL
%precedence  TOK_PARENT

%start start

        expr       : expr BINOP expr   {$$=->adopt(,);}
                   | UNOP              {$$ = ;}
                   | allocator         {$$ = ;}
                   | call              {$$ = ;}
                   | expr '[' expr ']' %prec TOK_BLK  {
                     destroy();
                     $$ = ->adopt(,);}
                   | '(' expr ')' %prec TOK_PARENT {$$ = ;}
                   | expr '.' expr {$$ = ->adopt(,);}
                   | variable {$$= ;}
                   | constant {$$ = ;}
                   ;
        BINOP      : TOK_IF   {$$ = ;}
                   | TOK_ELSE {$$ = ;}
                   | '='      {$$ = ;}
                   | TOK_EQ   {$$ = ;}
                   | TOK_NE   {$$ = ;}
                   | '<'      {$$ = ;}
                   | TOK_LE   {$$ = ;}
                   | '>'      {$$ = ;}
                   | TOK_GE   {$$ = ;}
                   | '+'      {$$ = ;}
                   | '-'      {$$ = ;}
                   | '*'      {$$ = ;}
                   | '/'      {$$ = ;}
                   | '%'      {$$ = ;}
                   ;

        UNOP       : '+' expr %prec TOK_POS {
                   ->swap_token_code(TOK_POS);
                   $$ = ->adopt();
                   }
                   | '-' expr %prec TOK_NEG{
                   ->swap_token_code(TOK_NEG);
                   $$ = ->adopt();
                   }
                   | '!' expr {$$ = ->adopt();}
                   ;
        allocator  : TOK_NEW TOK_IDENT '('')' {
                   destroy();
                   ->swap_token_code(TOK_TYPEID);
                   $$ = ->adopt();
                   }
                   | TOK_NEW TOK_STRING '(' expr ')'{

                   }
                   | TOK_NEW basetype '[' expr ']'{
                   destroy();destroy();
                   ->swap_token_code(TOK_NEWARRAY);
                   $$ = ->adopt(,);
                   }
                   ;
        call       : TOK_IDENT '(' exprs ')' %prec TOK_CALL{
                    destroy();
                    ->swap_token_code(TOK_CALL);
                    $$ = (->adopt())->cannibalize();
                   }
                   ;
        exprs      : exprs expr  {$$ = ->adopt();}
                   | {$$ = new astree ('{',{0,0,0}, "}");}
                   ;

        variable   : TOK_IDENT  {$$ = ;}
               | expr '[' expr ']'{
               destroy();
               $$ = ->adopt(,);
               }
               | expr '.' TOK_IDENT {$$ = ->adopt(,);}
               ;
        constant   :TOK_INTCON    {$$ = ;}
                |TOK_CHARCON   {$$ = ;}
               |TOK_STRINGCON {$$ = ;}
               |TOK_NULL      {$$ = ;}
               ;
    %%

我认为问题出在规则 expr : expr BINOP expr 因为当我摆脱它时，它不再显示这些冲突。我已经声明了上面的优先规则以避免 shift/reduce 冲突，但看起来它不起作用。有人可以给我调试歧义语法的捷径吗？无视语义规则。

parser.y: warning: 24 shift/reduce conflicts [-Wconflicts-sr]
parser.y: warning: 56 reduce/reduce conflicts [-Wconflicts-rr]
parser.y:140.14-143.12: warning: rule useless in parser due to conflicts [-Wother]
           | expr '[' expr ']'{
              ^^^^^^^^^^^
parser.y:144.14-56: warning: rule useless in parser due to conflicts [-Wother]
            | expr '.' TOK_IDENT {$$ = ->adopt(,);}

更新：我发现我的理解有问题

虽然我得到了正确的结果，但我的编译器一直告诉我以下语法中存在 shift/reduce 冲突。我认为不应该有冲突，因为我正确指定了优先级和结合性。

%left '+'
%left '*'

%%
expr : expr BINOP expr
     | TOK_INTCON 

BINOP :  '+'  
      |  '*'
%%

Answer 1

此回复针对您的更新部分，因为这是问题的核心。

TL;DR 的答案是优先级和关联性声明 %left '+' 和 %left '*' 在解析 BINOP 时适用，但在解析 expr 时不适用，因此它们太早了（他们此时什么都不做），在需要他们的时候就走了。

我修改了您的示例，以便 Bison 可以处理它：

$ cat expr.y
%token TOK_INTCON
%left '+'
%left '*'

%%
expr : expr BINOP expr
     | TOK_INTCON 

BINOP :  '+'  
      |  '*'
%%
$ bison -v expr.y
expr.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]

这里-v的重点是写expr.output，它显示了Bison是如何解释你的语法的。您可以仔细阅读它以准确了解 shift/reduce 冲突发生的位置——但简而言之，它会在输入包含

时发生

1 op 2 op 3

语法允许将其解析为：

  op
 /  \
1    op
    /  \
   2    3

（这是你每次选择 "shift" 而不是 "reduce" 时得到的解析树），或者：

    op
   /  \
  op    3
 /  \
1    2

%left、%right 和 %nonassoc 所做的是为 特定标记 分配优先级。现在，如 the Bison documentation section on how precedence works, precedence does flow through to rules, but crucially, not to nonterminals themselves: they only apply to individual rules within a nonterminal. They function to decide whether to shift to a new state, or reduce by a rule, and once the shift or reduce has happened, the decision is already made. (This is natural since the token or nonterminal is recognized by the shifting or reduction, which gives you either a new node for your parse tree, or a partial parse tree.)

中所述

通过将所有二元运算符缩减为 binop 非终结符，您剥夺了解析器区分每个不同二元运算符的方法。在 Bison 将生成的 LALR 语法中，如果每个运算符都有单独的规则，则每个运算符都有一个单独的状态，这允许单独的移位或归约决策。

$ cat expr-repaired.y
%token TOK_INTCON
%left '+'
%left '*'

%%
expr : expr '+' expr
     | expr '*' expr
     | TOK_INTCON 
%%
$ bison -v expr-repaired.y
$

有趣的是，状态总数保持不变（expr.output 和 expr-repaired.output 均显示七个状态）。但是，状态的含义是不同的。处理旧 BINOP 非终结符的几个状态已经消失；取而代之的是多个状态，用于正确处理左关联、不同优先级的运算符，同时决定是否减少 expr <some-op> expr 取决于我们决定如何减少 first expr.仔细看新状态6，例如：

State 6

    1 expr: expr . '+' expr
    1     | expr '+' expr .
    2     | expr . '*' expr

    '*'  shift, and go to state 5

    $default  reduce using rule 1 (expr)

如果我们处于这种状态并且下一个标记是 *，我们将移动，以便我们将处理 expr * expr 并在我们减少 expr + (expr-from-reduction) 之前减少它。

解决野牛语法中的 reduce/reduce 和 shift/reduce 冲突

Solving reduce/reduce and shift/reduce conflicts in bison grammar

compiler-construction

bison