3.1.1 Derivační strom
Derivační strom
Derivační strom graficky zobrazuje syntaktickou strukturu větné formy či přímo věty generované bezkontextovou gramatikou.
- Kořenem derivačního stromu je vždy počáteční neterminál bezkontextové gramatiky.
- Neterminály v derivačním stromu tvoří v případě popisu struktury věty vždy vnitřní uzly.
- Terminály (případně \(\varepsilon\)) tvoří v derivačním stromu vždy listy.
Počet potomků jednotlivých neterminálů je dán počtem symbolů na pravé straně v použitém pravidle. Tyto potomky uspořádáváme zleva doprava. Čtením listů derivačního stromu v pořadí shora dolů a zleva doprava dostaneme výslednou větu či větnou formu.
Příklad: Mějme gramatiku G zadanou jako: \(G = (\{A, B, C\}, \{a, b\}, P, A)\), kde
\[P = \{A \xrightarrow{(1)} aBBb, A \xrightarrow{(2)} AaA, B \xrightarrow{(3)} \varepsilon, B \xrightarrow{(4)} bCA, C \xrightarrow{(5)} AB, C \xrightarrow{(6)} a, C \xrightarrow{(7)} b\},\]
větu abbabb a posloupnost derivací:
\[A \stackrel{(1)}{\Rightarrow} aBBb \stackrel{(4)}{\Rightarrow} abCABb \stackrel{(1)}{\Rightarrow} abCaBBbBb \stackrel{(3)}{\Rightarrow} abCaBbBb \stackrel{(7)}{\Rightarrow} abbaBbBb \stackrel{(3)}{\Rightarrow} abbaBbb \stackrel{(3)}{\Rightarrow} abbabb.\]
Derivační strom pak vypadá:
