Diese Woche machen wir den Parser-Generator "unabhängig", das heißt, er wird seinen eigenen Parser generieren.
Inhalt der Python PEG Parser-Serie Wir haben also bereits einen Parser-Generator, von dem ein Teil ein Grammatik-Parser ist. Wir könnten es einen Meta-Parser nennen. Der Meta-Parser funktioniert ähnlich wie der generierte: GrammarParser erbt von Parser und verwendet denselben Mechanismus mark() / reset() / hope() . Dort wurde jedoch alles von Hand geschrieben. Aber ist das richtig?
Beim Entwerfen eines Compilers ist es üblich, dass der Compiler in der Sprache geschrieben wird, die er kompiliert. Ich erinnere mich mit Liebe daran, dass der Pascal-Compiler, den ich beim ersten Programmieren verwendet habe, in Pascal selbst geschrieben wurde, GCC in C und der Rust-Compiler in Rust.
Wie kann man das machen? Implementieren Sie zu Beginn einen Compiler für eine Teilmenge oder eine frühere Version einer Sprache in einer anderen Sprache. (Ich möchte Sie daran erinnern, dass der ursprüngliche Pascal-Compiler in FORTRAN geschrieben wurde!) Dann wird der neue Compiler in der Zielsprache geschrieben und mit dem zu Beginn implementierten Bootstrap-Compiler kompiliert. Sobald der neue Compiler gut genug funktioniert, wird der Bootstrap-Compiler entfernt und jede nachfolgende Version der Sprache oder des Compilers ist auf das beschränkt, was mit der vorherigen Version des Compilers kompiliert werden kann.
Machen wir es für unseren Meta-Parser. Wir werden eine Grammatik für die Grammatiken schreiben (Meta-Grammatik) und daraus einen neuen Meta-Parser generieren. Glücklicherweise habe ich diesen Schritt von Anfang an geplant, so dass es ganz einfach sein wird. Die Aktionen, die wir in der vorherigen Episode hinzugefügt haben, sind eine wichtige Komponente, da wir den Generator nicht ändern müssen und daher eine kompatible Datenstruktur erstellen müssen.
Hier ist eine vereinfachte Version des Metagramms ohne Aktionen:
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
Ich zeige Ihnen, wie Sie Aktionen von unten nach oben hinzufügen. Erinnern Sie sich an Teil 3, dass es alts gibt, die die alts name und alts . Anfangs war alts nur eine Liste von alts (eine externe Liste für Alternativen und eine interne Liste für jedes Element der Alternative), aber um Aktionen zu implementieren, habe ich sie so geändert, dass die Alternativen durch Alt Objekte mit items und action . Elemente werden weiterhin als einfache Zeichenfolgen dargestellt. Für item wir:
item: NAME { name.string } | STRING { string.string }
Dies erfordert eine kleine Erklärung: Wenn der Analysator das Token verarbeitet, gibt er ein TokenInfo Objekt mit type , string und anderen Attributen zurück. Wir möchten nicht, dass der Generator mit TokenInfo Objekten arbeitet, daher extrahieren die Aktionen hier die Zeichenfolge aus dem Token. Beachten Sie, dass der generierte Parser für alle Token in Großbuchstaben, z. B. NAME , die Zeichenfolgenversion (hier name ) als Namen der Variablen verwendet.
Als nächstes folgen items , die eine Liste von Zeichenfolgen zurückgeben sollen:
items: item items { [item] + items } | item { [item] }
Hier verwende ich rechtsrekursive Regeln, damit wir nicht von der Verarbeitung der linken Rekursion abhängig sind, die in Teil 5 hinzugefügt wurde. (Warum nicht? Es ist immer gut, die Dinge so einfach wie möglich zu halten, und diese Grammatik wird von einer Änderung unter der linken Rekursion nicht wesentlich profitieren.) Beachten Sie diese item aufgelistet, rekursiv jedoch nicht, da es sich bereits um eine Liste handelt.
alt Regel zum Erstellen eines Alt Objekts:
alt: items { Alt(items) }
Ich werde die Aktionen für rules weglassen und start , wie sie auf diese Weise definiert sind.
Es gibt jedoch zwei offene Fragen. Wie finde ich zuerst die Definition der Klassen Rule und Alt ? Dazu müssen wir dem generierten Code mehrere import hinzufügen. Am einfachsten wäre es, das Flag an den Generator zu übergeben, der besagt, dass dies eine Meta-Grammatik ist, und den Generator zu Beginn des generierten Programms einen zusätzlichen import einfügen zu lassen. Aber jetzt, da wir die Aktionen haben, werden viele andere Parser auch ihren Import anpassen wollen. Warum also nicht sehen, ob wir einen allgemeineren Ansatz implementieren können?
Es gibt viele Möglichkeiten, dies zu implementieren. Ein einfacher und allgemeiner Mechanismus besteht darin, oben in der Grammatik einen Abschnitt „Variablendefinitionen“ hinzuzufügen und dem Generator zu ermöglichen, diese Variablen zur Steuerung verschiedener Aspekte des generierten Codes zu verwenden. Ich entschied mich, das @ -Symbol zu verwenden, um mit der Definition der Variablen zu beginnen, gefolgt vom Variablennamen ( NAME ) und dem Wert ( STRING ). Zum Beispiel können wir den folgenden Codeblock oben in die Meta-Grammatik einfügen:
@subheader "from grammar import Rule, Alt"
Der Parser-Generator druckt den Wert der subheader Variablen nach dem Standardimport, der standardmäßig hinzugefügt wird (z. B. zum Importieren von memoize ). Wenn Sie mehrere import möchten, können Sie eine Zeichenfolge mit dreifachen Anführungszeichen verwenden, z.
@subheader """ from token import OP from grammar import Rule, Alt """
Dies lässt sich leicht zur Meta-Grammatik hinzufügen: Wir werden die start folgt aufteilen:
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
(Ich kann mich nicht erinnern, warum ich es "Meta" genannt habe, aber ich habe diesen Namen gewählt, als ich den Code geschrieben habe, und ich werde mich daran halten. :-)
Wir müssen dies dem Bootstrap-Metaparser hinzufügen. Da die Grammatik nicht nur eine Liste von Regeln ist, fügen wir ein Grammatikobjekt mit den Attributen metas und rules . Wir können die folgenden Aktionen festlegen:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
(Beachten Sie, dass meta ein Tupel zurückgibt und eval() zum Verarbeiten von Zeichenfolgen in Anführungszeichen verwendet.)
Ich habe die Umsetzung von Maßnahmen in den Regeln für alt ! Der Grund ist, dass sie etwas chaotisch herauskommen. Aber es macht keinen Sinn, weiter zu verschieben, also hier:
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Der Schmutz in der Definition wird durch meinen Wunsch verursacht, beliebigen Python-Code zwischen geschweiften Klammern gültig zu machen, einschließlich verschachtelter geschweifter Klammern. Zu diesem Zweck verwenden wir ein spezielles OP Token, das unseren Tokenizer für alle von Python erkannten Interpunktionen generiert (Rückgabe eines einzelnen Tokens vom Typ OP für mehrstellige Operatoren wie <= oder ** ). Die einzigen anderen Token, die in Python-Ausdrücken vorkommen können, sind Namen, Zahlen und Zeichenfolgen. Somit kann der Code zwischen den äußeren Klammern der Aktion anscheinend durch Wiederholungen von NAME | NUMBER | STRING | OP ausgedrückt werden NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .
Leider funktioniert dies nicht, da das OP auch mit geschweiften Klammern übereinstimmt. Da der PEG-Analysator immer gierig ist, wird die schließende Klammer erfasst, und wir werden niemals das Ende der Aktion sehen. Aus diesem Grund fügen wir eine kleine Optimierung hinzu, damit die Aktion einen alternativen Auswahlfehler auslösen und None zurückgeben kann. Ich weiß nicht, ob dies ein Standardphänomen bei anderen PEG-Parsern ist. Ich habe es sofort gefunden, als ich das Problem des Erkennens der schließenden Klammer lösen musste (auch ohne verschachtelte Paare). Dies scheint gut zu funktionieren, und ich denke, es passt in die allgemeine Philosophie der PEG-Analyse. Dies kann als eine besondere Form der Voraussicht angesehen werden (auf die ich weiter unten eingehen werde).
Mit diesem kleinen Hack können wir den Vergleich auf dem OP auf eine geschweifte Klammer fallen lassen. Dann wird ein Vergleich von stuff und action möglich sein.
Mit diesen Dingen kann eine Meta-Grammatik von einem Bootstrap-Metaparser analysiert werden, und der Generator kann sie in einen neuen Meta-Parser verwandeln, der sich selbst analysieren kann. Und vor allem kann der neue Meta-Parser immer noch dieselbe Meta-Grammatik analysieren. Wenn wir die Meta-Grammatik mit dem neuen Meta-Compiler kompilieren, ist das Ergebnis dasselbe: Dies beweist, dass der generierte Meta-Parser korrekt funktioniert.
Hier ist die vollständige Aktions-Meta-Grammatik. Er kann sich selbst analysieren, da er weiß, wie man lange Schlangen kombiniert:
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Jetzt, da wir eine funktionierende Meta-Grammatik haben, sind wir fast bereit, einige Verbesserungen vorzunehmen.
Aber zuerst müssen Sie ein wenig nachdenken: leere Zeilen! Es stellt sich heraus, dass das Modul stdlib tokenize zusätzliche Token erstellt, um unbedeutende tokenize ( NL Token) und Kommentare ( COMMENT Token) zu COMMENT . Anstatt sie in die Grammatik aufzunehmen (ich habe es versucht, es macht wenig Spaß!), Gibt es einen sehr einfachen Code, den wir unserer Tokenizer-Klasse hinzufügen können, um sie zu filtern. Hier ist die verbesserte peek_token Methode:
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
Dadurch werden die COMMENT und COMMENT Token vollständig entfernt, sodass wir uns in der Grammatik nicht mehr um sie kümmern müssen.
Lassen Sie uns zum Schluss die Meta-Grammatik verbessern! Sie werden rein kosmetisch sein: Ich mag es nicht, wenn ich gezwungen bin, alle Alternativen in einer Zeile zu schreiben. Die Meta-Grammatik, die ich oben gezeigt habe, analysiert sich aufgrund solcher Dinge nicht selbst:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
Dies liegt an der Tatsache, dass der Tokenizer am Ende der ersten Zeile ein NEWLINE Token erstellt. NEWLINE diesem Moment betrachtet der Meta-Parser dies als das Ende der Regel. Darüber hinaus folgt auf diese NEWLINE das INDENT Token, da die nächste Zeile eingerückt ist. Bis zum Beginn der nächsten Regel ist auch ein DEDENT Token vorhanden.
Hier erfahren Sie, wie Sie damit umgehen. Um das Verhalten des tokenize Moduls zu verstehen, können wir uns die Reihenfolge der Token ansehen, die für eingerückte Blöcke generiert werden, indem das tokenize Modul als Skript ausgeführt und Text übergeben wird:
$ python -m tokenize foo bar baz dah dum ^D
Wir sehen, dass dies die folgende Folge von Token erzeugt (ich habe die Ausgabe des obigen Codes etwas vereinfacht):
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
Somit wird eine ausgewählte Gruppe von Zeichenfolgen durch INDENT und DEDENT . Jetzt können wir die Meta-Grammatik- rule für die rule wie folgt umschreiben:
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
(Ich teile die Aktionen in Zeilen ein, damit sie normal in einer engen Textspalte gelesen werden. Dies ist möglich, weil der Tokenizer Zeilenumbrüche in den entsprechenden geschweiften Klammern ignoriert.)
Das Schöne daran ist, dass wir den Generator nicht einmal ändern müssen: Die Datenstruktur, die durch diese verbesserte Meta-Grammatik erstellt wird, ist dieselbe wie zuvor. Beachten Sie auch die dritte Option für die rule : Dies ermöglicht uns zu schreiben:
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
dass einige es sauberer finden als die Version, die ich zuvor gezeigt habe. Beide Formen sind leicht zu lösen, sodass wir uns nicht über den Stil streiten müssen.
Im nächsten Beitrag werde ich zeigen, wie ich verschiedene PEG-Funktionen implementiert habe, z. B. optionale Elemente, Wiederholungen und QuickInfos. (Um ehrlich zu sein, hatte ich vor, in diesem Artikel darüber zu sprechen, aber es ist bereits zu groß. Also werde ich es in zwei Teile teilen.)
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0