Happy Context-abhängigen Operator Precedence

Question

Ich habe zwei Schnipsel von Happy-Code hier, eine, die normale Vorrangregeln verwendet, und eine, die kontextabhängige Vorrangregeln verwendet (beide beschrieben here).

Normal:

%left '+' 
%left '*' 
%% 

Exp :: { Exp } 
    : Exp '+' Exp { Plus $1 $3 } 
    | Exp '*' Exp { Times $1 $3 } 
    | var   { Var $1 } 

Kontextabhängige:

%left PLUS 
%left TIMES 
%% 

Exp :: { Exp } 
    : Exp '+' Exp %prec PLUS { Plus $1 $3 } 
    | Exp '*' Exp %prec TIMES { Times $1 $3 } 
    | var      { Var $1 } 

Angesichts der Eingang:

a * b + c * d 

Die normale Version gibt:

Plus (Times (Var "a") (Var "b")) (Times (Var "c") (Var "d")) 

während die kontextabhängige Version gibt:

Times (Var "a") (Plus (Var "b") (Times (Var "c") (Var "c"))) 

Sollten diese die gleiche Leistung nicht beide geben? Was mache ich hier falsch, dass sie verschiedene Parse-Bäume erzeugen?

Answer 1

"Kontextabhängige Präzedenz" ist eine sehr irreführende Art, dieses Merkmal zu beschreiben. Die Beschreibung des Vorrangsalgorithmus im vorhergehenden Abschnitt ist jedoch weitgehend korrekt.

Wie es heißt, ein Vorrang Vergleich ist immer zwischen einer Produktion (die reduziert werden könnten) und einen Terminal (die verschoben werden könnten). Diese einfache Tatsache wird oft durch die Entscheidung überflutet, die Deklaration der Vorrangsdeklaration so zu gestalten, als ob die Priorität nur ein Attribut des Terminals wäre.

Die Priorität der Produktion wird durch Kopieren der Priorität des letzten Terminals in der Produktion festgelegt, sofern keine explizite Deklaration mit %prec vorliegt. Oder anders gesagt, die Precidence der Produktion wird mit einer %prec-Klausel festgelegt, die den Vorrang vor dem letzten Token hat. Wie auch immer, Sie können nur den Vorrang der Produktion definieren, indem Sie sagen, dass es derselbe wie der eines Terminals ist. Da dies nicht immer praktisch ist, gibt Ihnen der Parsergenerator die Möglichkeit, einen beliebigen Namen zu verwenden, der nicht der Name eines Grammatiksymbols ist. Die Implementierung besteht darin, den Namen als Terminal zu behandeln und die Tatsache zu ignorieren, dass er in keiner Grammatikregel tatsächlich verwendet wird, sondern logisch der Name einer Rangstufe, die dieser bestimmten Produktion zugewiesen werden soll.

In Ihrem ersten Beispiel lassen Sie die Produktion standardmäßig ihren Vorrang vor dem letzten (in der Tat, das einzige) Terminal in jeder Produktion. Aber in Ihrem zweiten Beispiel haben Sie zwei benannte Rangstufen definiert, PLUS und TIMES, und Sie verwenden diese, um den Vorrang zweier Produktionen festzulegen. Sie deklarieren jedoch nicht die Priorität eines Terminals. Wenn also der Parser-Generator versucht, die relative Priorität der Produktion, die reduziert werden könnte, und das Terminal, das verschoben werden könnte, zu überprüfen, findet nur eines dieser Dinge eine deklarierte Priorität. Und in diesem Fall verschiebt es sich immer.