date-created: 2024-05-14 12:21:37 date-modified: 2024-05-19 12:24:50

Parser | und das als DFA!

anchored to 112.00_anchor_overview

Overview

We would like to evaluate and understand how code can be highlighted given the a certain language, how its possible to parse a string denoting a command with flags etc to actually execute it correctly.

For that we are going to explore the world of parsers.

Parser:

Parser sind Programme, die einen String in eine Datenstruktur umwandeln können.

Dabei sind sie der erste Schritt vom Computerprogramm, wie wir sie so schon kennen, hin zum ausführbaren Programm. Umgesetzt wird das durch die Produktion eines Ableitungsbaum der Eingabe, durch einen Compiler / Interpreter –> wir wollen also verschiedene Beispiele der Grammatik anwenden, um so zu schauen, wie sie translatieren werden kann.

Motivation |

Wir wollen konzeptuell einen Parser bauen, welcher aufgrund von Regeln einer Grammatik eine Sprache erkennen bzw einen Inhalt eines Strings auf die Sprache prüft. Anders beschrieben also: -> Ein parser rekonstruiert die Ableitung eines Strings in einer kontextfreien Grammatik aus dem String selbst. Das kann man auch als einen Graphen für den String verstehen.

[!Tip] Eindeutigkeit der Ableitung Dabei kann hier schon erkannt werden, dass diese Ableitung des Strings nicht zwingend eindeutig sein muss / kann. Es können also lokale Matching gemacht werden, die eindeutig erscheinen, aber unter größerem Kontext dann vielleicht nicht richtig oder nicht eindeutig sind. –> etwa wenn unsere Grammatik sagt, dass sie “aaabb” sieht und daraus dann entweder:

• aa, abb oder
• aaa,bb erkennt. Wir müssten dann schauen, wir wir hiermit eine eindeutigkeit schaffen, weil diese Erkennung ja zuerst lokal passiert und wir den globalen Kontext noch nicht kennen können

Das ganze kann man jetzt noch an einem Beispiel festmachen, bzw zeigen.

naives parsing einer Sprache

Wir möchten einen naiven und simplen Ansatz zum parsen einer Grammatik bzw zum parsen eines Strings zum Prüfen, ob er von der Grammatik abgedeckt wird, betrachten. Betrachten wir hierbei eine CFG - Grammatik ( context free). $$\begin{array}{rl}S& \to aBC\\ B& \to c\mid cd\\ C& \to df\mid eg\end{array}$$ und ferner betrachten wir das Wort $acdf$. Ein Ansatz:

Wir könnten naiv einfach alle Regeln ausprobieren und schauen, ob unsere Sprache das Wort erkennen kann. Dabei nehmen wir die Regeln, die nicht passen auch nicht auf.

Am Beispiel schaut man sich jetzt einfach alle möglichen Umsetzung dieses Strings in der Grammatik an:

• $S\to aBC$ ist möglich, da das Wort mit a anfängt! (wir haben noch cdf übrig)
• danach folgt ein $c$, also $S\to aBC\to acC|acfC|aBdf|\underline{aBeg}$ ( der erste Schritt wird dabei nochmal aufgezählt, weil er für die Verarbeitung relevant ist, um zu zeigen, wie es geparsed werden könnte.) Die markierte Struktur wird die sein, die unser Wort repräsentiert!
  • Diese Erkenntnis haben wir jetzt durch einfaches Probieren der Kombinationen erhalten.
• ferner kommt jetzt also das d als nächster Buchstabe und auch hier führen wir wieder Schritt für Schritt alle Kombinationen durch, um zu schauen, wie / ob wir das Wort parsen können
• $S\to aBC\to (acC\to \underline{acdf})|(acdC\to acddf)|(aBdf\to \underline{acdf}\mid acddf)$ Wir haben in dieser Verarbeitung jetzt 2 mögliche Varianten gefunden und es parsen können!

Damit haben wir entsprechend evaluiert, indem wir alle Regeln durchlaufen sind.

Das Prinzip nennt sich folgend:

Top-Down-Parsing

[!Definition] Top-Down-Parsing

was beschreibt das Prinzip von Top-Down-Parsing ? #card

der obige Verlauf, also das durchprobieren von allen Regeln einer Grammatik um eine Eingabe labeln bzw. erkennen zu können, wird als Top-Down-Parsing beschrieben. Dabei gehen wir also einfach alle Kombinationen durch, indem wir das Wort Schritt für Schritt betrachten und schauen, zu welcher Regel es passen oder angewandt werden könnte.

[!Tip] LL-Parsing Ferner ist der Ansatz, dass man nach und nach die Linksproduktion des Inputs durcharbeitet, dann als LL-Parsing bekannt / bezeichnet

