Apstraktno sintaksno stablo

mini|307x307px|Apstraktno sintaksno stablo za sljedeći kod za Euklidov algoritam:while b ≠ 0: if a > b: a := a - b else: b := b - a return a U računarstvu, apstraktno sintaksno stablo (uobičajena skraćenica je AST - od engl. Abstract Syntax Tree) je konačno labelirano usmjereno stablo čiji su unutrašnji čvorovi labelirani operatorima, pri čemu listovi predstavljaju operande operatora. Slijedi da su listovi NULL operatori i predstavljaju samo varijable i konstante. U računarstvu, ovo se stablo koristi u parserima kao međuprikaz između stabla parsiranja i podatkovne strukture koja se često koristi u internom predstavljanju računarskog programa u jezičnim procesorima još dok se on optimizira tokom prevođenja prije generisanja koda. Skup svih takvih podatkovnih struktura opisuje apstraktna sintaksa.

AST se razlikuje od stabla parsiranja tako što miče čvorove i bridove za sintaksna pravila koja ne utiču na semantiku programa. Klasičan je primjer micanje zagrada za grupisanje, s obzirom da je u AST-u grupisanje operanada implicitno u hijerarhijskoj, stablastoj strukturi.

Kreiranje AST-a prilikom parsiranja jezika opisanog kontekstno nezavisnom gramatikom je u gotovo svim programskim jezicima izuzetno jednostavno. Većina produkcija gramatike kreira novi čvor čiji su bridovi znakovi produkcije. Produkcije koje se ne koriste pri gradnji AST-a, poput produkcija koje definiraju prednost operatora grupisanjem izraza, samo prolaze kroz čvor kao jedni od znakova. Alternativno, parser može kreirati potpuno stablo parsiranja, te naknadno preći preko njega pretvarajući ga u AST micanjem čvorova i bridova koji se ne koriste u apstraktnoj sintaksi.

Reference

Vanjski linkovi

AST View: an Eclipse plugin to visualize a Java abstract syntax tree

eli project: Abstract Syntax Tree Unparsing (OMG standard). JavaParser: The JavaParser library provides you with an Abstract Syntax Tree of your Java code. The AST structure then allows you to work with your Java code in an easy programmatic way. Spoon: A library to analyze, transform, rewrite, and transpile Java source code. It parses source files to build a well-designed AST with powerful analysis and transformation API. AST Explorer: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.

Kategorija:Formalni jezici