A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/Derivacnistrom.jpg/220px-Derivacnistrom.jpg)
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 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. 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 . 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
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk