Greibach-Normalform

(benannt nach Sheila Greibach) Die Javascriptelemente dieser Seite funktionieren am Besten mit dem IE (getestet an Version 6.0). Eine alternative Darstellung steht zur Verfügung. Ziel: Jede Regel hat die Form A - > a W mit A aus N, a aus T und W aus N* (-Regeln ausgenommen) Start:kontextfreie Grammatik ohne Linksrekursion und Kettenregeln Voraussetzung: Für jede kontextfreie Grammatik gibt es eine äquivalente Grammatik in GNF. Fragen:
Gegeben eine Regel S -> b. Was ist zu tun? Gar nichts, die Regel ist bereits im GNF-Format. a muss durch A ersetzt werden In allen Regeln, in denen A als linke Regelseite vorkommt, muss es durch a ersetzt werden <<Klick hier>> für Antwortmöglichkeiten	Antwort i) ist richtig. Die Regel entspricht bereits dem GNF-Format. W ist in diesem Fall leer. <<Klick hier>> für Antwort
Gegeben eine Regel X-> x y. Was ist zu tun? Gar nichts, die Regel ist bereits im GNF-Format. y muss zu einem Nichtterminal z.B. Y verändert werden; die modifizierte Regel heißt dann X -> x Y x muss zu einem Nichtterminal z.B. X verändert werden; die modifizierte Regel heißt dann X -> X y <<Klick hier>> für Antwortmöglichkeiten	Antwort ii) ist richtig. Die rechte Regelseite muss mit einem Terminalsymbol anfangen, darauf dürfen dann nur noch beliebig viele Nichtterminale folgen. Für das entsprechende Terminal wird ein noch nicht vorhandenes Nichtterminal eingeführt. Zusätzlich muss es die Regel Nichtterminal -> Terminal geben. <<Klick hier>> für Antwort
Gegeben eine Grammatik mit den Regeln S -> a A, A -> S A und A -> b c d. Was ist zu tun? Gar nichts, alle Regeln sind bereits im GNF-Format. Die zweite Regel ist nicht korrekt: S muss durch a A (aus der ersten Regel) ersetzt werden: A -> a A A. Zweite und dritte Regel sind noch nicht korrekt. Für c und d muss es neue Nichtterminale und Regeln C -> c/ D->d geben. In der zweiten Regel ersetzt man S durch a A (aus der ersten Regel): A -> a A A. <<Klick hier>> für Antwortmöglichkeiten	Antwort iii) ist richtig. Startet eine Regel mit einem Nichtterminal A so müssen für jede Regel in denen A die linke Regelseite ist (sogenannte A-Regeln) neue Regeln eingeführt werden, in denen A durch die jeweils rechte Regelseite ersetzt wird. Dieser Vorgang ist rekursiv, d.h. die jetzigen Regeln müssen noch nicht der GNF entsprechen. Es gibt ein effizientes Verfahren, um alle Regeln effektiv umzuwandeln und keine Regel auszulassen. <<Klick hier>> für Antwort
*Gegeben die Regeln Liste -> Eintrag Liste und Eintrag -> foo (mit Liste und Eintrag aus N, * und foo aus T). Was ist zu tun?** Gar nichts, die Regeln sind bereits im GNF-Format. foo muss Eintrag in der ersten Regel ersetzen: Liste -> * foo Liste. Für 'Eintrag Liste' muss ich ein neues Nichtterminal z.B. EiLi einführen. Anstelle der alten Regel gibt es zwei neue Regeln: Liste -> * EiLi und EiLi -> Eintrag Liste. <<Klick hier>> für Antwortmöglichkeiten	Antwort i) ist richtig. Die Regeln entsprechen voll dem GNF-Format. <<Klick hier>> für Antwort

2.3.3 Greibach-Normalform (GNF):