swp_1.tex

\chapter{Syntax}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Dieses Skriptum versucht einen kompakten und übersichtlichen Zugang zu den Themen
dieser Lehrveranstaltung zu schaffen.
Wir haben uns dabei stark am Vorlesungsskriptum orientiert.
Das Vorlesungsskriptum und folglich auch dieses Skriptum bezieht die angeführten
Sprachen und Konzepte großteils aus dem Skriptum ``Einführung in die Theorie der Informatik'' von A. Leitsch, TU Wien, 1989.

In der Informatik stehen wir oft vor dem Problem, dass wir eine Art Text auf
Fehler überprüfen wollen und in eine andere Darstellungsform übersetzen wollen.
Ein Webbrowser prüft beispielsweise HTML-Dokumente auf Fehler und übersetzt diese
sofern möglich in eine praktische visuelle Darstellung.

Dieses Problem wollen wir auch lösen können. Dazu brauchen wir zunächst einige grundlegende Definitionen.
Die Definitionen in diesem Skriptum unterscheiden sich teilweise von denen im Vorlesungsskriptum.
Das Übungsskriptum versucht an vielen Stellen exaktere Formulierungen zu bieten
oder solche die man weniger leicht durcheinander bringt.
Für Übung und Prüfung sind beide Varianten zulässig. Es sollte jedoch vermieden
werden Definitionen aus Übungsskriptum und Vorlesungsskriptum zu vermischen.
\ifthenelse{\boolean{long}}{}{\end{comment}}

\section{Grundlegende Definitionen}
\begin{defn}[Alphabet]
Ein Alphabet $\Sigma$ ist eine endliche Menge von Symbolen.
\end{defn}

Binärzahlen haben das Alphabet $\Sigma=\gbr{0,1}$.
Eine einfache Variante der Markup-Sprache HTML hat das Alphabet $\Sigma=\gbr{\texttt{<},\texttt{/},\texttt{>},\ldots,a,b,c,\ldots}$.

\begin{defn}
$\Sigma^*$ ist die Menge aller beliebigen Konkatenationen von Symbolen aus $\Sigma$.
Ein Element aus $\Sigma^*$ nennen wir Wort.
\end{defn}

Für $\Sigma=\gbr{0,1}$ ist $\Sigma^*=\gbr{\varepsilon,0,1,00,01,10,11,000,001,\ldots}$.

\begin{defn}[Sprache]
Eine Sprache $\mathcal{L}$ ist eine Teilmenge ($\subseteq$) von $\Sigma^*$.
\end{defn}

Sei $\Sigma=\gbr{0,1}$. Definieren wir die Sprache der Binärzahlen $\mathcal{B}$,
müssen wir zu jedem Wort aus $\Sigma^*$ entscheiden ob dieses Wort in $\mathcal{B}$ enthalten ist.
Im Fall der Binärzahlen könnten wir z.B. $\varepsilon$ herausnehmen, dann ist die Sprache
$\mathcal{B}=\Sigma^* \setminus \gbr{\varepsilon}$.

Würden wir die Programmiersprache $\mathcal{C}$ als formale Sprache definieren, so wäre
ein gesamtes (gültiges) $\mathcal{C}$-Programm ein Wort der Sprache, also ein Element der Menge $\mathcal{C}$.

\begin{defn}[Compiler]
Seien $\mathcal{A}$ und $\mathcal{B}$ Programmiersprachen. Ein Compiler ist ein Programm, welches Programme von $\mathcal{A}$ nach $\mathcal{B}$ übersetzt.
\end{defn}

Ein einfacher Compiler würde beispielsweise Binärzahlen zu Dezimalzahlen übersetzen.
\ifthenelse{\boolean{long}}{\begin{comment}}{}
\newpage
\ifthenelse{\boolean{long}}{\end{comment}}{}
\section{Grammatiken und Sprachen}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Oft möchte man nur prüfen ob ein Wort in einer Sprache enthalten ist.
Es ist umständlich die Menge aller Wörter einer Sprache aufzuschreiben und darin zu suchen.
Daher wollen wir eine kürzere Beschreibung für Sprachen finden um diese Überprüfung durchzuführen.

\begin{floatingfigure}[r]{4.5cm}
\vspace{-0.3cm}
\begin{center}
\begin{tikzpicture}[node distance=1.8cm, auto]
\node [state, initial] (0) {S};
\node [state, accepting, right of=0] (1) {A};
\path [->, bend left=30] (0) edge node {0} (1);
\path [->, bend right=30] (0) edge node {1} (1);
\path [draw, ->] (1) edge [loop below] node {1} ();
\path [draw, ->] (1) edge [loop above] node {0} ();
\end{tikzpicture}
\end{center}
 \caption{Binärzahl FSM}
 \label{fsm1}
\end{floatingfigure}

Über Automaten (FSM) ist dies möglich. Für Binärzahlen könnte man dies wie in Abbildung \ref{fsm1} machen.

Wir haben eine Eingabe (mglw. Wort der Sprache) und beginnen im Zustand $S$. Beide Übergänge von Zustand $S$ führen zu Zustand $A$. Es muss also entweder eine $0$ oder
eine $1$ gelesen werden (auch ``gematcht'' bzw. ``geparst''). Andernfalls gibt es keinen gültigen Übergang und da $S$ kein Endzustand ist wäre die Eingabe nicht gültig.
Im Zustand $A$ wurde bereits eine $0$ oder $1$ gelesen, also ist $w \in \mathcal{B}$. Die Übergänge von $A$ zu $A$ erlauben
weitere Zeichen zu lesen und so längere Wörter zu erhalten, die in der Sprache enthalten sind.

Eine ähnliche Herangehensweise stellen Grammatiken dar:
\ifthenelse{\boolean{long}}{}{\end{comment}}
\begin{defn}[Grammatik]
Eine Grammatik ist ein 4-Tupel $(V_N, V_T, S, \Phi)$.
\begin{\whichitem}
\item $V_N$ ist eine endliche Menge von Nonterminalen (entsprechen Zuständen der FSM),
\item $V_T$ ist eine endliche Menge von Terminalen (entsprechen Alphabet der Sprache),
\item $S \in V_N$ das Startsymbol (wie Initialzustand der FSM),
\item $\Phi=\gbr{\alpha \to \beta}$ eine endliche Menge von Produktionsregeln (Zustandsübergänge).

$\alpha$ ist hierbei eine beliebige Aneinanderreihung von Terminalen und Nonterminalen, die zumindest ein Nonterminal enthält,
also $(V_N \cup V_T)^* V_N (V_N \cup V_T)^*$.

$\beta$ ist eine beliebige Aneinanderreihung von Terminalen und Nonterminalen, einschließlich der leeren Menge,
also $(V_N \cup V_T)^*$.
\end{\whichitem}
\end{defn}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
Anhand der Binärzahlen wollen wir nun genauer betrachten wie die Produktionsregeln funktionieren.
Bei den Zustandsübergängen des Automaten hatten wir beispielsweise ein Wort $w=AB$ mit $A \in \gbr{0,1}$ und $B \in \gbr{0,1}^*$.
Mit dem Zustandsübergang würden wir nun das $A$ weglassen und hätten für das verbleibende zu lesende Wort $w'=B$.
Wir ersetzen also $AB$ durch $B$. Bei den Produktionsregeln der Grammatik halten wir ganz konkret fest was wir ersetzen.

\begin{floatingfigure}[r]{5.25cm}
\vspace{-0.5cm}
\begin{align*}
S &\to 0 \\
S &\to 1 \\
S &\to 0S \\
S &\to 1S
\end{align*}
 \caption{Binärzahl Grammatik}
 \label{grambin}
\end{floatingfigure}

Um die Grammatik der Binärzahlen $G_{\mathcal{B}}$ zu definieren müssen wir die Elemente des oben definierten 4-Tupels beschreiben.
Die Menge der Terminale ist das Alphabet $\gbr{0,1}$.
Den Startzustand nennen wir $S$. In Abbildung \ref{grambin} versuchen wir Produktionsregeln anzugeben um $\mathcal{B}$ zu definieren.
\ifthenelse{\boolean{long}}{}{\end{comment}}
Wir müssen nun zuerst definieren was eine Ableitung ist, um zu verifizieren wann ein Wort von einer Grammatik erzeugt werden kann.

\begin{defn}
Sei $\rbr{V_N,V_T,S,\Phi}$ eine Grammatik und $\alpha,\beta \in \rbr{V_N \cup V_T}^*$.
Wenn es 2 Zeichenfolgen $\tau_1,\tau_2$ gibt, so dass $\alpha=\tau_1 A \tau_2$, $\beta=\tau_1 B \tau_2$ und $A \to B \in \Phi$,
dann kann $\beta$ direkt (in einem Schritt) von $\alpha$ abgeleitet werden $(\alpha \to \beta)$.
\end{defn}

Diese Definition ist nur geeignet um eine Aussage darüber zu treffen was in genau einem Schritt abgeleitet werden kann. Wir definieren daher die reflexive Hülle dieses Operators.

\begin{defn}
Sei $\rbr{V_N,V_T,S,\Phi}$ eine Grammatik und $\alpha,\beta \in \rbr{V_N \cup V_T}^*$.
Wenn es $n \in \N$ Zeichenfolgen $\tau_1,\tau_n$ gibt, so dass $\alpha \to \tau_1, \tau_1 \to \tau_2 , \ldots , \tau_{n-1} \to \tau_n , \tau_n \to \beta$,
dann kann $\beta$ von $\alpha$ (in $n$ Schritten) abgeleitet werden $(\alpha \overset{+}{\to} \beta)$.
\end{defn}

