Risoluzione del conflitto di riduzione/riduzione in yacc/ocamlyacc

Question

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?

Answer 1

Sfortunatamente, l’unica risposta che riesco a trovare significa aumentare la complessità della grammatica.

1. diviso expr in simple_expr E expr_with_prefix
2. 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

Answer 2

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.