6. Språk

Gammal labb, från 2019

6.1 Inledning

Syftet med denna laboration är att illustrera begreppen interpretator (tolk) 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 variablers värden och beräkna enklare matematiska uttryck.

Kapitlet Grunderna till interpretator och kompilator i studiematerialet förbereder för denna laboration. Läs det först, och se till att du förstår begrepp som konkret syntax, abstrakt syntaxträd, token, parsning, med mera.

Nu har ni påbörjat en ny kurs, TDDE24. Kom ihåg att börja arbeta i det nya Gitlab-projekt och Git-repo som ni har fått för den nya kursen (vars namn innehåller kurskoden TDDE24)! Detta gäller både om ni arbetar vidare i samma grupp som under TDDE23-lab5 och om ni har format en ny grupp för TDDE24.

Checka in och pusha kod ofta, gärna flera gånger om dagen, även om ni inte är klara med labben. Dels är versionshantering bra för att få "kontrollpunkter" som man kan backa till vid behov, dels ger regelbundna incheckningar en tydlig logg över hur arbetet har gått till. Den loggen är inte minst bra för att demonstrera att ni har skrivit programkoden själva!

6.2 Språket Calc

För vårt Calc-språk kan vi börja med att skapa en konkret syntax. Hur ska den egentligen se ut? I Python kunde ju till exempel ett program som beräknar n! (n-fakultet) se ut så här:

n = int(input()) res = 1 while n > 0: res *= n n -= 1 print(res)

Vi hade så klart kunnat definiera en liknande syntax för Calc. Då hade vi behövt skriva kod för både lexikalisk analys ("int" är ett separat token) och parsning till ett abstrakt syntaxträd (första satsen är en tilldelning, där variabeln som tilldelas något är n och värdet är ett funktionsanrop till int där parametern är ett funktionsanrop till input). Det blir rätt mycket jobb och därför kommer vi istället att skapa ett språk som låter oss åka snålskjuts på Pythons egen parser. I Calc kommer samma beräkning (fakultetsfunktionen) att se ut så här istället:

['calc', ['read', 'n'], ['set', 'res', 1], ['while', ['n', '>', 0], ['set', 'res', ['res', '*', 'n']], ['set', 'n', ['n', '-', 1]]], ['print', 'res']]

Som du ser är det inte lika vackert, men fördelen är att alla programspråkskonstruktioner i Calc lagras och skrivs in på en form som stämmer överens med vanliga nästlade Python-listor. De listorna kan man sedan skriva in på kommandoraden eller i en .py-fil, och resultatet blir direkt en färdig datastruktur. Därmed kan vi hoppa över både den lexikaliska analysen och en stor del av den syntaktiska analysen.

Den nästlade listan är dessutom tillräckligt strukturerad för att direkt motsvara ett abstrakt syntaxträd, där vi t.ex. lätt kan ta fram satserna i ett program (den yttersta listan består av 'calc' och 4 satser), funktionen som anropas i en sats (första elementet i satsens lista, t.ex. 'read'), och så vidare. Listan kan också illustreras så här i trädformat:

(................calc...........) / | | | (read) (set) (while) (print) / / \ /|\ | n res 1 ...... res

Det är viktigt att inse att Calc faktiskt kommer att vara ett eget, nytt språk, trots att vi åker snålskjuts på detta sätt. Interpretatorn du ska skriva kommer ju inte att acceptera och förstå godtyckliga Python-listor, utan bara de specifika konstruktioner som stöds av Calc. Språket är alltså ett specialfall av Pythons listor, och vi har dessutom givit detta specialfall en egen betydelse där t.ex. 'set' inte är en godtycklig sträng utan betyder att vi sätter en variabel till ett värde.

Syntaxen för 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 inmatningssats anger namnet på en variabel som ska få ett numeriskt värde av användaren.	['read', VARIABLE]
OUTPUT	En utmatningssats anger 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 produktionsregler. 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, the name of the variable <CONSTANT> ::= a Python number

6.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]

6.4 Strukturen hos en interpretator

Ovan har vi visat strukturen hos ett Calc-program med hjälp av en BNF-grammatik. Något som kanske inte är omedelbart uppenbart är att denna struktur även passar utmärkt för själva interpretatorn.

<PROGRAM> ::= '[' 'calc' ',' <STATEMENTS> ']'

Detta ska resultera i funktionen eval_program(program), som behöver kontrollera att program börjar med 'calc', och därefter kan anropa eval_statements() med lämpliga parametrar.

<STATEMENTS> ::= <STATEMENT> | <STATEMENT> ',' <STATEMENTS>

Detta ska resultera i funktionen eval_statements(statements), som kan behöva anropa eval_statement() för att tolka en enskild sats.

<STATEMENT> ::= <ASSIGNMENT> | <REPETITION> | <SELECTION> | <INPUT> | <OUTPUT>

Detta ska resultera i funktionen eval_statement(statement), som behöver kontrollera vilken typ av sats det gäller, och sedan anropa eval_assignment(), eval_repetition(), eller någon annan liknande funktion för att tolka denna del -- och så vidare.