Diese Definition ist für $n \geq 1$ geeignet. Wenn $\alpha = \beta$ ist, wäre $n=0$. Wir definieren die reflexive, transitive Hülle durch eine Verknüpfung dieser beiden Fälle.

\begin{defn}
Es gilt $\alpha \overset{*}{\to} \beta$, genau dann wenn $\alpha \overset{+}{\to} \beta$ oder $\alpha = \beta$ (reflexive, transitive Hülle).
\end{defn}

Mit dieser Definition können wir alle Wörter ableiten die diese Grammatik produziert.

\begin{defn}
Sei $\rbr{V_N,V_T,S,\Phi}$ eine Grammatik $G$. $G$ akzeptiert die Sprache $L(G)=\gbr{w \: | \: S \overset{*}{\to} w, w \in V_T^*}$, d.h. die Menge aller Wörter $w$ die in beliebig
vielen Schritten aus dem Startsymbol $S$ ableitbar sind und in der Menge aller beliebigen Konkatenationen von Terminalsymbolen $V_T$ enthalten sind.
\end{defn}

\begin{defn}
Zwei Grammatiken $G$ und $H$ sind \textbf{äquivalent} wenn die von den Grammatiken akzeptierten Sprachen gleich sind, d.h. $L(G)=L(H)$.
\end{defn}

Die Äquivalenz von zwei Sprachen (bzw. zwei Grammatiken) zu zeigen ist im Allgemeinen nicht trivial. Wenn wir also versuchen eine Sprache $\mathcal{L}$ durch eine Grammatik $G$ zu beschreiben
ist es im Allgemeinen nicht trivial zu zeigen, dass $L(G)=\mathcal{L}$.

An dieser Stelle möchten wir festzuhalten: Um die Gleichheit zweier Mengen (Sprachen) $M,N$ zu zeigen muss gezeigt werden, dass jedes Element (Wort) aus $M$ in $N$ enthalten ist
und jedes Element (Wort) aus $N$ in $M$ enthalten ist.
Ungleichheit ist viel leichter zu zeigen, da es genügt ein Element (Wort) zu finden welches in genau einer Menge (Sprache) also nicht in beiden Mengen (Sprachen) enthalten ist. Der geneigte Leser kann probieren die Gleichheit oder Ungleichheit der Sprache unserer oben definierten Grammatik und der Sprache der Binärzahlen zu zeigen.

\begin{defn}
Ein Programm $P_{\mathcal{L}}$ welches für ein Wort $w$ entscheidet ob es in der Sprache $\mathcal{L}$ enthalten ist (d.h. \verb|true| dann und nur dann zurückliefert wenn es enthalten ist), nennen wir \textbf{Parser}.
\end{defn}

\section{Chomsky-Sprachhierarchie}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Durch die Grammatik können wir entscheiden ob ein Wort in einer Sprache enthalten ist.
Im Falle der Binärzahlen haben wir eine kurze und einfache Grammatik und können einen Parser schreiben
welches entscheidet ob ein Eingabewort in der Sprache enthalten ist.
Definieren wir eine Programmiersprache wie $\mathcal{C}$ formal, so wird nicht nur die Anzahl der Produktionsregeln höher sein
sondern auch die Komplexität der Produktionsregeln ($\alpha \to \beta$ mit komplexen Ausdrücken für $\alpha$ und $\beta$).
Es ist dann erheblich schwieriger einen Parser zu schreiben.
Wir haben also Interesse daran möglichst einfache Grammatiken zu finden. Dazu müssen wir
Grammatiken nach ihrer Komplexität vergleichen können.
\ifthenelse{\boolean{long}}{}{\end{comment}}

Wir haben Produktionsregeln definiert durch $\alpha \to \beta$, wobei
$\alpha$ zumindest ein Nonterminal enthält.
\begin{defn}
Eine Grammatik ist nach der Chomsky-Sprachhierarchie:
\begin{\whichitem}
\item allgemein/uneingeschränkt (unrestricted)

Keine Restriktionen
\item Kontext-sensitiv (context sensitive): $\abs{\alpha} \leq \abs{\beta}$

Es werden nicht mehr Symbole gelöscht als produziert.
\item Kontext-frei (context free): $\abs{\alpha} \leq \abs{\beta}, \quad \alpha \in V_N$

Wie Kontext-sensitiv; außerdem muss $\alpha$ genau \textbf{ein} Non-Terminal sein
\item regulär (regular): $\abs{\alpha} \leq \abs{\beta}, \quad \alpha \in V_N, \quad \beta=aA, \quad a \in V_T \cup \gbr{\varepsilon}, A \in V_N \cup \gbr{\varepsilon}$

Wie Kontext-frei; außerdem ist $\beta=aA$ wobei $a$ ein Terminal oder $\varepsilon$ ist und $A$ ein Nonterminal oder $\varepsilon$. (Anmerkung: $\varepsilon\varepsilon=\varepsilon$)
\end{\whichitem}
Es gilt $\mathbb{L}_{\text{regular}} \subset \mathbb{L}_{\text{context free}} \subset \mathbb{L}_{\text{context sensitive}} \subset \mathbb{L}_{\text{unrestricted}}$ ($\mathbb{L}_{\text{x}}$ Menge aller Sprachen der Stufe $x$).
\end{defn}

Nicht alle Grammatiken können in eine äquivalente Grammatik einer stärker eingeschränkten Stufe umgewandelt werden. Um zu zeigen, dass es sich um echte Teilmengen ($A \subset B$) handelt müssen wir zeigen, dass alle Elemente aus $A$ in $B$ enthalten sind und mindestens ein Element aus $B$ nicht in $A$ enthalten ist.
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Eine Beweisskizze dazu findet sich im Vorlesungsskriptum auf Seite 12. Dort wird unter anderem gezeigt, dass es für $L=\gbr{a^n b a^n|n \in \N_0}$ keine äquivalente reguläre Grammatik $G$ gibt, d.h. $\not \exists G \in \mathbb{L}_{\text{regular}} : L(G) = L$.
\ifthenelse{\boolean{long}}{}{\end{comment}}

Die Chomsky-Sprachhierarchie unterscheidet Sprachen anhand der Komplexität der produzierten Sprache.

\section{Parser}\label{subsec:parser}
Wir überspringen an dieser Stelle den BPARSE-Algorithmus (siehe Vorlesungsskriptum) und betrachten stattdessen
einen Recursive Descent Parser (RDP).

Bei einem RDP werden alle Nonterminale in Funktionen übersetzt und diese Funktionen behandeln die verschiedenen Produktionsregeln.
Die Eingabe wird in die Terminale unterteilt (auch Tokens genannt).
Wir verwenden im Pseudo-Code die Variable \verb|token|, die immer das aktuelle Token enthält, sowie die Funktion \verb|nextToken()|, die \verb|token| auf das nächste Token setzt.
Der Parser ruft die Startfunktion auf und gibt \verb|true| zurück wenn \verb|token| leer ist (d.h. das Ende der Eingabe erreicht wurde). \verb|ERROR| führt dazu, dass der Parser die Eingabe (das Wort) nicht akzeptiert.

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\begin{bsp}
Sei $G_{\text{b1}}=(\gbr{S,T},\gbr{0,1},S,\gbr{S \to 0,S \to 1T, T \to 0T, T \to 1T, T \to \varepsilon})$.
Der Pseudo-Code des RDP zu dieser Grammatik könnte so aussehen:

\begin{tabular}{p{0.47\hsize}p{0.47\hsize}}
\begin{verbatim}
FUNC S()
  IF token == 0
    nextToken()
  ELSE IF token == 1
    nextToken()
    T()
  ELSE
    ERROR
\end{verbatim}
&
\begin{verbatim}
FUNC T()
  IF token == 0
    nextToken()
    T()
  ELSE IF token == 1
    nextToken()
    T()
  ELSE IF token != epsilon
    ERROR  
\end{verbatim}
\end{tabular}
\end{bsp}

\begin{bsp}
Sei $G_{\text{b2}}=\rbr{\gbr{S,T},\gbr{0,1},S,\gbr{S \to 0, S \to 1T, T \to T0, T \to T1, T \to \varepsilon}}$.
Wir wissen $L(G_{\text{b1}})=L(G_{\text{b2}})$ (ohne Beweis) und versuchen auch hier einen einfachen rekursiven Parser zu schreiben.

\begin{tabular}{p{0.47\hsize}p{0.47\hsize}}
\begin{verbatim}
FUNC S()
  IF token == 0
    nextToken()
  ELSE IF token == 1
    nextToken()
    T()
  ELSE
    ERROR
\end{verbatim}
&
\begin{verbatim}
FUNC T()
  IF token == 0
    T()        // Endlos-Rekursion
    nextToken()
  ELSE IF token == 1
    T()        // Endlos-Rekursion
    nextToken()
  ELSE IF token != epsilon
    ERROR  
\end{verbatim}
\end{tabular}
\vspace{-0.3cm}

Wir erhalten hier im Parser eine Endlos-Rekursion, da in $T \to T0, T \to T1$ ein Nonterminal ganz links steht. Wir nennen dies ``Linksrekursion''.
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}

