English web site
5. Språk
5.1 Inledning
Syftet med denna laboration är att illustrera begreppen interpretator och kompilator. Vi definierar ett enkelt programspråk Calc som innehåller några av de vanligaste konstruktionerna från traditionella programspråk: tilldelning, villkor och upprepning. Man kan också göra in- och utmatning av variabler och beräkna enklare matematiska uttryck.
Varje språk har en syntax, en uppsättning regler som beskriver hur språket ser ut. Syntaxen avgör om en följd av tecken är ett korrekt program eller inte. Den konkreta syntaxen talar om vilka tecken ett program är uppbyggt av, t.ex. att symbolen + används för addition eller att ordet if används för att markera starten på villkorssatser. Den abstrakta syntaxen rör sig på en högre nivå och beskriver hur språket är uppbyggt generellt, t.ex. att ett program består av ett antal satser och att ett uttryck kan vara en variabel, en konstant eller ett sammansatt binäruttryck.
Oavsett om man ska konstruera en interpretator eller kompilator måste man börja med att analysera programmets källkod. Detta steg kallas parsning och går ut på att överföra den konkreta syntaxen till abstrakt syntax. Resultatet av det här steget är en datastruktur som brukar kallas abstrakt syntaxträd (AST). Denna struktur kan antingen tolkas och köras direkt (av en interpretator) eller översättas till ett annat språk (av en kompilator).
För den här laborationen kommer vi inte att ägna oss åt parsning, utan våra exempelprogram i det egna språk Calc kommer att vara färdiga abstrakta syntaxträd, rent konkreta lagrade i vanliga Python-listor.
5.2 Språket Calc
Nedanstående kod är ett exempel på ett program i Calc-språket:
['calc', ['read', 'n'], ['set', 'res', 1], ['while', ['n', '>', 0], ['set', 'res', ['res', '*', 'n']], ['set', 'n', ['n', '-', 1]]], ['print', 'res']]
När detta program körs händer följande: Först läses ett värde in från användaren och lagras i variabeln n. Därefter tilldelas variabeln res värdet 1. Efter detta sker en upprepning så länge variabeln n är större än 0. De satser som upprepas är att res multipliceras med n och att n minskas med 1. Slutligen skrivs värdet av res ut. Programmet beräknar alltså fakulteten av n.
Språket Calc definieras av nedanstående tabell:
| Konstruktion | Abstrakt syntax | Konkret syntax |
|---|---|---|
| PROGRAM | Ett program består av en följd av satser. | ['calc', STATEMENT1, ..., STATEMENTn] |
| STATEMENT | En sats kan vara en tilldelning, en upprepning, ett val, en inmatning eller en utmatning. | Se de enskilda typerna av satser nedan. |
| ASSIGNMENT | En tilldelning består av en variabel och ett uttryck vars värde ska beräknas för att sedan kopplas till det givna variabelnamnet. | ['set', VARIABLE, EXPRESSION] |
| REPETITION | En upprepning består av ett villkorsuttryck och en följd av satser, vilka upprepas så länge villkorsuttrycket är sant. | ['while', CONDITION, |
| SELECTION | Ett val består av ett villkorsuttryck följt av en eller två satser. Den första satsen utförs om villkorsuttrycket är sant, den andra (om den finns) om villkorsuttrycket är falskt. | ['if', CONDITION, |
| INPUT | En inmatning består av namnet på en variabel som ska få ett numeriskt värde av användaren. | ['read', VARIABLE] |
| OUTPUT | En utmatning består av namnet på en variabel vars värde ska skrivas ut. | ['print', VARIABLE] |
| EXPRESSION | Ett matematiskt uttryck kan vara en konstant, en variabel eller ett binäruttryck. | Se de enskilda typerna av uttryck nedan. |
| BINARYEXPR | Ett binäruttryck består av två uttryck med en operator i mitten. | [EXPRESSION1, BINARYOPER, EXPRESSION2] |
| CONDITION | Ett villkor består av två uttryck med en villkorsoperator i mitten. | [EXPRESSION1, CONDOPER, EXPRESSION2] |
| BINARYOPER | En binäroperator symboliserar ett av de fyra grundläggande räknesätten. | '+', '-', '*', '/' |
| CONDOPER | En villkorsoperator är större än, mindre än eller lika med. | '>', '<', '=' |
| CONSTANT | En konstant är ett tal i Python. | 14, 2.78 |
| VARIABLE | En variabel är en sträng i Python. | 'a', 'summa' |
Ett vanligt sätt att beskriva syntaxen för ett språk är att använda
Backus-Naur-form
(BNF). Det är en mer formell beskrivning som
består av ett antal produktionsrelger. I den följande grammatiken
använder vi två speciella symboler. ::= innebär att vi
definerar det begrepp som står till vänster, och att själva definitionen
står till höger. Tecknet | innebär olika alternativ. Grammatiken
för Python är
definierad på ungefär samma sätt.
En BNF-grammatik för språket Calc kan se ut så här:
PROGRAM ::= [ 'calc', STATEMENTS ] STATEMENTS ::= STATEMENT | STATEMENT, STATEMENTS STATEMENT ::= ASSIGNMENT | REPETITION | SELECTION | INPUT | OUTPUT ASSIGNMENT ::= [ 'set', VARIABLE, EXPRESSION ] REPETITION ::= [ 'while', CONDITION, STATEMENTS ] SELECTION ::= [ 'if', CONDITION, STATEMENT ] | [ 'if', CONDITION, STATEMENT, STATEMENT ] INPUT ::= [ 'read', VARIABLE ] OUTPUT ::= [ 'print', VARIABLE ] EXPRESSION ::= CONSTANT | VARIABLE | BINARYEXPR BINARYEXPR ::= [ EXPRESSION, BINARYOPER, EXPRESSION ] CONDITION ::= [ EXPRESSION, CONDOPER, EXPRESSION ] BINARYOPER ::= '+' | '-' | '*' | '/' CONDOPER ::= '<' | '>' | '=' VARIABLE ::= a Python string CONSTANT ::= a Python number
5.3 Hjälpfunktioner för att hantera språket Calc
För att lättare kunna hantera Calc-program har vi i förväg definierat ett antal hjälpfunktioner i filen calc.py. Det finns två kategorier av funktioner: dels har vi igenkänningsfunktioner (eng. recognizers) som testar om ett givet objekt är en viss konstruktion i Calc, dels har vi selektorer som plockar ut de olika delarna av en sammansatt Calc-konstruktion.
Som exempel kan vi titta på hjälpfunktionerna för konstruktionen ASSIGNMENT. Vi har först en igenkänningsfunktion som kontrollerar att indata är en lista, att listan har längden tre samt att första elementet är strängen 'set'. Därefter följer två selektorer som plockar ut variabeln respektive uttrycket som ska beräknas.
def isassignment(p): return isinstance(p, list) and len(p) == 3 and p[0] == 'set' def assignment_variable(p): return p[1] def assignment_expression(p): return p[2]
I nedanstående körexempel skapar vi först en Calc-sats som är en tilldelning där vi ska beräkna uttrycket b + 5 och placera resultatet i variabeln a. Exemplet visar hur hjälpfunktionerna fungerar.
>>> stmt = ['set', 'a', ['b', '+', 5]] >>> isassignment(stmt) True >>> assignment_variable(stmt) 'a' >>> assignment_expression(stmt) ['b', '+', 5]
5.4 Uppgifter
Uppgift 5A - Interpretator för Calc
I den här uppgiften ska du skriva ni interpretator för språket Calc, d.v.s. en uppsättning funktioner som tillsammans tolkar och kör Calc-program. Du ska använda de hjälpfunktioner som finns i filen calc.py. Huvudfunktionen ska heta eval_calc och den ska som indata ta ett argument - ett Calc-program representerat som en lista enligt definitionen ovan. Här följer några exempel på hur Calc-program interpreteras:
>>> calc1 = ['calc', ['set', 'a', 5], ['print', 'a']] >>> eval_calc(calc1) a = 5 >>> calc2 = ['calc', ['set', 'x', 7], ... ['set', 'y', 12], ... ['set', 'z', ['x', '+', 'y']], ... ['print', 'z']] >>> eval_calc(calc2) z = 19 >>> calc3 = ['calc', ['read', 'p1'], ... ['set', 'p2', 47], ... ['set', 'p3', 179], ... ['set', 'result', [['p1', '*', 'p2'], '-', 'p3']], ... ['print', 'result']] >>> eval_calc(calc3) Enter value for p1: 4 result = 9 >>> calc4 = ['calc', ['read', 'n'], ... ['set', 'sum', 0], ... ['while', ['n', '>', 0], ... ['set', 'sum', ['sum', '+', 'n']], ... ['set', 'n', ['n', '-', 1]]], ... ['print', 'sum']] >>> eval_calc(calc4) Enter value for n: 6 sum = 21
Några tips:
- Interpretatorn kommer under körningen att behöva hålla reda på vilka variabler som existerar och vilka värden de har. Detta löses lämpligen med en dictionary.
- När du testar interpretatorn kommer du att köra samma program många gånger. Därför kan det vara bra att spara programmen i variabler, som i körexemplet ovan, så att du lätt kan anropa dem igen.
- Inmatning och utmatning ska skötas så enkelt som möjligt. Körexemplet ovan visar hur det kan gå till. Felkontroll av indata är inte nödvändigt.
Ytterligare krav på lösningen:
- Lösningen ska vara funktionell i den bemärkelsen att det inte är tillåtet att använda en global variabeltabell. Den ska istället skickas med, modifieras och returneras.
- Strukturen på lösningen ska följa språkets definition, d.v.s. man ska känna igen begreppen från definitionen i koden och uppdelningen i delfunktioner ska följa språkets logiska uppbyggnad.
- De körexempel som ni redovisar ska täcka in alla konstruktioner i språket. Du får i redovisningen inte använda de exempel som finns i uppgiften, utan måste hitta på egna. (Några tips på enkla program: beräkna fakulteten av n, beräkna det n:te Fibonacci-talet, läs in n tal och beräkna det minsta)
- Det språk som interpretatorn ska acceptera ska vara exakt det som specificeras i avsnitt 5.2 ovan. Det ska varken förminskas eller utökas. Om interpretatorn stöter på en struktur som inte känns igen som en del av Calc-språket ska den ge ett felmeddelande.
Uppgift 5B - Kompilator för Calc (frivillig)
Observera att detta är en frivillig uppgift som inte behöver redovisas.
I den här uppgiften ska ni skriva en kompilator för språket Calc, d.v.s. en uppsättning funktioner som tillsammans översätter ett Calc-program till ett annat språk. För den här uppgiften är det lämpligt att översätta Calc till motsvarande Python-kod som vi sedan kan köra med Python-funktionen eval.
För att lösa uppgiften, börja med att göra en kopia av lösningen på 5A. För varje konstruktion i språket ska ni sedan tänka ut vilken motsvarande Python-kod som ska genereras.
För att göra lösningen någorlunda säker är det lämpligt att inte översätta variabler i Calc till variabler i Python. Istället bör man, även i denna uppgift, lagra variablerna i en dictionary. Vi vill ju inte få problem om användaren har variabelnamn som är reserverade ord i Python (t.ex. for) eller krockar med variabler i själva kompilatorn.
Sidansvarig: Peter Dalenius
Senast uppdaterad: 2012-10-24
