Apstraktno sintaksno stablo

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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.