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“. +more 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. +more 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. +more 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. +more * Všechny koncové uzly v jakékoliv fázi konstrukce čtené zleva doprava tvoří větnou formu v gramatice G. * Jestliže uzly n1, n2, … nk jsou bezprostřední následníci uzlu n, jsou ohodnoceny symboly A1, A2, … Ak a uzel n je ohodnocen A, pak v množině pravidel gramatiky existuje pravidlo A → A1 A2 … Ak. * 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. +more 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

Externí odkazy

[url=http://www. cs. +morevsb. cz/kot/soubory_animaci/a-deriv_strom. pdf]Ukázka vytváření derivačního stromu[/url] (PDF) * [url=http://www. ductape. net/~eppie/tree/]Syntax Tree Editor[/url] * [url=http://ltc. sourceforge. net/]Linguistic Tree Editor[/url].

Kategorie:Stromy (datové struktury) Kategorie:Formální jazyky