Linksrekursion

Für prädiktive Parser (ein Zeichen Vorschau) wird das schwer:

exp -> exp + term | ...

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 ^. 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$Ab, A$\to$c}