Nachdem ich im vorherigen Beitrag alle Teile des PEG-Parser-Generators zusammengestellt habe, bin ich bereit zu zeigen, wie einige andere interessante Dinge implementiert werden können.
Inhalt der Python PEG Parser-Serie Wir werden die folgenden Merkmale von PEG betrachten:
- Benannte Elemente:
NAME=item (Name kann in der Aktion verwendet werden) - Lookaheads:
&item (positiv) und !item (negativ) - Gruppieren von Elementen in Klammern: (Elementelement
item item ... ) - Optionale Artikel:
[item item ...] und item? - Doppelte Elemente:
item* (null oder mehr) und item+ (eines oder mehrere)
Benannte Argumente
Beginnen wir mit benannten Elementen. Dies ist praktisch, wenn wir mehrere davon in einer Alternative für dieselbe Regel haben, zum Beispiel:
expr: term '+' term
Wir können uns auf den zweiten term beziehen, indem wir dem Variablennamen die Nummer 1 hinzufügen, so dass es in der Aktion folgendermaßen aussieht:
expr: term '+' term { term + term1 }
Aber nicht jeder mag es, und ich persönlich würde lieber so etwas schreiben:
expr: left=term '+' right=term { left + right }
Dies wird in der Meta-Grammatik leicht unterstützt, indem die Regel für das item wie folgt geändert wird:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string }
(Wo atom nur ein alter item )
Dazu müssen wir die Definition der NamedItem Klasse zu grammar.py . Es ist eine dieser Datenklassen, die ich zuvor erwähnt habe - es hat auch die name und item .
Wir müssen auch kleine Änderungen am Codegenerator vornehmen, die ich als Übung für den Leser hinterlassen werde (oder Sie können in mein Repository schauen :-). Der generierte Code weist nun das Ergebnis der Zuordnung jedes Elements zu einer Variablen mit dem angegebenen Namen und nicht mit dem Namen zu, der aus dem Namen der Elementregel erhalten wurde. Dies funktioniert auch für Elemente, bei denen es sich um Token handelt (entweder in der Form NAME oder in Zeichenfolgenliteralen wie ':=' ).
Lookahead
Gefolgt von Lookahead. Sie sind wahrscheinlich in regulären Ausdrücken auf dieses Konzept gestoßen. Während des Forward-Lookaheads kann die analysierte Alternative sofort abgelehnt oder akzeptiert werden, ohne den Tokenizer-Zeiger zu verschieben.
Tatsächlich kann Lookahead als eleganterer Weg verwendet werden, um Verwechslungen mit den Parser-Ausnahmen zu vermeiden, über die ich in einem früheren Artikel geschrieben habe. Anstatt Aktionen zu erlauben, eine bereits akzeptierte Alternative durch Rückgabe von None abzulehnen, können wir vor dem OP eine Anweisung hinzufügen, "}" auszuschließen. Die alte Regel sah so aus:
| OP { None if op.string in ("{", "}") else op.string }
Die neue Version sieht folgendermaßen aus:
| !"}" OP { op.string }
Dadurch wird die Verarbeitung der geschweiften Klammern von der Aktion auf die Grammatik übertragen, zu der sie gehört. Wir müssen "{" nicht aktivieren, da es einer früheren Alternative entspricht (tatsächlich gilt dies auch für die alte Version, aber ich habe es vergessen :-).
Wir fügen der Regel für item wie folgt Grammatik für Lookaheads hinzu:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) }
Wir müssen die Lookahead- Lookahead zu grammar.py (und in @subheader !) Und den Generator ein wenig ändern, indem wir die Lookahead grammar.py hinzufügen:
def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive
In unserem Fall sieht der generierte Code für diese Alternative folgendermaßen aus:
if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string
Wie Sie dem obigen Grammatikfragment entnehmen können, kann Lookahead keine Eigennamen erhalten. Dies ist leicht zu beheben, aber ich habe immer noch keine Ahnung, wie nützlich es wäre. Bei negativen Prognosen ist der Wert außerdem immer None .
Gruppierung in Klammern
Lassen Sie uns nun Gruppen mit Klammern implementieren. Der beste Ort, um sie dem Metagramm hinzuzufügen, ist die Regel für atom :
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) }
Die ersten beiden Alternativen haben sich nicht geändert. Die Aktion für die neue Alternative verwendet einen Hack (dessen Implementierung ungeklärt bleibt), mit dem der Meta-Parser der Grammatik im laufenden Betrieb neue Regeln hinzufügen kann. Diese Hilfsfunktion (im Meta-Parser definiert) gibt den Namen des neuen Regelobjekts zurück. Es besteht aus einem festen Präfix gefolgt von einer Zahl, wodurch es eindeutig wird, z. B. _synthetic_rule_1 .
Sie können fragen, was passiert, wenn die synthetische Regel irgendwann fallen gelassen wird. Ich weiß nicht, wie ich das vermeiden soll, aber es sollte keine Probleme geben - im schlimmsten Fall gibt es eine nicht verwendete Regel in der Grammatik. Und dank Memoization wird dieselbe Aktion niemals zweimal für dieselbe Eingabeposition ausgeführt, sodass dies auch kein Problem darstellt (aber selbst wenn dies der Fall wäre, hätten wir im schlimmsten Fall eine tote Regel).
Wenn Sie alts in Klammern verwenden, können Sie einen vertikalen Balken als Trennzeichen innerhalb einer Gruppe definieren. Zum Beispiel, dass unsere neue Aktionslösung nicht versehentlich mit { übereinstimmt, könnten wir die Negation folgendermaßen ändern:
| !("{" | "}") OP { op.string }
Darüber hinaus können Gruppen auch Aktionen enthalten! Dies würde nicht helfen, das Problem mit den Aktionen zu lösen, aber in anderen Situationen kann es durchaus nützlich sein. Und da wir auf jeden Fall eine synthetische Regel generieren, ist keine zusätzliche Arbeit erforderlich, um sie zu implementieren (mit Ausnahme der Implementierung von synthetic_rule Regel :-).
Optionale Artikel
Wie im alten Pgen verwende ich eckige Klammern, um eine Gruppe optionaler Token anzuzeigen. Hier erweist es sich als nützlich. Beispielsweise kann eine Grammatikregel, die eine Python for Schleife beschreibt, damit angeben, dass eine Erweiterung von else kann. Und wieder können wir die Grammatik für atom wie folgt erweitern:
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }
Hier ist Maybe eine andere Datenklasse mit einem einzelnen item . Wir modifizieren den Codegenerator so, dass das Ergebnis der Synthesefunktion nicht fehlschlägt, wenn dieser Wert None . Dazu können Sie in der Implementierung or True hinzufügen. Zum Beispiel für [term] :
if (True and ((term := self.term()) or True) ): return term
Doppelte Elemente
Das Umschalten auf Wiederholung ist eine weitere nützliche PEG-Funktion (die Notation stammt aus regulären Ausdrücken und wird auch in pgen verwendet). Es gibt zwei Formen: Das Hinzufügen von * zu einem Atom bedeutet "null oder mehr Wiederholungen", während das Hinzufügen von + "eine oder mehrere Wiederholungen" bedeutet. Aus anderen Gründen musste ich die Grammatikregeln für item und atom neu schreiben und eine Zwischenregel hinzufügen, die ich molecule nannte:
item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) }
Beachten Sie, dass dies eine alternative Syntax für optionale Elemente ( atom? ) atom? . Es sind keine zusätzlichen Implementierungsbemühungen erforderlich, da dies nur eine weitere Möglichkeit ist, einen Maybe Knoten zu erstellen.
Das Umgestalten dieser Regeln war notwendig, weil ich bestimmte Situationen nicht gültig machen möchte:
- optionale Wiederholungen (da dies nur eine Wiederholung von null oder mehr ist);
- Wiederholungen (intern würde alle Übereinstimmungen erfassen, da PEG immer einen gierigen Algorithmus verwendet)
- wiederholte optionale Werte (die die Analyse unterbrechen würden, wenn das optionale Element nicht übereinstimmt).
Dies ist jedoch immer noch keine ideale Lösung, da Sie so etwas wie (foo?)* Schreiben können. Es wird notwendig sein, diese Situation im Parser-Generator zu überprüfen, aber ich werde dies außerhalb des Artikels tun.
Die Loop Datenklasse hat zwei Attribute: item und nonempty . Der generierte Code verwendet die Helfer-Parser-Methode loop() . Es ist der zuvor gezeigten Methode lookahead() sehr ähnlich:
def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None
Wenn nonempty False (in dem Sinne, dass die Grammatik * ), führt dies nicht zu einem Fehler. Es werden keine Einträge gefunden und eine leere Liste wird zurückgegeben. Um dies zu erreichen, implementieren wir den Parser-Generator so, dass is not None hinzugefügt wird. Eine weichere Prüfung aus einem vorherigen Beitrag würde bei einer leeren Liste False .
Das ist alles für heute! Ich wollte über den in TatSu vorhandenen Operator "cut" ( ~ ) sprechen, hatte aber bisher keine Gelegenheit, ihm zu begegnen. Ich bin noch nicht einmal bereit, darüber zu diskutieren - die TatSu-Dokumentation gibt nur ein einfaches Beispiel, das mich ein wenig interessiert. Ich habe es in anderen Generatoren von PEG-Parsern nicht gefunden, daher ist diese Funktion möglicherweise nur TatSu. Vielleicht erzähle ich eines Tages von ihm. (In der Zwischenzeit habe ich es nur für den Fall implementiert, dass man es nie weiß. :-)
Ich denke, der nächste Artikel befasst sich mit meiner Erfahrung beim Schreiben einer PEG-Grammatik, die Python-Grammatik analysieren kann. Ich werde Ihnen erzählen, wie der Sprint der Python-Kernel-Entwickler stattgefunden hat, der diese Woche in London mit logistischer Unterstützung von Bloomberg und finanzieller Unterstützung von PSF und einigen anderen Unternehmen stattfand (zum Beispiel hat Dropbox mir das Hotel und den Flug bezahlt). Besonderer Dank geht an Emily Morhouse und Pablo Galindo Salgado, die bei der Implementierung der Tools und Tests sehr geholfen haben. Als Nächstes schreiben wir Leistungstests und fügen dieser Grammatik Aktionen hinzu, damit AST-Bäume erstellt werden können, die vom CPython-Bytecode-Compiler kompiliert werden können. Es liegen noch so viel interessantere Dinge vor uns!
Lizenz für diesen Artikel und zitierten Code: CC BY-NC-SA 4.0