Fehlerhafte Bisonreduzierung mit% glr-parser und% merge rules

Question

Momentan versuche ich einen Parser für VHDL zu erstellen, der einige der Probleme hat, die C++ - Parser haben. Die kontextfreie Grammatik von VHDL erzeugt ein Parse Wald statt einen einzigen Baum Parse wegen seiner Zweideutigkeit in Bezug auf Funktionsaufrufe und Array-Abonnements

foo := fun(3) + arr(5); 

Diese Zuordnung nur eindeutig analysiert werden kann, wenn der Parser würde tragen um eine hirachisch, Typ-bewusste Symboltabelle , die es verwenden würde, um die Unklarheiten etwas on-the-fly zu lösen.

Ich will nicht, dies zu tun, denn für Aussagen wie die oben erwähnt, die Parsewald nicht exponentiell wachsen würde, aber eher linear auf die Menge der Funktionsaufrufe abhängig und Array-Abonnements.

(Außer natürlich, würde man den Parser mit Aussagen wie Folter)

foo := fun(fun(fun(fun(fun(4))))); 

Da Bison Kräfte der Benutzer nur einen einzigen Parse-Baum zu erstellen, I verwendet% merge Attribute alle Teilbäume sammeln rekursiv und hinzugefügt diese Teilbäume unter so genannte AMBIG Knoten im Singleton AST.

Das Ergebnis sieht wie this aus.

Um das obige zu erzeugen, habe ich den Token-Stream "I = I (N);" analysiert. Der Inhalt der Grammatik, die ich in der Datei parse.y verwendet habe, ist unten gesammelt. Es wird versucht, die mehrdeutigen Teile von VHDL zu ähneln:

start: prog 
; 

/* I cut out every semantic action to make this 
    text more readable */ 
prog: assignment ';' 
| prog assignment ';' 
; 

assignment: 'I' '=' expression 
; 

expression: function_call %merge <stmtmerge2> 
| array_indexing   %merge <stmtmerge2> 
| 'N' 
; 

function_call: 'I' '(' expression ')' 
| 'I' 
; 

array_indexing: function_call '(' expression ')' %merge <stmtmerge> 
| 'I' '(' expression ')'       %merge <stmtmerge> 
; 

The whole sourcecode can be read at this github repository.

Und jetzt kommen wir zum eigentlichen Problem kriegen. Wie Sie oben in der generierten Parser-Struktur sehen können, beziehen sich die Knoten FCALL1 und ARRIDX1 auf denselben Einzelknoten EXPR1, der seinerseits zweimal auf N1 verweist.

Dies sollte auf jeden Fall nicht passiert sein und ich weiß nicht warum. Stattdessen sollte es die Wege sein

FCALL1 -> EXPR2 -> N2 
ARRIDX1 -> EXPR1 -> N1 

Haben Sie eine Ahnung, warum Bison die oben genannten Knoten wieder verwendet?

Ich schrieb auch einen Bugreport auf dem offiziellen gnu Mailing Liste für Bison, ohne eine Antwort auf diesen Punkt obwohl. Leider aufgrund der restictions für neue Stackoverflow Benutzer, kann ich nicht nein Link zu diesem Fehlerbericht liefern ...

Answer 1

Das Verhalten erwartet wird.

expression kann eindeutig reduziert werden, und dieser reduzierte Wert wird von beiden möglichen mehrdeutigen Reduzierungen verwendet, die den Wert enthalten. Denken Sie daran, dass GLR wie LR ein Parser von links nach rechts ist. Wenn eine Reduzierungsaktion ausgeführt wird, sind alle Reduzierungen bereits erfolgt.Der Effekt unterscheidet sich nicht von der Verwendung eines Terminals auf der rechten Seite; Das Terminal wird nicht künstlich kopiert, um verschiedene Instanzen in den mehrdeutigen Produktionen zu erzeugen, die es benutzen.

Für die meisten Menschen wäre dies eher ein Feature als ein Bug, und ich meine das nicht als Scherz. Ohne den Stapel mit dem Graph-Aufbau hat GLR eine exponentielle Laufzeit. Wenn Sie beim Zusammenführen von Parse-Bäumen wirklich eine tiefe Kopie von freigegebenen AST-Knoten erstellen möchten, müssen Sie dies selbst tun, aber ich schlage vor, dass Sie einen Weg finden, die Tatsache zu nutzen, dass die Parse-Struktur tatsächlich eine gerichtete azyklische Struktur ist Graph eher als ein Baum; Sie werden wahrscheinlich in der Lage sein, den Mangel an Doppelarbeit auszunutzen.