Syntaktický strom: Porovnání verzí

Smazaný obsah Přidaný obsah
m - neex. šablony
m Styl
Řádek 15:
Abstraktní syntaktické stromy jsou také používané v programové analýze a v systémech pro [[Transformační programy|transformace programů]]
 
== Struktura syntaktického stromu ==
 
* vnitřní uzly stromu jsou '''operátory'''
* listy stromu jsou jeho '''operandy'''
Řádek 22 ⟶ 21:
 
== Syntaktický strom při interpretaci==
 
Abstraktní syntaktický strom (AST) je vhodný k řízení výkonu programu zejména pro Just-in-time kompilátory, kdy je lepší jako průběžný formát než bytekód. V přístupu řízení podle AST je potřeba analyzovat každou větu pouze jednou. Hlavní výhodou oproti bytekód interpretaci je, že AST udržuje globální program, strukturu a vztahy mezi instrukcemi (což v bytekódu nelze zjistit), a poskytuje kompaktnější reprezentaci. AST také umožňuje provádět lepší analýzu při běhu.
 
== Aplikace v kompilátorech==
 
Abstraktní syntaktický strom (AST) je [[Abstraktní datový typ| datová struktura]] široce používaná v [[Překladač|kompilátorech]]. Umožňuje reprezentovat strukturu programového kódu. AST je obvykle výsledek syntaktické části překladu programu. Většinou slouží jako mezikódová reprezentace programu pro další fáze překladu kompilátorem a má důležitou roli na výsledku kompilace, tedy například spustitelném programu.
 
=== Motivace ===
AST je produkt části překladu, které se říká [[Syntaktická analýza| syntaktická analýza]]. AST má vlastnosti, které jsou při dalších krokáchkrocích překladu nezbytné. V porovnání se [[Zdrojový kód|zdrojovým kódem]] AST neobsahuje určité prvky, jako například nedůležité interpunkce a oddělovače ( závorky, složené závorky, středníky, atd.) Důležitějším rozdílem je to, že AST může být upraveno a vylepšeno vlastnostmi a popisky pro každý prvek, který obsahuje. Takovéto úpravy a velepšenívylepšení jsou nemožné bez zdrojového kódu programu, protože by to znamenalo změnit ho. Zatímco AST obvykle obsahuje extra informace o programu, díky tomu, že mu předchází analytická část překladu kompilátorem. Jednoduchým příkladem přidaných informací v AST může být pozice elementu ve zdrojovém kódu. Tato informace se využívá v případě chyby v kódu, k upozornění uživatele, kde se chyba nachází.
 
Potřeba a uplatnění AST vychází ze zděděné podstaty programovacích jazyků a jejich dokumentace. Jazyky jsou často víceznačenévíceznačné už ze své podstaty. Z důvodů vyhnutí se této víceznačnosti, programovací jazyky jsou často specifikovány jako [[ Bezkontextová gramatika| bezkontextové gramatiky]]. Nicméně jsou zde často aspekty těchto programovacích jazyků, které nemůže bezkontextová gramatika vyjádřit nebo popsat, ale jsou součástí jazyka a jsou zdokumentovány v jeho specifikacích. Tyto detaily vyžadují kontext k tomu, aby mohlo být rozhodnuto o jejich správnosti a chování. Například pokud jazyk umožňuje definovat nové typy, bezkontextová gramatika nemůže předvídat jméno tohoto typu ani způsob, jak mohou být použity. Dokonce ani když jazyk obsahuje předdefinované typy, vynucení správného použití vyžaduje nějaký kontext. Dalším příkladem je [[Duck-typing]], kde se typ elementu může měnit v závislosti na kontextu. Přetěžování operátorů je další příklad, kde správné použití a výsledná funkce závisí na kontextu. Java nabízí výborný příklad, operátor "+" je zároveň matematickým operátorem sčítání a zároveň operátor pro spojování stringůřetězců.
AST je produkt části překladu, které se říká [[Syntaktická analýza| syntaktická analýza]]. AST má vlastnosti, které jsou při dalších krokách překladu nezbytné. V porovnání se [[Zdrojový kód|zdrojovým kódem]] AST neobsahuje určité prvky, jako například nedůležité interpunkce a oddělovače ( závorky, složené závorky, středníky, atd.) Důležitějším rozdílem je to, že AST může být upraveno a vylepšeno vlastnostmi a popisky pro každý prvek, který obsahuje. Takovéto úpravy a velepšení jsou nemožné bez zdrojového kódu programu, protože by to znamenalo změnit ho. Zatímco AST obvykle obsahuje extra informace o programu, díky tomu, že mu předchází analytická část překladu kompilátorem. Jednoduchým příkladem přidaných informací v AST může být pozice elementu ve zdrojovém kódu. Tato informace se využívá v případě chyby v kódu, k upozornění uživatele, kde se chyba nachází.
 
