Az absztrakt szintaxisfák a fordítóprogramokban széles körben használt adatszerkezetek a programkód szerkezetének ábrázolására. Az AST általában a fordítóprogram szintaxiselemzési fázisának eredménye. Gyakran a program köztes reprezentációjaként szolgál a fordítóprogram által megkövetelt több szakaszon keresztül, és nagy hatással van a fordítóprogram végső kimenetére.
MotivációSzerkesztés
Az AST számos olyan tulajdonsággal rendelkezik, amelyek segítik a fordítási folyamat további lépéseit:
- Az AST szerkeszthető és bővíthető olyan információkkal, mint a tulajdonságok és megjegyzések minden benne lévő elemhez. Egy program forráskódjánál ilyen szerkesztés és megjegyzés nem lehetséges, mivel az annak megváltoztatásával járna.
- A forráskódhoz képest az AST nem tartalmaz felesleges írásjeleket és elválasztójeleket (zárójelek, pontosvesszők, zárójelek stb.).
- Az AST általában többletinformációt tartalmaz a programról, a fordító által végzett elemzés egymást követő szakaszai miatt. Például tárolhatja az egyes elemek helyét a forráskódban, ami lehetővé teszi a fordító számára, hogy hasznos hibaüzeneteket írjon ki.
Az AST-ekre a programozási nyelvek és dokumentációjuk eredendő természete miatt van szükség. A nyelvek természetüknél fogva gyakran kétértelműek. E kétértelműség elkerülése érdekében a programozási nyelveket gyakran kontextusmentes nyelvtan (CFG) formájában adják meg. A programozási nyelveknek azonban gyakran vannak olyan aspektusai, amelyeket egy CFG nem tud kifejezni, de a nyelv részét képezik, és a nyelv specifikációjában dokumentálva vannak. Ezek olyan részletek, amelyek érvényességük és viselkedésük meghatározásához kontextusra van szükség. Például, ha egy nyelv lehetővé teszi új típusok deklarálását, a CFG nem tudja megjósolni sem az ilyen típusok nevét, sem a használatuk módját. Még ha egy nyelv rendelkezik is előre definiált típusokkal, a megfelelő használat kikényszerítéséhez általában szükség van valamilyen kontextusra. Egy másik példa a kacsa tipizálás, ahol egy elem típusa a kontextustól függően változhat. Az operátorok túlterhelése egy újabb eset, ahol a helyes használat és a végső funkció a kontextus alapján kerül meghatározásra. Erre kiváló példát szolgáltat a Java, ahol a ‘+’ operátor egyszerre numerikus összeadás és a karakterláncok összekapcsolása.
Bár a fordító belső működésében más adatszerkezetek is részt vesznek, az AST egyedülálló funkciót tölt be. Az első szakaszban, a szintaktikai elemzési szakaszban a fordító egy elemzési fát állít elő. Ezt a tagolófát a fordító szinte minden funkciójának elvégzésére fel lehet használni a szintaxis-irányított fordítás segítségével. Bár ez a módszer hatékonyabb fordítót eredményezhet, ellentétes a programok írásának és karbantartásának szoftvertechnikai elveivel. Az AST másik előnye a parse tree-vel szemben a méret, különösen az AST kisebb magassága és az elemek kisebb száma.
DesignEdit
Az AST tervezése gyakran szorosan összefügg a fordítóprogram tervezésével és annak elvárt funkcióival.
Az alapvető követelmények közé tartoznak a következők:
- A változók típusait meg kell őrizni, valamint az egyes deklarációk helyét a forráskódban.
- A végrehajtható utasítások sorrendjét explicit módon kell ábrázolni és jól definiálni.
- A bináris műveletek bal és jobb komponenseit tárolni és helyesen azonosítani kell.
- A hozzárendelési utasításokhoz azonosítókat és a hozzájuk rendelt értékeket kell tárolni.
Ezek a követelmények felhasználhatók az AST adatszerkezetének megtervezéséhez.
Egyes műveletekhez mindig két elemre lesz szükség, például az összeadás két tagjára. Néhány nyelvi konstrukció azonban tetszőlegesen nagy számú gyermeket igényel, mint például a parancssorból a programoknak átadott argumentumlisták. Következésképpen egy ilyen nyelven írt kód reprezentálására használt AST-nek elég rugalmasnak kell lennie ahhoz, hogy ismeretlen számú gyermek gyors hozzáadását is lehetővé tegye.
A fordítói ellenőrzés támogatása érdekében lehetővé kell tenni, hogy egy AST-t forráskódra bontani lehessen. Az előállított forráskódnak kellően hasonlónak kell lennie az eredetihez megjelenésében és azonosnak a végrehajtásban, újrafordításkor.
UsageEdit
Az AST-t intenzíven használják a szemantikai elemzés során, ahol a fordító ellenőrzi a program és a nyelv elemeinek helyes használatát. A szemantikai elemzés során a fordító az AST alapján szimbólumtáblákat is generál. A fa teljes átszelése lehetővé teszi a program helyességének ellenőrzését.
A helyesség ellenőrzése után az AST a kódgenerálás alapjául szolgál. Az AST-t gyakran arra használják, hogy a kódgeneráláshoz egy köztes reprezentációt (IR), néha köztes nyelvnek is nevezik.