Lösen verringern/verringern und verschieben/reduzieren Konflikte in Bison Grammatik

Question

Ich versuche, die r/r und s/r Konflikte in der folgenden Bison Grammatik

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

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

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

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

Ich denke, das Problem ist die Regel ausdr zu lösen: expr BINOP expr, denn wenn ich es loslasse, hört es auf, diese Konflikte zu zeigen. Ich habe die Vorrangregeln oben erklärt, um Konflikte zu vermeiden/zu reduzieren, aber es sieht so aus, als würde es nicht funktionieren. Kann mir jemand beim Debuggen einer mehrdeutigen Grammatik Abkürzungen geben? Ignoriere die semantischen Regeln.

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 {$$ = $2->adopt($1,$3);} 

UPDATE: entdeckte ich ein Problem in meinem Verständnis

Obwohl ich die richtigen Ergebnisse bin immer, mein Compiler immer wieder sagt, dass es eine Verschiebung/Konflikt in der folgenden Grammatik reduzieren. Ich denke, es sollte keine Konflikte geben, weil ich Präzedenz und Assoziativität richtig angegeben habe.

%left '+' 
%left '*' 

%% 
expr : expr BINOP expr 
    | TOK_INTCON 

BINOP : '+' 
     | '*' 
%% 

Answer 1

Diese Antwort bezieht sich auf Ihre UPDATE-Sektion, da dies das Herz des Problems ist.

Die TL; DR Antwort ist, dass die Vorrang-und-Assoziativität Erklärungen %left '+' und %left '*' anwenden, während BINOP Parsen aber nicht während expr Parsen, so dass sie zu früh (sie an diesem Punkt nichts zu tun) und werden durch die gegangen Zeit sie benötigt werden.

---

ich geändert Ihr Beispiel so, dass Bison damit umgehen kann:

$ 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] 

Der Punkt -v hier zu schreiben expr.output ist, die zeigt, wie Bison Ihre Grammatik interpretiert. Sie können dies prüfen, genau zu sehen, wo die Verschiebung/reduzieren Konflikt auftritt, aber kurz gesagt, kommt es, wenn der Eingang enthält, zB

1 op 2 op 3 

Die Grammatik diese analysiert werden können wie:

op 
/\ 
1 op 
    /\ 
    2 3 

(die den Parsing-Baum Sie, wenn Sie anstelle von „reduzieren“ jedes Mal wählen „shift“ erhalten ist), oder:

op 
/\ 
    op 3 
/\ 
1 2 

was %left, %right und %nonassoc do weist einem spezifischen Token eine Priorität zu. Nun, wie in the Bison documentation section on how precedence works notiert, geht die Priorität zu Regeln über, aber entscheidend ist nicht zu nonterminals selbst: sie gelten nur für einzelne Regeln innerhalb eines Nonterminal. Sie entscheiden, ob sie in einen neuen Zustand übergehen oder durch eine Regel reduzieren wollen, und sobald die Verschiebung oder Reduzierung erfolgt ist, wird die Entscheidung bereits getroffen. (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.)

Indem Sie alle Ihre binären Operatoren auf ein binop Nonterminal reduzieren, rauben Sie dem Parser einen Weg, zwischen den verschiedenen binären Operatoren zu unterscheiden. In der LALR-Grammatik, die Bison erzeugen wird, erhalten Sie, wenn Sie für jeden Operator eine eigene Regel haben, für jeden einen separaten Status, der eine separate Schicht-oder-Reduktion-Entscheidung erlaubt.

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

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

Interessanterweise ist die Gesamtzahl der Staaten gleich bleibt (beide expr.output und expr-repaired.output zeigen sieben Staaten). Die Bedeutung der Staaten ist jedoch unterschiedlich. Mehrere Zustände für den Umgang mit dem alten Nichtterminal BINOP sind weg; an ihrer Stelle sind mehrere Zustände für die korrekte Behandlung der linksassoziativen Operatoren unterschiedlicher Priorität, während entschieden wird, ob expr <some-op> expr zu reduzieren ist, abhängig davon, wie wir uns entschieden haben, die ersteexpr zu reduzieren. Schauen Sie genau auf den neuen Zustand 6, zum Beispiel:

State 6 

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

    '*' shift, and go to state 5 

    $default reduce using rule 1 (expr) 

Wenn wir in diesem Zustand und das nächste Token ist * sind, wir verschieben, so dass wir expr * expr behandeln werden und reduzieren es, bevor wir expr + (expr-from-reduction) reduzieren.