\begin{defn}[Mehrdeutig, Eindeutig]
Sei $G=(V_N,V_T,S,\Phi)$ eine Grammatik. Wenn es für ein Wort $w \in L(G)$ mehrere
unterschiedliche Ableitungssequenzen $\alpha,\beta$ gibt, d.h. $S \to \alpha_1, \alpha_1 \to \ldots, \ldots \to \alpha_n, \alpha_n \to w$ und $S \to \beta_1, \beta_1 \to \ldots, \ldots \to \beta_k, \beta_k \to w$,
wobei $\exists \beta_i : \beta_i \neq \alpha_i$, ist es mehrdeutig. Eine Grammatik ist genau dann eindeutig, wenn sie nicht mehrdeutig ist.
\end{defn}

\begin{defn}[Linksrekursiv]
Eine Grammatik ist direkt linksrekursiv wenn sie eine Produktion der Form $A\alpha \to A\beta$ enthält, wobei $A$ ein Nonterminal ist.
Eine Grammatik ist indirekt linksrekursiv wenn sie Produktionen der Form $A\alpha \to A_1\beta_1, A_1 \alpha_1 \to A_2\beta_2, \ldots, A_n \alpha_n \to A\beta_n$ enthält, wobei $A,A_i$ Nonterminale sind.
Eine Grammatik ist linksrekursiv wenn sie direkt oder indirekt linksrekursiv ist.
\end{defn}

Nun können wir mit Sprachen und Grammatiken umgehen und diese nach ihrer Komplexität einstufen.

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\section{Compilerbau}
Wir wollen uns nun damit beschäftigen wie wir Compiler für Programmiersprachen bauen können.
Wir hatten definiert, dass ein Compiler ein Wort $w$ einer Sprache $\mathcal{L}$ entgegennimmt und
die Übersetzung des Wortes $w'$ in einer Sprache $\mathcal{L}'$ zurückgibt.
Konkreter erhält unser Compiler beispielsweise einen ASCII-String, wobei unser Alphabet $\Sigma_\mathcal{L}$ meist
nicht dem ASCII-Alphabet entspricht. Betrachten wir beispielsweise die Programmiersprache $\mathcal{C}$ so können wir
auch Schlüsselwörter wie \verb|int| in $\Sigma_\mathcal{C}$ haben.
Außerdem gibt es eventuell Whitespaces (Leerzeichen, Tabulatoren, Zeilenumbrüche, etc.; je nach dem positionsabhängig), die keinen Einfluss darauf haben ob das
Eingabewort ein Wort der Sprache $\mathcal{C}$ ist, d.h. ein $\mathcal{C}$-Programm ist. Auch Variablen- oder Funktionsnamen werden abgesehen von einer
gewissen Form die sie einhalten müssen (z.B. ``dürfen nicht nur aus Zahlen bestehen'') keinen Einfluss darauf haben ob das Programm in der Sprache enthalten ist.
Wenn wir dies berücksichtigen, verkürzen wir die Grammatik und vereinfachen so unseren Parser sowie eventuelle weitere Rechenschritte.
\ifthenelse{\boolean{long}}{}{\end{comment}}

\section{Lexikalische Analyse}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Wir haben bereits in Abschnitt \ref{subsec:parser} von Tokens geredet. Von Tokens spricht man insbesondere bei einer Sprache die durch Whitespaces getrennt werden. Ein Token ist hierbei die kleinste Sequenz von Zeichen die für die Grammatik eine Bedeutung hat.
Der erste Schritt der Kompiliervorgangs ist es die Eingabe in eine Sequenz von Tokens umzuwandeln (dies kann natürlich wie bei unserem rekursiven Parser während dem Parsen passieren).

Wir wollen z.B. den $\mathcal{C}$-Code \verb|int main() { printf("helloworld"); return 123; }| in die Sequenz von Tokens \verb|INT ID ( ) { ID ( STRING ) ; RETURN NUM ; }| umwandeln. Wir nennen dies ``Lexikalische Analyse''. Es fällt auf, dass in der Token-Sequenz keine Namen oder Zahlen mehr vorkommen außerdem sind nun die Tokens
voneinander getrennt.
Es ist üblich zur lexikalischen Analyse nur reguläre Grammatiken zu verwenden. Diese sind mächtig genug um beispielsweise nur gewisse Variablennamen zu erlauben
und können andererseits sehr schnell berechnet werden.
Eine reguläre Grammatik kann auch über einen regulären Ausdruck (Regular Expression/Regex) kompakt dargestellt werden.
\ifthenelse{\boolean{long}}{}{\end{comment}}

\begin{defn}
Ein regulärer Ausdruck $A$ ist wie folgt rekursiv definiert (mit regulären Ausdrücken $Q$ und $R$):
\[A = \begin{cases}
\varepsilon & \text{Leerstring} \\
t & \text{ein Terminal, d.h. $t \in V_T$} \\
Q|R & \text{entweder $A=Q$ oder $A=R$} \\
QR & \text{Konkatenation zweier regulärer Ausdrücke} \\
Q? & \text{entspricht $Q|\varepsilon$, d.h. $Q$ ist optional} \\
Q* & \text{beliebige Konkatenation von $Q$ mit sich selbst, d.h. $A \in \gbr{\varepsilon,Q,QQ,\ldots}$} \\
Q+ & \text{entspricht $QQ*$, d.h. mindestens ein $Q$} \\
(Q) & \text{Klammerung des Ausdrucks $Q$}
\end{cases}\]
\end{defn}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
Die Sprache der Binärzahlen hatten wir bereits in Abschnitt \ref{subsec:parser} durch die Grammatik $G_{\text{b1}}=(\gbr{S,T},\gbr{0,1},S,\gbr{S \to 0,S \to 1T, T \to 0T, T \to 1T, T \to \varepsilon})$
beschrieben. Wir können nun diese Grammatik in einen regulären Ausdruck übersetzen indem wir uns nach und nach überlegen welche Werte folgen können.
Beginnend bei $S$ erhalten wir den Teilausdruck $0|(1\tau)$. Für $\tau$ müssen wir noch einen regulären Ausdruck einsetzen: $\tau=(0|1)*$.
Damit erhalten wir den Ausdruck $0|(1(0|1)*)$.
\ifthenelse{\boolean{long}}{}{\end{comment}}

Zur Vereinfachung erlauben wir Variablen (Bezeichner) in regulären Ausdrücken:
\begin{defn}
Sei $B$ die Menge aller Variablen (Bezeichnungen). Ein regulärer Ausdruck der eine Variable $b$ aus $B$ enthält ist ein erweiterter regulärer Ausdruck.
Wenn $E$ ein erweiterter regulärer Ausdruck ist und $c$ eine Variable aus $B$, dann ist $c := E$ ist eine reguläre Definition.
\end{defn}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
Die Sprache der natürlichen Zahlen inkl. Null beschreiben wir durch den Ausdruck
\verb#0|((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)#.
Durch die Definition erweiterter regulärer Ausdrücke können wir nun komplexe Ausdrücke in die einzelnen Bestandteile kapseln und so
besser lesbare Ausdrücke schaffen.
Diesen Ausdruck können wir nun aufteilen indem wir die Teilausdrücke \verb#digit_not_null := (1|2|3|4|5|6|7|8|9)# und \verb#digit := 0 | digit_not_null# definieren.
Dann erhalten wir den wesentlich leichter verständlichen Ausdruck \verb#0|(digit_not_null digit*)#.

Mit erweiterten regulären Ausdrücken können wir nun einfach den Eingabestring in eine Token-Sequenz aufteilen.
\ifthenelse{\boolean{long}}{}{\end{comment}}
Übersetzen wir dazu den erweiterten regulären Ausdruck zu einer Funktion so beobachten wir:
\begin{\whichitem}
\item Terminale werden zu \verb|if|-Abfragen,
\item \verb|Q*| wird zu einem Schleifenkonstrukt,
\item \verb#Q|R# wird zu einer \verb|if, else if, else|-Abfrage wobei der \verb|else| Fall zu einem Ablehnen der Eingabe führt,
\item \verb|QR| bedeutet, dass zuerst \verb|Q| überprüft wird, danach \verb|R|.
\end{\whichitem}
\section{Grammatikalische Analyse}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
Der letzte Schritt der Syntaxanalyse ist die grammatikalische Analyse. In diesem Schritt wollen wir anhand der Token-Sequenz prüfen ob das Eingabewort in der Sprache der Grammatik enthalten ist. Die Verarbeitung einschließlich diesen Schrittes nennen wir ``Parsing''. Als Nebenprodukt wird oft ein Parse-Baum aufgebaut, der zusätzlich zur Reihenfolge der Tokens auch die Kapselung im Programm ausdrückt.
Hierzu verwenden wir das Beispiel aus dem Vorlesungsskriptum und werden uns auch weitgehend an diesem orientieren.
Wir entwerfen eine Grammatik für einfache arithmetische Ausdrücke, bestehend aus Zahlen, Operatoren (Addition und Multiplikation) und Klammern. Die Bindungsstärke von Operatoren
behandeln wir auf Syntax-Ebene nicht.
\ifthenelse{\boolean{long}}{}{\end{comment}}

Bei kontext-freien oder regulären Grammatiken werden wir fortan nur noch die Produktionsregeln mit unterstrichenen Nonterminalen anschreiben, da die Grammatik dadurch vollständig definiert wird:
\begin{\whichitem}
\item $V_N$ ist die Vereinigung über alle Symbole auf der linken Seite der Produktionsregeln (d.h. alle Nonterminale),
\item $V_T$ ist die Vereinigung aller unterstrichenen Zeichenfolgen (d.h. alle Terminale),
\item $S$, das Startsymbol ist (soweit nicht anders festgehalten) das erste aufgeführte Nonterminal,
\item $\Phi$ wird explizit angegeben.
\end{\whichitem}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
Wir definieren nun die Sprache der einfachen arithmetischen Ausdrücke durch:
\begin{\whichenum}
\item $E \to E \u{+} E$
\item $E \to E \u{*} E$
\item $E \to \u{(} E \u{)}$
\item $E \to \u{\text{num}}$
\end{\whichenum}