Varför just denna programstruktur? Uppdelningen i en funktion per icke-terminal i språket ger oftast ett modulärt program med en tydlig uppdelning i lagom stora funktioner med tydliga ansvarsområden. Att man håller sig nära grammatikens struktur gör det också lättare att se hur man ska strukturera upp sitt program redan innan man har börjat skriva det, och det blir mindre risk att man tar sig vatten över huvudet genom att försöka tänka på alla delar av interpretatorn på en och samma gång.

Rekursion! De flesta icke-triviala programmeringsspråk har en rekursiv definition. I Calc ser vi t.ex. att ett EXPRESSION kan vara ett BINARYEXPR, som då kan innehålla ett EXPRESSION, som kan vara ett BINARYEXPR, och så vidare. Detta är inte direkt rekursion, som när en lista innehåller listor eller en funktion direkt anropar sig själv, men det är ändå rekursion. Som tur är klarar ju även Python av rekursiva anrop. Alltså kan man skriva interpretatorn på ett väldigt naturligt sätt, där evalueringsfunktionerna indirekt kan anropa sig själva. Med andra ord, parse_expression för ['x', '+', 5] kan vid behov anropa parse_binaryexpr, som sedan igen kan anropa parse_expression för värdet 'x'. Med hjälp av rekursionen fungerar detta automatiskt för ett godtydligt antal nivåer i godtyckligt komplicerade uttryck, och vi behöver bara tänka på en nivå i taget.

6.5 Variabeltabeller och funktionell programmering

Hur håller man reda på vilket värde en variabel har? I den interpretator du ska skriva kommer du att använda en variabeltabell, som implementeras som en dict som mappar variabelnamn till variablernas värden. Följande representerar till exempel att variabeln 'a' har värdet 7:

>>>my_table = {'a': 7}

Denna variabeltabell representerar programmets nuvarande tillstånd.

De funktioner som interpreterar olika delar av ett calc-program behöver alltså få tillgång till variabeltabellen så att de kan slå upp variabelnamnen där. Satsen ['print', 'a'] behöver t.ex. veta det nuvarande värdet på 'a', och behöver alltså en variabeltabell. Var ska den då komma från?

Man kunde tänka sig att göra tabellen till en global variabel, men det är allmänt en dålig idé, av flera anledningar. Till exempel gör det ju att man bara kan ha en variabeltabell i taget, och då blir det svårt att utöka språket så att man t.ex. kan skapa egna funktioner i 'calc'. Som vi har sett i Python ska tilldelningar i en funktion inte påverka tilldelningar i en annan:

def change_x(): x = 10 print(x) # prints 10 def main(): x = 8 y = 12 print(x) # prints 8 change_x() # prints 10 print(x) # prints 8

I exemplet ovan hade change_x och main sina egna värden på 'x', och tilldelningen i change_x påverkade inte värdet på x i main. Detta blir svårare att göra om man har en enda gemensam variabeltabell.

Istället får vi göra så att vi skickar in en variabeltabell som parameter till varje funktion i implementationen, t.ex. till eval_program som kommer att vara huvudfunktionen för att interpretera ett helt program.

Satser av typ 'input' och 'set' kommer att ändra variabelvärden, och alltså ändra programmets tillstånd. När sådana satser tolkas och utförs ska vi se till att inte ändra i den nuvarande variabeltabellen, som kom in som en parameter. Istället ska vi programmera funktionellt och icke-destruktivt, så vid just dessa tillfällen (när en variabel ska få ett nytt värde) ska vi skapa en kopia av den gamla tabellen och göra ändringen i denna kopia.

Så hur får anroparen tag på den ändrade tabellen? Lämpligen returnerar man alltid den tabell som gäller efter den tolkade satsen, vilket då kan vara antingen en ny tabell enligt ovan, eller den gamla om satsen inte ändrade några variabelvärden.

På detta sätt är det upp till anroparen att välja om man vill använda den nya tabellen eller inte. I denna labb kommer anroparen alltid att använda den nya tabellen, men i en utökning där man kan definiera nya egna funktioner i Calc-språket skulle det finnas tillfällen där man inte använde den nya tabellen. Anta t.ex. att en utökad Calc höll på att interpretera en motsvarighet till main-funktionen i Python-exemplet ovan. Vid anropet till change_x skulle en tom variabeltabell skickas in, så att change_x inte får tillgång till variabelvärdena för x och y från main. När change_x returnerade skulle tolkningen av main slänga bort den returnerade variabeltabellen, där x=10, och istället fortsätta med sin gamla variabeltabell där x=8,y=12.

Tips: För att kopiera variabeltabellen kan man använda sig av flera olika metoder.

• Eftersom våra variabeltabeller är grunda (inte innehåller nästlade listor, dictionaries eller liknande strukturer) går det utmärkt att använda metoden dict.copy() för att skapa en kopia.
• I mer komplexa fall kan man använda 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). Om värdet på en variabel i variabeltabellen skulle kunna vara en lista, skulle man kunna behöva använda deepcopy så att även listan blev kopierad istället för återanvänd.

6.6 Uppgifter

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03