Come risolvere spostamento YACC / ridurre i conflitti da operatore di post-incremento?

Question

Sto scrivendo una grammatica in YACC (in realtà Bison), e sto avendo un cambiamento / ridurre problema. È il risultato di compresi gli operatori di incremento e decremento postfix. Ecco una versione tagliata verso il basso della grammatica:

%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 mi dice che ci sono 12 turni / ridurre i conflitti, ma se io commento le righe per l'incremento e decremento Postfix, funziona benissimo. Qualcuno sa come risolvere questo conflitto? A questo punto, sto pensando di passare a un generatore di parser LL (k), il che rende molto più facile, ma grammatiche LALR sono sempre sembrati molto più naturale di scrivere. Sto considerando anche GLR, ma non so di qualsiasi buon C / C ++ GLR generatori di parser.

Answer 1

Bison / Yacc in grado di generare un parser GLR se si specifica %glr-parser nella sezione opzioni.

Answer 2

Prova questo:

%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 chiave è quella di dichiarare operatori in forma suffissa come non associativo . In caso contrario, si sarebbe in grado di

++var++--

La parentesi anche bisogno di essere data una precedenza per ridurre al minimo spostamento / ridurre le avvertenze

Answer 3

mi piace definire più elementi. Non dovrebbe essere necessario l'% a sinistra, a destra%,% roba prec.

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
;

Giocare con questo approccio.

Answer 4

Il problema di base è che non si dispone di una precedenza per i INC e DEC gettoni, in modo che non sa come risolvere le ambiguità che coinvolgono un lookahead di INC o DEC. Se si aggiunge

%right INC DEC

alla fine della lista di precedenza (si desidera unaries di essere superiore precedenza e postfix maggiore di prefisso), sarà risolvere il problema, e si può anche sbarazzarsi di tutte le cose PREINC / POSTINC, come è irrilevante.

Answer 5

preincremento e il post-operatori hanno nonassoc modo che definiscono nella sezione precedenza e nelle regole rendono la precedenza di questi operatori elevate utilizzando %prec