Wir sehen, dass diese Grammatik eine kontext-freie Grammatik ist. Außerdem sehen wir anhand von Regel 1 und 2, dass die Grammatik linksrekursiv ist.
Weiters können wir für den Satz \u{num + num * num} zwei mögliche Ableitungen finden. Wir verwenden dazu eine verkürzte Form der Darstellung aus Abschnitt \ref{subsec:parser}.
Die Vorgehensweise dabei nennt man auch Top-Down-Parsing.
\begin{\whichenum}
\item $E \to E \u{*} E \to E \u{*} E \u{+} E\to\u{\text{num+}}E\u{*}E\to\u{\text{num + num *}}E \to \u{\text{num + num * num}}$
\item $E \to E \u{+} E \to E \u{+} E \u{*} E\to\u{\text{num+}}E\u{*}E\to\u{\text{num + num *}}E \to \u{\text{num + num * num}}$
\end{\whichenum}
Dies zeigt, dass die Grammatik mehrdeutig ist.

Eine weitere Möglichkeit dies anschaulich darzustellen sind Parse-Trees. Ein Parse-Tree stellt einen konkreten Parse-Vorgang dar. Der Wurzel-Knoten das Startsymbol. Die Kinder jedes Knotens sind die einzelnen Terminale und Nonterminale die dieser Knoten produziert (von links nach rechts entsprechend der Grammatik). Die obigen Parse-Sequenzen lassen sich so darstellen:

\begin{tabular}{p{0.47\hsize}p{0.47\hsize}}
\begin{tikzpicture}[node distance=1.8cm, auto]
\node [state] (0) {E};

\node [state, below of=0, accepting] (1) {\u{+}};
\node [state, left of=1] (2) {E};
\node [state, right of=1] (3) {E};

\node [state, below of=3, accepting] (4) {\u{*}};
\node [state, left of=4] (5) {E};
\node [state, right of=4] (6) {E};

\node [state, below of=2, accepting] (7) {\u{num}};

\node [state, below of=5, accepting] (8) {\u{num}};
\node [state, below of=6, accepting] (9) {\u{num}};

\path [->] (0) edge (1);
\path [->] (0) edge (2);
\path [->] (0) edge (3);

\path [->] (3) edge (4);
\path [->] (3) edge (5);
\path [->] (3) edge (6);

\path [->] (2) edge (7);
\path [->] (5) edge (8);
\path [->] (6) edge (9);
\end{tikzpicture}
&
\begin{tikzpicture}[node distance=1.8cm, auto]
\node [state] (0) {E};

\node [state, below of=0, accepting] (1) {\u{*}};
\node [state, left of=1] (3) {E};
\node [state, right of=1] (2) {E};

\node [state, below of=3, accepting] (4) {\u{+}};
\node [state, left of=4] (5) {E};
\node [state, right of=4] (6) {E};

\node [state, below of=2, accepting] (7) {\u{num}};

\node [state, below of=5, accepting] (8) {\u{num}};
\node [state, below of=6, accepting] (9) {\u{num}};

\path [->] (0) edge (1);
\path [->] (0) edge (2);
\path [->] (0) edge (3);

\path [->] (3) edge (4);
\path [->] (3) edge (5);
\path [->] (3) edge (6);

\path [->] (2) edge (7);
\path [->] (5) edge (8);
\path [->] (6) edge (9);
\end{tikzpicture}
\end{tabular}

Das geparste Wort kann in den Blättern des Baumes von links nach rechts abgelesen werden. Hier ist die Mehrdeutigkeit ebenfalls sehr gut erkennbar.

Eine weitere Beobachtung ist, dass es ungünstig ist wenn es für unseren Parser nicht genügt, dass aktuelle Token zu kennen sondern für das Parsing auch weitere nachfolgende Tokens ermittelt werden müssen.
Ist das Eingabewort \verb|num|, so haben wir 3 Regeln die alle zutreffen könnten (ohne Kenntnis der nachfolgenden Tokens).
\ifthenelse{\boolean{long}}{}{\end{comment}}
\section{LL(1)-Grammatiken}
\begin{defn}[LL(1)-Grammatik]
Eine kontextfreie Grammatik $G$ ist eine LL(1)-Grammatik (ist in LL(1)-Form) wenn sie
\begin{\whichitem}
\item keine Linksrekursionen enthält (z.B. $L \to L \u{a}$)
\item keine Produktionen mit gleichen Präfixen für die selbe linke Seite enthält (z.B. $A \to \u{a} B$ und $A \to \u{a} C$)
\item ermöglicht immer in einem Schritt (d.h. nur mit Kenntnis des nächsten Tokens) zu entscheiden,
welche Produktionsregel zur Ableitung verwendet werden muss.
\end{\whichitem}
\end{defn}

LL(1) steht für ``\textbf{L}eft to right'', ``\textbf{L}eftmost derivation'', ``\textbf{1} Token Look-ahead''.

Wir definieren einfache Regeln zwecks Auflösung von:
\begin{\whichitem}
\item \textbf{Indirekten Linksrekursionen}

Gibt es Produktionen der Form $A \to \alpha B \beta$ sowie $B \to \gamma$, dann kann man die Produktion
$A \to \alpha \gamma \beta$ einfügen. Wenn $\alpha=\varepsilon$ ist können so indirekte Linksrekursionen \textbf{gefunden}, d.h. in direkte Linksrekursionen umgeformt werden.
Diese Umformung kann auch in anderen Fällen die Produktionen vereinfachen.
\item \textbf{Direkten Linksrekursionen}

Gibt es Produktionen der Form $A \to A \alpha$ und $A \to \beta$, dann kann man diese in Produktionen der Form $A \to \beta R$ sowie 
$R \to \alpha R | \varepsilon$ umwandeln.
\item \textbf{Linksfaktorisierungen}

Gibt es Produktionen der Form $A \to \alpha B$ sowie $A \to \alpha C$, wobei $\alpha$ der größte gemeinsame Präfix von $\alpha B$ und $\alpha C$ ist,
so können wir diese Produktion durch $A \to \alpha R$ und $R \to B | C$ ersetzen. Der größte gemeinsame Präfix einer Sequenz von Terminalen und Nonterminalen ist die größte
gemeinsame Zeichenkette dieser Sequenzen. Der größte gemeinsame Präfix von \u{if E then E else E} und \u{if E then E} ist \u{if E then E}.

\end{\whichitem}

Mit diesen Regeln können wir oftmals Grammatiken in äquivalente LL(1)-Grammatiken umformen.
Es gibt natürlich Grammatiken bei denen dies nicht möglich ist. In diesem Fall bleibt nur
die Möglichkeit eine andere Parsing-Methode zu verwenden oder die Sprache zu verändern.
\ifthenelse{\boolean{long}}{}{\begin{comment}}
\newpage
\begin{bsp} \qquad \\
\begin{tabular}{p{0.75\hsize}p{0.19\hsize}}
Überlegen wir uns einmal anhand eines kleineren Beispiels was eine direkte Linksrekursion eigentlich bedeutet und wie man diese intuitiv auflöst.
Wir werden anhand dieses Beispiels eine Herleitung der Regel für die direkte Linksrekursion skizzieren.&
\begin{\whichenum}
\item $A \to \u{b}$
\item \textcolor{red}{$A \to A \u{a}$}
\end{\whichenum}
\end{tabular}\\\begin{tabular}{p{0.75\hsize}p{0.19\hsize}}
Wir erkennen auf den ersten Blick, dass jedes Wort der Sprache dieser Grammatik wohl mit $\u{b}$ beginnen muss.
Dann folgen eine beliebige Anzahl von $\u{a}$. Als regulären Ausdruck könnte man schreiben \verb|ba*|
Versuchen wir nun die Sprache intuitiv umzubauen. Dazu ändern wir zunächst wie folgt die 2. Regel um:&
\begin{\whichenum}
\item $A \to \u{b}$
\item \textcolor{red}{$A \to \u{a} A$}
\end{\whichenum}
\\
Jetzt haben wir \verb|a*b| gebaut, also bauen wir ein neues Non-Terminal für die Produktionen der $\u{a}$, die
man erst nach einem $\u{b}$ produzieren können sollte.&
\begin{\whichenum}
\item $A \to \u{b}$
\item \textcolor{red}{$B \to \u{a} B$}
\end{\whichenum}
\end{tabular}\\\begin{tabular}{p{0.75\hsize}p{0.19\hsize}}
Nun können wir nur noch \verb|b| produzieren, daher fügen wir ein $B$ in die 1. Produktion ein. Außerdem würde die Rekursion von $B$ nie terminieren.&
\begin{\whichenum}
\item \textcolor{red}{$A \to \u{b} B$}
\item $B \to \u{a} B$
\end{\whichenum}
\\
Nun produzieren wir zuerst ein $\u{b}$ und dann beliebig viele $\u{a}$, allerdings terminiert die Rekursion nie. Wir fügen also eine Regel $B \to \varepsilon$ ein
und erhalten die richtig umgeformte Grammatik:&
\begin{\whichenum}
\item $A \to \u{b} B$
\item \textcolor{red}{$B \to \u{a} B | \varepsilon$}
\end{\whichenum}
\end{tabular}