Problem: Top-Down-Parsing wird eine exponentielle Laufzeit aufweisen Desto mehr Regeln wir haben, desto mehr müssen wir für jedes Wort probieren, was uns viel Zeit und Rechenleistung kosten kann. Ferner ist es auch polynomiell möglich, wie folgende Quelle belegen kann: link

Dennoch ist die Struktur sehr langsam!, Es brauch was besseres

[!Attention] Spoiler zum Erkennen von Grammatiken Wir werden baldig herausfinden, dass es Parser gibt, die eine Parsing-Strategie in deterministischer Struktur für Gramatiken in einer linearer Zeit konstruieren bzw. erkennen können.

Determinismus bei PDAs 112.09_kellerautomaten

Wir möchten einen deterministischen Kellerautomaten einführen - Push-Down Automata - da wir bis jetzt nur nicht-deterministische betrachtet haben ( und hierbei meinten, dass deterministische PDAs sinnfrei sind).

[!Lemma] Idee für Deterministische PDAs

was setzen wir voraus für einen deterministischen PDA? Was ist im Gegensatz zu FAs erlaubt, mit welcher Bedingung? #card

Wir nennen einen PDA bei welchem die Übergangsfunktion $\delta$ deterministisch ist, demnach also für jedes Tripel $(q,a,x)$ genau ein Folgezustand definiert und auch ein spezifisches Kellersymbol definiert ist. –> Also jede Kombination von Zustand, Eingabe und Stack-Speicher ist deterministisch definiert.

Man sieht hier schon, dass das schwieriger ist, als bei einem finite-automata, weil man jetzt den Inhalt des Stacks, sowie den aktuellen Zustand beachten muss.

Damit ist es etwa möglich, dass man ein Wort liest, aber nichts in den Stack schreibt. Also heißt das, dass hier auch $\epsilon$-Übergänge erlaubt sind! Dabei dürfen sie aber nur einmal im Tripel auftreten.

Wir können diese Idee jetzt folgend formalisieren:

[!Definition] deterministischer Kellerautomat Ein deterministischer Kellerautomat wird durch ein 6-Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ beschrieben, wobei die einzelnen Elemente folgende Eigenschaften aufweisen müssen:

was muss hier spezifisch für die Übergangsfunktion gelten? #card

• $Q$ beschreibt die endliche Menge von Zuständen
• $\Sigma$ ist das Eingabealphabet
• $\Gamma$ beschreibt das Stack-Alphabet
• $F\subseteq Q$ beschreibt die Menge von akzeptierenden Zuständen
• $q_0\in Q$ beschreibt den Startzustand
• $\delta :Q\times {\Sigma }_{\epsilon }\times {\Gamma }_{\epsilon }\cup \{\varnothing \}$ beschreibt jetzt die Übergangsfunktion, wobei $\varnothing$ angibt,m dass ein Übergang nicht erlaubt ist. Bei dieser Übergangsfunktion muss jetzt gelten:

$\forall (q,a,x)\in Q\times \Sigma \times \Gamma$ ist genau einer der unteren Übergänge definiert (also er darf nicht leer sein). Das gibt demnach folgende Kombinationen an: $$\delta (q,a,x),\delta (q\epsilon ,x),\delta (q,a,\epsilon ),\delta (q,\epsilon ,\epsilon )$$

[!Attention] Übergänge müssen immer genau einmal definiert sein

wan akzeptiert ein DPDA ein Wort, wenn er es eingelesen hat, wann nicht und warum? #card

Ferner gilt dadurch jetzt, dass ein DPDA ein Wort akzeptiert, wenn er nach dem Lesen des Wortes in einem akzeptierenden Zustand landet. In allen anderen Fällen wird er das Wort ablehnen -> Folgende Fälle wären das:

• nach Lesen des Wortes sind wir nicht $\in F$
• es wird pop auf einen leeren Stack durchgeführt
• es kommen endlose $\delta (.,\epsilon ,\epsilon )$ Übergänge auf, sodass wir also nicht mehr beenden.

Deterministisch Kontextfreie Sprachen

Wir haben mit der obigen Definition eines deterministischen Kellerautomaten nun eine Möglichkeit beschrieben, um bestimmte Sprachen verstehen zu können.

[!Satz] deterministisch kontextfreie Sprachen

wann nennen wir eine Sprache deterministisch kontextfrei? #card

Wir möchten eine Sprache $L$ deterministisch kontextfrei beschreiben, wenn es für sie einen DPDA gibt, der diese Sprache $L$ akzeptieren kann.

Es muss also möglich sein unter Konstruktion eines deterministischen Kellerautomaten die Sprache darstellen und erkennen zu können!

