Peg Parser

Vor einigen Jahren fragte mich jemand, ob es sinnvoll sei, Python in einen PEG-Parser (oder in eine PEG-Grammatik zu konvertieren; ich erinnere mich nicht genau, wer und wann es war). Dann sah ich ihn ein wenig an, kam aber zu keinem Ergebnis und ließ dieses Thema fallen. Ich habe kürzlich mehr über PEG (Parsing Expression Grammars, Parsing Expression Grammar) erfahren und denke jetzt, dass dies eine interessante Alternative zu dem selbstgeschriebenen Parser-Generator ist, der vor 30 Jahren entwickelt wurde, als ich gerade anfing, an Python zu arbeiten. Ich nannte es "pgen" und dies war wahrscheinlich der erste Code, den ich für Python schrieb.

Der Grund, warum ich mich derzeit für den PEG-Parser interessiere, ist, dass mich die Einschränkungen von pgen etwas ärgern. Es basiert auf einer eigenen Implementierung von LL (1), die eine Reihe von Annahmen enthält. Zum Beispiel mochte ich keine Grammatikregeln, die leere Zeilen erzeugen könnten, deshalb habe ich sie verboten. Dadurch wurde der Algorithmus zum Erstellen von Parsing-Tabellen vereinfacht. Ich habe auch meine eigene EBNF-ähnliche Grammatiknotation erfunden, die ich immer noch sehr mag.

Hier sind einige Probleme mit pgen, die mich nerven. Die „1“ im Namen LL (1) impliziert, dass nur das nächste Token analysiert wird, und dies schränkt unsere Fähigkeit ein, gute Grammatikregeln zu erstellen. Eine Python-Anweisung kann beispielsweise ein Ausdruck oder eine Zuweisung sein (oder etwas anderes, aber alle beginnen mit einem hervorgehobenen Schlüsselwort, z. B. if oder def ). Ich möchte die Syntax in pgen-Notation beschreiben. Beachten Sie, dass dies nur ein vereinfachtes Beispiel ist, bei dem es sich um eine Teilmenge von Python handelt, wie dies normalerweise bei der Beschreibung des Sprachdesigns der Fall ist. Dies wird eine Spielzeuggrammatik sein, die für weitere Demonstrationen nützlich sein wird.

 statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement 

Ein paar Worte zur Notation: NAME und NUMBER sind Token und außerhalb der Grammatik vordefiniert. Zitierte Zeichenfolgen vom Typ '+' oder 'if' sind ebenfalls Token. (Verschieben wir das nächste Mal die Diskussion darüber.) Grammatikregeln beginnen mit dem Namen der Regel, gefolgt von : und einer oder mehreren Alternativen, die durch | .

Das Problem ist, dass wenn Sie die Grammatik so beschreiben, pgen nicht funktioniert. Dies liegt an der Tatsache, dass einige Regeln ( expr und term ) rekursiv bleiben und er nicht klug genug ist, um mit solchen Situationen richtig expr . Normalerweise wird dies gelöst, indem nur diese Regeln neu geschrieben werden und die anderen Regeln unverändert bleiben. Zum Beispiel:

 expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)* 

Dies zeigt verschiedene Möglichkeiten von EBNF in pgen: Sie können Alternativen in Klammern verschachteln und Wiederholungen erstellen, indem Sie * nach dem Element setzen. Die Regel für den Ausdruck Ausdruck expr hier also "es ist ein Term, gefolgt von null oder mehr Wiederholungen der Sequenz <Term plus oder minus, gefolgt von Term>". Diese Grammatik hat dieselbe Sprache wie die erste Version, spiegelt jedoch nicht die Entwurfsabsicht der Sprache wider. Insbesondere wird nicht angezeigt, dass die Operatoren links gebunden sind. Dies ist wichtig, wenn Sie versuchen, Code zu generieren.

In diesem Beispiel (und auch in Python) gibt es jedoch ein weiteres ärgerliches Problem. Da nur ein Token analysiert wird, kann der Analysator nicht bestimmen, was er betrachtet - den Beginn eines Ausdrucks oder einer Zuweisung. Zu Beginn der Operatorverarbeitung sollte der Parser nur über das erste Token entscheiden, welche Alternative er analysiert. (Warum? So funktioniert die Implementierung von Parsing in pgen) Nehmen wir an, unser Programm sieht wie folgt aus:

 answer = 42 

