Kompilatorer och interpretatorer: Hemtentamen 2020-08-18

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

A -> A x | y

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

A -> x y | x z

Skriv om till dessa tre produktioner:

A -> x R
R -> y | z

Uppgift 1 (5 p)

Uppgift 2 (5 p)

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!

(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)

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

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

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)

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)

Uppgift 6 (5 p)

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)