Risoluzione del conflitto di riduzione/riduzione in yacc/ocamlyacc
Domanda
Sto cercando di analizzare una grammatica in ocamlyacc (più o meno la stessa del normale yacc) che supporta l'applicazione di funzioni senza operatori (come in Ocaml o Haskell) e il normale assortimento di operatori binari e unari.Ricevo un conflitto di riduzione/riduzione con l'operatore '-', che può essere utilizzato sia per la sottrazione che per la negazione.Ecco un esempio della grammatica che sto utilizzando:
%token <int> INT
%token <string> ID
%token MINUS
%start expr
%type <expr> expr
%nonassoc INT ID
%left MINUS
%left APPLY
%%
expr: INT
{ ExprInt $1 }
| ID
{ ExprId $1 }
| expr MINUS expr
{ ExprSub($1, $3) }
| MINUS expr
{ ExprNeg $2 }
| expr expr %prec APPLY
{ ExprApply($1, $2) };
Il problema è che quando ottieni un'espressione come "a - b" il parser non sa se questa deve essere ridotta come "a (-b)" (negazione di b, seguita dall'applicazione) o "a - b" ( sottrazione).La riduzione della sottrazione è corretta.Come risolvo il conflitto a favore di quella regola?
Soluzione
Sfortunatamente, l’unica risposta che riesco a trovare significa aumentare la complessità della grammatica.
- diviso
expr
insimple_expr
Eexpr_with_prefix
- consentire solo
simple_expr
O(expr_with_prefix)
in un'APPLICAZIONE
Il primo passaggio trasforma il conflitto di riduzione/riduzione in un conflitto di spostamento/riduzione, ma le parentesi lo risolvono.
Avrai lo stesso problema con "abc":è a(b(c))
O (a(b))(c)
?Dovrai anche interrompere applied_expression
e richiesto (applied_expression)
nella grammatica.
Penso che questo basterà, ma non ne sono sicuro:
expr := INT
| parenthesized_expr
| expr MINUS expr
parenthesized_expr := ( expr )
| ( applied_expr )
| ( expr_with_prefix )
applied_expr := expr expr
expr_with_prefix := MINUS expr
Altri suggerimenti
Bene, la risposta più semplice è semplicemente ignorarlo e lasciare che sia la risoluzione di riduzione/riduzione predefinita a gestirlo: ridurre la regola che appare per prima nella grammatica.In questo caso ciò significa ridurre expr MINUS expr
in preferenza a MINUS expr
, che è esattamente quello che vuoi.Dopo aver visto a-b
, vuoi analizzarlo come un segno meno binario, anziché come un segno meno unario e quindi applicarlo.