Apstraktno sintaksno stablo
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
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.