In diesem Abschnitt konzentrieren wir uns auf die allgemeine parsergesteuerte Generierung und beginnen mit einer einfachen Anleitung für eine Python-ähnliche Grammatik, die als CFG bereitgestellt wird.
Stellen Sie sich ein Vokabular vor, das aus Zeichenfolgen wie „d“ und „ef“ besteht, die gemäß einer impliziten CFG kombiniert werden können, um eine Python-ähnliche Syntax zu erzeugen, und nehmen Sie an, dass diese Zeichenfolgen gemäß einem Prozess wie Algorithmus 1 sequenziell abgetastet und verkettet werden.
Betrachten wir außerdem ein Terminalsymbol DEF in der CFG, das der Zeichenfolge „def“ entspricht und durch den trivialen regulären Ausdruck def gegeben ist. Betrachten wir außerdem ein NAME-Symbol, das durch den regulären Ausdruck [^\W\d]\w* gegeben ist (z. B. Python-Bezeichner). Wir möchten Zeichenfolgen, die aus dem oben genannten Vokabular entnommen wurden, sequenziell auf eine Weise analysieren, die der Python-Syntax entspricht.
Beispielsweise könnte die folgende Sequenz eine solche sein: ["d", "ef", " f", "oo(", "):", " ", "pass"]. Alle Elemente der Sequenz sind per Definition Elemente des Vokabulars. Die Verkettung der Sequenz ergibt "def foo(): pass", eine gültige Sequenz von Token, die eine Funktion definieren. In der Situation, die wir betrachten, haben wir alle Token bis zu einem bestimmten Punkt beobachtet und wissen nichts über die Token danach.
Beispielsweise haben wir bei der dritten Beobachtung in der Beispielsequenz die zusammengesetzte Zeichenfolge „def f“. Wenn wir diese Zeichenfolge lexikalisch analysieren/parsen würden, würde ein herkömmlicher Ansatz die Symbolsequenz DEF NAME zurückgeben, die das „f“ fälschlicherweise als vollständiges NAME-Token identifiziert. Wie wir aus dem Rest der Sequenz ersehen können, ist das korrekte NAME-Token „foo“.
Im Allgemeinen sind die nächsten gültigen Zeichenfolgen, die aus dem Vokabular ausgewählt werden können, solche, die entweder
den NAME weiter ausbauen/erweitern, der derzeit mit "f" beginnt (wie es die vollständige Sequenz in unserem Beispiel tut), und/oder
alles, was mit "(" beginnt – also ein LPAR-Symbol mit regulärem Ausdruck (– und anschließend eine gültige Argumentsignatur angibt.
Im ersten Fall kann das „f“ als teilweise übereinstimmendes NAME-Symbol in Python betrachtet werden, und – wenn wir uns daran erinnern, dass sein regulärer Ausdruck [^\W\d]\w* ist – können wir sagen, dass es mit beiden Untermustern (also [^\W\d] und \w*) im regulären Ausdruck übereinstimmt. Unsere Verwendung von FSMs formalisiert den Begriff der Untermuster durch die Zustände eines FSMs. In diesem Fall kann der reguläre Ausdruck für NAME durch ein FSM, M, mit drei Zuständen dargestellt werden: 0 (also der Anfangszustand q0), 1 (also [^\W\d]) und 2 (also \w*), wobei 1, 2 ∈ F.
Mit Algorithmus 3 würden wir die FSM-Zustandssequenzen (0, 1), (1, 2), (2, 2) für „f“ und die FSM M erhalten, die dem NAME-Symbol entspricht. Diese FSM-Sequenzen für „f“ sagen uns, dass die Übereinstimmung für diese Vokabelzeichenfolge in den Zuständen 0, 1 oder 2 beginnen und in den Zuständen 1 oder 2 enden kann.
Gemäß Fall 1 oben kann die Analyse – für das NAME-Symbol – fortgesetzt werden, nachdem sie zuvor in den Zuständen 1 oder 2 beendet wurde. Gemäß Fall 2 könnte die nächste Zeichenfolge auch mit einem LPAR beginnen oder ein solches enthalten, was bedeuten würde, dass M beendet worden wäre, was möglich ist, da 1 und 2 Endzustände in M sind, bei denen die Analyse nach dem Lesen von „f“ beendet worden wäre. Das Beenden von M zeigt auch an, dass ein NAME-Symbol abgeschlossen wurde und dass die Grammatik einen Übergang in einen Zustand, der LPAR akzeptiert, zugelassen hat.
In dieser Abbildung sind die nächsten gültigen Vokabularzeichenfolgen mindestens „d“, „ef“, „pass“, „ “, „oo(“, da alle diese Zeichenfolgen den teilweise übereinstimmenden NAMEN erweitern würden und die letzte auch den Analysestatus zu einem Status fortführen würde, der ein LPAR liest. Die verbleibende Zeichenfolge „):“ aus der Teilmenge des Vokabulars, die wir betrachtet haben, würde zu einer Sequenz mit ungültiger Syntax führen.
In Bezug auf den FSM-Indizierungsansatz bedeutet dies, dass Algorithmus 4 die FSM-Zustände 0, 1 und 2 auf die Teilmenge „d“, „ef“, „pass“, „ “, „oo(“ für das Symbol NAME und sein FSM M abbilden würde.
In dieser Abbildung werden die zugrunde liegenden Parserzustände weggelassen, die bestimmen, welche Grammatiksymbole und Übergänge zulässig sind. Wir verwenden Kellerautomaten (PDA), um den FSM-Ansatz zu erweitern und die verbleibenden Details zu behandeln.
4.1 Kellerautomaten-Formulierung
Wir definieren Kellerautomaten mit Hilfe der folgenden 6-Tupel-Darstellung [Sipser, 1996, Definition 2.13]:
Um einen Indizierungsansatz für einen PDA-gesteuerten Parser zu erstellen, müssen wir die Verbindung zwischen den Symbolen einer CFG – über das entsprechende Alphabet eines PDA – und den Lexarierungs- und Scanschritten nutzen, die die von einem PDA gelesenen Symbole erzeugen.
Genauer gesagt werden Parser von Lexern und Scannern unterstützt, die Symbole aus einer Folge von Zeicheneingaben identifizieren, wie wir implizit in Abschnitt 4 dargestellt haben. Für jeden Parse-/PDA-Zustand können geordnete Listen von Terminalsymbolen erstellt werden, basierend auf den Symbol- und Stapelübergängen, die die Abbildung δ in jedem Zustand zulässt. Das bedeutet, dass wir für jeden Parse-Zustand eine FSM erstellen können, die die Vereinigung aller FSMs ist, die einem vom Zustand gelesenen Terminalsymbol entsprechen.
Ein Scan-Schritt identifiziert dann eine Menge möglicher Terminalsymbole V ⊂ Σ für die Zeichen, die seit dem letzten vollständig identifizierten Symbol im Analyseprozess gelesen wurden. Beispielsweise ergibt im Anfangszustand q0 eines PDA für die Python-ähnliche CFG in Abschnitt 4 das Scannen und Lexikonisieren der Zeichenfolge „de“ V = {DEF, NAME}: d. h. DEF für jede Vokabelzeichenfolge, die die Zeichenfolge „def“ vervollständigt – gefolgt von einer Zeichenfolge, die nicht auch vom NAME-FSM gelesen wird (z. B. „def“) – und NAME für alle anderen Zeichenfolgen, die von seinem FSM gelesen werden (z. B. „default“). Beachten Sie, dass die Schritte des Scanners – und die Sampling-Schritte des LLM – die Menge V schließlich reduzieren, bis ein einzelnes Terminalsymbol v ∈ V bestimmt ist.
Indem wir Algorithmus 3 auf jede Zeichenfolge in V anwenden und dabei die kombinierten FSMs für jeden Analysezustand verwenden, können wir Parserkonfigurationen bestimmen, die aus den PDA-Zuständen, den entsprechenden FSM-Zuständen und den potenziellen Terminalsymbolen bestehen.
In Analogie zu den Schritten in Algorithmus 3 können wir das Urbild der Übergangskarte des PDA verwenden, um PDA-Stapelwerte zu bestimmen, die die PDA-Zustände q ∈ Q und Terminalsymbolsätze V einer Parserkonfiguration lesen:
Die von dieser Karte bereitgestellten Stapelwerte werden benötigt, um Pfade – sofern vorhanden – durch den PDA zu finden, die erfolgreiche, vollständige Analysen jeder Zeichenfolge in V ausgehend von ihren möglichen Parserkonfigurationen ermöglichen. Für Parserzustands- und Terminalkombinationen, die REDUCE-Operationen eines LALR(1)-Parsers entsprechen, bestehen diese Parserkonfigurationen aus mehr als nur den Top-of-Stack-Werten in Γ; sie bestehen aus Unterstapeln, die allen gültigen Präfixen für die REDUCE-Operationen entsprechen, die eine Vokabelzeichenfolge mit sich bringt. Letztendlich wird jede Parserkonfiguration, die eine vollständige Analyse einer Vokabelzeichenfolge ermöglicht, als Eintrag im Index für den PDA hinzugefügt, und in diesem Fall muss der Index eine Trie-Datenstruktur sein, um Abfragen der Stapelwerte des Parsers zu ermöglichen.
Dieses Dokument ist .
L O A D I N G . . . comments & more!
About Author
Writings, Papers and Blogs on Text Models@textmodels
We publish the best academic papers on rule-based techniques, LLMs, & the generation of text that resembles human text.
