Göm menyn

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.

Kapitlet Grunderna till interpretator och kompilator i studiematerialet förbereder för denna laboration.

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', STATEMENTS]
STATEMENTS En följd av STATEMENTs 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,
  STATEMENT1, ..., STATEMENTn]
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,
  STATEMENTTrue,
  STATEMENTFalse]
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 is_assignment(p): """ Returns whether given argument is a valid assignment statement """ return isinstance(p, list) and len(p) == 3 and p[0] == 'set' def assignment_variable(p): """ Returns the name of the variable from a valid assignment statement """ return p[1] def assignment_expression(p): """ Returns the expression from a valid assigment statement """ 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]] >>> is_assignment(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_program och den ska som indata ta ett argument, ett Calc-program representerat som en lista enligt definitionen ovan, samt ett frivilligt argument (en. optional argument) som är en initial variabeltabell. Funktionen ska även returnera variabeltabellen den aktuella variabeltabellen efter att programmet har körts. Här följer några exempel på hur Calc-program interpreteras:

>>> calc1 = ['calc', ['set', 'a', 5], ['print', 'a']] >>> new_table = eval_program(calc1) a = 5 >>> my_table = {'a': 7} >>> new_table = eval_program(calc1, my_table) a = 5 >>> my_table {'a': 7} >>> new_table {'a': 5} >>> calc2 = ['calc', ['set', 'x', 7], ... ['set', 'y', 12], ... ['set', 'z', ['x', '+', 'y']], ... ['print', 'z']] >>> new_table = eval_program(calc2) z = 19 >>> new_table {'x': 7, 'y': 12, 'z': 19} >>> calc3 = ['calc', ['read', 'p1'], ... ['set', 'p2', 47], ... ['set', 'p3', 179], ... ['set', 'result', [['p1', '*', 'p2'], '-', 'p3']], ... ['print', 'result']] >>> new_table = eval_program(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']] >>> new_table = eval_program(calc4) Enter value for n: 6 sum = 21

Notera att all utskrift ska vara på formatet ovan (det inkluderar även den utskrift som kommer från input-funktionen. Formatet är för utskrift av variabler är namnet på variabeln, ett blanksteg, lika med tecknet, ett blanksteg, värdet på variabeln och till sist en radbrytning. När man ska mata in ett värde används följande format: följande sträng 'Enter value for ', namnet på variabeln, kolon till sist ett blanksteg. Notera att ingen ny radbrytning ska göras (input-funktionen gör inte någon radbrytning) eftersom att användaren kommer göra en radbrytning när denna trycker på enter-knappen.

Anledning till att exakt denna formen ska användas är att rättningsscriptet även testar utskrifterna från programmet.

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 och kopieras, modifieras och returneras vid behov. Notera att det gäller för alla funktioner som du skriver.
  • Strukturen på lösningen måste 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.

Några tips:

  • För att kopiera variabeltabellen kan man med fördel använda sig av funktionen deepcopy som finns i standardmodulen copy. Funktionen returnerar en kopia av indatan där all data är kopierad oavsett vilket djup den befinner sig på (en så kallad deepcopy).
  • 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 i enlighet med körexemplen ovan. Felkontroll av indata är inte nödvändigt.
  • OBS Lösningen ska följa språkets definition, med ungefär en funktion per typ av språkkonstruktion (ASSIGNMENT, INPUT, ...). Detta är också ett krav. Ett tips är att skriva ned vilka funktioner man behöver (något för evaluera ASSIGNMENT...), vad de ska ha för in- och utdatatyper. Det vill säga vilka typsignaturer de har. Om man evaluerar [5,'+',3] (med någon variabeltabell) i en lämplig hjälpfunktion, vad bör returvärdet ha för typ? Om man evaluerar assignment-uttrycket ['set', 'res', <EXPRESSION>] (med någon variabeltabell)?

Testning För att se till att din funktion klarar av uppgiften finns det ett pythonprogram som kör automatisk testning på din kod. Programmet kan antingen hämtas (test_5.py) om du inte befinner dig på datorerna i SU-salarna eller köras direkt från filsystemet (~TDDC66/tester/test_5.py) om du befinner dig på en av datorerna i ovannämnda salar. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 5A.

Feedback För att ständigt förbättra undervisningen uppskattar vi om ni individuellt fyller i följande formulär. Notera att det är friviligt och inte påverkar betygen på något sätt.

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 exec.

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: 2016-12-09