Beispiel

Betrachten wir folgende kontextfreie Sprache $L=\{0^n{1}^n\mid n\ge 0\}$ wie können wir dafür jetzt etwa einen DPDA konstruieren, der diese Sprache erkennen kann? #card Wir können tabellarisch alle möglichen Zustände unseres Automaten formulieren. Wir wissen grundsätzlich, dass wir hier mit dem Stack zählen wollen, wie viele Nullen auftreten, bevor wir dann anschließend diese Menge beim Zählen der Einsen danach wieder nach und nach minimieren. Wenn man Ende alles leer ist, dann haben wir entsprechend ein passendes Wort gefunden. Grafisch sieht der Automat etwa folgend aus:

und dieser wurde aus folgender Tabelle entworfen:

[!Important] undefined-Zustand beim DPDA

was ist bei dem undefined-Zustand des DPDA zu beachten, sofern man ihn verwendet? #card

Wichtig ist hier, dass der neue undefined Zustand explizit genannt werden muss, (wenn er genutzt wird) weil man sonst nicht weiß, was bei Zuständen passiert, die normal nicht auftreten würden.

-> es brauch also den Eintrag, weil man somit explizit beschreibt, wie man aus diesem Zustand herauskommen kann / bzw in diesen hineinkommt.

Das ganze kann man graphisch so erweitern, wenn man das vorherige Beispiel betrachtet:

Es kann vorkommen, dass manche Übergänge, die nicht definiert sind ( beim PDA), bei nicht Nennung des undefined Zustandes einfach nicht erreicht werden dürfen!

[!Tip] Folgerung von deterministischen PDAs Wir können also deterministische Kellerautomaten bauen die Kontext-freie Grammatiken erkönnen könnten. Dabei gilt das aber nicht für alle Grammatiken!

Verallgemeinerung eines DPDAs

Man kann jetzt eine explizite Erweiterung des DPDA betrachten, welcher uns die Arbeit mit diesem vereinfachen kann:

[!Satz] Jeder DPDA hat einen Äquivalent, dass erst nach Eingabe akzeptiert/ablehnt.

Es gilt jetzt: Jeder DPDA hat einen äquivalenten DPDA, der immer den kompletten Input liest, bevor er akzeptiert oder ablehnt.

wie könnten wir das beweisen bzw. einen entsprechenden DPDA konstruieren, der das erfüllt? Warum ist diese Erweiterung sinnvoll? #card

Grundsätzlich ist es wichtig diese Verallgemeinerung vorzunehmen, um so eventuelles aufhängen eines Automaten verhindern zu können. Dieses Aufhängen kann aus zwei Gründen auftauchen:

1. pop wird auf einem leeren Stack angewandt. Dadurch sollte sich der Zustand des Tripel eigentlich ändern, aber wir landen im gleichen Zustand, wie zuvor!

• Verhindern kann man das, indem der Kellerboden (Stack-Anfang) mit einem # markiert wird, wobei dann jeder Zustand, der pop anwendet beim vorliegenden Symbol # entsprechend ablehnen wird bzw. in eine reject-Sackgasse übergeht. Hier liest man dann die Eingabe dennoch bis zum Ende

2. Es treten endlose $\delta (.,\epsilon ,\epsilon )$-Übergänge auf. Das heißt wir haben keine explizite Eingabe vom Stack oder der Eingabe und wiederholen uns somit wieder unendlich

• Verhindern können wir das durch lokales Erkennen dieser Loops, welche wir anschließend auch in eine zuvor beschriebene reject-Sackgasse leiten.

Bei Beiden Fällen muss man aufpassen, dass diese Situationen nicht am Ende auftreten, bzw. muss man diese Situation etwas vorsichtiger betrachten: Der Eingang zu dieser Sackgasse kann so eventuell auch akzeptierend sein, wenn unser Übergang dahin am Ende einer Eingabe tatsächlich akzeptierend sein soll - aber das Pattern einer Schleife, die wir verbieten, hat.

Komplementbildung von DCFLs

Nachdem wir nun kontextfreie deterministische Sprachen bewiesenermaßen mit einem DPDA Automaten Darstellen können, möchten wir noch die Abgeschlossenheit dieser prüfen.

Wir betrachten hier die Komplementbildung:

[!Satz] Klasse von DCFLs ist abgeschlossen unter Komplementbildung

wie können wir das beweisen? was muss man spezifisch beachten? #card

Wir können das jetzt relativ einfach zeigen, wenn wir einen DPDA konstruieren können, der die Sprache erkennt. Ähnlich, wie bei den det. endlichen Automaten können wir hier einfach die Menge von akzeptierenden Zuständen als $Q\setminus \{F\}$ beschreiben, also wieder das Komplement der Zustände als akzeptierend setzen.