Dieses Programm wird durch drei Token dargestellt: NAME (mit answer ), = und NUMBER (mit Wert 42 ). Das einzige, was wir zu Beginn der Analyse wissen, ist das erste NAME Token. Die Regel, die wir zu diesem Zeitpunkt zu analysieren versuchen, ist die statement (der Anfangscharakter der Grammatik). expr sind drei Alternativen definiert: expr , assignment und if_statement . Wir können if_statement sofort ausschließen, da das vorherige Token nicht if . Aber sowohl expr als auch assignment können mit dem NAME Token beginnen, und aus diesem Grund lehnt pgen unsere Grammatik als mehrdeutig ab.

Dies ist nicht ganz richtig, da technisch die Grammatik selbst nicht ist; Ich kann keine genauere Formulierung finden, also lassen Sie uns auf diese eingehen. Und wie löst pgen das? Es berechnet für jede Grammatikregel eine sogenannte FIRST-Menge. Wenn sie sich überschneiden, wird eine Ausnahme ausgelöst.

Können wir dieses Problem nicht lösen, indem wir dem Parser einen größeren Anzeigepuffer zur Verfügung stellen? In unserem Beispiel ist ein zweites Vorschau-Token ausreichend, da in dieser Grammatik das zweite Zuweisungstoken = . In einer realistischeren Sprache wie Python benötigen Sie möglicherweise einen unbegrenzten Puffer, da der Inhalt links vom = token = beliebig komplex sein kann, zum Beispiel:

 table[index + 1].name.first = 'Steven' 

In diesem Fall müssen Sie zehn Token analysieren, bevor wir uns treffen = . Aber ich versichere Ihnen, es kann längere Ausdrücke geben. Um dieses Problem in pgen zu lösen, haben wir den Grammatikanalysator so geändert, dass einige falsche Ausdrücke akzeptiert werden, und in einem nachfolgenden Durchgang eine zusätzliche Prüfung hinzugefügt. Es wird ein SyntaxError-Fehler ausgegeben, wenn er nicht mit der linken und rechten Seite übereinstimmen kann. Für unsere Spielzeugsprache kommt es darauf an, Folgendes zu schreiben:

 statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr] 

Eckige Klammern kennzeichnen ein optionales Teil. Und dann prüfen wir beim nächsten Durchgang des Compilers (z. B. beim Generieren von Bytecode), ob = oder nicht, und wenn ja, prüfen wir, ob die linke Seite mit der Zielsyntax übereinstimmt.

Es gibt ein ähnliches Problem für Funktionsaufrufargumente. Wir möchten so etwas schreiben (wieder in einer vereinfachten Version der Python-Syntax):

 call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr 

Der Parsing-Algorithmus, der nur das nächste Token berücksichtigt, kann dem Parser jedoch nicht mitteilen, ob NAME am Anfang von Argumenten der Beginn von posarg (da expr mit NAME beginnen kann) oder der Beginn von kwarg . Der aktuelle Python-Parser löst dieses Problem erneut, indem er Folgendes ermittelt:

 arg: expr ['=' expr] 

und vervollständigt dann die Alternative in einem nachfolgenden Compiler-Durchlauf. (Wir haben sogar einen kleinen Fehler gemacht und foo((a) = 1) genau wie foo(a = 1) analysiert. Dies wurde nur in Python 3.8 behoben.)

Wie löst ein PEG-Parser diese Probleme? Verwenden eines unendlichen Sicherungspuffers! Die typische Implementierung verwendet den sogenannten Packrat-Parser, der nicht nur das gesamte Programm vor dem Parsen in den Speicher lädt, sondern auch das Zurücksetzen des Analysators auf eine beliebige Anzahl von Token ermöglicht. Obwohl sich der Begriff PEG hauptsächlich auf die grammatikalische Notation bezieht, sind aus PEG-Grammatiken erzeugte Parser typischerweise Parser mit rekursiver Abstammung und unbegrenzter Rendite. Der Packrat-Parser macht das Ego effizient, indem er sich an die Regeln erinnert, die bereits für bestimmte Positionen analysiert wurden.

