Derivace a derivační strom, víceznačnost gramatiky
Thursday, May 30, 2013
8:40 AM
Derivace
Posloupnost kroků odvození terminálu pomocí přepisovacích pravidel gramatiky
Derivační pohled odpovídá konstrukci parsovacího (syntaktického) stromu shora dolů (top-down).
Parsování zdola nahoru (bottom-up) je spjato s pravými derivacemi.
Podle toho, který neterminál nahradit v každém kroku derivace, se rozlišují levá a pravá derivace.
DERIVACE řetězce α je posloupnost kroků odvození α pomocí přepisovacích pravidel gramatiky
S = α1 => α2 => … => αn = α
Dtto S =>* α pozn.: =>* je uzávěr relace => (všechny přechody kam se dá transitivně dostat)
PŘÍMÁ DERIVACE: α A β => α γ β ,kde A -> γ є P (pozn.: P je množina pravidel, pomocí kterých lze odvodit jazyk.)
Derivační strom
Derivační strom (parse tree) je orientovaný acyklický graf a je grafickou reprezentací, která říká, v jakém pořadí byla přepisovací pravidla uplatňována na neterminály, tedy jak vznikla věta jazyka. 
Kořen stromu je označen startovacím symbolem gramatiky
Každý vnitřní uzel je ohodnocen neterminálními symboly. 
Listy jsou ohodnoceny terminálními symboly.
Listy se čtou zleva doprava a dávají větu (generovanou gramatikou).
Jestliže uzly n1, n2, . . . , nk jsou bezprostřední následníci uzlu n, jsou ohodnoceny symboly A1, A2, . . . , Ak a uzel n je ohodnocen A, pak v množině pravidel gramatiky existuje pravidlo A à A1A2 … Ak.
Není třeba značit orientaci hran.
Jiná definice jazyka generovaného gramatikou je množina vět, které mohou být vytvořeny derivačním stromem. Proces hledání derivačního stromu pro danou větu (řetězec terminálů) se nazývá parsování tohoto řetězce
Derivační strom ignoruje variace v pořadí, v jakém jsou symboly přepisovány. Proto je mezi derivacemi a derivačními stromy vztah 1:N – např.:
Jsou různé derivace, jejich derivační strom ale vypadá stejně:
Pro získání jednoznačného derivačního stromu pro derivaci se proto užívá buď pravá a nebo levá derivace.
Víceznačnost gramatik
Gramatika, která generuje větu, pro níž lze sestavit aspoň dva různé derivační stromy, je víceznačná. Jinak řečeno:  je to taková gramatika, která produkuje více než jednu levou nebo víc než jednu pravou derivaci pro tutéž větu.
Příklad: Pro gramatiku
umožňuje vytvořit dvě levé derivace pro id + id * id (násobení není upřednostněno před sčítáním):
Nutnou podmínkou jednoznačnosti gramatiky je, aby pro žádný neterminální symbol neexistovalo jak pravidlo rekurzivní zprava, tak i pravidlo rekurzivní zleva
Problém nejednoznačnosti bezkontextových jazyků je algoritmicky nerozhodnutelný.
Je potřeba buďto vytvořit jednoznačné gramatiky pro kompilaci aplikací, nebo u nejednoznačných gramatik zavést dodatečná pravidla, která řeší případné nejednoznačnosti.
Odstranění levé rekurze
Levorekurzivní gramatiku nelze použít k analýze shora dolů
Odstranění pravidla rekurzivního zleva: 
Nechť je dána BKG G = (N, T, P, S), ve které‚ 
A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn
jsou všechna A pravidla v P a žádné z β nezačíná A. 
Pak G' = ( N ∪ { A'}, T, P', S ), kde P' obsahuje místo  uvedených pravidel pravidla: 
A → β1 | β2 | … | βn | β1 A'| β2 A'| … | βn A' 
A' → α1 | α2 | … | αm | α1 A' | α2 A'| …| αm A' 
From <[link]> 