Haben wir also einen DPDA $M$, dann konstruieren wir $\overline{M}$ mit $L(\overline{M})$, wobei wir die nicht-akzeptierenden mit den akzeptierenden Zuständen vertauschen!

Problem: Wenn der Automat $M$ jetzt eine Eingabe akzeptiert, indem er nach Lesen der Eingabe eine Folge von $\delta (.,\epsilon ,.)$ Übergängen aufweist, würde das invertieren der akzeptierenden Zustände dazu führen, dass diese Wörter immernoch erkannt werden und wir somit nicht ganz das Komplement erhalten haben.

Lösung dazu schafft die Konstruktion der verallgemeinerung, indem also der neue Automat $M^{\prime }$ immer den kompletten Input liest, bevor er entscheidet. Dann ist unsere Konstruktion für $M^{\prime }$ richtig!

Es lässt sich hieraus noch ein Korollar definieren:

[!Korollar] CFLs können nicht DCFLs sein Es gibt also Context-Free-Languages die keine deterministisch-Context-Free-Languages sind.

wie könnten wir das beweisen? #card

Wie soeben bereits betrachtet können wir einsehen, dass es Kontextfreie Sprachen gibt, deren Komplement nicht kontextfrei ist. Eine solche Sprache wäre etwa: $L=\{a^j{b}^k{c}^l\mid j=k\vee k=l\}$ -> Sie ist kontextfrei aber nicht deterministisch kontextfrei.

Ferner können wir noch über die Abgeschlossenheit der Sprache(n-Gruppe) sagen:

[!Attention] DCFLs Abgeschlossenheit

DCFls sind nicht abgeschlossen unter :: Vereinigung, Schnitt, Konkatenation, der Hüllenbildung und der Umkehr

Beispiel

Wir können ferner eine Sprache betrachten, die nicht deterministisch kontextfrei ist, aber sie dennoch von einer context-freien Grammatik beschrieben werden kann - dafür aber einen NPDA benötigt! $$L=\{w{w}^R\mid w\in \{0,q{\}}^{\ast }\}$$ Es wird hier also die Sprache von einem Wort, das gespiegelt an sich gehangen wird, beschrieben. Die Konstruktion des NPDA könnte hierbei die Sprache akzeptieren, da man sie von folgender Grammatik erzeugen kann: $$\begin{array}{r}S\to 0S0\mid 1S1\mid \epsilon \end{array}$$

Takeaways von DPDAs

Aus den obigen Betrachtungen können wir einige Resultate, Zusammenfassungen ziehen:

[!Tip] Aspekte von deterministischen Kellerautomaten Deterministische Kellerautomaten sind die Art von Automaten, die tatsächlich umgesetzt werden können ( da hier kein nicht-det vorausgesetzt wird)

• Sprachen von DPDAs erkannt sind deterministische kontextfreie Sprachen
• Sie sind unter Komplementbildung abgeschlossen, jedoch nicht unter Vereinigung, Schnitt, Konkatenation, Hüllenbildung und Umkehr
• Grammatiken, die ein DCFL erzeugen kann, haben die Form, dass sie eine eindeutige Reduktion einer Eingabe bzw eines Wortes aufweisen.

Um die Reduktion besser beschreiben zu können, möchten wir sie uns nochmal anschauen.

[!Definition] Reduktion

Grundlegend ist eine Reduktion hierbei erstmal das Inverse einer Produktion

wie können wir diese jetzt im Kontext von zwei Strings aus Variablen und Terminalen, $v,u$ beschreiben? Was meinen wir mit “reduziert zu “ #card

Wir sagen, dass $u$ zu $v$ reduziert wird, und beschreiben diesen Vorgang mit $u\rightarrowtail v$ , wenn gilt, dass $v$ direkt zu $u$ übergeht, also $v⟹u$

Wir sagen, dass $u$ reduziert zu $v$, beschrieben mit $u{\rightarrowtail }^{\ast }v$, falls es eine Folge von Reduktionen gibt: $$u=u_1\rightarrowtail u_2\rightarrowtail \cdots \rightarrowtail u_k=v$$ Also wir können hier auf irgendeinen Pfad von Reduktionen zu unserem Wort kommen. (Es ist ähnlich zu der Produktion, wo wir durch einen Anfang und den Regeln nach und nach ein Wort produzieren können; hier verspeisen wir das Wort entlang der Regeln)

Wir nennen eine Reduktion von $u$ unter einer Grammatik $G$ jetzt, wenn es eine Reduktion von $u{\rightarrowtail }^{\ast }S$ gibt, wobei $S$ die Startvariable beschreibt (Der Gramamtik).

