Eftersom jag har kodat på ett skolprojekt under hela veckoslutet tänkte jag  skriva en artikel om det. Uppgiften var att skriva en programtolk för det simpla MiniPL programmeringsspråket (tekniska specifikationen finns här för de nyfikna).

En vad?

En programtolk/interpretator (eng. interpreter) är ett program som tar in kod av ett specifikt språk och gör/kör det som koden begär. Detta är skillnad till en kompilator, som helt enkelt översätter kod från ett språk till ett annat. Programtolken är ofta uppdelad i 4  huvudsakliga delar: lexikal-, syntax- och semantisk analys, som tillsammans skapar en mängd programinstruktioner, och till sist själva körningen av instruktionerna.

Tolkningen börjar med lexikalanalys där karaktärer grupperas till ”symboler” eller ord (eng. tokens). Vi tar som exempel meningen ”Datorer har en von Neumann-arkitektur.” Karaktärerna kan grupperas till följande symboler: ”Datorer”, ”har”, ”en”, ”von Neumann”, ”-”, ”arkitektur” och till sist ”.”-tecknet. Till symbolerna tillsätts tilläggsdata, som att symbolen ”Datorer” är ett substantiv i plural, symbolen ”har” är ett verb osv.

Syntaxanalysen tar in dessa symboler, och försöker bygga upp satser och meningar av dessa, enligt specifierade grammatikregler. Satserna och meningarna sparas i ett så kallat (abstrakt) syntaxträd. Av exempelmeningen kan man bygga upp följande träd:

I programmeringsspråk är det ytterst viktigt att man kan tolka de givna symbolerna bara på ett visst sätt, dvs. språket får inte vara tvetydigt. Olikt en människa vet inte datorn vad den skall göra då en kod kan betyda två olika saker. Tvetydighet uppkommer oftast i syntaxanalysen, då man inte kan utgöra hurdant syntaxträd som ska byggas upp med hjälp av grammatikreglerna. Grammatiken måste omformas för att fixa problemet.

Efter att syntaxet är granskat så söker den semantiska analysen efter ”meningen” bakom meningarna — vad den givna koden eller texten betyder. En syntaktiskt korrekt mening behöver inte vara semantiskt korrekt. Ett typexempel är ”Färglösa gröna idéer sover häftigt.” Meningen är inte alls vettig (så länge man inte är alltför poetisk av sig), men följer ändå de svenska grammatikreglerna.

Vi tittar igen på exemplet ”Datorer har en von Neumann-arkitektur.” Den semantiska analysen för detta påstående kan bland annat bestå av att svara dessa frågor: Är datorer saker med en ”arkitektur”? Är ”von Neumann-arkitektur” en egenskap som en dator kan ha? Syntaxträdet omvandlas eller påfylls sedan med den information som man har samlat och rent syntaktiska element skärs bort, som punkter och bindestreck.

I semantisk analys av programmeringsspråk granskas det att variabel-/funktiontyperna är överensstämmande och att de variabler/funktioner som används är definierade. Syntaxträdet omvandlas samtidigt till en mängd programinstruktioner (oftast ändå i formen av ett träd) samt en ”symboltabell”, där definitionerna av variabler och funktioner sparas.

Efter allt detta kan instruktionerna köras. Under körningen sparas variabelvärden i symboltabellen, varifrån de kan återhämtas senare. Programtolken borde innehålla en liten mängd basfunktioner (som aritmetik och loopar) som sedan kan användas av programmerare för att bygga upp mer komplexa funktioner. Eller varför inte en ny programtolk?