Beheben des Reduzieren/Reduzieren-Konflikts in yacc/ocamlyacc

Question

Ich versuche, eine Grammatik in Ocamlyacc (so ziemlich die gleiche wie normales Yacc) zu analysieren, die Funktionsanwendungen ohne Operatoren (wie in Ocaml oder Haskell) und die normale Auswahl an binären und unären Operatoren unterstützt.Ich erhalte einen Reduzieren/Reduzieren-Konflikt mit dem Operator „-“, der sowohl zur Subtraktion als auch zur Negation verwendet werden kann.Hier ist ein Beispiel der Grammatik, die ich verwende:

%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) };

Das Problem besteht darin, dass der Parser bei einem Ausdruck wie „a – b“ nicht weiß, ob dieser als „a (-b)“ (Negation von b, gefolgt von Anwendung) oder „a – b“ ( Subtraktion).Die Subtraktionsreduktion ist korrekt.Wie löse ich den Konflikt zugunsten dieser Regel?

Answer 1

Leider ist die einzige Antwort, die mir einfällt, die Erhöhung der Komplexität der Grammatik.

1. Teilt expr hinein simple_expr Und expr_with_prefix
2. nur zulassen simple_expr oder (expr_with_prefix) in einem APPLY

Der erste Schritt verwandelt Ihren Reduzieren/Reduzieren-Konflikt in einen Verschiebungs/Reduzieren-Konflikt, aber die Klammern lösen das.

Sie werden das gleiche Problem mit „a b c“ haben:ist es a(b(c)) oder (a(b))(c)?Sie müssen auch abbrechen applied_expression und erforderlich (applied_expression) in der Grammatik.

Ich denke, das reicht, bin mir aber nicht sicher:

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

Nun, die einfachste Antwort besteht darin, es einfach zu ignorieren und es der Standardauflösung zum Reduzieren/Reduzieren zu überlassen – reduzieren Sie die Regel, die zuerst in der Grammatik erscheint.In diesem Fall heißt das reduzieren expr MINUS expr bevorzugt gegen MINUS expr, das ist genau das, was Sie wollen.Nach dem Sehen a-b, möchten Sie es als binäres Minus und nicht als unäres Minus analysieren und dann anwenden.