Unifikační gramatika: Porovnání verzí
Smazaný obsah Přidaný obsah
m + kategorie & anglické termíny |
m robot: přidáno {{Autoritní data}} |
||
Řádek 22: | Řádek 22: | ||
Zvláštností unifikačních gramatik je, že přijímají i [[kontextový jazyk|kontextové jazyky]] a algoritmus pro jejich [[parsing]] je [[NP-úplnost|NP-těžký]]. |
Zvláštností unifikačních gramatik je, že přijímají i [[kontextový jazyk|kontextové jazyky]] a algoritmus pro jejich [[parsing]] je [[NP-úplnost|NP-těžký]]. |
||
{{Autoritní data}} |
|||
[[Kategorie:Formální jazyky]] |
[[Kategorie:Formální jazyky]] |
Verze z 9. 8. 2021, 21:14
Unifikační gramatika (anglicky unification grammar nebo model-theoretic grammar) je bezkontextová gramatika doplněná o pravidla popisující unifikaci nad strukturami rysů vázanými na každý vrchol derivačního stromu. Jedná se o zobecnění atributových gramatik.
Každý terminál (potažmo preterminál) má přiřazenu strukturu rysů a každé pravidlo přidává do derivačního stromu rovnice nad těmito strukturami. Jednoduchý příkladem je například tato gramatika fragmentu angličtiny:
Bezkontextové pravidlo | Unifikační rovnice |
---|---|
Zvláštností unifikačních gramatik je, že přijímají i kontextové jazyky a algoritmus pro jejich parsing je NP-těžký.