Abstraktní syntaktické stromy jsou datové struktury široce používané v překladačích k reprezentaci struktury programového kódu. AST je obvykle výsledkem fáze syntaktické analýzy překladače. Často slouží jako mezistupeň reprezentace programu v několika fázích, které překladač vyžaduje, a má silný vliv na konečný výstup překladače.
MotivaceÚprava
AST má několik vlastností, které pomáhají dalším krokům procesu kompilace:
- AST lze upravovat a rozšiřovat o informace, jako jsou vlastnosti a anotace pro každý prvek, který obsahuje. Taková editace a anotace je u zdrojového kódu programu nemožná, protože by znamenala jeho změnu.
- V porovnání se zdrojovým kódem neobsahuje AST nepodstatnou interpunkci a oddělovače (závorky, středníky, závorky atd.).
- A AST obvykle obsahuje další informace o programu, a to kvůli postupným fázím analýzy kompilátorem. Může například uchovávat pozici každého prvku ve zdrojovém kódu, což překladači umožňuje vypisovat užitečná chybová hlášení.
AST jsou potřebné kvůli vlastní povaze programovacích jazyků a jejich dokumentace. Jazyky jsou ze své podstaty často nejednoznačné. Aby se této nejednoznačnosti předešlo, jsou programovací jazyky často specifikovány jako bezkontextová gramatika (CFG). Často však existují aspekty programovacích jazyků, které CFG nemůže vyjádřit, ale jsou součástí jazyka a jsou dokumentovány v jeho specifikaci. Jedná se o detaily, které vyžadují kontext, aby bylo možné určit jejich platnost a chování. Například pokud jazyk umožňuje deklarovat nové typy, CFG nemůže předvídat názvy takových typů ani způsob jejich použití. I když má jazyk předdefinovanou sadu typů, vynucení správného použití obvykle vyžaduje určitý kontext. Dalším příkladem je kachní typování, kdy se typ prvku může měnit v závislosti na kontextu. Přetěžování operátorů je dalším případem, kdy se správné použití a výsledná funkce určují na základě kontextu. Vynikající příklad poskytuje Java, kde operátor ‚+‘ slouží jak k číselnému sčítání, tak ke spojování řetězců.
Přestože se na vnitřním fungování překladače podílejí i další datové struktury, AST plní jedinečnou funkci. Během první fáze, fáze syntaktické analýzy, vytváří překladač strom syntaxe. Tento strom parsování lze použít k provádění téměř všech funkcí překladače pomocí syntakticky orientovaného překladu. Ačkoli tato metoda může vést k efektivnějšímu překladači, je v rozporu se zásadami softwarového inženýrství při psaní a údržbě programů. Další výhodou, kterou má AST oproti parsovacímu stromu, je velikost, zejména menší výška AST a menší počet prvků.
DesignEdit
Návrh AST často úzce souvisí s návrhem překladače a jeho očekávanými funkcemi.
Mezi základní požadavky patří následující:
- Proměnné typy musí být zachovány, stejně jako umístění jednotlivých deklarací ve zdrojovém kódu.
- Pořadí spustitelných příkazů musí být explicitně reprezentováno a dobře definováno.
- Levé a pravé složky binárních operací musí být uloženy a správně identifikovány.
- U příkazů přiřazení musí být uloženy identifikátory a jim přiřazené hodnoty.
Tyto požadavky lze použít při návrhu datové struktury AST.
Některé operace budou vždy vyžadovat dva prvky, například dva členy pro sčítání. Některé jazykové konstrukce však vyžadují libovolně velký počet potomků, například seznamy argumentů předávané programům z příkazového řádku. V důsledku toho musí být AST používaný k reprezentaci kódu zapsaného v takovém jazyce také dostatečně flexibilní, aby umožňoval rychlé přidání neznámého množství potomků.
Pro podporu verifikace překladačem by mělo být možné AST rozložit do podoby zdrojového kódu. Vytvořený zdrojový kód by měl být po rekompilaci dostatečně podobný vzhledu originálu a identický v provedení.
UsageEdit
AST se intenzivně používá při sémantické analýze, kdy překladač kontroluje správné použití prvků programu a jazyka. Překladač také během sémantické analýzy generuje tabulky symbolů založené na AST. Úplné procházení stromu umožňuje ověřit správnost programu.
Po ověření správnosti slouží AST jako základ pro generování kódu. AST se často používá k vygenerování mezilehlé reprezentace (IR), někdy nazývané mezijazyk, pro generování kódu.