Kodprov 2018-12-19

Öppna en terminal och kör följande kommandon:

1. cd (detta tar dig till din hemkatalog)
2. mkdir kodprov181219
3. cd kodprov181219
4. curl http://wrigstad.com/ioopm/patata.zip
5. unzip k.zip

Nu har du fått ett antal filer och kataloger:

uppgift1 – katalog med alla filer för uppgift 1
uppgift2 – katalog med alla filer för uppgift 2
Makefile – en makefil för att lämna in kodprovet

Denna uppgift går ut på att implementera en string tokenizer i C, analogt med den som redan finns och som användes i Inlupp 1 (2018) i ordfrekvensräknaren. En string tokenizer delar upp en sträng i delsträngar givet vissa avdelare. Om vi tänker att vår avdelare är ',' (kommatecknet) kan vi exemplifiera med följande strängar (för tydlighets skull skriver vi _ istället för mellanslag i exemplen!):

• "Fee,_foo,_fi,_fum!" delas upp i fyra strängar: "Fee", "_foo", "_fi" och "_fum!".
• "Han_var,_som_laxhandlare,_oöverträffad." delas upp i tre strängar: "Han_var", "_som_laxhandlare", och "_oöverträffad.".
• "ett,,,två" delas upp i två strängar: "ett" och "två".
• "ett,", ",ett" och ",ett," delas alla upp i en sträng: "ett".

Observera att endast avdelaren försvinner vid uppdelning, dvs. i ovanstående exempel är alla inledande mellanslag kvar i de resulterade strängarna. Detta går emellertid att lösa genom att ha flera avdelare! Vi skickar in våra avdelare som en sträng av tecken som alla är avdelare (ordningen i strängen spelar ingen roll). Om vi har som avdelare “_,” (dvs. mellanslag och kommatecken) och återbesöker ovanstående exempel blir vi helt av med mellanslagen:

• "Fee,_foo,_fi,_fum!" delas upp i fyra strängar: "Fee", "foo", "fi" och "fum!".
• "Han_var,_som_laxhandlare,_oöverträffad." delas upp i fem strängar: "Han", "var", "som", "laxhandlare", och "oöverträffad.".

Målet med kodprovet är att vi skall återskapa funktionaliteten hos strtok() (och lite mer). Vi börjar med att gå igenom hur strtok() fungerar. Följande kodsnutt skriver ut om den kompileras och körs.

'Fee'
'_foo'
'_fi'
'_fum!'

Kodsnutten:

char *str = strdup("Fee,_foo,_fi,_fum!");
char *delimiters = ",";
char *substring = strtok(str, delimiters);

while (substring)
  {
    printf("'%s'\n", substring);
    substring = strtok(NULL, delimiters);
  }

free(str);

Observera det “märkliga” anropet strtok(NULL, delimiters) inuti loopen. Funktionen fungerar så att vid första anropet sparas strängen som skall delas upp och innan strtok() returnerar sparas internt en pekare till var nästföljande anrop skall börja. Ett anrop vars första argument är NULL anses vara ett efterföljande anrop och ett vars första argument inte är NULL “installerar” en ny sträng som skall tokeniseras. När det inte finns några fel delsträngar returnerar funktionen NULL, vilket vi använder ovan stom stoppargument.

Observera även att strtok() är en destruktiv funktion! Med detta menas att den förstör strängen som skall tokeniseras. Varje delsträng som returneras är faktiskt en delsträng i den ursprungliga strängen, vilket betyder att strtok() kör i konstant minne. Om "Fee,_foo,_fi,_fum!" är strängen som skickades in och avdelarna är “,_” kommer vi efter att vi är färdiga (dvs. efter sista anropet i while-loopen) att ha följande sträng: "Fee\0_foo\0_fi\0_fum!".

Observera att vi faktiskt aldrig tagit bort några mellanslag ut strängen ovan – vi hoppar istället över dem genom att returnera en pekare till det första tecken som inte är en avdelare: första anropet returnerar en pekare till första (och enda) F:et; andra anropet till första f:et, tredje till andra f:et och fjärde till tredje f:et.

Idag skall vi utöka funktionaliteten hos strtok() med att spara undan information så att vi kan återskapa originalsträngen igen. För strängen "Fee\0_foo\0_fi\0_fum!" sparar vi en array av int:ar som ser ut så här: [',', 3, ',' 8, ',', 12, '\0', 18]; Dessa intar kommer i par: ',' och 3 betyder “ersätt 3:e positionen (indexat från 0) med ','”. Att återskapa originalsträngen betyder då att gå igenom arrayen göra ersättningar tills den första inten i paret är \0. Totalt 3 ersättningar skall alltså appliceras för att återfå "Fee,_foo,_fi,_fum!" från "Fee\0_foo\0_fi\0_fum!".

Denna uppgift bygger på AST-delen av den symboliska kalkylatorn (dvs. ingen parsning). Koden för ett abstrakt syntaxträd med följande konstruktioner är utdelad. Du kommer inte att behöva läsa och förstå den mesta av denna kod!

• Satser (Statement):
  • Tilldelning (Assigment), t.ex. x = 42 som tilldelar resultatet av ett uttryck till en variabel.
  • Utskrift (Print), t.ex. print(3 + 5) som skriver ut resultatet av ett uttryck på terminalen.
  • Variabeldeklaration (VariableDeclaration), t.ex. var x som anger att en variabel finns och kan tilldelas.
  • Sekvenser (Sequence), t.ex. var x; x = 42; print(x); som grupperar ;-separerade satser som evalueras i ett gemensamt environment.
  • Uttryck enligt nedan.
• Uttryck (Expression):
  • Variabler (Variable), t.ex. x.
  • Addition (Addition) och subtraktion (Subtraction) t.ex. x + 4 och y + (2 - z).
  • Konstanter av heltalstyp (Integer), flyttalstyp (Float) och strängkonstanter (StringLiteral).
  • Konstanten “bottom” (Bottom) som avser avsaknaden av ett värde (jmf. null).

Utöver dessa klasser finns ytterligare abstrakta klasser som ingår i en arvshierarki under Statement, samt klassen Environment som håller reda på variablers värden. Observera att Environment hanteras lite annorlunda än i inlupp 3 – för enkelhets skull har den blivit global.

För enkelhets skull är dessa klasser deklarerade i två olika filer:

• ASTFixed.java – här ligger klasser som du INTE FÅR ändra i
• YourCode.java – här ligger klasser som du FÅR ändra i (detta är den enda fil som lämnas in!)

Testkod finns i Driver.java.

Nedan följer några exempel på valida “program” i form av sekvenser av satser, för tydlighets skull skrivna på olika rader. Följande program skriver ut “49” som sitt resultat.

var x;        // anger att variabeln x finns och har värdet "bottom"
var y;        // anger att variabeln y finns och har värdet "bottom"
var z;        // anger att variabeln z finns och har värdet "bottom"
x = 7;        
y = 42;
z = x + y;
print(z);

Följande program skriver ut “<bottom>” som sitt resultat. Analogt med att printa null.

var z;        // anger att variabeln z finns och har värdet "bottom"
print(z);

Följande program skriver ut “A/An java.lang.RuntimeException was thrown (Bottom used as a value!)”. Analogt med att avreferera null.

var x;       // anger att variabeln x finns och har värdet "bottom"
var y;       // anger att variabeln y finns och har värdet "bottom"
print(x + y);

Följande program skriver ut “A/An java.lang.RuntimeException was thrown (Access to undeclared variable!)” eftersom z inte deklarerats innan den användes.

print(z);