Nachdem ich nun die Grundlagen eines proprietären Parsers skizziert habe, können wir seine Methoden, wie versprochen, aus der Grammatik generieren. Ich werde auch zeigen, wie man einen Packrat-Parser mit dem @memoize Dekorator @memoize .
Inhalt der Python PEG Parser-Serie Letztes Mal haben wir uns einige Parser-Methoden angesehen. Mit einigen Einschränkungen, die wir etwas später entfernen werden, können sie einfach automatisch aus der Grammatik generiert werden.
Wir brauchen zwei Dinge: etwas, das die Grammatik liest und eine geeignete Datenstruktur aufbaut; und etwas, das diese Datenstruktur übernimmt und einen Parser generiert. Wir brauchen auch andere Hilfsmethoden, aber sie sind nicht interessant, deshalb werde ich sie weglassen.
Wir erstellen also einen einfachen Compiler-Compiler. Ich werde die grammatikalische Notation ein wenig vereinfachen, insofern wir nur Regeln und Alternativen haben; Dies ist eigentlich genug für die Spielzeuggrammatik, die ich in den vorherigen Teilen verwendet habe:
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
Mit der vollständigen Notation können wir die Grammatik beschreiben als:
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
Dies ist unsere erste Meta-Grammatik (Grammatik für Grammatiken), und unser Parser-Generator wird ein Meta-Compiler sein (ein Compiler ist ein Programm, das Programme von einer Sprache in eine andere übersetzt; ein Meta-Compiler ist ein Compiler, bei dem die Eingabe eine Grammatik ist, und Die Ausgabe ist ein Parser.
Eine einfache Möglichkeit, eine Meta-Grammatik zu beschreiben, besteht darin, nur die integrierten Datentypen zu verwenden: Der rechte Teil der Regel ist eine Liste von Elementlisten, von denen jedes nur eine Zeichenfolge sein kann. (Übrigens können wir NAME und STRING trennen, indem wir prüfen, ob das erste Zeichen ein Anführungszeichen ist.)
Für Regeln verwende ich die einfache Rule , und die gesamte Grammatik ist eine Liste solcher Objekte. Hier ist die __repr__ Ausnahme von __repr__ und __eq__ :
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
Und hier ist die GrammarParser Klasse, die es verwendet:
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
ENDMARKER auf die Verwendung von ENDMARKER . Dort stelle ich sicher, dass nach der letzten Regel nichts mehr übrig bleibt (und dies kann passieren, wenn die Grammatik einen Tippfehler enthält). Ich habe auch auf die Stelle hingewiesen, an der die grammar() -Methode eine Liste von Regeln zurückgibt. Alles andere ist der ToyParser Klasse aus dem letzten Artikel sehr ähnlich, daher werde ich nicht weiter darauf ToyParser . alts nur, dass item() eine Zeichenfolge zurückgibt, alternative() eine Liste von Zeichenfolgen zurückgibt und die Variable alts in rule() eine Liste von Zeichenfolgen sammelt. Anschließend kombiniert die Methode rule() den Namen der Regel (Zeichenfolge) und konvertiert sie in ein Rule .
Wenn wir diesen Algorithmus auf unsere Spielzeuggrammatik anwenden, gibt die grammar() -Methode die folgende Liste von Regeln zurück:
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
Nachdem wir den Parsing-Teil unseres Meta-Compilers haben, erstellen wir einen Code-Generator. Zusammen bilden sie einen elementaren Meta-Compiler:
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
Dieser Code ist ziemlich hässlich, aber er funktioniert (irgendwie), und in Zukunft werde ich ihn trotzdem umschreiben.
Einige Zeilen in der for alt in rule.alts möglicherweise erklärt werden: Für jedes Element in der Alternative wählen wir eine von drei Optionen:
- Wenn das Element ein String-Literal ist, zum Beispiel
'+' , generieren wir self.expect('+') - Wenn das Element vollständig in Großbuchstaben geschrieben ist, z. B.
NAME , generieren wir (name := self.expect(NAME)) - Andernfalls generieren wir zum Beispiel, wenn es
expr , (expr := self.expr())
Wenn in einer Variante mehrere Elemente mit demselben Namen vorhanden sind (z. B. term '-' term ), fügen wir der zweiten eine Ziffer hinzu. Es gibt hier auch einen kleinen Fehler, den ich in der nächsten Folge korrigieren werde.
Hier ist ein kleiner Teil des Ergebnisses seiner Arbeit (die ganze Klasse wäre sehr langweilig). Machen Sie sich keine Sorgen über den redundanten if (True and ... ) Code, der benötigt wird, damit jede generierte Bedingung mit and . Der Python-Byte-Compiler optimiert dies.
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
@memoize auf den @memoize Dekorateur: Ich habe ihn eingeführt, um zu einem anderen Thema @memoize : Verwenden von Memoization, um den generierten Parser schnell genug zu machen.
Hier ist die Funktion memoize() , die diesen Dekorator implementiert:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
Wie in anderen Dekoratoren enthält es eine verschachtelte Funktion, die eine dekorierte Funktion ersetzt (oder umschließt), z. B. die statement() -Methode der ToyParser Klasse. Da es sich bei der ToyParser Funktion um eine Methode handelt, ist der Wrapper auch eine Methode: Das erste Argument heißt self und bezieht sich auf die ToyParser Instanz, für die die dekorierte Methode aufgerufen wird.
Der Wrapper speichert das Ergebnis des Methodenaufrufs für jede Eingabeposition zwischen - daher wird er als Packrat-Parser bezeichnet! [ca. trans. packrat ist ein "Dieb", aber dieser Begriff wird nicht in russischsprachigen Quellen übersetzt.] Cache ist ein Wörterbuch mit Wörterbüchern, das in einer Parser Instanz gespeichert ist. Der Schlüssel des externen Wörterbuchs ist die Position im Eingabedatenstrom. Ich habe auch self.memos = {} zu Parser .__ init__() hinzugefügt, um es zu initialisieren. Interne Wörterbücher werden nach Bedarf hinzugefügt. Ihre Schlüssel bestehen aus einer Methode und ihren Argumenten. (Das aktuelle Design enthält keine Argumente, aber wir könnten uns die Funktion "accept expect() merken, die expect() hat, was ziemlich trivial ist.)
Das Ergebnis der Parser-Methode wird in Form eines Tupels dargestellt, da es tatsächlich zwei Werte gibt: das Ergebnis selbst (für unsere generierten Methoden ist dies der Node für die Übereinstimmungsregel) und einen Zeiger auf die aktuelle Position im Eingabestream, die wir von self.mark() . Daher zwischenspeichern wir sowohl den Rückgabewert ( res ) als auch die neue Position ( endpos ) im internen Wörterbuch mit gespeicherten Werten. Bei nachfolgenden Aufrufen derselben Analysemethode mit denselben Argumenten an derselben Eingabeposition werden sie aus dem Cache übernommen. Bewegen Sie dazu einfach den Zeiger mit self.reset() auf die Eingabeposition und schauen Sie in den Cache.
Es ist auch wichtig, negative Ergebnisse zwischenzuspeichern - tatsächlich sind die meisten Anrufe negativ. In diesem Fall ist der Rückgabewert None und die Eingabeposition ändert sich nicht. Sie können assert hinzufügen, um dies zu überprüfen.
Hinweis In Python ist es üblich, einen Cache in einer lokalen Variablen in der Funktion memoize() zu implementieren. In unserem Fall funktioniert dies nicht: Wie ich am Ende des Debuggens herausgefunden habe, muss jede Parser Instanz einen eigenen Cache haben. Sie können jedoch verschachtelte Wörterbücher pos , indem Sie ( pos , func , args ) als Schlüssel verwenden.
Nächste Woche werde ich Code und Traces vorbereiten, um zu zeigen, wie all dies beim Parsen eines Beispielprogramms tatsächlich zusammengestellt und ausgeführt wird. Ich bin immer noch auf der Suche nach einer besseren Möglichkeit, die Zusammenarbeit von Tokenisierungspuffer, Parser und Cache zu visualisieren. Vielleicht kann ich ein animiertes GIF in ASCII erstellen, anstatt nur die Trace-Listen als Text anzuzeigen.
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0