Die Grammatik ist noch besser, wenn Sie (einige) Semantiken gemäß den Regeln hinzufügen können. Insbesondere für den Python-Analysator, den ich entwickle, muss ich von jeder Alternative einen AST-Knoten zurückgeben, da ich mich an die aktuelle AST-Implementierung in CPython halten möchte.
Inhalt der Python PEG Parser-Serie Viele Grammatiken verwenden eine Konvention, mit der Sie Regeln Aktionen hinzufügen können - normalerweise einen Codeblock in {geschweiften Klammern}. Genauer gesagt sind sie an Alternativen gebunden. Der Code in diesem Block ist in derselben Sprache wie der Rest des Compilers geschrieben, z. B. in C, ergänzt durch die Möglichkeit, auf Elemente in der Alternative zu verweisen. Im ursprünglichen pgen Python habe ich diese Funktionalität nicht hinzugefügt, aber für ein neues Projekt möchte ich sie implementieren.
So machen wir das für den vereinfachten Parser-Generator, den ich im Rahmen dieser Reihe von Beiträgen entwickle.
Die Syntax für Aktionen lautet normalerweise:
rule: item item item { action 1 } | item item { action 2 }
Da dies die Grammatik ausführlicher macht, erlauben Parser-Generatoren normalerweise mehrzeilige Regeln, zum Beispiel:
rule: item item item { action 1 } | item item { action 2}
Dies macht den Parser etwas komplizierter, ist aber für die Lesbarkeit wichtig, daher werde ich eine solche Aufzeichnung unterstützen.
Die ewige Frage ist, wann dieser Block ausgeführt werden soll. In Yacc / Bison erfolgt dies unmittelbar nachdem der Parser die Regel erkannt hat, da die Token-Liste kein Rollback enthält. Wenn Sie jede Aktion genau einmal ausführen, kann dies zu globalen Nebenwirkungen führen (z. B. Aktualisierung der Symboltabelle oder einer anderen Compilerdatenstruktur).
Bei PEG-Parsern mit ihrer unbegrenzten Rückkehr zur Liste der Token haben wir mehrere Möglichkeiten:
- Führen Sie keine Aktionen aus, bis alles analysiert wurde. Ich werde dies nicht berücksichtigen, da ich während des Parsens einen AST erstellen möchte.
- Führen Sie immer dann aus, wenn die Alternative erkannt wird. Ihr Code muss idempotent sein (d. H. Den gleichen Effekt haben, egal wie oft er ausgeführt wurde). Dies bedeutet, dass die Aktion ausgeführt werden kann, das Ergebnis jedoch möglicherweise verworfen wird.
- Zwischenspeichern Sie das Ergebnis und führen Sie die Aktion nur zum ersten Mal aus - wenn die Alternative an dieser Position erkannt wird.
Ich habe die dritte Option gewählt - in jedem Fall zwischenspeichern wir das Ergebnis der Methode mit dem Packrat-Algorithmus, damit wir auch die Ergebnisse zwischenspeichern können.
Für den Inhalt in {curlies} wird traditionell C-Code mit einer Vereinbarung verwendet, die auf $ basiert, um auf Elemente in einer erkannten Alternative zu verweisen (z. B. $1 , um auf das erste Element zu verweisen), und Zuweisung $$ , um das Ergebnis der Aktion anzuzeigen. Es klingt sehr altmodisch (ich habe Erinnerungen an die Verwendung der Funktionszuweisung in Algol-60, um den Rückgabewert anzuzeigen), daher werde ich es pythonischer gestalten: In die Klammern müssen Sie einen Ausdruck einfügen, dessen Ergebnis das Ergebnis der Aktion ist, und die Verknüpfungen zu den Elementen werden einfache Namen, die den Text des Elements angeben. Als Beispiel ist hier ein einfacher Taschenrechner, der Zahlen addieren und subtrahieren kann:
start: expr NEWLINE { expr } expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term } term: NUMBER { float(number.string) }
Führen wir es am Beispiel 100 + 50 - 38 - 70 . Er wird die Antwort berechnen, weil er erkennt die Teile durch Berechnung von ((100 + 50) - 38) - 70 , was natürlich 42 .
Ein kleines Detail: In der Aktion für term enthält term Variablennummer ein TokenInfo Objekt. TokenInfo müssen .string Attribut .string , um das Token in Zeichenfolgenform .string .
Was tun wir, wenn eine Alternative mehrere Vorkommen mit demselben Regelnamen hat? Der Parser-Generator gibt jedem Vorkommen einen eindeutigen Namen und fügt 1 , 2 usw. hinzu. Für spätere Ereignisse innerhalb derselben Alternative. Zum Beispiel:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
Die vollständige Implementierung ist ziemlich langweilig, daher möchte ich nicht weiter darauf eingehen. Ich lade Sie ein, in mein Repository zu schauen und mit dem Code zu spielen :
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
Mit der Visualisierung können Sie sich jetzt mit den Pfeiltasten nach links und rechts hin und her bewegen!
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0