NORMÁLNÍ FORMA GREIBACHOVÉ

Základní
Rozšiřující

Jedna ze standardizací podoby pravidel ↗bezkontextové gramatiky. Jestliže obecná bezkontextová gramatika obsahuje přepisovací pravidla typu X → α, kde X je neterminální symbol a α je řetězec složený z terminálů a/nebo neterminálů, pak bezkontextová gramatika v n.f.G. obsahuje jen pravidla jediného typu: X → aα, kde X je neterminální symbol, a je symbol terminální, α je řetězec buď prázdný, nebo složený výhradně z neterminálů (viz také ↗terminál a neterminál v syntaktické struktuře). Platí, že každý ↗bezkontextový jazyk s výjimkou takového, který obsahuje prázdný řetězec, se dá vygenerovat nějakou gramatikou v n.f.G. (prázdný řetězec se však v případě potřeby dá vygenerovat jediným zvláštním pravidlem S → λ, kde S je počáteční symbol gramatiky a λ prázdný řetězec). Znamená to, že pravidla každé bezkontextové gramatiky (s uvedenou výjimkou) lze převést do n.f.G. Generování/analýza bezkontextového jazyka v n.f.G. má tu výhodu, že pravá strana každého pravidla začíná terminálním symbolem, což umožňuje rychlejší ↗parsing, jelikož je odstraněna levá rekurze a aktuální symbol v právě zpracovávaném vstupu se snadno a rychle porovná s prvním symbolem pravidel gramatiky, přičemž se na aktuální vstup mohou aplikovat jen ta pravidla, jež mají terminál na své pravé straně roven aktuálnímu symbolu na vstupu. Gramatice v n.f.G. přesně odpovídá koncept zásobníkového automatu. Viz také ↗normální forma Chomského.

Citace
Vladimír Petkevič (2017): NORMÁLNÍ FORMA GREIBACHOVÉ. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/NORMÁLNÍ FORMA GREIBACHOVÉ (poslední přístup: 21. 11. 2024)

CzechEncy – Nový encyklopedický slovník češtiny

Všechna práva vyhrazena © Masarykova univerzita, Brno 2012–2020

Provozuje Centrum zpracování přirozeného jazyka