Es ist auffällig, dass unsere Umformung der Form entspricht die in den Regeln beschrieben wurde.
\end{bsp}

\begin{bsp} \qquad \\
\begin{tabular}{p{0.7\hsize}p{0.24\hsize}}
In diesem Beispiel möchten wir nun auch die Regeln der Linksfaktorisierung und indirekte Linksrekursion durch intuitive Herangehensweise 
herleiten.
Gegeben sei die folgende Grammatik die arithmetische Ausdrücken einer bestimmten Form beschreibt:&
\vspace{-0.5cm}
\begin{\whichenum}
\item $E \to G$
\item $G \to E \u{+} E$
\item $G \to E \u{*} E$
\item $E \to \u{(} E \u{)}$
\item $E \to \u{(} \u{\text{num}} \u{)}$
\item $E \to \u{(} G \u{)} \u{/} \u{(} G \u{)}$
\end{\whichenum}
\end{tabular}\\
\begin{tabular}{p{\hsize}}
Versuchen wir nun zu Bestimmen: Gibt es Linksrekursionen oder gemeinsame Präfixe? Gibt es weitere Probleme bei dieser Grammatik?

In der Grammatik sind keine direkten Linksrekursionen. Regeln 2, 5 und 6 haben einen gemeinsamen Präfix ($\u{(}$).
Man sieht auch recht schnell, dass durch die Produktionen $E \to G \to E \u{*} E$ eine indirekte Linksrekursion entsteht.
\end{tabular}\\
\vfill
\begin{tabular}{p{0.7\hsize}p{0.24\hsize}}
Wenn wir uns überlegen wie man die gemeinsamen Präfixe entfernen kann wird man intuitiv auf die gleiche Idee kommen
die oben in den Regeln festgehalten wurde: Wir führen ein neues Non-Terminal ein welches die Produktion von ($\u{(}$) übernimmt
und anschließend einen der Reste produziert.
Wir erhalten dann die nebenstehende Grammatik.&
\vspace{-0.75cm}\begin{\whichenum}
\item $E \to G$
\item $G \to E \u{+} E$
\item $G \to E \u{*} E$
\item \textcolor{red}{$E \to \u{(} B$}
\item \textcolor{red}{$B \to E \u{)}$}
\item \textcolor{red}{$B \to \u{\text{num}} \u{)}$}
\item \textcolor{red}{$B \to G \u{)} \u{/} \u{(} G \u{)}$}
\end{\whichenum}
\end{tabular}\\\begin{tabular}{p{0.65\hsize}p{0.29\hsize}}
Wie können wir nun die indirekte Linksrekursion lösen?
Wir hatten sie durch die Produktionen $E \to G \to E \u{*} E$ erkannt. Versuchen wir nun diesen Zwischenschritt zu eliminieren.
Dazu können wir die Regel $G$ einfach ``einsetzen'' - d.h. aus Regel 1 werden 2 neue Regeln, aus Regel 7 werden sogar 4 neue Regeln (alle Kombinationen).&
\begin{\whichenum}
\item \textcolor{red}{$E \to E \u{+} E$}
\item \textcolor{red}{$E \to E \u{*} E$}
\item $E \to \u{(} B$
\item $B \to E \u{)}$
\item $B \to \u{\text{num}} \u{)}$
\item \textcolor{red}{$B \to E \u{+} E \u{)} \u{/} \u{(} E \u{*} E \u{)}$}
\item \textcolor{red}{$B \to E \u{+} E \u{)} \u{/} \u{(} E \u{+} E \u{)}$}
\item \textcolor{red}{$B \to E \u{*} E \u{)} \u{/} \u{(} E \u{*} E \u{)}$}
\item \textcolor{red}{$B \to E \u{*} E \u{)} \u{/} \u{(} E \u{+} E \u{)}$}
\end{\whichenum}
\end{tabular}

Lösen wir zunächst wieder die gemeinsamen Präfixe (Regeln 6-9).
Dadurch entstehen wieder neue gemeinsame Präfixe die dann gelöst werden müssen (Regeln 7-10): \\
\begin{tabular}{p{0.3\hsize}p{0.3\hsize}p{0.29\hsize}}
\begin{\whichenum}
\item $E \to E \u{+} E$
\item $E \to E \u{*} E$
\item $E \to \u{(} B$
\item $B \to E \u{)}$
\item[] \setcounter{enumi}{4}
\item $B \to \u{\text{num}} \u{)}$
\item \textcolor{red}{$B \to E C$}
\item \textcolor{red}{$C \to \u{+} E \u{)} \u{/} \u{(} E \u{*} E \u{)}$}
\item \textcolor{red}{$C \to \u{+} E \u{)} \u{/} \u{(} E \u{+} E \u{)}$}
\item \textcolor{red}{$C \to \u{*} E \u{)} \u{/} \u{(} E \u{*} E \u{)}$}
\item \textcolor{red}{$C \to \u{*} E \u{)} \u{/} \u{(} E \u{+} E \u{)}$}
\end{\whichenum}
&\begin{\whichenum}
\item $E \to E \u{+} E$
\item $E \to E \u{*} E$
\item $E \to \u{(} B$
\item $B \to E \u{)}$
\item[] \setcounter{enumi}{4}
\item $B \to \u{\text{num}} \u{)}$
\item $B \to E C$
\item \textcolor{red}{$C \to \u{+} E \u{)} \u{/} \u{(} E D$}
\item \textcolor{red}{$C \to \u{*} E \u{)} \u{/} \u{(} E D$}
\item \textcolor{red}{$D \to \u{+} E \u{)}$}
\item \textcolor{red}{$D \to \u{*} E \u{)}$}
\end{\whichenum}
&\begin{\whichenum}
\item $E \to E \u{+} E$
\item $E \to E \u{*} E$
\item $E \to \u{(} B$
\item \textcolor{red}{$B \to E F$}
\item \textcolor{red}{$F \to \u{)}$}
\item $B \to \u{\text{num}} \u{)}$
\item \textcolor{red}{$F \to C$}
\item $C \to \u{+} E \u{)} \u{/} \u{(} E D$
\item $C \to \u{*} E \u{)} \u{/} \u{(} E D$
\item $D \to \u{+} E \u{)}$
\item $D \to \u{*} E \u{)}$
\end{\whichenum}
\end{tabular}\\\begin{tabular}{p{0.65\hsize}p{0.29\hsize}}
Nun haben wir nur noch die direkte Linksrekursionen (Regeln 1 und 2).
Wir wissen aus dem vorherigen Beispiel bereits wie wir diese auflösen und erhalten die nebenstehende Grammatik.
Wir sehen, dass die Regeln genau unser intuitives Vorgehen festhalten und verallgemeinern.
Außerdem garantieren korrekte Anwendungen der Regeln, dass die Grammatik nach der
Umformung noch die gleiche Sprache beschreiben.&
\begin{\whichenum}
\item \textcolor{red}{$E \to \u{(} B R$}
\item \textcolor{red}{$R \to \u{+} E$}
\item \textcolor{red}{$R \to \u{*} E$}
\item \textcolor{red}{$R \to \varepsilon$}
\item $B \to E F$
\item $F \to \u{)}$
\item $B \to \u{(} \u{\text{num}} \u{)}$
\item $F \to C$
\item $C \to \u{+} E \u{)} \u{/} \u{(} E D$
\item $C \to \u{*} E \u{)} \u{/} \u{(} E D$
\item $D \to \u{+} E \u{)}$
\item $D \to \u{*} E \u{)}$
\end{\whichenum}
\end{tabular}
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}
\section{LL(1)-Tabellen}
LL(1)-Tabellen ermöglichen es einen generischen LL(1)-Parser zu schreiben, der mit
einer beliebigen LL(1)-Tabelle (und damit Sprache) arbeiten kann. Wir werden uns nun erarbeiten wie eine solche LL(1)-Tabelle berechnet werden kann.
Für die Definition der FIRST- und FOLLOW-Mengen stellen wir uns Nonterminale wieder
als Zustände in einem Graph oder eine Maschine vor.
\begin{defn}[FIRST-Menge]
Die FIRST-Menge eines Nonterminals $X$ ist die Menge aller Terminalsymbole die im Zustand $X$ \textbf{als erstes} geparst werden können.
Die FIRST-Menge eines Terminals $x$ ist immer das Terminalsymbol selbst.

Formal bedeutet dies:
\begin{\whichenum}
\item Wenn $x$ ein Terminal ist: $\text{FIRST}(x)=\gbr{x}$
\item Wenn die Grammatik Produktionsregeln enthält, so dass $X \to \ldots \to \varepsilon$, dann ist: $\varepsilon \in \text{FIRST}(X)$
\item Für jede Produktionsregel der Form $X \to Y_1 Y_2 \ldots Y_n$ ist $x \in \text{FIRST}(X)$, wenn $x \in \text{FIRST}(Y_i)$ und für alle
$Y_j$ mit $j < i$ gilt, dass $\varepsilon \in \text{FIRST}(Y_j)$.
\end{\whichenum}
Für aufeinanderfolgende Terminal- bzw. Nonterminalsymbole $X_1 X_2 \ldots X_n$:
\begin{\whichenum}
\item Wenn $x \in \text{FIRST}(X_i)$ und für alle $X_j$ mit $j < i$ gilt, dass $\varepsilon \in \text{FIRST}(X_j)$,
dann ist $x \in \text{FIRST}(X_1 X_2 \ldots X_n)$.
\item Wenn für alle $X_i$ $\varepsilon \in \text{FIRST}(X_i)$ ist, dann ist auch $\varepsilon \in \text{FIRST}(X_1 X_2 \ldots X_n)$.
\end{\whichenum}
\end{defn}

