So ändern Sie semantische Aktionen beim Entfernen der linken Rezension von einem Grammer

Question

Gibt es einen Algorithmus, der uns sagt, wie semantische Aktionen, die mit einer linksrezisiven Grammatik verbunden sind, ändern können? Zum Beispiel haben wir die folgende Grammatik und die damit verbundenen semantischen Aktionen:

$ S rightarrow id = expr $ {ss = expr.size}

S $ rightarrow $ wenn exprr dann $ s_1 $ $ s_2 $ {$ s_1.t = st + 2; $ $ S_2.t = st + 2; $ $ ss = expr.size + s_1.size + s_2.size + 2; $}

S $ rightarrow $ while expr do $ s_1 $ {$ s_1.t = st + 4; $ $ ss = expr.size + s_1.s + 1; $}

S $ rightarrow $ $ S_1 $; $ S_2 $ {$ s_1.t = s_2.t = st; $ $ ss = s_1.s + s_2.s; $}

Offensichtlich lautet die nicht rezisive Version des Grammers:

S $ rightarrow $ id = exprr t

S $ rightarrow $ wenn exprr dann $ s_1 $ $ s_2 $ t

S $ rightarrow $ während expr do $ s_1 $ t

T $ rightarrow $; $ S_2 $ t

T $ rightarrow $ $ epsilon $

Wir müssen aber auch die semantischen Aktionen entsprechend ändern. Irgendwelche Ideen, wie das getan werden kann?

Answer 1

Nach dem, was ich entdeckt habe, gibt es keine allgemeine Technik, um die semantischen Aktionen zu verändern, während ich die linke Rezension beseitigt. Stattdessen besteht die beste Methode darin, ein repräsentatives Beispiel zu nehmen, seinen Parse -Baum zu zeichnen und dann zu überprüfen, welche semantischen Aktionen uns das gleiche Ergebnis wie die vorherige Grammatik geben.

Answer 2

Ich habe eine teilweise Lösung (ich suche einen allgemeinen). Wenn Ihre Grammatik keine Epsilon -Produktionen hat, sind keine Nicht -Terminals nullbar. Dies bedeutet, dass der Algorithmus zum Entfernen der linken Rekursion durchläuft (obwohl er Epsilon -Produktionen einführt).

Wenn Sie semantische Aktionen der Form -Aktion (Etikett, Graf) hinzufügen, die die leere Zeichenfolge erkennen, einen Verschiebung/Reduzieren von Parser verwenden und alle ** Alternativen untersuchen, ist es überhaupt nicht erforderlich, den Parse -Baum neu zu organisieren. Wenn ein Terminal erkannt wird, wird ein Attribut auf den Parser -Stapel gedrückt, dies ist eine Schichtaktion. Wenn eine Aktion auftritt, wird N -Werte aus dem Stapel geöffnet und einen Knoten mit dem angegebenen Etikett und den Werten als Kinder aus dem Stapel gedrückt. Dies ist die Reduzierung der Aktion.

Der Parser muss die aktuelle Position und den Parser -Stapel ausbreiten, und die Operationen von Verschiebungen und Reduzieren sollten mit funktionellen Aktualisierungen nicht durchgeführt werden, nicht mit Mutationen. Es ist klar, dass die Grammatik die Verschiebungsabfolge nicht verändert und die Aktionen reduziert, sodass der resultierende Parsebaum unter Refactoring invariant ist.

Dies bedeutet, dass Sie, wenn Sie einen AST -und einen Parse -Baum generieren, auf die Attribute nach Nummer beziehen müssen. Die Maschinerie funktioniert, da der Parser -Stapel und der Kontrollstapel entkoppelt sind und die Refactoring nur den Steuerungsstapel ändert. Die Schwierigkeit ist, dass die Grammatik zunächst epsilonfrei sein muss, da die Reduzierung der Aktionsbegriffe selbst nullbar sind.

** Die Annahme, dass alle Alternativen untersucht werden, wird so erfolgen, dass die Überlegungsreihenfolge unerheblich ist. Obwohl Refactorings äquivalente Grammatiken produzieren, gibt es keine automatische Zusicherung, dass die daraus resultierenden Parsebäume gleich sein werden, es sei denn, alle Möglichkeiten werden untersucht. In diesem Fall bleibt die Bestellung unbestimmt, aber die Ergebnisse sind gleich.