Inspiriert nur von einem teilweisen Verständnis von PEG, beschloss ich, es zu implementieren. Das Ergebnis ist möglicherweise nicht das beste unter Allzweck-PEG-Parsern - es gibt bereits viele davon (zum Beispiel ist TatSu in Python geschrieben und generiert Python-Code) -, aber dies ist ein guter Weg, um PEG zu verstehen. In Zukunft möchte ich es durch die aktuelle Implementierung des Parsers in CPython ersetzen.
Inhalt der Python PEG Parser-Serie In diesem Abschnitt lege ich den Grundstein für das Verständnis der Arbeit des Parsers am Beispiel einer einfachen selbstgeschriebenen Implementierung der Spielzeuggrammatik aus einem früheren Artikel.
(Übrigens platziere ich als Experiment keine Links in meinem Text. Wenn Sie etwas nicht verstehen, können Sie es einfach googeln. :-)
In der Regel verwendet ein PEG einen rekursiven Abstiegsparser mit einem unbegrenzten Puffer für die Rückgabe. Hier ist eine Spielzeuggrammatik aus einem früheren Artikel:
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
Der super-abstrakte Parser des rekursiven Abstiegs für diese Sprache definiert seine Funktion für jede Regel, in der die Alternativen verstanden werden. Zum Beispiel hätten wir für die statement folgende Funktion:
def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False
Dies ist natürlich ein zu vereinfachtes Beispiel: Es werden wichtige Details ausgelassen, z. B. was der Eingabe dieser Funktion zugeführt wird und was das Ergebnis ihrer Ausführung sein wird.
Beginnen wir mit den Argumenten. Klassische Parser verwenden einen separaten Tokenizer, der die Eingabe (Textdatei oder Zeile) in eine Reihe von Token aufteilt, z. B. Schlüsselwörter, Bezeichner (Namen), Zahlen und Operatoren. PEG-Parser (wie andere moderne Parser wie ANTLR) kombinieren häufig Tokenisierung und Parsing, aber für mein Projekt habe ich beschlossen, einen separaten Tokenizer zu belassen.
Die Python-Tokenisierung ist ziemlich kompliziert, daher möchte ich sie nicht in PEG-Regeln implementieren. Sie sollten beispielsweise die Einrückung verfolgen (dies erfordert einen Stapel im Tokenizer). Interessant ist auch die Verarbeitung von Zeilenumbrüchen in Python (sie sind von Bedeutung, mit Ausnahme der in entsprechenden Klammern eingeschlossenen). Viele Arten von Zeichenfolgen verursachen auch eine gewisse Komplexität. Kurz gesagt, ich habe keine Beschwerden über den vorhandenen Python-Tokenizer, daher möchte ich ihn so lassen, wie er ist. CPython verfügt übrigens über zwei Tokenizer: den internen, der vom Parser verwendet wird, der in C geschrieben ist, und den Standardbibliothek, der eine exakte Kopie ist, die in reinem Python implementiert ist. Dies wird in meinem Projekt nützlich sein.
Ein klassischer Tokenizer verfügt normalerweise über eine einfache Schnittstelle, die aus einer einzelnen Funktion get_token() . Jedes Mal wird das nächste Token in der Eingabesequenz zurückgegeben, wobei eine Gruppe von Zeichen analysiert wird. Das tokenize Modul von CPython ist keine Ausnahme: Die Kern-API ist ein Generator, der jeweils ein Token ausgibt. Jedes Token ist ein Objekt vom Typ TypeInfo , das mehrere Felder enthält, von denen das wichtigste der Typ des Tokens ist (z. B. NAME , NUMBER , STRING ) und dessen Zeichenfolgenwert die Zeichensätze sind, aus denen es besteht (z. B. abc , 42 oder "Hello, world" ). Es gibt auch zusätzliche Felder. Zum Beispiel für den Token-Index im Eingabestream, der bei Fehlermeldungen hilfreich ist.
Ein spezieller Token-Typ ist ENDMARKER , der angibt, dass das Ende der Eingabedatei erreicht wurde. Der Generator fällt aus, wenn Sie ihn ignorieren und versuchen, den nächsten Token zu erhalten.
Aber ich war abgelenkt. Wie realisieren wir unbegrenzte Renditen? Wenn Sie die Token-Liste zurücksetzen, müssen Sie sich die Position im Quellcode merken und von diesem Punkt aus erneut analysieren können. Die Tokenizer-API erlaubt es uns nicht, den Zeiger zu verschieben, aber Sie können den Token-Stream in einem Array erfassen und von dort aus abspielen, was wir tun werden. Sie können dies auch mit itertools.tee() wiederholen, dies ist jedoch in unserem Fall wahrscheinlich weniger effektiv, wenn Sie sich die Warnungen in der Dokumentation ansehen.
Ich nehme an, Sie könnten zuerst alle Eingaben in die Liste tokenisieren und sie dann als Eingabe für den Parser verwenden. Wenn jedoch am Ende der Datei ein ungültiges Token vorhanden war (z. B. eine Zeile mit einem fehlenden schließenden Anführungszeichen) und in der Datei auch ein Syntaxfehler aufgetreten ist, erhalten Sie zuerst eine Fehlermeldung vom Tokenizer. Ich glaube, das ist schlecht für den Benutzer, da ein Syntaxfehler die Hauptursache für eine ungültige Zeile sein kann. Ich habe also etwas andere Anforderungen an den Tokenizer, insbesondere sollte er als Lazy List implementiert werden.
Die Kern-API ist sehr einfach. Das Tokenizer Objekt kapselt ein Array von Token und Positionen in diesem Array. Er hat drei Hauptmethoden:
get_token() gibt das nächste Token zurück und bewegt den Zeiger (oder liest das nächste Token aus der Quelle, wenn wir uns am Ende des Token-Puffers befinden);mark() gibt die aktuelle Position im Puffer zurück;reset(pos) setzt die Position im Puffer (das Argument muss von mark() ).
Wir haben eine peek_token() hinzugefügt, die das nächste Token zurückgibt, ohne die Position im Puffer zu verschieben.
So sieht die Basis der Tokenizer Klasse aus:
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
Hier wird der Einfachheit halber etwas weggelassen (z. B. müssen die Namen von Methoden und Instanzvariablen mit einem Unterstrich beginnen), dies ist jedoch nur ein Prototyp der Tokenizer API.
Der Parser muss auch eine Klasse werden, damit statement() , expr() usw. könnte als Methoden implementiert werden. Der Tokenizer wird zu einer Instanzvariablen, aber ich möchte nicht, dass die Parser-Methoden get_token() direkt aufrufen. get_token() implementieren wir die wait() -Methode in der Parser Klasse, die genau wie die Parser-Methode erfolgreich sein oder fehlschlagen kann. Das Argument für die Funktion wait() ist das erwartete Token: entweder eine Zeichenfolge (z. B. + ) oder ein Token-Typ (z. B. NAME ). Die Art des Rückgabewerts ist noch nicht wichtig. Ich werde darauf zurückkommen, nachdem ich das Ergebnis der Arbeit des Parsers besprochen habe.
Lassen Sie die Grammatikregelfunktionen vorerst nur True oder False . Dies ist gut für die theoretische Informatik (dort beantwortet der Parser die Frage „Ist dies eine gültige Zeichenfolge in der Sprache?“), Aber nicht für uns. Unsere Aufgabe ist es, einen AST zu erstellen. Schreiben wir diesen Code neu, sodass jede Analysemethode bei Erfolg ein Node Objekt oder bei Misserfolg None zurückgibt.
Die Node Klasse kann sehr einfach sein:
class Node: def __init__(self, type, children): self.type = type self.children = children
Hier bestimmt type den Typ des AST-Knotens (z. B. add oder if ), und die Nachkommen sind eine Liste von Knoten und Token ( TokenInfo Instanzen). Dies reicht aus, damit der Compiler Code generieren oder andere Analysen durchführen kann, z. B. Flusen oder statische Typprüfung. Obwohl ich in Zukunft die Art und Weise ändern möchte, wie AST präsentiert wird.
Um in dieses Schema zu passen, muss die TokenInfo expect() -Methode bei Erfolg ein TokenInfo Objekt und bei einem Fehler None . Um zu früheren Token zurückkehren zu können, verpacke ich die Aufrufe in die Methoden mark() und reset() des Tokenizers (hier ändert sich die API nicht). Folgendes ist passiert:
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
Noch einmal: Ich habe einige Details weggelassen, aber dies ist bereits funktionierender Code.
Jetzt muss ich eine wichtige Anforderung für Parser-Methoden einführen. Jeder sollte entweder Node und den Tokenizer nach dem letzten Token der Grammatikregel platzieren, die er erkannt hat. entweder None und lassen Sie die Position des Tokenizers unverändert. Wenn die Parser-Methode mehrere Token liest und dann abfällt, muss die Position des Tokenizers wiederhergestellt werden. Dazu sind mark() und reset() vorgesehen. Beachten Sie, dass expect() auch diese Regel befolgt.
Hier ist eine Skizze des eigentlichen Parsers. Hier verwende ich den Walross-Operator aus Python 3.8 ( := ):
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
Ich habe die Implementierung einiger Methoden weggelassen, damit der Leser die Möglichkeit hatte, sich selbst zu üben. Dies ist wirklich besser als nur zu lesen, wie ein solcher Parser implementiert wird. Am Ende werden wir solchen Code automatisch aus der Grammatik generieren. Konstanten wie NAME und NUMBER werden aus dem token Modul der Standardbibliothek importiert. Dies bindet uns weiter an die aktuelle Implementierung des Python-Tokenizers. Wenn wir einen verallgemeinerten PEG-Parser erstellen möchten, müssen wir Wege finden, dies zu vermeiden.
Beachten Sie auch, dass ich ein wenig betrogen bin. Die expr Methode muss rekursiv bleiben, aber ich habe den Parser rechts rekursiv gemacht, da der Parser für rekursiven Abstieg nicht mit linksrekursiven Grammatikregeln funktioniert. Dies kann behoben werden, ist aber immer noch Gegenstand wissenschaftlicher Forschung, und ich möchte darüber separat sprechen. Denken Sie daran, dass diese Implementierung nicht zu 100% mit unserer vereinfachten Grammatik übereinstimmt.
Die wichtigsten Dinge, die Sie bisher verstehen sollen:
- Grammatikregeln entsprechen Parsermethoden. Wenn sich eine Grammatikregel auf eine andere bezieht, wird eine Methode einer anderen Regel aufgerufen.
- Wenn eine Folge von Token unterschiedlich interpretiert werden kann, werden die entsprechenden Parser-Methoden nacheinander aufgerufen.
- Wenn sich eine Grammatikregel auf ein Token bezieht, ruft die Methode die Funktion
expect() . - Wenn der Parser seine Grammatikregel an der aktuellen Position erfolgreich erkennt, gibt er den entsprechenden AST-Knoten zurück. Wenn er seine Grammatikregel nicht erkennen kann, gibt er
None . - Parser-Methoden sollten die Tokenizer-Position explizit zurücksetzen, wenn sie das Parsen beenden, nachdem sie ein oder mehrere Token verwendet haben (direkt oder indirekt, indem eine andere erfolgreiche Parsing-Methode aufgerufen wird). Dies gilt nicht nur, wenn eine der Optionen abgelehnt wird, um mit der nächsten fortzufahren, sondern auch, wenn die Analyse insgesamt abgelehnt wird.
Wenn alle Analysemethoden diesen Regeln entsprechen, müssen sie nicht jeweils in mark() und reset() -Aufrufen eingeschlossen werden. Dies kann durch Induktion nachgewiesen werden.
Darüber hinaus ist es verlockend, explizite Aufrufe von mark() und reset() mithilfe des Kontextmanagers und der with Anweisung with entfernen, aber es funktioniert nicht: Sie sollten reset() nicht aufrufen, wenn dies erfolgreich ist! Als weitere Lösung können Sie versuchen, Ausnahmen für den Kontrollfluss zu verwenden, damit der Kontextmanager weiß, ob der Tokenizer zurückgesetzt werden sollte (ich denke, TatSu macht etwas Ähnliches). Zum Beispiel so etwas:
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
Insbesondere kann eine kleine Leiter mit if in atom() zum Erkennen eines Ausdrucks in Klammern wie folgt geschrieben werden:
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
Aber es scheint mir zu "magisch" - wenn Sie solchen Code lesen, sollten Sie daran denken, dass jede Analysemethode (einschließlich wait() ) eine Ausnahme auslösen kann. Und dass diese Ausnahme vom Kontextmanager in der with Anweisung abgefangen und ignoriert wird. Dies ist eher ungewöhnlich, obwohl realisierbar (durch Rückgabe von True von __exit__ ). Mein letztendliches Ziel ist es jedoch, Code in C und nicht in Python zu generieren, und in C gibt es keine with Anweisung, um den Kontrollfluss zu ändern.
Wie auch immer, hier sind einige Themen für die folgenden Teile:
- Generierung von Parser-Methoden aus der Grammatik;
- Packrat-Parsing (Memoisierung);
- EBNF-Merkmale wie
(x | y) , [xy ...] , x* , x+ ; - Ablaufverfolgung (zum Debuggen eines Parsers oder einer Grammatik);
- PEG-Funktionen wie Lookahead und Cut;
- wie man mit linken rekursiven Regeln umgeht;
- C-Code-Generierung
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0