Dies vereinfacht den Algorithmus, aber natürlich gibt es einen Preis: Speicher. Vor dreißig Jahren hatte ich einen guten Grund, LL (1) zu verwenden: Speicher war teuer. Er (wie andere Technologien wie LALR (1), bekannt geworden durch YACC) verwendet eine Zustandsmaschine und einen Stapel, um einen Analysebaum effizient zu erstellen.

Glücklicherweise haben Computer mit CPython viel mehr Speicher als vor 30 Jahren, und das Speichern der gesamten Datei im Speicher ist kein Problem mehr. Die größte Nicht-Test-Datei in stdlib, die ich finden konnte, ist beispielsweise _pydecimal.py , was ungefähr 223 _pydecimal.py dauert. In der Gigabyte-Welt ist dies im Wesentlichen nichts, was mich dazu veranlasste, Parser anders zu betrachten.

Aber es gibt noch eine Sache im aktuellen CPython-Parser, die mich stört. Compiler sind komplexe Dinge, und die Implementierung für CPython ist keine Ausnahme. Obwohl das Ergebnis des pgen-Parsers ein Parsing-Baum ist, wird er nicht direkt als Eingabe für den Bytecode-Generator verwendet: Er wird zuerst in einen abstrakten Syntaxbaum (AST) konvertiert, und erst dann wird dieser AST in Bytecode kompiliert. (Tatsächlich ist es dort noch komplizierter, aber wir werden vorerst nicht auf Details eingehen.)

Warum nicht sofort aus einem Analysebaum kompilieren? Genau so war es, aber vor ungefähr 15 Jahren stellten wir fest, dass der Compiler überkompliziert war. Also haben wir AST und die Transformationsphase von AST getrennt vom Analysebaum isoliert. Während sich Python weiterentwickelte, blieb AST stabiler als das Parsen, was die Wahrscheinlichkeit von Fehlern im Compiler verringerte.

AST ist auch einfacher mit Bibliotheken von Drittanbietern zu arbeiten, die Python-Code testen möchten. Es kann mit dem beliebten ast Modul bezogen werden. Außerdem können Sie Knoten von Grund auf neu erstellen und vorhandene ändern sowie Teile zu Bytecode kompilieren. Letzteres ermöglichte die Schaffung einer ganzen Branche von Spracherweiterungen für Python. (Der Analysebaum ist auch für Python-Benutzer über das Parsing-Modul zugänglich, die Arbeit damit ist jedoch viel schwieriger. Daher ist er nicht so beliebt.)

Jetzt möchte ich diese Dinge kombinieren und sehen, ob wir einen neuen Parser für CPython erstellen können, der PEG und Packrat verwendet, um den AST direkt während des Parsens zu erstellen. Somit wird es möglich sein, die Erzeugung des Zwischenbaums des Parsens wegzulassen, was uns Speicher sparen kann, obwohl ein unendlicher Puffer für Token verwendet wird. Ich bin noch im Implementierungsprozess, aber ich habe bereits einen Prototyp, der eine Teilmenge von Python in AST mit ungefähr der gleichen Geschwindigkeit wie der aktuelle CPython-Parser kompilieren kann. Es wird jedoch mehr Speicher benötigt, und es scheint mir, dass das Erweitern der Teilmenge in die vollständige Sprache den PEG-Parser verlangsamt. Bisher habe ich jedoch noch keine Optimierungen vorgenommen, daher werde ich weiterarbeiten.

Der letzte Vorteil des Wechsels zu PEG besteht darin, dass es mehr Flexibilität für die weitere Entwicklung der Sprache bietet. In der Vergangenheit wurde gesagt, dass die LL (1) -Einschränkungen in pgen die Python-Grammatik einfach hielten. Dies mag durchaus zutreffen, aber wir haben viele andere Prozesse, um ein unkontrolliertes Sprachwachstum zu verhindern (hauptsächlich den PEP-Prozess, der durch sehr strenge Anforderungen an die Abwärtskompatibilität und eine neue Verwaltungsstruktur unterstützt wird). Ich mache mir darüber also keine Sorgen.

Ich würde gerne viel mehr über PEG und meine Implementierung erzählen, aber es wird in den nächsten Beiträgen sein, nachdem ich den Code bereinigt habe.

Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0