Come risolvere spostamento YACC / ridurre i conflitti da operatore di post-incremento?
-
23-08-2019 - |
Domanda
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.
Soluzione
Bison / Yacc in grado di generare un parser GLR se si specifica %glr-parser
nella sezione opzioni.
Altri suggerimenti
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
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.
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.
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