Deriva?ni strom
je v
informatice
(orientovany, ko?enovy)
strom
, ktery reprezentuje
syntaktickou strukturu
slovniho ?et?zce podle
formalni gramatiky
. V deriva?nim strom? jsou vnit?ni uzly ozna?eny jako
neterminaly
gramatiky
, zatimco
koncove uzly
jsou ozna?eny jako
terminaly
. Deriva?ni stromy mohou byt vyu?ity pro generovani nebo analyzu v?t v p?irozenem
jazyce
(viz
zpracovani p?irozeneho jazyka
), stejn? tak jako b?hem zpracovani po?ita?ovych jazyk? (
programovaci jazyky
). Deriva?ni stromy jsou odli?ne od
abstraktnich syntaktickych strom?
(n?kdy zkracen? ozna?ovanych jen jako syntakticke stromy) v tom, ?e jejich struktura a jednotlive prvky konkretn?ji odra?eji syntaxi vstupniho jazyka.
Pokud je formalni gramatika vicezna?na, m??e existovat vice deriva?nich strom? pro dany
?et?zec
(tedy
syntakticka dvojsmyslnost
).
Deriva?ni strom se sklada z
uzl?
a v?tvi. Obrazek ni?e popisuje
lingvisticky
deriva?ni strom reprezentujici ?eskou v?tu ?Honza kopl do mi?e“. Deriva?ni strom je v tomto p?ipad? cela struktura, po?inajici ko?enem stromu (V) a kon?ici v koncovych uzlech (
listech
), tj.
Honza
,
kopl
,
do
a
mi?e
(viz obrazek vpravo). Ve stromu jsou pou?ity nasledujici zkratky:
- V
jako
v?ta
, tedy nejvy??i urove? v tomto p?ikladu.
- JF
jako jmenna fraze. Prvni JF (nejvice vlevo) slou?i jako
podm?t
v?ty. Druha (vpravo) slou?i jako
p?edm?t
.
- SF
jako slovesna fraze, ktera slou?i jako
p?isudek (predikat)
.
- S
jako
sloveso
, v tomto p?ipad? vyjad?ene slovem
kopl
.
- P
jako
p?edlo?ka
, v tomto p?ipad?
do
.
- PJ
jako
podstatne jmeno
.
Ukazka deriva?niho stromu pro v?tu ?Honza kopl do mi?e“.
V deriva?nim strom? je ka?dy uzel bu?to uzlem ko?enovym, uzlem v?tve nebo koncovym uzlem (
listem
). V tomto p?ikladu je V uzel ko?enovy, JF a SF jsou uzly v?tve a jednotliva slova, tedy
Honza
,
kopl
,
do
a
mi?e
jsou uzly koncove.
Uzel m??e byt take definovan jako
rodi?
nebo
potomek
.
Rodi?
je takovy uzel, ktery je v?tvi spojen alespo? s jednim svym
potomkem
. V tomto p?ikladu je uzel V rodi?em uzl? JF a SF.
Potomek
je potom takovy uzel, ktery je p?imo spojen alespo? s jednim uzlem na vy??i urovni, tedy bli?e ke ko?enu.
Deriva?ni strom derivace podle gramatiky G je
orientovany
acyklicky
souvisly graf
, ktery ma jediny ko?en, do v?ech ostatnich uzl? vstupuje prav? jedna hrana, a dale ma tyto vlastnosti:
- Ko?en stromu je ohodnocen startovacim symbolem gramatiky.
- Listy
jsou ohodnoceny
terminalnimi symboly
, v?echny ostatni uzly jsou ohodnoceny
neterminalnimi symboly
.
- V?echny koncove uzly v jakekoliv fazi konstrukce ?tene zleva doprava tvo?i v?tnou formu v gramatice G.
- Jestli?e uzly
n
1
,
n
2
, …
n
k
jsou bezprost?edni naslednici uzlu
n
, jsou ohodnoceny symboly
A
1
,
A
2
, …
A
k
a uzel
n
je ohodnocen
A
, pak v mno?in? pravidel gramatiky existuje pravidlo A →
A
1
A
2
…
A
k
.
- Deriva?ni strom kreslime, zapisujeme nebo znazor?ujeme zleva doprava a shora dol?, proto neni t?eba zna?it orientaci a po?adi hran.
- O deriva?nich a syntaktickych stromech se mluvi v p?ipad?
bezkontextove gramatiky
, co? je b??ny zp?sob zadavani
syntaxe
programovacich jazyk? a p?irozenych jazyk?.
- Syntax programovacich jazyk? je navr?ena jednozna?n?, tj. jedna v?ta se da (spravn?) analyzovat pouze jednim zp?sobem. Pou?iva se
deterministicka bezkontextova gramatika
. V p?ipad? p?irozenych jazyk? jednozna?nost nejde zaru?it a nasledn? jedna v?ta ma i vic deriva?nich strom? (a vyznam?).
- N?ktere rysy programovacich jazyk?, konkretn?
leva rekurze
, p?sobi p?i syntakticke analyze a dal?im zpracovani problemy. Proto se gramatika transformuje a deriva?ni stromy jsou takte? pozm?n?ne.
Leva rekurze
se vyskytuje nap?iklad ve vyrazech s operatory.
- Syntakticky strom nemusi vzniknout v?dycky jako explicitni datova struktura. Strom se projde pr?b??n? p?i analyze, nap?. v
analyze rekurzivnim sestupem
.
Viz take
syntakticka analyza shora dol?
a
syntakticka analyza zdola nahoru
.
- VAVRE?KOVA, ?arka.
Syntakticka analyza, P?eklada?e, P?edna?ka ?.3
[online]. Opava: Ustav informatiky, FPF SU Opava, rev. 2007-10-09.
Dostupne online
. (?esky)
[
nedostupny zdroj
]