In der Informatik und formellen Sprachtheorie ist eine Grammatik ohne Zusammenhänge in Greibach normale Form, wenn die Rechten der ganzen Produktion mit einem Endsymbol anfangen, das fakultativ von einigen Variablen gefolgt ist. Eine nichtstrenge Form erlaubt eine Ausnahme dieser Format-Beschränkung, für dem leeren Wort (Epsilon, ε) zu erlauben, ein Mitglied der beschriebenen Sprache zu sein. Die normale Form trägt den Namen von Sheila Greibach.

Genauer ist eine Grammatik ohne Zusammenhänge in Greibach normale Form, wenn alle Produktionsregeln von der Form sind:

oder

wo A ein Nichtendsymbol ist, ist α ein Endsymbol,

ist (vielleicht leer) die Folge von Nichtendsymbolen nicht einschließlich des Anfang-Symbols, S ist das Anfang-Symbol, und ε ist das leere Wort.

Bemerken Sie, dass die Grammatik ohne linken recursions sein muss.

Jede Grammatik ohne Zusammenhänge kann in eine gleichwertige Grammatik in Greibach normale Form umgestaltet werden. (Einige Definitionen denken nicht, dass die zweite Form der Regel erlaubt wird, in welchem Fall eine Grammatik ohne Zusammenhänge, die das leere Wort erzeugen kann, nicht so umgestaltet werden kann.) Insbesondere gibt es einen Aufbau, der sicherstellt, dass die resultierende normale Form-Grammatik der Größe am grössten Teil von O (n) ist, wo n die Größe der ursprünglichen Grammatik ist. Diese Konvertierung kann verwendet werden, um zu beweisen, dass jede Sprache ohne Zusammenhänge durch einen nichtdeterministischen pushdown Automaten akzeptiert werden kann.

In Anbetracht einer Grammatik in GNF und einer ableitbaren Schnur in der Grammatik mit der Länge n wird jeder verfeinernde parser an der Tiefe n hinken.

Siehe auch

• Backus-Naur bilden
• Chomsky normale Form
• Kuroda normale Form

Referenzen

• John E. Hopcroft und Jeffrey D. Ullman, Einführung in Automaten-Theorie, Sprachen und Berechnung, Addison-Wesley Publishing, Massachusetts, 1979 Lesend. Internationale Standardbuchnummer 0 201 02988 X. (Sieh Kapitel 4.)
• Norbert Blum und Robert Koch: Greibach Normale Wieder besuchte Form-Transformation. Information und Berechnung 150 (1), 1999, Seiten 112-118 Vorabdruck