KNF Linksrekursion < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:36 Fr 19.02.2010 | | Autor: | RalU |
| Aufgabe | Um direkte Linksrekursion in einer KNF zu eliminieren, gibt es folgende Regeln:
1) Produktionen ordnen:
A->A [mm] \alpha_{1} [/mm] | A [mm] \alpha_{2} [/mm] | ... | A [mm] \alpha_{k} [/mm] | [mm] \beta_{1} [/mm] | [mm] \beta_{2} [/mm] | ... | [mm] \beta_{m}
[/mm]
2) Folgende Ersetzung durchführen:
A -> [mm] \beta_{1} [/mm] A' | [mm] \beta_{2} [/mm] A' | ... | [mm] \beta_{m} [/mm] A'
A'-> [mm] \alpha_{1} [/mm] A' | [mm] \alpha_{2} [/mm] A' | ... | [mm] \alpha_{k} [/mm] A' | [mm] \varespilon [/mm] |
Für die linksrekursive Produktion S -> S + K|K
würde bei Anwendung dieser Regeln folgndes rauskommen:
S -> KS'
S' -> + S' | [mm] \varepsilon
[/mm]
Wenn ich nun die neuen Produktionsregeln verwende, muss ich aber bei Ableitung von S mein K in jedem Fall zuerst ausführen. Das mußte ich vorher (bei der alten linksrekursiven Produktion) ja nicht. Ist das dann nicht eigentlich fehlerhaft? Was ist eigentlich der Grund, warum ich das K vor mein S' setzen muss (bei S -> KS') ?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 So 21.02.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
