<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\begin{slide}{Linksrekursion}

FÃ¼r prÃ¤diktive Parser (ein Zeichen Vorschau) wird das schwer:

\begin{verbatim}
exp -&gt; exp + term | ...
\end{verbatim}

Def: eine Grammatik $G=(\Sigma,V,S,R)$ heiÃŸt linksrekursiv,
wenn $\exists v \in V, w \in (\Sigma\cup V)^*: v \to_R^+ v\cdot w$.

Satz: zu jeder CFG $G$ gibt es eine nicht linksrekursive CFG $G'$
mit $L(G')=L(G)$.

einfachster Fall: Grammatik mit Regeln $\{A \to A b, A \to c \}$

\end{slide}

\begin{slide}{Linksrekursion (II)}

Def: CFG $G=(\Sigma,V,S,R)$ ist in Greibach-Normalform,
falls fÃ¼r jede Regel $(l\to r)\in R$ gilt: $r\in \Sigma V^*$.

mÃ¶glich ist auch: \dots $r\in \Sigma(V\cup\Sigma)^*$

Satz: zu jeder CFG $G$ gibt es eine CFG $G'$ in Greibach-Normalform
mit $L(G)\setminus{\epsilon}=L(G')$.

Aufgaben (evtl. autotool): Greibach-Normalform von
\begin{itemize}
\item $(\{a,b\},\{S,T\},S,\{S\to TS\mid b, T\to ST\mid a\})$
\item $(\{a,b\},\{S,T\},S,\{S\to TT\mid b, T\to SS\mid a\})$
\end{itemize}

\end{slide}
</pre></body></html>