Aus dieser Definition folgt beispielsweise für einfache Regeln $A \to B$, dass die FIRST-Menge $\text{FIRST}(A) = \rbr{\text{FIRST}(B) \setminus \gbr{\varepsilon}}\cup \ldots$ ist.

\begin{defn}
Wir definieren die FIRST*-Menge als FIRST-Menge ohne $\varepsilon$ (zwecks Übersichtlichkeit):
\[\text{FIRST*}(X) = \text{FIRST}(X) \setminus \gbr{\varepsilon}.\]
\end{defn}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\begin{bsp}
Betrachten wir folgendes Beispiel:
\begin{align*}
A &\to \u{b} &\qquad&& A &\to \varepsilon \\
A &\to A \u{a} &\qquad&& B &\to \u{b} | \u{q} \\
A &\to A B C &\qquad&& C &\to A \u{c}
\end{align*}
Für diese Grammatik berechnen wir nun die FIRST- und FOLLOW-Mengen.
\begin{align*}
\text{FIRST}(\u{b}) &=& \gbr{\u{b}} & \tag{wird meist nicht aufgeschrieben da trivial} \\
\text{FIRST}(A) &=& &\gbr{\u{b}} \tag{durch die 1. Produktion} \\
                &\quad& \cup \quad &\text{FIRST*}(A) \tag{durch die 2. Produktion} \\
                &\quad& \cup \quad &\gbr{\u{a}} \tag{2. Produktion kann wegfallen d.h. $\varepsilon$ werden} \\
                &\quad& \cup \quad &\text{FIRST*}(A) \tag{durch die 3. Produktion} \\
                &\quad& \cup \quad &\text{FIRST*}(B) \tag{3. Produktion, wenn $A$ wegfällt} \\
                &\quad& \cup \quad &\gbr{\varepsilon} \tag{durch die 3. Produktion}
\end{align*}
Wir wissen aus der Mengenlehre, dass $M \cup M' = M$ mit $M' \subseteq M$ und können daher $\text{FIRST*}(A)$ weglassen:
\begin{align*}
                &=\gbr{\u{b}} \cup \gbr{\u{a}} \cup \text{FIRST*}(B) \cup \gbr{\varepsilon} \\
                &=\gbr{\u{b},\u{a},\varepsilon} \cup \text{FIRST*}(B)
\end{align*}
Um $\text{FIRST*}(B)$ zu erhalten müssen wir also zuerst $\text{FIRST}(B)$ ausrechnen:
\begin{align*}
\text{FIRST}(B) &= \gbr{\u{b}} \cup \gbr{\u{q}} \\
                &= \gbr{\u{b},\u{q}} \\
\text{FIRST}(A) &=\gbr{\u{b},\u{a},\varepsilon} \cup \gbr{\u{b},\u{q}} \\
                &=\gbr{\u{b},\u{a},\varepsilon,\u{q}}
\end{align*}
\begin{align*}
\text{FIRST}(C) &=\text{FIRST*}(A) \cup \gbr{\u{c}} \tag{da $A\to \varepsilon$ werden kann} \\
                &= \gbr{\u{b},\u{a},\u{q}} \cup \gbr{\u{c}} \\
                &= \gbr{\u{b},\u{a},\u{q},\u{c}}
\end{align*}
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}

\begin{defn}
Jede Eingabe des Parsers endet mit dem ``End of Input'' Symbol $\$$.
\end{defn}
\begin{defn}[FOLLOW-Menge]
Die FOLLOW-Menge eines Nonterminals $X$ ist die Menge aller Terminalsymbole die direkt auf Zustand $X$ \textbf{folgen} können.
Das heißt, alle Terminalsymbole die nach Abarbeitung des Zustands $X$ als erstes geparst werden können.

Formal bedeutet dies:
\begin{\whichenum}
\item Wenn $X$ das Startsymbol ist, dann ist $\$ \in \text{FOLLOW}(X)$
\item Für alle Regeln der Form $A \to \alpha B \beta$ ist $\text{FIRST*}(\beta) \subseteq \text{FOLLOW}(B)$
\item Für alle Regeln der Form $A \to \alpha B$ bzw. $A \to \alpha B \beta$ mit $\varepsilon \in \text{FIRST}(\beta)$
ist $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(B)$
\end{\whichenum}
\end{defn}
\ifthenelse{\boolean{long}}{}{\begin{comment}}
An dieser Stelle ist anzumerken, dass $\varepsilon$ nie in einer FOLLOW-Menge enthalten sein kann.
\newpage
\begin{bsp}
Betrachten wir das gleiche Beispiel wie zuvor:
\begin{align*}
A &\to \u{b} &\qquad&& A &\to \varepsilon \\
A &\to A \u{a} &\qquad&& B &\to \u{b} | \u{q} \\
A &\to A B C &\qquad&& C &\to A \u{c}
\end{align*}
\begin{align*}
\text{FOLLOW}(A) &=& &\gbr{\$} \tag{da $A$ das Startsymbol ist} \\
                 &\quad& \cup \quad &\gbr{\u{a}} \tag{durch die 2. Produktion} \\
                 &\quad& \cup \quad &\text{FIRST*}(B) \tag{durch die 3. Produktion} \\
                 &\quad& \cup \quad &\gbr{\u{c}} \tag{durch die 6. Produktion} \\
                 &=& &\gbr{\$, \u{a}} \cup \gbr{\u{b},\u{q}} \cup \gbr{\u{c}} \\
                 &=& &\gbr{\$, \u{a},\u{b},\u{q},\u{c}} \\
\text{FOLLOW}(B) &=& &\text{FIRST*}(C) \tag{durch die 3. Produktion} \\
                 &=& &\gbr{\u{b},\u{a},\u{q},\u{c}} \\
\text{FOLLOW}(C) &=& &\text{FOLLOW}(A) \tag{durch die 3. Produktion} \\
                 &=& &\gbr{\$, \u{a},\u{b},\u{q},\u{c}}
\end{align*}
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}

\begin{algo}[Parse-Table]
Der Parse-Table Algorithmus berechnet aus einer Grammatik eine Parse-Table (auch LL(1)-Tabelle) $M$.
\begin{\whichenum}
\item Für jede Produktion $X \to \alpha$:
\begin{\whichenum}
\item Für jedes Element $y \in \text{FIRST*}(\alpha)$ bzw. wenn $\alpha = y$:
\begin{\whichenum}
\item Füge $X \to \alpha$ in $M(X,y)$ ein.
\end{\whichenum}
\item Wenn $\varepsilon \in \text{FIRST}(\alpha)$:
\begin{\whichenum}
\item Für alle $y \in \text{FOLLOW}(X)$:
\begin{\whichenum}
\item Füge $X \to \alpha$ in $M(X,y)$ ein.
\end{\whichenum}
\end{\whichenum}
\end{\whichenum}
\end{\whichenum}
Leere Einträge in der LL(1)-Tabelle sind Fehlerfälle. Diese können auch explizit mit ERROR beschriftet werden.
\end{algo}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\newpage
\begin{bsp}
Betrachten wir das gleiche Beispiel wie zuvor:
\begin{align*}
A &\to \u{b} &\qquad&& A &\to \varepsilon \\
A &\to A \u{a} &\qquad&& B &\to \u{b} | \u{q} \\
A &\to A B C &\qquad&& C &\to A \u{c}
\end{align*}
Wir haben bereits die FIRST- und FOLLOW-Mengen berechnet, wir können also gleich den Algorithmus ausführen.
\[\begin{array}{|c|c|c|}
\hline
  & \text{FIRST}                              & \text{FOLLOW} \\\hline
A & \gbr{\u{b},\u{a},\varepsilon,\u{q}}       & \gbr{\$, \u{a},\u{b},\u{q},\u{c}} \\\hline
B & \gbr{\u{b},\u{q}}                         & \gbr{\u{b},\u{a},\u{q},\u{c}} \\\hline
C & \gbr{\u{b},\u{a},\u{q},\u{c}} & \gbr{\$, \u{a},\u{b},\u{q},\u{c}} \\ \hline
\end{array}\]
Wir beginnen mit der leeren LL(1)-Tabelle. Wir haben eine Zeile pro Non-Terminal und
eine Spalte je Terminal sowie eine Spalte für ``End of Input''. 
Ausführung für $A \to \u{b}$:
\[\begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a} & \u{b} & \u{c} & \u{q} & \$ \\\hline
A &       &       &       &       &    \\\hline
B &       &       &       &       &    \\\hline
C &       &       &       &       &    \\ \hline
\end{array} \to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a} & \u{b} & \u{c} & \u{q} & \$ \\\hline
A &       & \color{red}{A \to \u{b}} &       &       &    \\\hline
B &       &             &       &       &    \\\hline
C &       &             &       &       &    \\ \hline
\end{array}\]
Schritt 1b trifft auf diese Produktionsregel nicht zu.
Ausführung für $A \to A \u{a}$ und für $A \to ABC$ (auch hier wird die Bedingung aus Schritt 1b noch nicht erfüllt):
\[\to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a} & \u{b} & \hspace{-2pt} \u{c}\hspace{-2pt}  & \u{q} & \hspace{-2pt} \$\hspace{-2pt}  \\\hline
\hspace{-1pt} A \hspace{-1pt} & \hspace{-2pt} \color{red}{A \to A \u{a}} \hspace{-2pt} & \hspace{-2pt} A \to \u{b} \hspace{-2pt}   &       & \hspace{-2pt} \color{red}{A \to A \u{a}}\hspace{-2pt}  &    \\
  &               & \hspace{-2pt} \color{red}{A \to A \u{a}} \hspace{-2pt} &       &               &    \\\hline
