Résoudre réduire/réduire les conflits dans yacc/ocamlyacc
Question
J'essaie d'analyser une grammaire en ocamlyacc (à peu près la même que yacc ordinaire) qui prend en charge l'application de fonctions sans opérateurs (comme en Ocaml ou Haskell) et l'assortiment normal d'opérateurs binaires et unaires.Je reçois un conflit de réduction/réduction avec l'opérateur '-', qui peut être utilisé à la fois pour la soustraction et la négation.Voici un exemple de la grammaire que j'utilise :
%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) };
Le problème est que lorsque vous obtenez une expression telle que "a - b", l'analyseur ne sait pas si elle doit être réduite à "a (-b)" (négation de b, suivie de l'application) ou à "a - b" ( soustraction).La réduction par soustraction est correcte.Comment puis-je résoudre le conflit en faveur de cette règle ?
La solution
Malheureusement, la seule réponse que je puisse trouver consiste à augmenter la complexité de la grammaire.
- diviser
expr
danssimple_expr
etexpr_with_prefix
- autoriser seulement
simple_expr
ou(expr_with_prefix)
dans un APPLIQUER
La première étape transforme votre conflit de réduction/réduction en un conflit de déplacement/réduction, mais les parenthèses résolvent ce problème.
Vous allez avoir le même problème avec « ab c » :est-ce a(b(c))
ou (a(b))(c)
?Vous devrez également rompre applied_expression
et requis (applied_expression)
dans la grammaire.
Je pense que cela suffira, mais je ne suis pas sûr :
expr := INT
| parenthesized_expr
| expr MINUS expr
parenthesized_expr := ( expr )
| ( applied_expr )
| ( expr_with_prefix )
applied_expr := expr expr
expr_with_prefix := MINUS expr
Autres conseils
Eh bien, cette réponse la plus simple consiste simplement à l'ignorer et à laisser la résolution de réduction/réduction par défaut le gérer - réduire la règle qui apparaît en premier dans la grammaire.Dans ce cas, cela signifie réduire expr MINUS expr
de préférence à MINUS expr
, c'est exactement ce que vous voulez.Après avoir vu a-b
, vous souhaitez l'analyser comme un moins binaire, plutôt que comme un moins unaire puis comme une application.