6. Språk

Labb 6 ändrades under 2020. Bland annat delar vi upp arbetet i två delar för att göra det lättare att komma igång och minska mängden information som måste tas in innan man kan börja programmera. Vi har också gjort andra små justeringar här och där. Den gamla labben från 2019 finns också kvar för tidigare studenter.

Om något är oklart eller du hittar några problem i den nya versionen av labben: Prata med din handledare så ska vi titta på det!

6.1 Inledning

Denna laboration och dess tillhörande studiematerial har flera syften.

• Vi illustrerar begreppen interpretator (tolk) och kompilator.
• Vi fortsätter att arbeta med nästlade strukturer -- och rekursiva strukturer, vilket i den här labben helt enkelt betyder att ett uttryck (som 1 + 2) kan innehålla andra uttryck (som 1 och 2).
• Detta ger i sin tur mer övning på att skriva algoritmer, inte minst rekursiva algoritmer, som är mycket väl lämpade för att behandla nästlade strukturer.

För att uppnå målen ska vi gå vidare från det tidigare enkla "logikspråket" och definiera 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.

Ny kurs...

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, men det hade blivit ganska mycket arbete. Då hade vi behövt skriva kod för:

• Lexikalisk analys: "int" är ett separat token och inte tre separata tecken (gå tillbaka till studiematerialet om du inte är med på vad vi menar).
• 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.
• Tolkning och exekvering av det abstrakta syntaxträdet: Hur utför vi satserna och vad blir resultatet?

För att undvika de första två punkterna 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) därför 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 som motsvarar ett syntaxträd. Därmed kan vi hoppa över både den lexikaliska analysen och en stor del av den syntaktiska analysen.

Den nästlade listan är alltså i sig själv 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.

6.2.1. Språket ConstCalc

Att direkt ge sig på hela Calc kan lätt bli en övermäktig uppgift. Därför vill vi gärna hitta en deluppgift som kan slutföras och testas som ett första steg. Detta gör vi genom att strunta i att hantera variabler och upprepning/loopar, och vårt resulterande språk kallar vi för ConstCalc.

Vi använder nu Extended Backus-Naur Form för att beskriva syntaxen för detta språk. Ni har redan lärt er om detta från studiematerialet, men vi använder nu ytterligare ett par språkkonstruktioner i EBNF, inklusive (* ... *)som används för kommentarer.

(* För att vi inte själva ska råka läsa fel och blanda ihop EBNF-komma och det ',' som ingår i vårt språk skapar vi en icke-terminal för detta... *) COMMA = ',' ; (* Ett program består av en följd av satser. Eftersom ordet calc ska stå inom apostrofer behöver vi lägga detta inom citattecken i grammatiken. Jämför med att hakparenteserna ska vara utan apostrofer i vårt språk, men *har* en nivå av apostrofer i grammatiken. *) PROGRAM = '[', "'calc'", COMMA, STATEMENTS, ']' ; (* STATEMENTS är ett ensamt STATEMENT, eller ett STATEMENT följt av komma och STATEMENTS (som i sin tur är 1 STATEMENT som möjligen följs av flera, och så vidare). *) STATEMENTS = STATEMENT | STATEMENT, COMMA, STATEMENTS ; (* En sats kan vara ett val eller en utmatning. *) STATEMENT = SELECTION | OUTPUT ; (* 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. Notera att [ ... ] betyder att det som står inom hakparenteserna får utelämnas ("optional"). *) SELECTION = '[', "'if'", COMMA, CONDITION, COMMA, STATEMENT, [COMMA, STATEMENT], ']' (* En utmatningssats anger ett uttryck vars värde ska skrivas ut. *) OUTPUT = '[', "'print'", COMMA, EXPRESSION, ']' ; (* Ett matematiskt uttryck kan vara en konstant eller ett binärt uttryck. *) EXPRESSION = CONSTANT | BINARYEXPR ; (* Ett binärt uttryck består av två uttryck med en matematisk operator i mitten. *) BINARYEXPR = '[', EXPRESSION, COMMA, BINARYOPER, COMMA, EXPRESSION, ']' ; (* Ett villkor består av två uttryck med en villkorsoperator i mitten. *) CONDITION = '[', EXPRESSION, COMMA, CONDOPER, COMMA, EXPRESSION, ']' ; (* En binäroperator symboliserar ett av de fyra grundläggande räknesätten. Eftersom man i språket måste skriva detta med citattecken som i [10, "+", 20] måste vi här ha med *dubbla* citattecken. Om vi bara skrev '+' skulle uttrycket vara [10, +, 20] vilket inte kan tolkas i Python. *) BINARYOPER = "'+'" | "'-'" | "'*'" | "'/'" ; (* En villkorsoperator är större än, mindre än eller lika med. *) CONDOPER = "'<'" | "'>'" | "'='" ; (* En konstant är ett tal i Python. Text mellan två frågetecken anger att något är definierat "utanför" EBNF -- vi går alltså inte så långt som att vi definierar exakt hur en sträng ser ut. *) CONSTANT = ? a Python number ? ;

