Apstraktno sintaksno stablo

U računarstvu, apstraktno sintaksno stablo (još i stablo sažete sintakse, obično kraćeno kao 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čunalnog programa u jezičnim procesorima još dok se on optimizira tokom prevođenja netom prije generiranja 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 utječu na semantiku programa. Klasičan je primjer micanje zagrada za grupiranje, s obzirom na to da je u AST-u grupiranje operanada implicitno u hijerarhijskoj, stablastoj strukturi.

Kreiranje AST-a prilikom parsiranja jezika opisanog kontekstno neovisnom 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 grupiranjem 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.

Izvori

Nedovršeni članak Apstraktno sintaksno stablo koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.