In der syntaktischen Analyse arbeitet ein Parser mit dem Tokenstrom, der vom Lexer kommt. Mit Hilfe einer Grammatik wird geprüft, ob gültige Sätze im Sinne der Sprache/Grammatik gebildet wurden. Der Parser erzeugt dabei den Parse-Tree. Man kann verschiedene Parser unterscheiden, beispielsweise die LL- und die LR-Parser.
Für z. B. alle Sprachen, in deren Wörtern Zeichen über eine Konstante hinaus gezählt werden müssen. Diese Sprachen lassen sich oft mit Variablen im Exponenten beschreiben, die unendlich viele Werte annehmen können.
$a^ib^{2*i}$ ist nicht regulär
$a^ib^{2*i}$ für $0 \leq i \leq 3$ ist regulär
Wo finden sich die oben genannten VAriablen bei einem DFA wieder?
Warum ist die erste Sprache oben nicht regulär, die zweite aber?
Einordnung: Erweiterung der Automatenklasse DFA um einen Stack
Def.: Ein Kellerautomat (PDA) $P = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ \perp,\ F)$ ist ein Septupel aus
Definition eines PDAs
Ein PDA ist per Definition nichtdeterministisch und kann spontane Zustandsübergänge durchführen.
Strukturen mit paarweise zu matchenden Symbolen.
Bei jedem Zustandsübergang wird ein Zeichen (oder $\epsilon$) aus der Eingabe gelesen, ein Symbol von Keller genommen. Diese und das Eingabezeichen bestimmen den Folgezustand und eine Zeichenfolge, die auf den Stack gepackt wird. Dabei wird ein Symbol, das später mit einem Eingabesymbol zu matchen ist, auf den Stack gepackt.
Soll das automatisch vom Stack genommene Symbol auf dem Stack bleiben, muss es wieder gepusht werden.
Ein PDA für $L=\lbrace ww^{R}\mid w\in \lbrace a,b\rbrace^{\ast}\rbrace$:
Def. Ein PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, \perp, F)$ ist deterministisch $: \Leftrightarrow$
Deterministische PDAs werden auch DPDAs genannt.
Satz: Die von DPDAs akzeptierten Sprachen sind eine echte Teilmenge der von PDAs akzeptierten Sprachen.
Reguläre Sprachen sind eine echte Teilmenge der von DPDAs akzeptierten Sprachen.
Def. Eine kontextfreie (cf-) Grammatik ist ein 4-Tupel $G = (N, T, P, S)$ mit N, T, S wie in (formalen) Grammatiken und P ist eine endliche Menge von Produktionen der Form:
$X \rightarrow Y$ mit $X \in N, Y \in {(N \cup T)}^{\ast}$.
$\Rightarrow, \overset{\ast}{\Rightarrow}$ sind definiert wie bei regulären Sprachen.
Def.: Gibt es in einer von einer kontextfreien Grammatik erzeugten Sprache ein Wort, für das mehr als ein Ableitungsbaum existiert, so heißt diese Grammatik mehrdeutig. Anderenfalls heißt sie eindeutig.
Satz: Es ist nicht entscheidbar, ob eine gegebene kontextfreie Grammatik eindeutig ist.
Satz: Es gibt kontextfreie Sprachen, für die keine eindeutige Grammatik existiert.
Satz: Die kontextfreien Sprachen und die Sprachen, die von PDAs akzeptiert werden, sind dieselbe Sprachklasse.
Satz: Eine von einem DPDA akzeptierte Sprache hat eine eindeutige Grammatik.
Def.: Die Klasse der Sprachen, die von einem DPDA akzeptiert werden, heißt Klasse der deterministisch kontextfreien (oder LR(k)-) Sprachen.
Vorgehensweise im Compilerbau: Eine Grammatik für die gewünschte Sprache definieren und schauen, ob sich daraus ein DPDA generieren lässt (automatisch).
Die Syntax bezieht sich auf die Struktur der zu analysierenden Eingabe, z. B. einem Computerprogramm in einer Hochsprache. Diese Struktur wird mit formalen Grammatiken beschrieben. Einsetzbar sind Grammatiken, die deterministisch kontextfreie Sprachen erzeugen.
Def.: Ein Nichtterminal A einer kontextfreien Grammatik G heißt unerreichbar, falls es kein $a,b \in {(N \cup T)}^{\ast}$ gibt mit $S \overset{\ast}{\Rightarrow} aAb$. Ein Nichtterminal A einer Grammatik G heißt nutzlos, wenn es kein Wort $w \in T^{\ast}$ gibt mit $A \overset{\ast}{\Rightarrow} w$.
Def.: Eine kontextfreie Grammatik $G=(N, T, P, S)$ heißt reduziert, wenn es keine nutzlosen oder unerreichbaren Nichtterminale in N gibt.
Bevor mit einer Grammatik weitergearbeitet wird, müssen erst alle nutzlosen und dann alle unerreichbaren Symbole eliminiert werden. Wir betrachten ab jetzt nur reduzierte Grammatiken.
Hier ist ein einfacher Algorithmus, der (indeterministisch) top-down Ableitungen vom Nonterminal X aufbaut:
Eingabe: Ein Nichtterminal $X$ und das nächste zu verarbeitende Eingabezeichen $a$.
Recursive Descent-Algorithmus
Welche Produktion nehmen?
Wir brauchen die "terminalen k-Anfänge" von Ableitungen von Nichtterminalen, um eindeutig die nächste zu benutzende Produktion festzulegen. $k$ ist dabei die Anzahl der sog. Vorschautoken.
Def.: Wir definieren $First$ - Mengen einer Grammatik wie folgt:
Def.: Bei einer kontextfreien Grammatik $G$ ist die Linksableitung von $\alpha \in (N \cup T)^{\ast}$ die Ableitung, die man erhält, wenn in jedem Schritt das am weitesten links stehende Nichtterminal in $\alpha$ abgeleitet wird.
Man schreibt $\alpha \overset{\ast}{\Rightarrow}_l \beta.$
Manchmal müssen wir wissen, welche terminalen Zeichen hinter einem Nichtterminal stehen können.
Def. Wir definieren Follow - Mengen einer Grammatik wie folgt:
$\forall \beta \in (N \cup T)^*:$ $$Follow_k(\beta) = \lbrace w \in T^\ast \mid \exists \alpha, \gamma \in (N \cup T)^\ast\ \text{ mit }\ S \overset{\ast}{\Rightarrow}_l \alpha \beta \gamma\ \text{ und }\ w \in First_k(\gamma) \rbrace$$Def.: Eine kontextfreie Grammatik G = (N, T, P, S) ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form:
$S \overset{\ast}{\Rightarrow}_l\ wA \gamma\ {\Rightarrow}_l\ w\alpha\gamma \overset{\ast}{\Rightarrow}_l wx$und
$S \overset{\ast}{\Rightarrow}_l wA \gamma {\Rightarrow}_l w\beta\gamma \overset{\ast}{\Rightarrow}_l wy$mit $(w, x, y \in T^\ast, \alpha, \beta, \gamma \in (N \cup T)^\ast, A \in N)$ und $First_k(x) = First_k(y)$ gilt:
$\alpha = \beta$Das hilft manchmal:
Für $k = 1$: G ist $LL(1): \forall A \rightarrow \alpha, A \rightarrow \beta \in P, \alpha \neq \beta$ gilt:
Die ersten beiden Zeilen bedeuten:
$\alpha$ und $\beta$ können nicht beide $\epsilon$ ableiten, $First_1(\alpha) \cap First_1(\beta) = \emptyset$
Die dritte und vierte Zeile bedeuten:
$(\epsilon \in First_1(\beta)) \Rightarrow (First_1(\alpha) \cap Follow_1(A) = \emptyset)$ $(\epsilon \in First_1(\alpha)) \Rightarrow (First_1(\beta) \cap Follow_1(A) = \emptyset)$Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der deterministisch parsbaren Sprachen.
Die von LL(k)-Grammatiken erzeugten Sprachen sind eine echte Teilmenge der von LL(k+1)-Grammatiken erzeugten Sprachen.
Für eine kontextfreie Grammatik G ist nicht entscheidbar, ob es eine LL(1) - Grammatik G' gibt mit $L(G) = L(G')$.
In der Praxis reichen $LL(1)$ - Grammatiken oft. Hier gibt es effiziente Parsergeneratoren, deren Eingabe eine LL(k)- (meist LL(1)-) Grammatik ist, und die als Ausgabe den Quellcode eines (effizienten) tabellengesteuerten Parsers generieren.
Eingabe: Eine Grammatik G = (N, T, P, S) mit $\perp \in T$ als Endezeichen
Ausgabe: Eine Parsertabelle P
Algorithmus zur Generierung einer LL-Parsertabelle
Statt $First_1(\alpha)$ und $Follow_1(\alpha)$ wird oft nur $First(\alpha)$ und $Follow(\alpha)$ geschrieben.
Rekursive Programmierung bedeutet, dass das Laufzeitsystem einen Stack benutzt (bei einem Recursive-Descent-Parser, aber auch bei der Parsertabelle). Diesen Stack kann man auch "selbst programmieren", d. h. einen PDA implementieren. Dabei wird ebenfalls die oben genannte Tabelle zur Bestimmung der nächsten anzuwendenden Produktion benutzt. Der Stack enthält die zu erwartenden Eingabezeichen, wenn immer eine Linksableitung gebildet wird. Diese Zeichen im Stack werden mit dem Input gematcht.
Eingabe: Eine Grammatik G = (N, T, P, S), eine Parsertabelle P mit $w\perp$ als initialem Kellerinhalt
Ausgabe: Wenn $w \in L(G)$, eine Linksableitung von $w$, Fehler sonst
Algorithmus zum tabellengesteuerten LL-Parsen
Baumaufbau von oben nach unten
eine Möglichkeit: recursive-descent parser
alternativ: tabellengesteuerter Parser
First- und Follow-Mengen bestimmen Wahl der Ableitungen
nicht mehr rekursiv, sondern mit PDA
Die Menge der LL-Sprachen ist eine echte Teilmenge der deterministisch kontextfreien Sprachen.
Bei $LL$-Sprachen muss man nach den ersten $k$ Eingabezeichen entscheiden, welche Ableitung ganz oben im Baum als erste durchgeführt wird, also eine, die im Baum ganz weit weg ist von den Terminalen, die die Entscheidung bestimmen. Das ist nicht bei allen deterministisch parsebaren Grammatiken möglich und erschwert die Fehlerbehandlung.
Bei der Bottom-Up-Analyse wird der Parse Tree wird von unten nach oben aufgebaut, von links nach rechts. Dabei entsteht eine Rechtsableitung.
Def.: Bei einer kontextfreien Grammatik $G$ ist die Rechtsableitung von $\alpha \in (N \cup T)^{\ast}$ die Ableitung, die man erhält, wenn das am weitesten rechts stehende Nichtterminal in $\alpha$ abgeleitet wird. Man schreibt $\alpha \overset{\ast}{\Rightarrow}_r \beta$.
Mit Hilfe der Produktionen und der Vorschautoken werden die Ableitungen "rückwärts" angewandt und "Reduktionen" genannt.
Hier entsteht ein Tafelbild.
Hier entsteht ein Tafelbild.
Hier entsteht ein Tafelbild.
Parser-Automat
Im Stack stehen nur Zustandsnummern, am Anfang die Nummer des Startzustandes (+ Bottomzeichen, oft auch $\$$).
Lesen des obersten Stackelements ergibt Zustand $q$
Lesen des nächsten Eingabezeichens ergibt Zeichen $a$
Nachschlagen der Reaktion auf $(q, a)$ in der Parse Table
Durchführung der Reaktion
Shift: Schiebe logisch das nächste Eingabesymbol auf den Stack (in Wirklichkeit Zustandsnummern)
Reduce: (Identifiziere ein Handle oben auf dem Stack und ersetze es durch das Nichtterminal der dazugehörigen Produktion.) Das ist gleichbedeutend mit: Entferne so viele Zustände vom Stack wie die rechte Seite der zu reduzierenden Regel Elemente hat, und schreibe den Zustand, der im Goto-Teil für $(q, a)$ steht, auf den Stack.
Accept: Beende das Parsen erfolgreich
Reagiere auf einen Syntaxfehler
Def.: Ein (dotted) Item einer Grammatik $G$ ist eine Produktion von $G$ mit einem Punkt auf der rechten Seite der Regel vor, zwischen oder nach den Elementen.
Bsp.:
Zu der Produktion $A \rightarrow BC$ gehören die Items:
$[A\rightarrow \cdot B C]$$[A\rightarrow B \cdot C$]
$[A\rightarrow B C \cdot]$Das zu $A \rightarrow \epsilon$ gehörende Item ist $[A \rightarrow \cdot]$
füge $I$ zu $CLOSURE_0 (I)$ hinzu
gibt es ein Item $[A \rightarrow \alpha \cdot B\beta]$ aus $CLOSURE_0 (I)$ und eine Produktion $(B \rightarrow \gamma)$, füge $[B \rightarrow \cdot \gamma]$ zu $CLOSURE_0 (I)$ hinzu
für eine Itemmenge $I$ und $X \in N \cup T, A \in N, \alpha, \beta \in (N \cup T)^{\ast}$.
Bilde die Hülle von $S' \rightarrow S$ und mache sie zum ersten Zustand.
Für jedes noch nicht betrachtete $\cdot X, X \in (N \cup T)$ in einem Zustand $q$ des Automaten berechne $GOTO_0(q, X)$ und mache $GOTO_0(q, X)$ zu einem neuen Zustand $r$. Verbinde $q$ mit einem Pfeil mit $r$ und schreibe $X$ an den Pfeil. Ist ein zu $r$ identischer Zustand schon vorhanden, wird $p$ mit diesem verbunden und kein neuer erzeugt.
Erstelle eine leere Tabelle mit den Zuständen als Zeilenüberschriften. Für den Aktionstabellenteil überschreibe die Spalten mit den Terminalen, für den Sprungtabellenteil mit den Nonterminals.
Shift: Für jeden mit einem Terminal beschrifteten Pfeil aus einem Zustand erstelle in der Aktionstabelle die Aktion shift mit der Nummer des Zustands, auf den der Pfeil zeigt. Für Pfeile mit Nonterminals schreibe in die Sprungtabelle nur die Nummer des Folgezustands.
Schreibe beim Zustand $[S' \rightarrow S \cdot]$ ein $accept$ bei dem Symbol $\bot$.
Für jedes Item mit $[A \rightarrow \beta \cdot]$ aus allen Zuständen schreibe für alle Terminals $reduce$ und die Nummer der entsprechenden Grammatikregel in die Tabelle.
(0) $S^{'} \rightarrow S$
(1) $S \rightarrow a A b S c S$
(2) $S \rightarrow a A b S$
(3) $S \rightarrow d$
(4) $A \rightarrow e$
LR(0)-Automat
LR(0)-Parsertabelle
Zunächst: Zu jeder LR(k)-Sprache gibt es eine LR(1)-Grammatik.
Ist eine Grammatik nicht LR(0), müssen nichtdeterminsistische Tabelleneinträge verhindert werden:
SLR(1)-Parsing ($A \rightarrow \beta$ wird nur reduziert, wenn das Vorschautoken in der $FOLLOW$-Menge von $A$ ist.)
(kanonisches) LR(1)-Parsing (wie LR(0) mit einem Vorschautoken)
LALR(1)-Parsing (Zusammenfassung aller LR(1)-Zustände, die sich nur in den LOOKAHEAD-Mengen unterscheiden)
Mehrdeutige Grammatiken sind oft leichter zu lesen und kleiner als die Grammatiken, die man erhält, wenn man die Mehrdeutigkeit auflöst, sofern möglich.
Folgendes kann bei Mehrdeutigkeiten helfen:
Angabe von Vorrangregeln
Angabe von Assoziativität
Voreinstellung des Parsergenearators: z. B. Shiften bei Shift-Reduce-Konflikten
Voreinstellung des Parsergenearators: z. B. Reduzieren nach der Regel, die in der Grammatik zuerst kommt bei Reduce-Reduce-Konflikten
Sprachenhierarchie
LR-Analyse baut den Ableitungbaum von unten nach oben auf
es wird ein DFA benutzt zusammen mit einem Stack, der Zustände speichert
eine Parse-Tabelle steuert über Aktions- und Sprungbefehle das Verhalten des Parsers
die Tabelle wird mit (dotted) Items und Closures konstruiert
mit Bottom-Up-Parsing LR(1) kann man alle deterministisch kontextfreien Sprachen parsen
LR(0)-, SLR- und LALR- Parsing sind vereinfachte Verfahren für Teilmengen der LR-Sprachen