Derivační strom

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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:

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[editovat | editovat zdroj]

Derivační strom derivace podle gramatiky G je orientovaný acyklický 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 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 A2Ak.
  • 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é[editovat | editovat zdroj]

  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 a zdola.

Literatura[editovat | editovat zdroj]

  • 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ý) 

Externí odkazy[editovat | editovat zdroj]