Derivační stromy
V kapitole 2.1 Pojem gramatiky, odvození jsme se mimojiné zabývali odvozením neboli
derivací. Vysvětlili jsme si, že derivace je vlastně relace na množině (N ∪ Σ)∗
, která se řídí
pravidly v dané gramatice. Značili jsme si ji dvojitou šipkou ⇒G, kde G je zadaná gramatika.
Ukažme si to raději na jednoduchém příkladě:
Příklad 1.
Mějme gramatiku G = ({S, A, B}, {a, b, ε}, P, S), kde množina P = {
S → aABb | bbB
A → aa | bBb | aAa
B → b | bB }
Mějme například řetězec aaAaBb. Z toho řetězce můžeme odvodit v gramatice G řetězec
aabBbaBb, protože v P je pravidlo A → bBb.
Zdá se vám to nepřehledné? Zkusme si to v obou řetězcích raději naznačit, a to tak, že
část, na kterou bude pravidlo použito, označíme hvězdičkou z obou stran:
aa∗A∗aBb ⇒G aa∗bBb∗aBb
Všimněte si, že neterminál A v původním řetězci jsme nahradili řetězcem bBb, protože v
množině P existuje pravidlo A → bBb. A to je přesně princip odvození neboli derivace.
Jak to ale vše souvisí s derivačními stromy? Určitě se takto musíte ptát. Odpovím opět
otázkami. Proč jsme v řetězci aaAaBb vybrali k odvození zrovna neterminál A? Proč jsme
nejdříve nederivovali neterminál B? Má pořadí použitých pravidel nějaký vliv na výsledek –
tj. slovo, které je odvozeno z gramatiky G? K odpovědi na tuto otázku nám pomůže znalost
derivačních stromů.
Definice – derivační strom
Nechť G = (N, Σ, P, S) je bezkontextová gramatika. Strom T nazveme derivačním stromem
v G právě tehdy, když platí následující podmínky:
1. každý uzel má návěští (označení) z (Σ ∪ N),
2. kořen stromu T má návěští S,
3. vnitřní uzel má návěští z N,
4. list má návěští patřící do N ∪ Σ ∪ {ε},
5. má-li vnitřní uzel A následníky X1, X2, X3, . . . , Xn (v pořadí zleva doprava), pak
A → X1X2X3 . . . Xn ∈ P,
6. má-li uzel návěští ε, pak je listem a je jediný následník svého otce.
Pokud zřetězíme všechny listy po řadě zleva doprava, dostaneme slovo w ∈ L(G), které je
výsledkem derivačního stromu T .
1
Příklad 2.
Mějme stejnou gramatiku G = ({S, A, B}, {a, b, ε}, P, S) jako v příkladu 1. Množina pravidel
P = {
S → aABb | bbB
A → aa | bBb | aAa
B → b | bB }
Vezmeme např. slovo aabbbabb jeho odvození v gramatice G:
S ⇒ aABb ⇒ aaAaBb ⇒ aabBbaBb ⇒ aabbbaBb ⇒ aabbbabb
Pokud bychom přesně sledovali derivace, které jsme provedli, získáme následující derivační
strom:
A Ba b
a
b B
a b
b
A
b
S
Poznámka.
Všimněte si důležitého faktu, vedou-li šipky z nějakého vnitřního uzlu X do uzlů X1, X2, ..., Xn
(v pořadí zleva doprava), pak opravdu pravidlo X → X1X2 . . . Xn patří do P. Např.
• ve 2. úrovni stromu jsou po řadě uzly a, A, B, b spojené s kořenem S a skutečně:
S → aABb.
• Nebo ve 3. úrovni jsou uzly a, A, a spojeny šipkami s vnitřním uzlem 2. úrovně A –
pravidlo A → aAa ∈ P.
• Ještě jeden příklad: ve 4. úrovni jsou uzly b, B, b spojeny šipkami s vnitřním uzlem A
3. úrovně. Je to proto, že jsme použili pravidlo A → bBb.
Navíc pro derivační strom opravdu platí, že vnitřní uzly mají vždy v návěští neterminál,
kdežto listy naopak vždy terminál.
2
Příklad 3.
Buď G = ({E, T, F}, {i, (, ), ∗, +}, P, E) gramatika s následujícími pravidly:
P = {E → E + T | T
T → T ∗ F | F
F → (E) | i }
Úkol: Vypište alespoň tři různé derivace E ⇒∗
i + i. K práci vám může pomoci derivační
strom s výsledkem i+i:
E
F
T
E
T
+
F i
i
Poté nalezněte odvození pro slova i + i ∗ i a (i + i) ∗ i.
Řešení. Existuje 10 různých odvození slova i + i, všem přísluší derivační strom uvedený v
zadání. Nabízím alespoň tři z nich.
1. E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + F ⇒ i + i
2. E ⇒ E + T ⇒ E + F ⇒ E + i ⇒ T + i ⇒ F + i ⇒ i + i
3. E ⇒ E + T ⇒ T + T ⇒ T + F ⇒ F + F ⇒ i + F ⇒ i + i
2. úkolem bylo nalézt odvození slov i + i ∗ i a (i + i) ∗ i v gramatice G. Zde je:
1. E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + T ∗ F ⇒ i + F ∗ F ⇒ i + i ∗ F ⇒ i + i ∗ i
2. E ⇒ T ⇒ T ∗ F ⇒ T ∗ i ⇒ F ∗ i ⇒ (E) ∗ i ⇒ (E + T ) ∗ i ⇒ (E + F) ∗ i ⇒ (E + i) ∗ i ⇒
(T + i) ∗ i ⇒ (F + i) ∗ i ⇒ (F + i) ∗ i ⇒ (i + i) ∗ i
3
Poznámka.
Předchozí příklad nám poslouží jako ukázka jednoho důležitého faktu. Ve chvíli, kdy jste měli
nalézt alespoň 3 různé derivace slova i + i, tak jste svým odvozováním „sledovali derivační
strom uvedený v zadání. Ten zůstává v našem příkladu pro libovolnou derivaci vždy stejný.
Ne vždy tomu tak musí být – o tom si však budeme povídat až příště, můžu však prozradit,
že se budeme bavit o jednoznačnosti nebo víceznačnosti bezkontextových gramatik.
Definice – kanonická derivace
Buď G = (N, Σ, P, S) bezkontextová gramatika. Levou (respektive pravou) derivací řetězce
α ∈ (N ∪ Σ)∗
na řetězec β ∈ (N ∪ Σ)∗
rozumíme derivaci takovou, že je v každém odvození
nahrazen vždy ten nejlevější (nejpravější) neterminál. Souhrně se takovým derivacím říká
kanonické derivace.
Poznámka.
Příklad levé i pravé derivace jsme mohli vidět v příkladu 3. Například odvození
• E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + F ⇒ i + i
• E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + T ∗ F ⇒ i + F ∗ F ⇒ i + i ∗ F ⇒ i + i ∗ i
jsou levé derivace (přepisujeme vždy nejlevější neterminál). Naopak odvození
• E ⇒ E + T ⇒ E + F ⇒ E + i ⇒ T + i ⇒ F + i ⇒ i + i
• E ⇒ T ⇒ T ∗ F ⇒ T ∗ i ⇒ F ∗ i ⇒ (E) ∗ i ⇒ (E + T ) ∗ i ⇒ (E + F) ∗ i ⇒ (E + i) ∗ i ⇒
(T + i) ∗ i ⇒ (F + i) ∗ i ⇒ (F + i) ∗ i ⇒ (i + i) ∗ i
jsou pravé derivace (přepisujeme vždy nejpravější neterminál).
4