Auch hier kann man wieder eine Linksreduktion betrachten #card

Es handelt sich um eine Reduktion der jeder reduzierte String erst dann reduziert wird, wenn alle Strings zu seiner linken bereits reduziert sind - es ist also die Rechtsproduktion aber rückwärts betrachtet!

[!Attention] Nutzen der Reduktion Mit der Regeln der Reduktion, bzw der Konstruktion dieser, beschreiben wir die Arbeitsschritte einer PDA. Wenn man also eine Eingabe unter Betrachtung der Übergänge passend zum Startpunkt $S$ reduzieren kann, dann hat man etwas gefunden, was der PDA akzeptieren kann.

Handles | Determinismus in Reduktionen schaffen

Um jetzt immer eine Eindeutigkeit beschreiben zu können, möchten wir Handles einführen, die uns dabei helfen bestimmte Umformungen zu markieren.

[!Definition] Handles Sei jetzt $w$ ein String aus Terminalen und Variablen bestehend, welcher von einer kontextfreien Grammatik $G$ erzeugt wird.

wie konstruieren wir jetzt Handles, was muss für die Konstruktion herrschen/ was resultieren sie dann? #card

Ferner sei noch $u_i$ ein Teilwort des Wortes $w$, dass in einer Linksreduktion von $w$ in folgender Form $w{\rightarrowtail }^{\ast }{u}_i$ mit $u_i{\rightarrowtail }^{\ast }{u}_{i+1}{\rightarrowtail }^{\ast }S$ vorliegt. Es ist also ein Teil innerhalb des Wortes, welcher notwendig ist, um es richtig zu reduzieren. Hierbei muss dieses Teilwort $u_i$ von einer Regel $T\to h$ erzeugt werden, also es wird durch diese Regel verursacht.

Wir nennen jetzt $u_i$ einen validen String

Ferner gibt es jetzt eine Zerlegung dieses Strings von seinem zum nächsten $u_{i+1}$ beschrieben mit: $$u_i=\stackrel{x}{\overbrace{x_1\dots x_j}}\stackrel{h}{\overbrace{h_1\dots h_k}}\stackrel{y}{\overbrace{y_1\dots y_l}}\rightarrowtail \stackrel{x}{\overbrace{x_1\dots x_j}}\stackrel{T}{\overbrace{T}}\stackrel{y}{\overbrace{y_1\dots y_l}}=u_{i+1}$$ Dabei nennen wir hier $h$ zusammen mit der Regel $T\to h$ einen Handle von $u_i$

Diese Konstruktion funktioniert weil:

• In einer Linksreduktion das Suffix $y$ immer aus Terminalen besteht - Variablen müssten von der vorhergehenden Reduktion zur rechten von $h$ stammten was nicht erlaubt ist.
• Ein valider String kann potentiell mehrere Handles haben. Wenn das so ist dann ist die Grammatik nicht eindeutig

Diese fehlende Eindeutigkeit müssen wir verhindern, denn dadurch verlieren wir die Möglichkeit einfach und schnell parsen zu können!

Beispiel | Handles

Betrachten wir ferner ein Beispiel, was Handles in einer Grammatik verwendet:

[!Example] Betrachten wir folgende Grammatik: $G_1$ $$\begin{array}{r}>R\to S\mid T\\ >S\to aSb\mid ab\\ >T\to aTbb\mid abb>\end{array}$$ Sie weißt die Sprache $B\cup C=B=\{a^n{b}^n\mid n\ge 1\},C=\{a^n{b}^{2n}\mid n\ge q\}$ auf. Betrachten wir jetzt exemplarisch ein paar Wörter und ihre Reduktion: aaabbb kann man zerlegen in: $aa\underbrace{ab}hbb\rightarrowtail a\underbrace{aSb}b\rightarrowtail \underbrace{aSb}\rightarrowtail S\rightarrowtail R$ aaabbbbbb kann man zerlegen in: $aa\underbrace{abb}h\rightarrowtail a\underbrace{aTbb}bb\rightarrowtail \underbrace{aTbb}\rightarrowtail T\rightarrowtail R$ Beide Reduktionen konnte man umsetzen, aber zu Beginn steht links immer der gleiche String. –> Die Handles sind unterschiedlich, obwohl sie gleich aussehen (ohne Kontext!)

Das heißt ferner, dass ein NPDA diese Ersetzungen durchführen kann, weil dann der Ausführungsbaum alles probiert, aber ein deterministischer Automat müsste erst entscheiden, welche Ersetzung er tätigt. Man könnte ihn somit falsch lesen lassen: $aa\underbrace{abb}b\rightarrowtail a\underbrace{aTbb}b\rightarrowtail aTb\rightarrowtail ?$ so haben wir ihn, obwohl das Wort passen sollte, so falsch aufsplitten lassen, dass das Wort nicht erkannt wird!