\hspace{-1pt} B \hspace{-1pt} &               &               &       &               &    \\\hline
\hspace{-1pt} C \hspace{-1pt} &               &               &       &               &    \\ \hline
\end{array} \to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a} & \u{b} & \hspace{-2pt} \u{c}\hspace{-2pt}  & \u{q} & \hspace{-2pt} \$ \hspace{-2pt} \\\hline
A & \hspace{-2pt} A \to A \u{a} \hspace{-2pt} & \hspace{-2pt}  A \to \u{b}  \hspace{-2pt}  &       &\hspace{-2pt}  A \to A \u{a} \hspace{-2pt} &    \\
  & \hspace{-2pt} \color{red}{A \to A B C} \hspace{-2pt}   & \hspace{-2pt}  A \to A \u{a}\hspace{-2pt}  &       & \hspace{-2pt} \color{red}{A \to A B C}  \hspace{-2pt}  &    \\
  &               & \hspace{-2pt} \color{red}{A \to A B C}  \hspace{-2pt}  &       &               &    \\\hline
B &               &               &       &               &    \\\hline
C &               &               &       &               &    \\ \hline
\end{array}\]
Ausführung für $A \to \varepsilon$ (Schritt 1b):
\[\to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a} & \u{b}     & \u{c}             & \u{q}             & \$ \\\hline
A & A \to A \u{a}     & A \to \u{b}       & \color{red}{A \to \varepsilon} & A \to A \u{a}     & \color{red}{A \to \varepsilon} \\
  & A \to A B C       & A \to A \u{a}     &                   & A \to A B C       &    \\
  & \color{red}{A \to \varepsilon} & A \to ABC         &                   & \color{red}{A \to \varepsilon} &    \\
  &                   & \color{red}{A \to \varepsilon} &                   &                   &    \\\hline
B &                   &                   &                   &                   &    \\\hline
C &                   &                   &                   &                   &    \\ \hline
\end{array}\]
Ausführung für $B \to \u{b}|\u{q}$ und $C \to A \u{c}$
\[\to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a}             & \u{b}             & \u{c}             & \u{q}             & \$ \\\hline
A & A \to A \u{a}     & A \to \u{b}       & A \to \varepsilon & A \to A \u{a}     & A \to \varepsilon \\
  & A \to A B C       & A \to A \u{a}     &                   & A \to A B C       &    \\
  & A \to \varepsilon & A \to ABC         &                   & A \to \varepsilon &    \\
  &                   & A \to \varepsilon &                   &                   &    \\\hline
B &                   & \color{red}{B \to \u{b}}       &                   & \color{red}{B \to \u{q}}       &    \\\hline
C & \color{red}{C \to A \u{c}}     & \color{red}{C \to A \u{c}}     & \color{red}{C \to A \u{c}}     & \color{red}{C \to A \u{c}}     &    \\ \hline
\end{array}\]
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}

\begin{defn}
Eine Grammatik ist eine LL(1)-Grammatik, wenn die berechnete LL(1)-Tabelle keine Mehrfacheinträge hat.
\end{defn}

\begin{defn}
Eine Parsing-Tabelle stellt einen vollständigen Parse-Vorgang dar.
Jede Zeile entspricht einem Bearbeitungsschritt im Parse-Vorgang.
In Spalten werden Stack, Eingabe und die angewandte Produktionsregel aufgetragen.

\begin{algo}[Parsing mit Parsing-Tabelle und LL(1)-Tabelle]
Sei $X$ das oberste Stack-Element, $t$ das aktuelle Token der Eingabe $w$ und $\mathcal{L}$ die von der Grammatik akzeptierte Sprache.
\begin{\whichenum}
\item Wenn $X$ ein Non-Terminal ist:
\begin{\whichenum}
\item Nimm den Wert von $M(X,t)$
\item Ist der Eintrag leer oder ein Fehlereintrag: Abbruch ($w \not \in \mathcal{L}$).
\item Sonst: Ersetze das oberste Stack-Element $X$ durch Produktion in umgekehrter Reihenfolge ($WVU$ wenn $M(X,t)=X\to UVW$).
\end{\whichenum}
\item Andernfalls ($X$ ist ein Terminal):
\begin{\whichenum}
\item Wenn $X=t=\$$: Parsing erfolgreich ($w \in \mathcal{L}$).
\item Sonst, wenn $X=t\neq\$$, dann nimm $X$ vom Stack und gehe zum nächsten Token im Input.
\item Sonst: Abbruch ($w \not \in \mathcal{L}$).
\end{\whichenum}
\end{\whichenum}
\end{algo}
\end{defn}

Diese Definition kann für andere Parser leicht angepasst werden.

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\newpage
\begin{bsp}
Gegeben sei die folgende Grammatik (ähnlich der Grammatik aus dem vorherigen Beispiel):
\begin{align*}
A &\to A \u{a} &\qquad&& B &\to \u{b} | \u{q} \\
A &\to A B C &\qquad&& C &\to A \u{c} \\
A &\to \varepsilon &\qquad&& & \\
\end{align*}
Zeigen oder widerlegen Sie, dass das Wort $\u{abbqa}$ von der Grammatik akzeptiert wird.
Zeigen oder widerlegen Sie, dass das Wort $\u{abc}$ von der Grammatik akzeptiert wird.

\textit{Lösung:} Wir formen die Grammatik zu einer LL(1)-Grammatik um, berechnen dann die LL(1)-Tabelle und beweisen mittels einer Parsing-Tabelle, dass
das gegebene Wort von der Grammatik akzeptiert wird.
\[
\begin{array}{l}
A \to A \u{a} \\
A \to A B C \\
A \to \varepsilon \\
B \to \u{b} | \u{q} \\
C \to A \u{c}\end{array}
\quad \Ra \quad
\begin{array}{l}
\color{red}{A \to R} \\
\color{red}{R \to \u{a} R} \\
\color{red}{R \to B C R} \\
\color{red}{R \to \varepsilon} \\
B \to \u{b} | \u{q} \\
C \to A \u{c}\end{array}
\quad \Ra \quad
\begin{array}{l}
\color{red}{A \to \u{a} A} \\
\color{red}{A \to B C A} \\
\color{red}{A \to \varepsilon} \\
B \to \u{b} | \u{q} \\
C \to A \u{c}\end{array}
\]
Anhand der FIRST- und FOLLOW-Mengen ist bereits erkennbar, dass die Mehrdeutigkeiten behoben sind.
\begin{align*}
\text{FIRST}(B) &=& &\gbr{\u{b},\u{q}} \\
\text{FIRST}(A) &=& &\gbr{\u{a}} \cup \text{FIRST*}(B) \cup \gbr{\varepsilon} &=& \gbr{\u{a},\u{b},\u{q},\varepsilon} \\
\text{FIRST}(C) &=& &\text{FIRST*}(A) \cup \gbr{\u{c}}  &=& \gbr{\u{a},\u{b},\u{q},\u{c}}
\end{align*}
\begin{align*}
\text{FOLLOW}(A) &=& &\gbr{\$} \cup \text{FOLLOW}(A) \cup \gbr{\u{c}} &=& \gbr{\$,\u{c}} \\
\text{FOLLOW}(B) &=& &\text{FIRST*}(C) &=& \gbr{\u{a},\u{b},\u{q},\u{c}} \\
\text{FOLLOW}(C) &=& &\text{FIRST*}(A) \cup \text{FOLLOW}(A) &=& \gbr{\u{a},\u{b},\u{q},\$,\u{c}}
\end{align*}
Wir können nun die LL(1)-Tabelle berechnen. Dazu führen wir im ersten Schritt die Regeln für die FIRST-Menge des Non-Terminals $A$ durch:
\[\begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a}         & \u{b}         & \u{c}         & \u{q}         & \$         \\\hline
A &               &               &               &               &            \\\hline
B &               &               &               &               &            \\\hline
C &               &               &               &               &            \\ \hline
\end{array} \to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a}         & \u{b}         & \u{c}         & \u{q}         & \$         \\\hline
A & A \to \u{a} A & A \to B C A   &               & A \to B C A   &            \\\hline
B &               &               &               &               &            \\\hline
C &               &               &               &               &            \\ \hline
\end{array}\]
Da $\varepsilon$ in der FIRST-Menge ist, führen wir im zweiten Schritt die Regeln für die FOLLOW-Menge des Non-Terminals $A$ durch:
\[ \to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a}         & \u{b}         & \u{c}             & \u{q}         & \$                \\\hline
A & A \to \u{a} A & A \to B C A   & A \to \varepsilon & A \to B C A   & A \to \varepsilon \\\hline
B &               &               &                   &               &                   \\\hline
C &               &               &                   &               &                   \\ \hline
\end{array}\]
Nun noch $B$ und $C$:
\[ \to \begin{array}{|l|l|l|l|l|l|}
\hline
  & \u{a}         & \u{b}         & \u{c}             & \u{q}         & \$                \\\hline
A & A \to \u{a} A & A \to B C A   & A \to \varepsilon & A \to B C A   & A \to \varepsilon \\\hline
B &               & B \to \u{b}   &                   & B \to \u{q}   &                   \\\hline
C & C \to A \u{c} & C \to A \u{c} & C \to A \u{c}     & C \to A \u{c} &                   \\ \hline
\end{array}\]
Diesmal haben wir keine Mehrfach-Einträge. Diese Grammatik ist also eine LL(1)-Grammatik. Die Parsing-Tabelle für $\u{abbqa}$ sieht dann wie folgt aus:
\[\begin{array}{|l|r|l|}
\hline
\textbf{Stack}                    & \textbf{Input}  & \textbf{Produktion} \\ \hline
\$ A                              & \u{abbqa}\$     & A \to \u{a} A \\
\$ A \u{a}                        & \u{abbqa}\$     &  \\
\$ A                              &  \u{bbqa}\$     & A \to BCA \\
\$ A C B                          &  \u{bbqa}\$     & B \to \u{b} \\
\$ A C \u{b}                      & \u{bbqa}\$      &  \\
\$ A C                            & \u{bqa}\$       & C \to A \u{c} \\
\$ A \u{c} A                      & \u{bqa}\$       & A \to BCA \\
\$ A \u{c} ACB                    & \u{bqa}\$       & B \to \u{b} \\
\$ A \u{c} AC\u{b}                & \u{bqa}\$       &  \\
\$ A \u{c} AC                     & \u{qa}\$        & C \to A \u{c} \\
\$ A \u{c} A\u{c}A                & \u{qa}\$        & A \to BCA \\
\$ A \u{c} A\u{c}ACB              & \u{qa}\$        & B \to \u{q} \\
\$ A \u{c} A\u{c}AC\u{q}          & \u{qa}\$        &  \\
\$ A \u{c} A\u{c}AC               & \u{a}\$         & C \to A \u{c} \\
\$ A \u{c} A\u{c}A\u{c}A          & \u{a}\$         & A \to \u{a}A \\
\$ A \u{c} A\u{c}A\u{c}A\u{a}     & \u{a}\$         &  \\
\$ A \u{c} A\u{c}A\u{c}A          & \$              & A \to \varepsilon \\
\$ A \u{c} A\u{c}A\u{c}           & \$              & \text{FAIL} \\ \hline
\end{array}\]
Wir haben somit \textbf{widerlegt}, dass die gegebene Grammatik das Wort $\u{abc}$ akzeptiert.
\[\begin{array}{|l|r|l|}
\hline
\textbf{Stack}        & \textbf{Input} & \textbf{Produktion} \\ \hline
\$ A                  & \u{abc}\$      & A \to \u{a} A \\
\$ A \u{a}            & \u{abc}\$      &  \\
\$ A                  &  \u{bc}\$      & A \to BCA \\
\$ A C B              &  \u{bc}\$      & B \to \u{b} \\
\$ A C \u{b}          & \u{bc}\$       &  \\
\$ A C                & \u{c}\$        & C \to A \u{c} \\
\$ A \u{c} A          & \u{c}\$        & A \to \varepsilon \\
\$ A \u{c}            & \u{c}\$        & \\
\$ A                  & \$             & A \to \varepsilon \\
\$                    & \$             & \text{ACCEPT} \\ \hline
\end{array}\]
\vspace{-0.2cm}
Mit dieser Parsing-Tabelle wurde \textbf{gezeigt}, dass die Grammatik das Wort $\u{abc}$ akzeptiert.
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}

