Kompilatorer och interpretatorer: Hemtentamen 2020-08-18

Det här är hemtentan som går tisdag 18 augusti 2020 i kursen DT125G Kompilatorer och interpretatorer, provkod A001. Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), telefon 070-73 47 013.

Tid: 14:15 - 19:15

Instruktioner

  1. Den här hemtentan ersätter den planerade salstentan, och är endast för de studenter som anmält sig till den tentan.
  2. Uppgifterna ska lösas enskilt, dvs inga grupper av två eller flera studenter.
  3. Du får använda dator, böcker och vilka andra hjälpmedel som helst, men du får inte samarbeta eller fråga någon (utom mig). Exempelvis är det tillåtet att söka och läsa på webbplatser som Stack Overflow, men inte att ställa egna frågor. Du kan alltså provköra kommandon och program, om du vill.
  4. Diskutera inte uppgifterna eller dela med dig av svar förrän tidigast dagen efter tentan.
  5. Lös de angivna uppgifterna och samla svaren på lämpligt sätt, till exempel i en PDF.
  6. Den här kursen fick aldrig någon Blackboard-sida när den gick, så tentan kommer därför att publiceras på kursen vanliga webbsida, http://basen.oru.se/kurser/koi/2019-2020-p1/. Skicka in svaren med vanlig e-post (thomas.padron-mccarthy@oru.se), senast vid tentatidens slut. Om du inte senast en timme efter tentatidens slut fått ett svar från mig med en bekräftelse på att du skickat in svaren, bör du kontakta mig, enklast genom att ringa eller SMS:a mig (ifall det är e-posten som inte fungerar). Tänk på att en del mailtjänster (särskilt Microsoft-tjänster som Hotmail.com, Outlook.com och Live.com) ibland kastar bort brev med bilagor, utan att meddela det.
  7. Skriv gärna svaren i ett ordbehandlingsprogram. Rita gärna eventuella diagram i ett ritprogram. Det är inte förbjudet att skriva och rita för hand, men då måste text och bilder scannas in eller fotograferas. Det finnas scanner-appar till Android och iPhone, till exempel Adobe Scan, som ger bättre resultat än att bara ta vanliga kort med kameran.
  8. Tentatiden är utökad med en extra timme för att täcka in problem med e-post, inscanning eller fotografering av diagram, och liknande.
  9. Om du behöver fråga något, så kontakta gärna mig. Ring eller skicka SMS, för jag kanske inte kommer att sitta vid datorn hela tiden.
  10. Oklara och tvetydiga formuleringar kommer att misstolkas. Lösningar som inte går att läsa eller förstå kan naturligtvis inte ge några poäng.
  11. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
  12. Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.
  13. Maximal poäng är 36. För godkänt betyg krävs minst 20 poäng.
  14. Resultat meddelas senast 15 arbetsdagar efter tentamensdatum. Eftersom svaren skickas in elektroniskt scannas tentorna inte för retur.

Formelsamling

1. Eliminering av vänsterrekursion

En vänsterrekursiv grammatik kan skrivas om så att den inte är vänsterrekursiv. Antag att en regel (eller, korrektare uttryckt, två produktioner) i grammatiken ser ut så här:
A -> A x | y
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:

A -> y R
R -> x R | empty

2. Vänsterfaktorisering

Antag att grammatiken innehåller denna regel (två produktioner):
A -> x y | x z
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

Skriv om till dessa tre produktioner:

A -> x R
R -> y | z

Uppgift 1 (5 p)

En kompilators arbete brukar delas in i ett antal faser. Ange vilka det är, och förklara kort vad varje fas gör. Vad är in- och utdata från respektive fas?

Uppgift 2 (5 p)

Vi ska skriva ett program som hjälper elever i lågstadiet att träna på addition. Meningen är att eleven ska mata in två tal och även deras summa, och så skriver programmet ut om det var rätt eller fel. Två körexempel, med elevens inmatning understruken:
En övning i addition!
Ange två tal och deras summa: 10 29 39
Rätt!
En övning i addition!
Ange två tal och deras summa: 20 30 60
Nej, 20 + 30 blir 50!
C-programmet nedan är tyvärr inte helt korrekt, och när vi försöker köra det får vi de kursiverade fel- och varningsmeddelandena. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna? Motivera dina svar!

(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)

#include <stdio.h>