Wir sehen hier, dass bei einem deterministischen DPDA Wörter falsch reduziert bzw nicht reduziert werden könne, wenn Terme auf der Linken Seite teils gleich aussehen und somit mehrere Regeln diese Struktur verarbeiten könnten ( sie sehen also nicht ganz eindeutig aus und somit kann unser DPDA sie falsch reduzieren).

Wie können wir dieses Problem nun beheben? #card Es lässt sich hier im Beispiel damit lösen, dass man ein Präfix einbringt, was eindeutig festlegt, wie bzw. welcher Form das Wort folgen wird, damit diese Uneindeutigkeit verloren geht. $R\to 1S\mid 2T$ wird quasi der neue Start und somit wird direkt am Anfang gesagt, wie reduziert wird. betrachtet man die falschen Wörter von oben folgt: $1aaabbb,2aaabbbbbb$ sind nicht mehr gleich, weil sie jetzt eindeutig bestimmt sind am Anfang!

Diese Idee können wir jetzt formalisieren:

Forced handle

[!Definition] Forced Handles Wir beschreiben einen Handle $h$ eines validen Strings $v=xhy$ als erzwungen (forced), wenn gilt:

was muss gelten? #card

$h$ ist der einzige Handle in allen Validen Strings der Form $v^{\prime }=xh{y}^{\prime }$ -> Also es ist eindeutig bestimmt, weil es in jeder Variation eines Strings, der rechts davon ist, dennoch eindeutig ist. (der Linke Term vom Handle ist egal, weil der schon bearbeitet wurde)

Damit können wir jetzt also formalisiert sagen, wann eine Grammatik als deterministisch kontextfreie Grammatik beschrieben werden kann.

DCFGs

[!Definition] Deterministisch Kontextfreie Grammatik für forced handles. Eine deterministische kontextfreie Grammatik ist eine kontextfreie Grammatik in der jeder valide String einen Forced handle hat.

wie kann man also herausfinden, wob eine CFG $G$ deterministisch ist oder nicht? Was brauch es dazu? #card

Für jede CFG $G$ existiert ein \\DFA// $DK$ welcher die Handles erkennen kann. Dabei akzeptiert dieser Automat $DK$ nur dann ein Wort $z$ wenn:

1. $Z$ ist ein Präfix eines validen Strings $v=zy$ und
2. $z$ endet mit einem Handle $h$ von $v$ und das so, dass der akzeptierende Zustand von $DK$ auf $z$ die Handles ( also die möglichen Handles) erkennen kann / identifiziert.

Demnach folgt für uns jetzt:

Ein DFA $DK$ kann die Handles einer CFG erkennen.

Eine CFG ist ferner genau dann deterministisch, wenn jeder akzeptierend Zustand unseres Automaten $DK$ dann genau einem Handle entspricht. Dabei ist auch wichtig, dass jeder akzeptierende Zustand keinen ausgehenden Pfad zu einem anderen akzeptierenden Zustand hat (haben darf). -> Die Handles sind also forced

Konstruktion eines CFG-erkennenden DFA

Wir wollen nun also den zuvor benannten DFA bauen, der die Handles einer CFG erkennen kann und somit entscheidet, ob eine CFG DFCG ist oder nicht!

Wir wollen zuerst einen nicht-deterministischen Automaten bauen, da es die Betrachtung einfacher macht!

[!Lemma] Konstruktion der DK-Tests

Sei jetzt $G$ eine CFG. Dann bauen wir jetzt einen NFA (nicht det, weil es einfacher zu Konstruieren ist, wir können ihn ja später zu einem DFA umwandeln) $J$ welcher alle Eingaben von der Form $z=xu$ akzeptiert, wobei $u$ das Suffix beschreibt, für dass es in der Sprache eine Regel $B\to u_1,\dots u_k$ gibt. Dieser Ausdruck ist regulär $[.\ast ]u$

wie konstruieren wir mit dieser Information jetzt einen NFA? #card

Wir können jetzt daraus einen NFA bauen, welcher alles annimmt und schaut, ob er anschließend in das Suffix $u$ übergeht. Dafür muss er den Fortschritt $u_1,u_2\dots$ mit einzelnen Zuständen “Speichern” (er hat ja keinen Stack) und somit können wir dann den Automaten folgend aufbauen: Da es sich um einen NFA handelt, muss bei unserer Berechnung mindestens ein Blatt des Berechnungsbaums akzeptiert werden. Um das umsetzen zu können setzen wir jetzt folgende Startbedingungen des NFA:

