Ich habe die linke Rekursion mehrmals als Stolperstein erwähnt, und es ist Zeit, es herauszufinden. Das Hauptproblem besteht darin, dass ein Parser mit einem linksrekursiven Abstieg sofort aufgrund eines Stapelüberlaufs abstürzt.
Inhalt der Python PEG Parser-Serie Betrachten Sie diese hypothetische Grammatikregel:
expr: expr '+' term | term
Wenn wir diese Grammatik in die linksrekursive Parser-Methode implementieren würden, würden wir ungefähr Folgendes erhalten:
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
Daher beginnt expr() mit einem Aufruf von expr() , der mit einem Aufruf von expr() beginnt, der mit einem Aufruf beginnt ... Dies kann nur mit einem Stapelüberlauf enden, der als RecursionError Ausnahme ausgedrückt wird.
Die traditionelle Lösung besteht darin, die Grammatik neu zu schreiben. In den vorherigen Teilen habe ich genau das getan. Tatsächlich kann die obige Grammatikregel wie folgt umgeschrieben werden:
expr: term '+' expr | term
Beim Erstellen des Analysebaums würde sich seine Form jedoch unterscheiden. Dies könnte die Situation ruinieren, wenn wir der Grammatik den Operator '-' hinzufügen (da a - (b - c) nicht mit (a - b) - c identisch ist). Dies wird normalerweise mit leistungsstärkeren PEG-Funktionen wie Gruppierung und Iteration gelöst, und wir können die obige Regel wie folgt umschreiben:
expr: term ('+' term)*
Genau so wird die aktuelle Python-Grammatik für den pgen-Parser geschrieben (der die gleichen Probleme mit linksrekursiven Regeln hat).
Es gibt jedoch ein kleines Problem: Da Operatoren wie '+' und '-' (in Python) meistens binär sind, müssen wir bei der Analyse von a + b + c das Ergebnis des Parsens durchlaufen (welches im Wesentlichen eine Liste von ['a', '+', 'b', '+', 'c'] ), um einen linksrekursiven Analysebaum zu erstellen (der ungefähr so aussehen würde [['a', '+', 'b'] , '+', 'c'] ).
Die ursprüngliche linksrekursive Grammatik weist bereits auf die gewünschte Assoziativität hin, daher wäre es schön, einen Parser direkt aus dieser Form zu generieren. Und wir können! Ein Leser wies auf einen guten Trick mit mathematischen Beweisen hin, der leicht zu implementieren war. Jetzt werde ich versuchen zu erklären.
Schauen wir uns ein Beispiel für die Eingabe foo + bar + baz . Der Analysebaum, den wir daraus erhalten möchten, entspricht (foo + bar) + baz . Dies erfordert drei expr() Aufrufe der Funktion expr() : einer entspricht dem Operator '+' der obersten Ebene expr() dem zweiten); eine weitere - an den internen Operator '+' (d. h. den ersten); und die dritte ist die Wahl der zweiten Alternative (d. h. term ).
Da ich mit Spezialwerkzeugen keine guten Diagramme zeichnen kann, werde ich dies hier mit ASCII-Grafik zeigen:
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
Die Idee ist, dass wir in der Funktion expr() ein „Orakel“ benötigen, das uns sagt, ob wir die erste Alternative ( expr() den rekursiven Aufruf von expr() ) oder die zweite ( expr() den Aufruf von expr() ) wählen sollen. Beim ersten Aufruf von expr() Orakel uns expr() , der ersten Alternative zu folgen ( expr() ); im zweiten (rekursiven) Aufruf - ähnlich, aber im dritten sollte es uns auffordern, term() aufzurufen. Im Code sieht es folgendermaßen aus:
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
Wie schreibe ich so ein Orakel? Mal sehen ... Wir könnten versuchen, die Anzahl der ( expr() ) expr() -Aufrufe im Aufrufstapel zu verfolgen und sie mit der Anzahl der '+' Operatoren im folgenden Ausdruck zu vergleichen. Wenn der Aufrufstapel tiefer als die Anzahl der Anweisungen ist, sollte das Orakel false zurückgeben (zwingen Sie uns, term() auszuwählen). Ich kann es kaum erwarten, dies mit sys._getframe() zu implementieren, aber es gibt einen besseren Weg: Lassen Sie uns den Aufrufstapel umdrehen!
Die Idee ist, dass wir mit einem Aufruf beginnen, bei dem das Orakel false zurückgibt, und das Ergebnis speichern. Dies gibt uns die Sequenz expr() -> term() -> 'foo' . (Es sollte einen Analysebaum für den Anfangsbegriff zurückgeben, 'foo' . Der obige Code gibt nur True , aber im zweiten Teil der Artikelserie habe ich bereits gezeigt, wie der Analysebaum stattdessen zurückgegeben wird.) Ein solches Orakel ist einfach zu implementieren, da es sollte False beim ersten Aufruf einfach False - es ist keine Stapelprüfung oder ein Blick in die Zukunft erforderlich.
Dann rufen wir erneut expr() auf, und dieses Mal gibt das Orakel True , aber anstelle des linken rekursiven Aufrufs von expr() ersetzen wir das gespeicherte Ergebnis aus dem vorherigen Aufruf. Und da der erwartete Operator '+' und das nächste geeignete Token ebenfalls vorhanden sind, erhalten wir einen Analysebaum für foo + bar .
Wieder wiederholen wir den Algorithmus und wieder stellt sich alles heraus: Dieses Mal erhalten wir einen Analysebaum für den vollständigen Ausdruck, und er ist wirklich linksrekursiv ( (foo + bar) + baz ).
Dann wiederholen wir den Algorithmus erneut. Obwohl Oracle dieses Mal True zurückgibt und das gespeicherte Ergebnis des vorherigen Aufrufs ebenfalls verfügbar ist, gibt es keinen Operator '+' mehr, und die erste Alternative schlägt fehl. Daher versuchen wir die zweite Option, die erfolgreich ist, und finden nur den Anfangsbegriff ( 'foo' ). Dieses Ergebnis ist schlechter als das aus der ersten Alternative erhaltene, daher stoppen wir in diesem Stadium und speichern die längste Analyse (d. H. (foo + bar) + baz ).
Um dies in expr() , habe ich zuerst den Algorithmus ein wenig modifiziert, um den Aufruf von oracle() mit dem expr() Aufruf von expr() zu expr() . Nennen wir es oracle_expr() . Code:
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
Als nächstes schreiben wir einen Wrapper, der die oben beschriebene Logik implementiert. Es wird eine globale Variable verwendet (keine Sorge, ich werde sie später entfernen). Die Funktion oracle_expr() liest die globale Variable und der Wrapper steuert sie:
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
Der Code ist natürlich schrecklich, aber zumindest vermittelt er die Essenz des Algorithmus. Lassen Sie es uns umgestalten, damit wir stolz darauf sein können.
Das wichtigste Verständnis (das mir gehört, obwohl ich wahrscheinlich nicht der erste bin, der dies bemerkt) ist, dass wir den Memoization-Cache anstelle einer globalen Variablen verwenden können. Darin speichern wir das Ergebnis von Anruf zu Anruf. Also werden wir eine separate Funktion oracle_expr() los, weil Wir können einen Standardaufruf für expr() generieren, unabhängig davon, ob er sich links oder rechts in einer rekursiven Position befindet.
Wir benötigen also einen separaten @memoize_left_rec Dekorator, der nur für @memoize_left_rec Regeln verwendet wird. Es ruft die Funktion oracle_expr() , zieht den gespeicherten Wert aus dem Memoization-Cache und enthält eine Schleife, die die Funktion expr() mehrmals expr() , bis jedes neue Ergebnis mit einem immer längeren Teil der Eingabedaten als dem vorherigen vergleichbar ist. Und da jede Eingabeposition und jede Analysemethode separat zwischengespeichert wird, geht es natürlich nicht um das Zurückverfolgen oder einige rekursive Regeln (in der von mir verwendeten Spielzeuggrammatik expr sowohl expr als auch term rekursiv).
Ein weiterer Vorteil des Prototyps, den ich im dritten Teil erstellt habe, besteht darin, dass leicht überprüft werden kann, ob das neue Ergebnis länger als das alte ist: Die Methode mark() gibt den Index im Array der Eingabetoken zurück, sodass wir ihn einfach anstelle von parsed_length .
Ich lasse den Beweis weg, warum dieser Algorithmus immer funktioniert, egal wie verrückt die Grammatik ist. Tatsächlich habe ich es nicht einmal gelesen. Ich sehe, dass dies für einfache Fälle wie expr in meiner Spielzeuggrammatik sowie für etwas komplexere Fälle expr (z. B. die Verwendung einer linken Rekursion, die alternativ hinter optionalen Elementen verborgen ist, oder die gegenseitige Rekursion zwischen mehreren Regeln). Die schwierigste Situation, an die ich mich in der Python-Grammatik erinnern kann, wird immer noch durch diesen Algorithmus gelöst, daher vertraue ich nur dem Satz und den Leuten, die ihn bewiesen haben.
Schreiben wir den Kampfcode.
Zunächst muss der Parsergenerator bestimmen, welche Regeln rekursiv bleiben. Dies ist ein gelöstes Problem in der Graphentheorie. Ich werde den Algorithmus hier nicht zeigen, und tatsächlich möchte ich ihn noch weiter vereinfachen. Ich expr davon aus, dass die einzigen expr Regeln in der Grammatik direkt expr sind, wie in unserer Spielzeuggrammatik. Um die Rekursivität der linken Seite zu überprüfen, müssen Sie nur nach einer Alternative suchen, die mit dem Namen der aktuellen Regel beginnt:
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
Jetzt werden wir den Parser-Generator so ändern, dass er für linksrekursive Regeln einen anderen Dekorator generiert. Denken Sie daran, dass wir im dritten Teil alle Parser-Methoden in @memoize . Jetzt nehmen wir eine kleine Änderung im Generator vor, sodass wir für @memoize_left_rec Regeln @memoize_left_rec , und implementieren dann Magie im memoize_left_rec Dekorator. Der Rest des Generators und anderer Code müssen nicht geändert werden! (Obwohl ich mit dem Visualisierungscode basteln musste)
Als Referenz ist hier noch einmal der ursprüngliche @memoize Dekorator, der aus Teil 3 kopiert wurde. Denken Sie daran, dass self eine Parser Instanz ist, die über ein memo Attribut (initialisiert mit einem leeren Wörterbuch) und mark() und reset() -Methoden verfügt, mit denen die aktuelle Position abgerufen und festgelegt wird Tokenizer:
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
Der @memoize Dekorateur merkt sich frühere Aufrufe für jede Position im Eingabestream - für jede Position im (faulen) Array von Eingabetoken gibt es ein separates memo Wörterbuch. Die ersten vier Zeilen von memoize_wrapper dazu, das richtige memo Wörterbuch zu erhalten.
Und hier ist @memoize_left_rec . Nur der else Zweig unterscheidet sich geringfügig von der Implementierung in @memoize oben:
def memoize_left_rec(func): def memoize_left_rec_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:
Es ist wahrscheinlich interessant, wie dies für die expr() -Methode funktioniert. Mal sehen, wie der folgende Code ausgeführt wird:
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
Am Beispiel des Parsens von foo + bar + baz .
Immer wenn Sie die Funktion expr() aufrufen, wird der Aufruf vom Dekorateur "verknüpft", der an der aktuellen Position nach dem vorherigen Aufruf sucht. Beim ersten Aufruf gelangen wir zum Zweig else , wo wir wiederholt die dekorierte Funktion expr() . Natürlich werden wir zuerst wieder zum Dekorateur gelangen, aber dieses Mal befindet sich bereits ein Wert im Cache, sodass die Rekursion unterbrochen wird.
Was passiert als nächstes? Der anfängliche Cache-Wert wird in dieser Zeile berechnet:
Dies führt dazu, dass dekoriertes expr() None zurückgibt, wonach das erste if in expr() fällt (wenn expr: = self.expr() ). Das heißt, wir fahren mit dem zweiten if , das den term erfolgreich erkennt (in unserem Beispiel 'foo' ) und expr eine Instanz von Node zurückgibt. Woher kommen wir zurück? Zur while im Dekorateur. Wir aktualisieren den Memoization Cache mit einem neuen Ergebnis (dieser Instanz von Node ) und führen dann die nächste Iteration aus.
expr() wird erneut aufgerufen, und diesmal gibt der abgefangene rekursive Aufruf die zwischengespeicherte Instanz von Node (term) zurück und fährt dann mit dem zu expect('+') Aufruf fort expect('+') . Alles ist in Ordnung, da wir jetzt auf dem ersten '+' Operator sind. Danach suchen wir nach einem Begriff, der auch erfolgreich ist (gefunden 'bar' ).
Jetzt expr() , nachdem es foo + bar bereits erkannt hat, zur while , die dieselben Aktionen ausführt: Es aktualisiert den Memoization-Cache mit einem neuen (längeren) Ergebnis und startet die nächste Iteration.
Dieses Spiel wird erneut wiederholt. Wiederum ruft der abgefangene rekursive Aufruf expr() ein neues Ergebnis (diesmal foo + bar ) aus dem Cache ab, und wir erwarten ein weiteres '+' (zweites) und einen weiteren term ( 'baz' ). Wir erstellen einen Node der (foo + bar) + baz , und geben ihn an die while , die ihn in den Cache legt und erneut wiederholt.
Aber jetzt gehen wir einen anderen Zweig des Algorithmus entlang. Wir erwarten ein weiteres '+' , finden es aber nicht! Daher kehrt dieser Aufruf von expr() zu seiner zweiten Alternative zurück und gibt nur term . Wenn dies vor der while angezeigt while , stellt sich heraus, dass dieses Ergebnis kürzer als das letzte ist. Es unterbricht also und gibt ein längeres Ergebnis ( (foo + bar) + baz ) an denjenigen zurück, der den Aufruf von expr() initiiert hat (zum Beispiel wird der Aufruf von statement() hier nicht angezeigt).
Hier endet also die heutige Geschichte: Wir haben die Linksrekursion erfolgreich in einem PEG-Parser implementiert. Nächste Woche möchte ich das Hinzufügen von "Aktionen" zur Grammatik diskutieren, damit wir das von der Parser-Methode zurückgegebene Ergebnis für diese Alternative anpassen können (anstatt immer eine Node ).
Wenn Sie mit dem Code herumspielen möchten, überprüfen Sie das GitHub-Repository . (Ich habe auch einen Visualisierungscode für die linke Rekursion hinzugefügt, bin aber nicht ganz zufrieden damit, daher werde ich hier keinen Link dazu bereitstellen.)
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0