Kompilerkonstruktion: Abstrakt syntaks

De to foregående breve har omhandlet parseren. Nu går vi videre og bevæger os fra forenden af en kompiler over mod bagenden. I kompiler bruges interne et mellemformat (intermediate representation) som kommunikationsmiddel mellem forenden og bagenden. Vi vil i denne uge se hvordan denne mellemkode er bygget op og hvad den indeholder.

Parseren har sikret at kildeprogrammet er syntaktisk korrekt, men dette er ikke nok at sikre sig at et program er syntaktisk korrekt det skal også være semantisk korrekt. En "klassisk" fejl i et program er at typerne ikke passer sammen som et eksempel forsøges det i programmet herunder at lægge s af typen String sammen med j af typen int hvilket naturligvis ikke giver mening (rent semantisk).

public void m(){
    String s = "Hello Error";
    int i = 0, j = 10;
    i = j + s;
}

Litteratur

Læsevejledning

Appel kapitel 4

I sektion 4.1 adderes semantisk aktioner først til en recursive descent parser og herefter til en top-down parser (implementeret i JavaCC). De semantiske aktioner er er kodestumper implementeret i Java som kompilerkonstruktøren skriver, de skal altså laves manuelt. Hvis der er anvendes en automatisk parser generator, som i JavaCC eksemplet, sørger parser generatoren for at indsætte kodestumperne på de rigtige pladser i den kode der genereres. Når parseren så kører eksekveres kodestumperne hver gang parseren reducerer en produktion i grammatikken. Dette er en klassisk tilgangsvinkel som kan bruges i mange værktøjer f.eks. YACC og Bison.

Med denne klassiske tilgangsvinkel blandes parsning med dele af den semantiske analyse og dette fremmer ikke modulariteten af den implementerede kompileren. Derfor foreslås der i sektion 4.2 en alternativ tilgangsvinkel hvor en mellemkode anvendes i form at et parse træ, som blot er en datastruktur der anvendes af kompileren, mens den kører. Der beskrives to parse træer konkrete syntaks træer og abstrakte syntaks træer. Den sidste type er meget mere kompakt og er mere velegnet i bagenden af kompileren.

Når man bruger SableCC er det væsentligt at forstå Sektion 4.3. Her forklares det at for programmeringssprog er det en god at antage, at syntaksen ændre sig sjælent, mens man derimod gerne vil have mange forskellige fortolkninger af syntaksen. For at gøre det nemt at lave mange forskellige fortolkninger bruges et objekt-orienteret design mønster, der kaldes for visitor. Dette design mønster forklares i flere detaljer i den supplerende litteratur.

Gamma et al. "Visitor Design Pattern"

Ideen med et design mønster er populært sagt at lære af andres succeser. Som det fremgår af motivations sektionen kommer visitor mønstret netop fra arbejdet med abstrakte syntaks træer for programmeringssprog og har her vist sig meget succesfuld. Kerne ideen er at opbygget to nedarvingshierarkier en for elementerne i syntaksen og en for hver fortolkning af syntaksen som så "besøger" syntaksen. I kan springe sektionerne implementering Implementation og Sample Code pp 337-344.

Opgaver

Opgaven er lidt anderledes denne gang. 

• Hvis I anvender SableCC så lav en fortolkning af det abstrakte syntaks træ som SableCC leverer. Kig i manualen kapitel 6 The Framework for at forstå hvordan SableCC anvender visitor design mønstret.
• Hvis I anvender JavaCC eller lignende adder semantiske aktioner til jeres grammatik lignende det der er gjort i Program 4.2 side 88 i bogen.

Venlig hilsen
Kristian Torp
torp (at) cs (dot) auc (dot) dk