Comment résoudre changement YACC / réduire les conflits de l'opérateur de post-incrémentation?

Question

J'écris une grammaire YACC (en fait Bison), et je vais avoir un changement / réduire problème. Il en résulte notamment les opérateurs d'incrément postfix et de décrémentation. Voici une version dégrossi de la grammaire:

%token NUMBER ID INC DEC

%left      '+' '-'
%left      '*' '/'
%right     PREINC
%left      POSTINC

%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     INC expr %prec PREINC
|     DEC expr %prec PREINC
|     expr INC %prec POSTINC
|     expr DEC %prec POSTINC
|     '(' expr ')'
;

%%

Bison me dit qu'il ya 12 décalage / réduction des conflits, mais si je commente les lignes pour l'incrément postfix et décrémentation, il fonctionne très bien. Est-ce que quelqu'un sait comment résoudre ce conflit? À ce stade, j'envisage de passer à un générateur d'analyseur LL (k), ce qui le rend beaucoup plus facile, mais ai toujours LALR grammaires semblait beaucoup plus naturel d'écrire. Je considère également GLR, mais je ne sais pas de tout bon C / C ++ GLR générateurs d'analyseur.

Answer 1

Bison / Yacc peut générer un analyseur GLR si vous spécifiez %glr-parser dans la section option.

Answer 2

Essayez ceci:

%token NUMBER ID INC DEC

%left       '+' '-'
%left       '*' '/'
%nonassoc   '++' '--'
%left       '('
%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     '++' expr 
|     '--' expr 
|     expr '++'
|     expr '--'
|     '(' expr ')'
;

%%

La clé est de déclarer les opérateurs de Postfix non associatif . Sinon, vous seriez en mesure de

++var++--

La parenthèse doivent également être donné une priorité pour réduire au minimum quart de travail / réduire les avertissements

Answer 3

Je tiens à définir d'autres éléments. Vous ne devriez pas avoir le% à gauche, à droite%,% prec choses.

simple_expr: NUMBER
 | INC simple_expr
 | DEC simple_expr
 | '(' expr ')'
;

term: simple_expr
 | term '*' simple_expr
 | term '/' simple_expr
;

expr: term
 | expr '+' term
 | expr '-' term
;

Jouez avec cette approche.

Answer 4

Ce problème fondamental est que vous ne disposez pas d'une priorité pour les jetons de INC et DEC, il ne sait pas comment résoudre les ambiguïtés concernant un ou INC de préanalyse DEC. Si vous ajoutez

%right INC DEC

à la fin de la liste de priorité (vous voulez unaries d'être une priorité plus élevée et Postfix supérieur à préfixe), il fixer, et vous pouvez même se débarrasser de tous les trucs PREINC / POSTINC, car il est hors de propos.

Answer 5

préincrémentation et les opérateurs ont nonassoc donc post-incrémentation définir que dans la section de priorité et les règles font la priorité de ces opérateurs haut en utilisant %prec