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 ?

Answer 1

Malheureusement, la seule réponse que je puisse trouver consiste à augmenter la complexité de la grammaire.

1. diviser expr dans simple_expr et expr_with_prefix
2. 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

Answer 2

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.