6.3 Hjälpfunktioner för att hantera språken

För att lättare kunna hantera ConstCalc- och Calc-program har vi i förväg definierat ett antal hjälpfunktioner i filen calc.py, som redan ska finnas i ditt Git-arkiv för TDDE24. Det finns två kategorier av funktioner: dels har vi igenkänningsfunktioner (eng. recognizers) med namn is_... som testar om ett givet objekt verkar vara en viss konstruktion i språket, dels har vi selektorer som plockar ut de olika delarna av en sammansatt konstruktion.

Som exempel kan vi titta på hjälpfunktionerna för konstruktionen OUTPUT. Vi har först en igenkänningsfunktion som kontrollerar att indata är en lista, att listan har längden 2 samt att första elementet är strängen 'print'. Därefter följer en selektor som plockar ut uttrycket som ska beräknas och skrivas ut.

def is_output(p): """ Returns whether the given argument appears to be a valid output statement """ return isinstance(p, list) and len(p) == 2 and p[0] == 'print' def output_expression(p): """ Returns the expression from a valid output statement """ return p[1]

Se även selektorerna first_statement() och rest_statement(). Dessa är direkt kopplade till att STATEMENTS kan bestå av STATEMENT följt av STATEMENTS. Grammatiken definierar alltså inte en lista av 1 eller flera statements utan ett träd, där en sekvens av 4 stycken STATEMENT i följd formar följande struktur:

STATEMENTS / \ STATEMENT STATEMENTS / \ STATEMENT STATEMENTS / \ STATEMENT STATEMENTS | STATEMENT

Man måste då behandla dem på detta sätt även i implementationen, genom anrop till bland annat first_statement() och rest_statement().

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 = ['print', [4, '+', 5]] >>> is_output(stmt) True >>> output_expression(stmt) ['4', '+', 5]

6.4 Strukturen hos en interpretator

Ovan har vi visat strukturen hos ett ConstCalc-program med hjälp av en EBNF-grammatik. Något som kanske inte är omedelbart uppenbart är att denna struktur även passar utmärkt för själva interpretatorn. För varje språkkonstruktion som vi ska exekvera (program och satser) kommer du att skapa en egen funktion vars namn börjar med exec:

• PROGRAM = '[', "'calc'", COMMA, STATEMENTS, ']' ;

  Detta ska hanteras av funktionen exec_program(program), som behöver kontrollera att program börjar med 'calc', och därefter kan anropa exec_statements() med lämpliga parametrar.

• STATEMENTS = STATEMENT, { COMMA, STATEMENTS } ;

  Detta ska hanteras av funktionen exec_statements(statements), som kan behöva anropa exec_statement() för att tolka en enskild sats.

• STATEMENT = SELECTION | OUTPUT ;

  Detta ska hanteras av funktionen exec_statement(statement), som behöver använda igenkänningsfunktionerna för att testa vilken typ av sats det gäller, och sedan anropa exec_selection() eller exec_output() för att tolka/utföra denna sats -- och så vidare.

På motsvarande sätt skapar du funktioner vars namn börjar med eval_ för de språkkonstruktioner som ska evalueras till ett värde (sanningsvärde eller tal):

• CONDITION = '[', EXPRESSION, COMMA, CONDOPER, COMMA, EXPRESSION, ']' ;

  Detta ska hanteras av funktionen eval_condition(), som tar ett villkorsuttryck (t.ex. [5, "<", [2, "+", 4]]) och returnerar dess sanningsvärde.

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: [3 + [[4 + 5] * 6]].

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, eval_expression för [3 + [[4 + 5] * 6]] kan med hjälp av en igenkänningsfunktion detektera att detta uttryck är ett binärt uttryck, och därmed kan eval_expression anropa eval_binaryexpr... som sedan igen kan anropa eval_expression för parametrarna, som råkar vara värdet 3 och binäruttrycket [[4 + 5] * 6]. 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 Uppgifter, del 1