• $J$ erhält einen Startzustand, welcher mit $\epsilon$ Übergängen zu allen Zuständen der Form $B\to \circ u$ übergeht ( also alle Suffixe die unsere Grammatik zulassen kann)
• Da wir jetzt zu jeder Grammatik einen Übergang haben, kann unser NFA entsprechend schauen, wie bzw. ob eine Regel getroffen wird, wenn eine Eingabe getätigt wird.

Erweiterung des NFA Wir können diesen Automaten jetzt noch verfeinern, indem wir jetzt mit Handles arbeiten und somit spezifischer die Zustände bzw. die Regeln der Grammatik finden und akzeptieren können.

[!Definition] Erweiterung der DK-Tests um Handles, Reduktion

Wir betrachten erneut den Grundlegenden NFA $J$ welcher die Wörter $z=xu$ mit Suffix $u=$ Regel der Grammatik akzeptiert, dabei wird dann Schritt für Schritt ein Zustand für jeden Verarbeitungsschritt gesetzt, welcher am Ende akzeptierend sein solte. Das haben wir mit einem Startzustand welcher mit einem $\epsilon$-Übergang zu allen von diesen Regel-erkennenden Strängen übergeht, geschafft.

Wir wollen jetzt den Automat un Handles und um Reduktions Übergänge erweitern, damit wir entsprechend die Grammatik erkennen könne.

wie gehen wir vor, sodass unser DFA Handles und Reduktionen der Grammatik erkennen kann? #card

Für diese Konstruktion nehmen wir also den gleichen Automaten $J$ wieder.

• Mit gleichen Zustände, wie $J$, jedoch nun einen Startzustand $S$ welcher die Startvariable der Grammatik wiedergibt. Anschließend führen $\epsilon$ Übergänge zu allen Teilpfaden, die dann Regel erkennen soll/wird.
• Es werden shift-Übergänge übernommen, die quasi einen Terminal unter Anwendung einer Regel durchlaufen, also
• Wir fügen aber auch noch reduce-Übergänge ein, welche Reduktionen bei einer Eingabe versuchen. Das heißt, dass sie mit $\epsilon$-Übergängen folgende Reduktionen probieren: $B\to uCv,C\to r$ und somit:
• In dieser Betrachtung sind dann alle matched Zustände der Form $B\to u\circ$ akzeptierend,sie haben keine augehenden Pfade mehr, sind also beendet!

Es folgt daraus dann, dass man mit diesem Automaten valide Handles bzw valide Strings finden kann.

[!Lemma] DK-Test erkennt valide Strings

warum kann unser DK-NFA jetzt valide Strings der Form $xhy,h=$handle erkennen? #card

Der neu konstruierte Automat $K$ geht auf einer bestimmten Eingabe $z$ in einen akzeptierenden Zustand, genau dann, wenn $z=xh$ darstellt und $h$ ein Handle für einen validen String $xhy$ mit einer Regel $T\to h$ ist.

Konvertierung des NDA $K$ in DFA $DK$

Wir möchten ferner den NDA in einen DFA umwandeln, damit wir eine Struktur erhalten, die realistisch umsetzbar ist!

[!Satz] Konstruktion eines DFA auf Grundlage des NFA $K$

Sei $G$ eine CFG. Wir möchten jetzt einen DFA $DK$ konstruieren, der die Handles der Grammatik erkennen kann.

wie können wir vorgehen (wenn wir den NDA schon kennen?) Wie ist $DK$ aufgebaut? Wie baut man daraus dann einen Tester? #card

Wir verwenden die Konversion eines NDA zu einem DFA Übersetzung von NFA zu DFA und werden hier anschließend solche Zustände entfernen, die wir eh nicht erreichen können (Minimierung)

Damit hat unser Automat $DK$ dann Zustände, die jeweils eine oder mehrer items (was Zwischenschritte bei einer Erkennung einer Regel waren) enthalten (Die Zustände sind jetzt Potenzmengen!). Dadurch gilt dennoch, dass ein akzeptierender Zustand mindestens eine abgeschlossene Regel ist.

[!Lemma] $DK$-Test bauen und prüfen, ob eine Grammatik $G$ Deterministisch ist

Wir haben jetzt definiert, wie man einen Automaten $DK$ bauen kann, der ein DFA ist und Handler einer Grammatik (CFG) erkennen kann. Wie finden wir heraus, ob die Grammatik deterministisch ist? #card

Mit dieser Konstruktion können wir jetzt den Tester erweitern/bauen:

