Kompilatorer och interpretatorer för civilingenjörer: Hemtentamen 2020-03-20

Tid: 08:15 - 14: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. Lös de angivna uppgifterna och samla svaren på lämpligt sätt, till exempel i en PDF. Skicka sen in lösningarna till mig, antingen som ett kursmeddelande i Blackboard eller via vanlig e-post (thomas.padron-mccarthy@oru.se), senast vid tentatidens slut.
4. Om du inte senast under dagen efter tentan får 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 Hotmail.com, Outlook.com, Live.com) ibland kastar bort brev med bilagor, utan att meddela det.
5. Skriv gärna svaren i ett ordbehandlingsprogram. Rita gärna eventuella diagram i ett ritprogram. Undvik helst att skicka in Word-dokument, om de inte konverterats till PDF. Det är inte förbjudet att skriva och rita för hand, men då måste text och bilder scannas in eller fotograferas. Det ska finnas scanner-appar till Android och iPhone, och de ska ge bättre resultat än att bara ta vanliga kort med kameran.
6. Tentatiden är utökad med två timmar för att täcka in problem med e-post, inscanning eller fotografering av diagram, och liknande.
7. 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 dina program, kommandon och liknande.
8. 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.
9. 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.
10. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
11. 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.
12. Maximal poäng är 41. För godkänt betyg krävs totalt minst 21 poäng.
13. Resultat meddelas på kursens hemsida eller via e-post senast fredag 10 april 2020. 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 (10 p)

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

#inglude <stdio.h>              // error: invalid preprocessing directive #inglude

int main(void) {
    int x, y, z, t;

    printf("Ange x: );          // warning: missing terminating " character
    scanf("%d", &x);
    printf("Ange y: ")          // error: expected ';' before '}' token
    scanf("%d", y);             // Segmentation fault (core dumped)
    t = x + y;                  // warning: variable 't' set but not used
    u = x + y;                  // error: 'u' undeclared
    printf("z = %d\n", z);      // warning: 'z' is used uninitialized
    f(8);                       // warning: implicit declaration of function 'f'
                                // undefined reference to 'f'
} // main

Uppgift 3 (5 p)

x = y;
z = y - z * 2 - t * 3 * 4;
if (u < v) {
    t = t + 5;
    u = u + 6;
    v = v + 7;
}
else {
    t = t + 7;
}

Ö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

Man ska kunna mata in personer som ska spåras, genom att skriva till exempel person 1 eller person 17. Man ska också kunna mata in vem som smittat vem, genom att skriva till exempel person 1 har smittat person 2. Personer och "smittningar" ska kunna matas in i godtycklig ordning.

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

person 1
person 2
person 1 har smittat person 2
person 3
person 2 har smittat person 3
person 4
person 3 har smittat person 4

Uppgift 4 (3 p)

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

Uppgift 5 (5 p)

Uppgift 6 (5 p)

person 1
person 1 har smittat person 1
person 1 har smittat person 2

b) Enligt inmatningen ovan har person 1 smittat sig själv. Det kan knappast vara rätt. Förklara vilken inverkan det har på parse-trädet.

c) Enligt inmatningen ovan har person 1 smittat person 2, men person 2 finns inte angiven i inmatningen. Det verkar inte heller vara rätt. Förklara vilken inverkan det har på parse-trädet.

Uppgift 7 (8 p)