int main(void) {
  int a, b, summan;

  printf("En övning i addition!\n)    // warning: missing terminating " character
  printf("Ange två tal och deras summa: "); // error: expected ';' before 'printf'
  scanf("%d", &a);
  scanf("%d", b);                     // Segmentation fault (core dumped)
  scanf("%d", &gissning);             // error: 'gissning' undeclared
  if (gissning == summan)             // warning: 'summan' is used uninitialized
    printf("Rätt!\n");
  else
    print("Nej, %d + %d blir %d!\n",  // undefined reference to 'print'
          a, b, summan);
  return "0"; // warning: returning 'char *' from a function with return type 'int'
}

Uppgift 3 (5 p)

Det här är ett programavsnitt i ett C-liknande språk:
a = b - c - d * e;
while (c < d) {
    if (e < f)
        c = c + 1;
    else
        d = d - 1;
    e = c;
}

Översätt ovanstående programavsnitt till två av följande tre typer av mellankod. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod

Scenario till uppgift 4-7

Här är några tomatplantor med än så länge ganska omogna tomater:

Tomater

För att hjälpa tomatodlare att hålla reda på sina tomater har vi skapat ett särskilt tomatspråk. Man kan använda tomatspråket för att mata in vilka tomater och tomatplantor man har. Varje tomat och varje tomatplanta ska ha ett unikt nummer.

Man ska kunna mata in vilka tomatplantor man har, genom att skriva till exempel planta 1 eller planta 17. Man ska kunna mata in vilka tomater man har, genom att skriva till exempel tomat 1 eller tomat 17. Dessutom kan man ange ett valfritt skick både på plantorna och tomaterna, så i stället för bara planta 17 eller tomat 17 kan man skriva exempelvis planta 17 vissen respektive tomat 17 omogen. Skicket utgörs av ett enda ord, som i sin tur består av bokstäver.

Man kan också ange att en eller flera tomater sitter på en viss tomatplanta med kommandot placering, till exempel placering 1, 2, 4, 17 på 12, vilket betyder att tomat nummer 1, 2, 4 och 17 sitter på planta 12.

Här är ett exempel på hur en fullständig inmatning kan se ut:

planta 1
planta 2 avbruten
tomat 1
tomat 2 mogen
tomat 3 rutten
placering 1, 2, 3 på 1
tomat 4
placering 4 på 1
planta 3 brunnit
Tomatspråket kan skrivas i fritt format, så inmatningen ovan kan också skrivas till exempel så här:

planta 1 planta             2 avbruten tomat 1 tomat 2 mogen tomat

3 rutten placering 1
, 2    , 3 på 1 tomat 4 placering 4 på 1 planta 3 brunnit

Uppgift 4 (3 p)

a) Två av terminalerna som behövs för att man ska kunna skriva en grammatik för språket är heltal och skick. Ett heltal är ett positivt heltal skrivet med vanliga decimala siffror 0-9. Ett skick är en följd av bokstäver. Skriv reguljära uttryck som beskriver hur heltal och skick får se ut.

b) Vilka andra terminaler, förutom heltal och skick behövs för att man ska kunna skriva en grammatik för språket?

Uppgift 5 (5 p)

Skriv en grammatik för språket. Startsymbolen ska vara inmatning, som representerar en fullständig inmatning enligt scenariot ovan.

Uppgift 6 (5 p)

a) Ett parse-träd (ibland kallat "konkret syntaxträd") innehåller noder för alla icke-terminaler. Rita upp parse-trädet för den här inmatningen, enligt din grammatik i uppgiften ovan:

planta 1
tomat 2
placering 3 på 4
planta 4

b) Enligt inmatningen ovan sitter tomat 3 på planta 4, men tomat 3 finns inte med i inmatningen, och planta 4 matar man inte in förrän efteråt. Det verkar inte vara rätt. Förklara vilken inverkan detta har på parse-trädet!

Uppgift 7 (8 p)

Skriv en prediktiv recursive-descent-parser för språket. i ett språk som åtminstone liknar C, C++, C# eller Java. Du behöver inte skriva exakt korrekt programkod, men det ska framgå vilka procedurer som finns, hur de anropar varandra, och vilka jämförelser med tokentyper som görs. Du kan anta att det finns en funktion som heter scan, som returnerar typen på nästa token, och en funktion som heter error, som man kan anropa när något gått fel och som skriver ut ett felmeddelande och avslutar programmet.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 13 augusti 2020