Cesko.wiki Unifikační gramatika
Technology
12 hours ago
8
4
2
Author
Albert FloresUnifikač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 |
|---|---|
| \textrm{S} \rightarrow \textrm{NP} \, \textrm{VP} | \widehat{\textrm{S}}=\widehat{\textrm{VP}} \sqcup [\textrm{SUBJ:} \, \widehat{\textrm{NP}}] |
| \textrm{VP} \rightarrow \textrm{V} \, \textrm{NP} | \widehat{\textrm{VP}}=\widehat{\textrm{V}} \sqcup [\textrm{DOBJ:} \, \widehat{\textrm{NP}}] |
| \textrm{NP} \rightarrow \textrm{N} | \widehat{\textrm{NP}}=\widehat{\textrm{N}} |
| \textrm{N} \rightarrow \textrm{boys} | [\textrm{LEX}: \, \text{‘boy’}] |
| \textrm{N} \rightarrow \textrm{books} | [\textrm{LEX}: \, \text{‘book’}] |
| \textrm{V} \rightarrow \textrm{read} | [\textrm{LEX}: \, \text{‘read’}] |
Zvláštností unifikačních gramatik je, že přijímají i kontextové jazyky a algoritmus pro jejich parsing je NP-těžký.