Auflösung reduzieren/reduzieren Konflikt in yacc/ocamlyacc

Question

Ich versuche, eine Grammatik in ocamlyacc (ziemlich genau das gleiche wie reguläre yacc) zu analysieren, die Funktion Anwendung ohne Operatoren (wie in Ocaml oder Haskell) und das normale Sortiment unterstützt von binären und unären Operatoren. Ich bekomme einen Konflikt mit dem Operator '-', der sowohl für die Subtraktion als auch für die Negation verwendet werden kann. Hier ist ein Beispiel der Grammatik 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 ist, dass, wenn Sie einen Ausdruck wie erhalten „a - b“ der Parser nicht weiß, ob dies sollte reduziert werden, als „a (- b) "(Negation von b, gefolgt von der Anwendung) oder" a - b "(Subtraktion). Die Subtraktionsreduktion ist korrekt. Wie kann ich den Konflikt zugunsten dieser Regel lösen?

Answer 1

Leider kann ich mit der einzigen Antwort die Komplexität der Grammatik erhöhen.

1. gespalten expr in simple_expr und expr_with_prefix
2. erlauben nur simple_expr oder (expr_with_prefix) in APPLY

Der erste Schritt wird Ihr verringern/verringern Konflikt in eine Schiebe-/Reduzier Konflikt, aber die Klammern lösen, die .

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

ich denke, das wird es tun, aber ich bin mir 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, diese einfachste Antwort ist, es ignorieren einfach und lassen Sie den Standard verringern/verringern Auflösung damit umgehen - reduziert die Regel das erscheint zuerst in der Grammatik. In diesem Fall bedeutet das, expr MINUS expr gegenüber MINUS expr zu reduzieren, was genau das ist, was Sie wollen. Nachdem Sie a-b gesehen haben, möchten Sie es als binäres Minus analysieren, anstatt als unäres Minus und dann als Anwenden.