Abstraktit syntaksipuut ovat tietorakenteita, joita käytetään yleisesti kääntäjissä kuvaamaan ohjelmakoodin rakennetta. AST on yleensä kääntäjän syntaksianalyysivaiheen tulos. Se toimii usein ohjelman väliesityksenä useiden kääntäjän tarvitsemien vaiheiden läpi, ja sillä on suuri vaikutus kääntäjän lopulliseen tulosteeseen.
MotivaatioMuokkaus
AST:llä on useita ominaisuuksia, jotka auttavat kääntämisprosessin myöhempiä vaiheita:
- AST:tä voidaan muokata ja sitä voidaan laajentaa informaatiolla, kuten ominaisuuksin ja huomautuksin, jokaiselle sen sisältämälle elementille. Tällainen muokkaus ja kommentointi on mahdotonta ohjelman lähdekoodin kohdalla, koska se merkitsisi sen muuttamista.
- Vertailtuna lähdekoodiin AST ei sisällä epäolennaisia välimerkkejä ja rajauksia (hakasulkeita, puolipisteitä, sulkuja jne.).
- AST sisältää yleensä ylimääräistä tietoa ohjelmasta kääntäjän peräkkäisten analyysivaiheiden vuoksi. Se voi esimerkiksi tallentaa jokaisen elementin sijainnin lähdekoodissa, jolloin kääntäjä voi tulostaa hyödyllisiä virheilmoituksia.
ASTeja tarvitaan ohjelmointikielten ja niiden dokumentoinnin luontaisen luonteen vuoksi. Kielet ovat usein luonteeltaan moniselitteisiä. Tämän moniselitteisyyden välttämiseksi ohjelmointikielet määritellään usein kontekstittomana kielioppina (CFG). Ohjelmointikielissä on kuitenkin usein näkökohtia, joita CFG:llä ei voida ilmaista, mutta jotka ovat osa kieltä ja jotka dokumentoidaan sen määrittelyssä. Nämä ovat yksityiskohtia, jotka edellyttävät kontekstia niiden pätevyyden ja käyttäytymisen määrittämiseksi. Jos kieli esimerkiksi sallii uusien tyyppien ilmoittamisen, CFG ei voi ennustaa tällaisten tyyppien nimiä eikä tapaa, jolla niitä tulisi käyttää. Vaikka kielessä olisikin ennalta määritelty joukko tyyppejä, oikean käytön valvominen vaatii yleensä jonkinlaista kontekstia. Toinen esimerkki on ankkatyypitys, jossa elementin tyyppi voi muuttua kontekstista riippuen. Operaattorien ylikuormitus on jälleen yksi tapaus, jossa oikea käyttö ja lopullinen funktio määräytyvät kontekstin perusteella. Java tarjoaa erinomaisen esimerkin, jossa ’+’-operaattori on sekä numeerinen yhteenlasku että merkkijonojen ketjutus.
Vaikka kääntäjän sisäiseen toimintaan liittyy muitakin tietorakenteita, AST:llä on ainutlaatuinen tehtävä. Ensimmäisessä vaiheessa, syntaksianalyysivaiheessa, kääntäjä tuottaa jäsennyspuun. Tätä jäsennyspuuta voidaan käyttää lähes kaikkien kääntäjän toimintojen suorittamiseen syntaksisuuntautuneen kääntämisen avulla. Vaikka tämä menetelmä voi johtaa tehokkaampaan kääntäjään, se on vastoin ohjelmistotekniikan periaatteita, jotka koskevat ohjelmien kirjoittamista ja ylläpitoa. Toinen etu, joka AST:llä on jäsennyspuuhun verrattuna, on koko, erityisesti AST:n pienempi korkeus ja elementtien pienempi määrä.
DesignEdit
AST:n suunnittelu liittyy usein läheisesti kääntäjän suunnitteluun ja sen odotettuihin ominaisuuksiin.
Ydinvaatimuksia ovat muun muassa seuraavat:
- Muuttujatyypit on säilytettävä, samoin kuin kunkin deklaraation sijainti lähdekoodissa.
- Toteutettavien lausekkeiden järjestys on esitettävä eksplisiittisesti ja määriteltävä hyvin.
- Binäärioperaatioiden vasemman- ja oikeanpuoleiset komponentit on tallennettava ja tunnistettava oikein.
- Identifikaattorit ja niille annetut arvot on tallennettava allokointilausekkeita varten.
Näiden vaatimusten avulla voidaan suunnitella AST:n tietorakenne.
Jotkut operaatiot edellyttävät aina kahta alkiota, kuten yhteenlaskuoperaatioiden kaksi termiä. Jotkin kielikonstruktiot vaativat kuitenkin mielivaltaisen suuren määrän lapsia, kuten komentotulkista ohjelmille välitettävät argumenttiluettelot. Tämän seurauksena AST:n, jota käytetään tällaisella kielellä kirjoitetun koodin esittämiseen, on oltava myös tarpeeksi joustava, jotta siihen voidaan nopeasti lisätä tuntematon määrä lapsia.
Kääntäjän verifioinnin tukemiseksi AST:n purkamisen lähdekoodin muotoon pitäisi olla mahdollista. Tuotetun lähdekoodin tulisi olla ulkonäöltään riittävän samankaltaista ja suoritukseltaan identtistä alkuperäisen kanssa, kun se käännetään uudelleen.
UsageEdit
AST:tä käytetään intensiivisesti semanttisessa analyysissä, jossa kääntäjä tarkistaa ohjelman ja kielen elementtien oikean käytön. Kääntäjä luo myös AST:n perusteella symbolitaulukoita semanttisen analyysin aikana. Puun täydellinen läpikäynti mahdollistaa ohjelman oikeellisuuden todentamisen.
Korrektiuden todentamisen jälkeen AST toimii pohjana koodin generoinnille. AST:n avulla luodaan usein koodin generointia varten väliesitys (IR), jota joskus kutsutaan myös välikieleksi.