Derivační strom

Derivační strom je v informatice (orientovaný, kořenový) strom, který reprezentuje syntaktickou strukturu slovního řetězce podle formální gramatiky. V derivačním stromě jsou vnitřní uzly označeny jako neterminály gramatiky, zatímco koncové uzly jsou označeny jako terminály. Derivační stromy mohou být využity pro generování nebo analýzu vět v přirozeném jazyce (viz zpracování přirozeného jazyka), stejně tak jako během zpracování počítačových jazyků (programovací jazyky). Derivační stromy jsou odlišné od abstraktních syntaktických stromů (někdy zkráceně označovaných jen jako syntaktické stromy) v tom, že jejich struktura a jednotlivé prvky konkrétněji odrážejí syntaxi vstupního jazyka.

Pokud je formální gramatika víceznačná, může existovat více derivačních stromů pro daný řetězec (tedy syntaktická dvojsmyslnost).

Základní popis

Derivační strom se skládá z uzlů a větví. Obrázek níže popisuje lingvistický derivační strom reprezentující Českou větu „Honza kopl do míče“. Derivační strom je v tomto případě celá struktura, počínající kořenem stromu (V) a končící v koncových uzlech (listech), tj. Honza, kopl, do a míče (viz obrázek vpravo). Ve stromu jsou použity následující zkratky:

V jako věta, tedy nejvyšší úroveň v tomto příkladu.
JF jako jmenná fráze. První JF (nejvíce vlevo) slouží jako podmět věty. Druhá (vpravo) slouží jako předmět.
SF jako slovesná fráze, která slouží jako přísudek (predikát).
S jako sloveso, v tomto případě vyjádřené slovem kopl.
P jako předložka, v tomto případě do.
PJ jako podstatné jméno.

Ukázka derivačního stromu pro větu „Honza kopl do míče“.

V derivačním stromě je každý uzel buďto uzlem kořenovým, uzlem větve nebo koncovým uzlem (listem). V tomto příkladu je V uzel kořenový, JF a SF jsou uzly větve a jednotlivá slova, tedy Honza, kopl, do a míče jsou uzly koncové.

Uzel může být také definován jako rodič nebo potomek. Rodič je takový uzel, který je větví spojen alespoň s jedním svým potomkem. V tomto příkladu je uzel V rodičem uzlů JF a SF. Potomek je potom takový uzel, který je přímo spojen alespoň s jedním uzlem na vyšší úrovni, tedy blíže ke kořenu.

Definice

Derivační strom derivace podle gramatiky G je orientovaný acyklický souvislý graf, který má jediný kořen, do všech ostatních uzlů vstupuje právě jedna hrana, a dále má tyto vlastnosti:

Kořen stromu je ohodnocen startovacím symbolem gramatiky.
Listy jsou ohodnoceny terminálními symboly, všechny ostatní uzly jsou ohodnoceny neterminálními symboly.
Všechny koncové uzly v jakékoliv fázi konstrukce čtené zleva doprava tvoří větnou formu v gramatice G.
Jestliže uzly n₁, n₂, … n_k jsou bezprostřední následníci uzlu n, jsou ohodnoceny symboly A₁, A₂, … A_k a uzel n je ohodnocen A, pak v množině pravidel gramatiky existuje pravidlo A → A₁ A₂ … A_k.
Derivační strom kreslíme, zapisujeme nebo znázorňujeme zleva doprava a shora dolů, proto není třeba značit orientaci a pořadí hran.

Různé

O derivačních a syntaktických stromech se mluví v případě bezkontextové gramatiky, což je běžný způsob zadávání syntaxe programovacích jazyků a přirozených jazyků.
Syntax programovacích jazyků je navržena jednoznačně, tj. jedna věta se dá (správně) analyzovat pouze jedním způsobem. Používá se deterministická bezkontextová gramatika. V případě přirozených jazyků jednoznačnost nejde zaručit a následně jedna věta má i víc derivačních stromů (a významů).
Některé rysy programovacích jazyků, konkrétně levá rekurze, působí při syntaktické analýze a dalším zpracování problémy. Proto se gramatika transformuje a derivační stromy jsou taktéž pozměněné. Levá rekurze se vyskytuje například ve výrazech s operátory.
Syntaktický strom nemusí vzniknout vždycky jako explicitní datová struktura. Strom se projde průběžně při analýze, např. v analýze rekurzivním sestupem.

Viz také syntaktická analýza shora dolů a syntaktická analýza zdola nahoru.

Literatura

VAVREČKOVÁ, Šárka. Syntaktická analýza, Překladače, Přednáška č.3 [online]. Opava: Ústav informatiky, FPF SU Opava, rev. 2007-10-09. Dostupné online. ^{[nedostupný zdroj]}

Externí odkazy

Obrázky, zvuky či videa k tématu derivační strom na Wikimedia Commons
Ukázka vytváření derivačního stromu (PDF)
Syntax Tree Editor
Linguistic Tree Editor