6.6. Det fullständiga Calc-språket

Nu är det dags att utöka språket för att också hantera variabler -- och då blir det också rimligt att införa fler nya språkkonstruktioner, som loopar. Nyheter är markerade i fetstil nedan.

(* För att vi inte själva ska råka läsa fel och blanda ihop EBNF-komma och det ',' som ingår i vårt språk skapar vi en icke-terminal för detta... *) COMMA = ',' ; (* Ett program består av en följd av satser. Eftersom ordet calc ska stå inom apostrofer behöver vi lägga detta inom citattecken i grammatiken. Jämför med att hakparenteserna ska vara utan apostrofer i vårt språk, men *har* en nivå av apostrofer i grammatiken. *) PROGRAM = '[', "'calc'", COMMA, STATEMENTS, ']' ; (* STATEMENTS är ett ensamt STATEMENT, eller ett STATEMENT följt av komma och STATEMENTS (som i sin tur är 1 STATEMENT som möjligen följs av flera, och så vidare). *) STATEMENTS = STATEMENT | STATEMENT, COMMA, STATEMENTS ; (* En sats kan vara en tilldelning, en upprepning, ett val, en inmatning eller en utmatning. *) STATEMENT = ASSIGNMENT | REPETITION | SELECTION | INPUT | OUTPUT ; (* 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. *) ASSIGNMENT = '[', "'set'", COMMA, VARIABLE, COMMA, EXPRESSION, ']' ; (* En upprepning består av ett villkorsuttryck och en följd av satser, vilka upprepas så länge villkorsuttrycket är sant. *) REPETITION = '[', "'while'", COMMA, CONDITION, COMMA, STATEMENTS, ']' ; (* 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. Notera att [ ... ] betyder att det som står inom hakparenteserna får utelämnas ("optional"). *) SELECTION = '[', "'if'", COMMA, CONDITION, COMMA, STATEMENT, [COMMA, STATEMENT], ']' (* En inmatningssats anger namnet på en variabel som ska få ett numeriskt värde av användaren. *) INPUT = '[', "'read'", COMMA, VARIABLE, ']' ; (* En utmatningssats anger ett uttryck vars värde ska skrivas ut. *) OUTPUT = '[', "'print'", COMMA, EXPRESSION, ']' ; (* Ett matematiskt uttryck kan vara en konstant, en variabel eller ett binärt uttryck. *) EXPRESSION = CONSTANT | VARIABLE | BINARYEXPR ; (* Ett binärt uttryck består av två uttryck med en matematisk operator i mitten. *) BINARYEXPR = '[', EXPRESSION, COMMA, BINARYOPER, COMMA, EXPRESSION, ']' ; (* Ett villkor består av två uttryck med en villkorsoperator i mitten. *) CONDITION = '[', EXPRESSION, COMMA, CONDOPER, COMMA, EXPRESSION, ']' ; (* En binäroperator symboliserar ett av de fyra grundläggande räknesätten. Eftersom man i språket måste skriva detta med citattecken som i [10, "+", 20] måste vi här ha med *dubbla* citattecken. Om vi bara skrev '+' skulle uttrycket vara [10, +, 20] vilket inte kan tolkas i Python. *) BINARYOPER = "'+'" | "'-'" | "'*'" | "'/'" ; (* En villkorsoperator är större än, mindre än eller lika med. *) CONDOPER = "'<'" | "'>'" | "'='" ; (* En variabel är en sträng definierad som i Python -- strängen anger namnet på variabeln. Text mellan två frågetecken anger att något är definierat "utanför EBNF" -- vi går alltså inte så långt som att vi definierar exakt hur en sträng ser ut. *) VARIABLE = ? a Python string ? ; (* En konstant är ett tal i Python. *) CONSTANT = ? a Python number ? ;

6.7 Variabeltabeller och funktionell programmering

Nu har vi alltså infört variabler, men hur håller man reda på vilket värde en variabel har? I den utökade 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 exec_program som fortfarande är 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.8. Uppgifter, del 2

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2023-11-06