1. Wir bauen wie obig beschrieben den Automaten $DK$
2. Wir analysieren die Zustände des Automaten: Wir sagen, dass er deterministisch ist, wenn folgende zwei Punkte gelten:
3. es gibt genau eine abgeschlossene Regel in einem akzeptierenden Zustand
4. ein akzeptierender Zustand hat keine weitere Regel $B\to u\circ av,a\in \Sigma$ (also eine zweideutige Fortsetzung zu einer anderen Reduktion)

Konstruktion eines DPDA unter Anwendung von $DK$

Mit dem obigen Konstrukt können wir jetzt den deterministischen Kellerautomaten bauen, welcher dann eine Produktion einer Grammatik $G$ erkennen und reduzieren kann. (er kann sie also lesen und produzieren).

Folgend möchten wir den Ablauf dafür beschreiben:

[!Definition] Konstruktion DPDA aus $DK$

Wir wollen jetzt die Idee des DFA $DK$ verwenden, um eine Produktion/Reduktion durchführen zu können.

Wie können wir jetzt eine Reduktion durchführen und anschließend das Wort adäquat weiterverarbeiten? Warum brauch es den Stack? #card

Wir folgen einem Schema:

1. Wir konstruieren wieder den DFA $DK$, wie obig beschrieben. Wir wissen, dass wenn $DK$ akzeptiert, dann zeit sein Zustand auf ein Handle der Reduktion. –> Ferner sind alle Reduktionen erzwungen und sie können beim Verarbeiten der Eingabe $x$ von links ausgeführt werden. Dabei muss man den Rest des Inputs noch nicht lesen.
2. Wir bauen unseren DPDA also so, dass er einfach $DK$ simuliert. Wenn DK das erste mal akzeptiert, dann müssen wir die Reduktion umsetzen und eigentlich von vorne Anfangen –> Das geht aber nicht, weil wir den Input schon verloren haben (beim DFA). Hier jetzt einfach die Eingebae im Stack zu speichern ist auch nicht möglich, weil wir sonst bei einer Reduktion den ganzen Stack popen müssten –> damit aber die Eingabe verlieren xd

Lösung: Statt der Eingabe speichern wir die Zustände des Automaten $DK$.

1. Immer wenn $P$(DPDA) ein Symbol aus $x$ liest, schreibt er dann den entsprechenden Zustand von DK auf den Steck ( da ist dann auch der derzeitige Teilstring enthalten).
2. Wenn jetzt $DK$ eine Reduktion erkennt, dann popt der DPDA einfach $\mid u\mid$ Symbole vom Stack –> er liest dann den letzten Zustand von $DK$ auf dem Stack und fährt dann mit der Vearbeitung von diesem Punkt fort.
3. Wenn jetzt der DPDA am Ende von $x$ ist und die Startvariable $S\in G$ auf den Stack schreibt (also quasi passend reduzieren konnte!), dann akzeptiert er!
4. Dieser akzeptierende Zustand zeigt die deterministische Ableitung von $x$!

Beispiele für Parser

• yacc (yet another compiler compiler) ist ein Parser (compiler) von Stephen C. Johnson welcher auf dem Paper von Knuth basiert und für UNIX entwickelt wurde. Er ist ein Compiler-Compiler für die erste C++ Version!
• bison (GNU yacc) und Berkley Yacc sind open-source Erweiterung von yacc, von Bjarne Stroustup
• tree-sitter ist ein moderner Parser-Generator für Dinge, wie Syntax-Highlighting in Atom,VSCode etc. BSP: Tree-Sitter Grammatik für:
  • markdown
  • bibtex
  • haskell

Folgerungen | Erkenntnisse

Unser betrachteter Parser liest immer eine Eingabe von links nach rechts. Er führt dabei Rechtsableitungen durch - in der Produktion wird von $S$ abwärts jeweils rechts ersetzt. Dabei schaut er 0 Zeichen in die Zukunft, erkennt also direkt forced handles. ->> Daher nennen wir sie auch $LR(k=0)Parser$!

• Wir haben auch gesehen, dass unser DFA $DK$ aus shift/reduce-Schritten besteht. Ein Parser dieser Struktur heißt shift-reduce-Parser

• Der Zwang zu forced handles schränkt die Grammatik natürlich stark ein! Daher gibt es Erweiterungen, bei denen handles erst zwingend werden, wenn schon $k$ Schritte nach rechts vorausschgeschaut werden kann. Man nennt sie dann $LR(k)$ Grammatiken!

[!Tip] Äquivalenz von $LR(k)$-Grammatiken

Alle $LR(k)$-Grammatiken sind Äquivalent –> man kann sie in eine $LR(1)$ Grammatik übersetzen.

Man nennt sie jetzt kanonische-LR-Parer oder $LR(1)$ Dadurch wird eine Grammatik u.U. aber auch sehr groß! Weiterhin sind alle $LR(k)$ Grammatiken deterministisch!