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é

1. 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ů.
2. 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ů).
3. 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.
4. 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. (Český) ^{[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