\ifthenelse{\boolean{long}}{}{\begin{comment}}
\newpage
Das folgende Beispiel ist ein Prüfungsbeispiel aus dem Jahr 2011.
\begin{bsp}
Erstellen Sie FIRST- und FOLLOW-Mengen aller Non-Terminale der folgenden Grammatik:
\begin{align*}
S &\to A \\
A &\to AB \\
A &\to \u{a} \\
B &\to CA \\
B &\to \u{b} \\
C &\to \u{c} D \\
C &\to \u{c} \\
C &\to \varepsilon \\
D &\to \u{c} \\
D &\to \u{b}
\end{align*}
\begin{align*}
\text{FIRST}(S) &= \text{FIRST*}(A)=\gbr{\u{a}} \\
\text{FIRST}(A) &= \gbr{\u{a}} \\
\text{FIRST}(B) &= \gbr{\u{b}} \cup \text{FIRST*}(C) \cup \text{FIRST*}(A)=\gbr{\u{a},\u{b},\u{c}} \\
\text{FIRST}(C) &= \gbr{\u{c},\varepsilon} \\
\text{FIRST}(D) &= \gbr{\u{c},\u{b}}
\end{align*}
\begin{align*}
\text{FOLLOW}(S) &= \gbr{\$} \\
\text{FOLLOW}(A) &= \text{FOLLOW}(S) \cup \text{FIRST*}(B) \cup \text{FOLLOW}(B)=\gbr{\$,\u{a},\u{b},\u{c}} \\
\text{FOLLOW}(B) &= \text{FOLLOW}(A)=\gbr{\$,\u{a},\u{b},\u{c}} \\
\text{FOLLOW}(C) &= \text{FIRST*}(A)=\gbr{\u{a}} \\
\text{FOLLOW}(D) &= \text{FOLLOW}(C)=\gbr{\u{a}}
\end{align*}
Diese Grammatik ist nicht LL(1) aufgrund von Mehrdeutigkeiten und einer Linksrekursion ($A \to AB$).

Wir werden zunächst die Grammatik vereinfachen indem wir $D$ einsetzen. Dann lösen wir die Linksrekursion.
\[
\begin{array}{l}
S \to A \\
A \to AB \\
A \to \u{a} \\
B \to CA \\
B \to \u{b} \\
C \to \u{c} D \\
C \to \u{c} \\
C \to \varepsilon \\
D \to \u{c} \\
D \to \u{b}
\end{array}
\quad \Ra \quad
\begin{array}{l}
S \to A \\
A \to AB \\
A \to \u{a} \\
B \to CA \\
B \to \u{b} \\
\color{red}{C \to \u{cc}} \\
\color{red}{C \to \u{cb}} \\
C \to \u{c} \\
C \to \varepsilon \\
\quad
\end{array}
\quad \Ra \quad
\begin{array}{l}
S \to A \\
\color{red}{A \to \u{a} R} \\
\color{red}{R \to BR} \\
\color{red}{R \to \varepsilon} \\
B \to CA \\
B \to \u{b} \\
C \to \u{cc} \\
C \to \u{cb} \\
C \to \u{c} \\
C \to \varepsilon \\
\end{array}
\quad \Ra \quad
\begin{array}{l}
\quad \\
A \to \u{a} R \\
R \to BR \\
R \to \varepsilon \\
B \to CA \\
B \to \u{b} \\
C \to \u{cc} \\
C \to \u{cb} \\
C \to \u{c} \\
C \to \varepsilon \\
\end{array}
\]
Im letzten obigen Schritt haben wir hier $S \to A$ gestrichen und $A$ stattdessen zum Startsymbol machen.

Wir setzen nun $C$ ein und anschließend $A$ (die Regel bleibt trotzdem erhalten, da sie nur verschwindet wenn sie gar nicht mehr verwendet wird, hier ist $A$ allerdings das Startsymbol).
\[\Ra \quad
\begin{array}{l}
A \to \u{a} R \\
R \to BR \\
R \to \varepsilon \\
\color{red}{B \to A} \\
B \to \u{b} \\
\color{red}{B \to \u{cc} A} \\
\color{red}{B \to \u{cb} A} \\
\color{red}{B \to \u{c} A} \\
\end{array}
\quad \Ra \quad
\begin{array}{l}
A \to \u{a} R \\
R \to BR \\
R \to \varepsilon \\
\color{red}{B \to \u{a} R} \\
B \to \u{b} \\
\color{red}{B \to \u{cca} R} \\
\color{red}{B \to \u{cba} R} \\
\color{red}{B \to \u{ca} R} \\
\end{array}
\quad \Ra \quad
\begin{array}{l}
A \to \u{a} R \\
\color{red}{R \to \u{a} R R} \\
\color{red}{R \to \u{b} R} \\
\color{red}{R \to \u{cca} R R} \\
\color{red}{R \to \u{cba} R R} \\
\color{red}{R \to \u{ca} R R} \\
R \to \varepsilon \\
\end{array}\]
Im mittleren obigen Schritt hat die Grammatik noch immer Mehrdeutigkeiten. Wir können über $R \to BR$ beliebig viele $B$ produzieren. Jedes $B$ kann selbst aber weitere $R$ produzieren.
Um uns diesem Problem weiter anzunähern wollen wir $B$ aus $R$ eliminieren. Dazu setzen wir im letzten obigen Schritt $B$ in $R$ ein.

Wir erhalten Konstrukte der Form $R \to \alpha R R | \varepsilon$. Das ist äquivalent zu $R \to \alpha R$. Anschließend lösen wir den gemeinsamen Präfix $\u{c}$ auf.
\[\Ra \quad
\begin{array}{l}
A \to \u{a} R \\
\color{red}{R \to \u{a} R} \\
R \to \u{b} R \\
\color{red}{R \to \u{cca} R} \\
\color{red}{R \to \u{cba} R} \\
\color{red}{R \to \u{ca} R} \\
R \to \varepsilon \\
\end{array}
\quad \Ra \quad
\begin{array}{l}
A \to \u{a} R \\
R \to \u{a} R \\
R \to \u{b} R \\
\color{red}{R \to \u{c} C R} \\
R \to \varepsilon \\
\color{red}{C \to \u{ca}} \\
\color{red}{C \to \u{ba}} \\
\color{red}{C \to \u{a}} \\
\end{array}
\]
Damit haben wir eine LL(1)-Grammatik erhalten.
\end{bsp}
\ifthenelse{\boolean{long}}{}{\end{comment}}