%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Links-Rekursion}

\begin{verbatim}
Ausdruck = Name oder Literal 
   oder Zeichen "(" ; Ausdruck ; Zeichen ")"
   oder Ausdruck Operator Ausdruck
\end{verbatim}

Def: eine Variable $A$ in CFG $G$ heißt links-rekursiv,
falls $\exists w \in (V \cup \Sigma)^* : A \to_R^+ A w$.

Aufgabe: Wie kann man entscheiden,
ob gegebenes $G$ links-rekursiv ist?

\end{slide}

\begin{slide}{Links-Rekursion (II)}

Satz: Zu jeder CFG $G$ gibt es CFG $G'$ ohne Links-Rekursion
mit $L(G)=L(G')$.

Beweis (Idee):  ersetze $\{A \to A w , A\to r \}$ 
durch $\{A \to r B , B \to \epsilon, B \to w B\}$.

Aufgaben (evtl. autotool): entferne Links-Rekursionen aus
\begin{itemize}
\item
  $S \to Aa \mid b, A \to Ac \ Sd \mid \epsilon$.
\item
  $S \to TS \mid  b, T \to ST \mid a$
\item
  $S \to b \mid TT, T \to a \mid SS$
\end{itemize} 

\end{slide}