Potřeba a uplatnění AST vychází ze zděděné podstaty programovacích jazyků a jejich dokumentace. Jazyky jsou často víceznačené už ze své podstaty. Z důvodů vyhnutí se této víceznačnosti, programovací jazyky jsou často specifikovány jako [[ Bezkontextová gramatika| bezkontextové gramatiky]]. Nicméně jsou zde často aspekty těchto programovacích jazyků, které nemůže bezkontextová gramatika vyjádřit nebo popsat, ale jsou součástí jazyka a jsou zdokumentovány v jeho specifikacích. Tyto detaily vyžadují kontext k tomu, aby mohlo být rozhodnuto o jejich správnosti a chování. Například pokud jazyk umožňuje definovat nové typy, bezkontextová gramatika nemůže předvídat jméno tohoto typu ani způsob, jak mohou být použity. Dokonce ani když jazyk obsahuje předdefinované typy, vynucení správného použití vyžaduje nějaký kontext. Dalším příkladem je [[Duck-typing]], kde se typ elementu může měnit v závislosti na kontextu. Přetěžování operátorů je další příklad, kde správné použití a výsledná funkce závisí na kontextu. Java nabízí výborný příklad, operátor "+" je zároveň matematickým operátorem sčítání a zároveň operátor pro spojování stringů.
 
Ačkoliv jsou zde i další datové struktury spojené s vnitřní prací kompilátoru, AST zastupuje unikátní funkci. Během první fáze překladu, [[Syntaktická analýza|syntaktické analýzy]], překladač vytváří syntaktický strom. Tento strom může být použit k interpretaci téměř všech funkcí překladače, co se týká syntaktické části překladu. Ačkoliv tato metoda může vést k efektivnějšímu překladu, jde proti principu softwarového inženýrství při psaní a správě programů. Další výhodou je menší velikost stromu, menší hloubka i počet elementů.
 
=== Návrh ===
 
Při navrhování AST si musíme být vědomy funkcionality, kterou bude překladač očekávat. Jak již bylo řečeno, nemůžeme ukládat programové deklarace ve zdrojové formě. Zároveň s tím deklarace musí uchovávat typ a jejich umístění.Pořadí vykonávaných částí musí být přesně určeno a dobře definováno. Binární operace si musí pamatovat levé a pravé komponenty. Přiřazené stavy musí uchovat identifikátor, který uchová přiřazenou hodnotu. Tyto požadavky mohou být použity pro návrh takovéto datové struktury.
 
Řádek 46 ⟶ 41:
 
=== Návrhové vzory ===
Kvůli složitosti požadavků na AST a následující složitosti překladače, je výhosnévýhodné aplikovat principy vývoje zvukového softwaru. Jedním z principů je použít ověřené návrhové vzory ke zlepšené modularity a usnadnění vývoje.
 
Kvůli složitosti požadavků na AST a následující složitosti překladače, je výhosné aplikovat principy vývoje zvukového softwaru. Jedním z principů je použít ověřené návrhové vzory ke zlepšené modularity a usnadnění vývoje.
 
Díky znalosti toho, že různé operace nemusí mít nutně různé datové typy, je důležité mít zvukovou hierarchii uzlů. To je obzvlášť nutné při vytváření a modifikaci AST během běhu překladače.
Řádek 54 ⟶ 48:
 
=== Použití ===
AST je intenzivně používáno během [[Syntaktická analýza|syntaktické analýzy]], kde kompilátor kontroluje správnost použití elemntůelementů programu a jazyka. Také, během této analýzy, kompilátor generuje tabulku symbolů dle AST. Kompletní průchod stromem umožňuje ověřit správnost programu.
 
Po ověření správnosti, AST slouží jako základ pro krok, ve kterém se v kompilátoru generuje strojový kód programu. Často se jedná o případ, kdy AST je použito ke generování "mezikódové„mezikódové reprezentace"reprezentace“, která se poté používá ke generování konečného strojového kódu.
AST je intenzivně používáno během [[Syntaktická analýza|syntaktické analýzy]], kde kompilátor kontroluje správnost použití elemntů programu a jazyka. Také, během této analýzy, kompilátor generuje tabulku symbolů dle AST. Kompletní průchod stromem umožňuje ověřit správnost programu.
 
Po ověření správnosti, AST slouží jako základ pro krok, ve kterém se v kompilátoru generuje strojový kód programu. Často se jedná o případ, kdy AST je použito ke generování "mezikódové reprezentace", která se poté používá ke generování konečného strojového kódu.
 
== Související články ==
Řádek 66 ⟶ 59:
 
== Externí odkazy ==
 
* [http://www.eclipse.org/jdt/ui/astview/index.php AST View]: an [[Eclipse (software)|Eclipse]] plugin to [[Scientific visualization|visualize]] a [[Java (programming language)|Java]] abstract syntax tree
* [http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html Good information about the Eclipse AST and Java Code Manipulation]
Řádek 82 ⟶ 74:
; Tutoriál
* {{cite web | url = http://www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf | title = Abstract Syntax Tree Metamodel Standard }}
 
 
 
[[Kategorie:Stromy (datové struktury)]]