Comment les opérateurs binaires devraient-ils être définis dans bison?

Question

J'écris un analyseur en C avec bison, et bien qu'il semble fonctionner correctement dans toutes les circonstances, j'ai essayé jusqu'à présent, je reçois un tas d'avertissements shift/réduire sur mes opérateurs binaires (et un sur mon unaire NOT opérateur aussi bien).

binary_op : 
     PLUS { } 
     | MINUS { } 
     | TIMES { } 
     | SLASH { } 
     | POWER { } 
     | AND { } 
     | OR { } 
     | LE { } 
     | LT { } 
     | GE { } 
     | GT { } 
     | EQ { } 
     | NE { } 
     | MOD { } 
    ; 

unary_op : 
    NOT { } 
    ; 

expr : 
    ... 
    | unary_op expr { } 
    | expr binary_op expr { } 

Quand je lance mon fichier .y par --verbose bison, je vois:

state 51 
    11 set_existence: expr . IN set 
    12    | expr . NOT IN set 
    34 expr: expr . binary_op expr 
    34  | expr binary_op expr . 

    ... 
    NOT shift, and go to state 26 
    AND shift, and go to state 27 
    OR  shift, and go to state 28 
    .... 
    NOT  [reduce using rule 34 (expr)] 
    AND  [reduce using rule 34 (expr)] 
    OR  [reduce using rule 34 (expr)] 

Je ne vois pas de problème en fait l'analyse des opérateurs binaires, mais il semble que je devrais probablement résoudre le changer/réduire les problèmes de toute façon. Je ne peux pas comprendre où le conflit est - les productions de set_existence semblent complètement indépendantes. Ma meilleure hypothèse (un tir dans le noir) est que cela pourrait avoir quelque chose à voir avec le fait que l'égaliseur est utilisé comme un opérateur binaire (comparaison d'égalité) ainsi que l'affectation (par exemple, "foo = bar = baz;" foo à true/false selon que bar et baz sont égaux). Si je change ma comparaison d'égalité pour être == ("foo = bar == baz;"), mon analyseur agit comme prévu mais a toujours le même décalage/réduire les conflits.

EDIT: Je n'ai associativité spécifié:

%left OR 
%left AND 
%left NOT 
%left LT LE GT GE NE EQ 
%left PLUS MINUS 
%left TIMES MOD SLASH 
%left POWER 

Answer 1

Il y a deux façons d'éviter cela. La première consiste à utiliser les commandes %left, %right et %nonassoc pour spécifier le niveau de priorité (voir the manual).

L'autre option, que je préfère personnellement, est d'encoder la précédence directement dans la grammaire. Par exemple, voici un BNF pour les expressions arithmétiques simples:

expr ::= term | expr + term 
term ::= factor | term * factor 
factor ::= number | (expr) 

Cela permet d'éliminer l'analyse syntaxique ambiguë au niveau de la grammaire.