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}



Johannes Waldmann 2008-01-24