Kompilatorer och interpretatorer: Hemtentamen 2021-10-29

Tid: 08:15 - 13:15

Instruktioner

1. Den här hemtentan ersätter den planerade salstentan.
2. 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.
3. Uppgifterna ska lösas enskilt, dvs inga grupper av två eller flera studenter.
4. 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. Självklart är det förbjudet att använda sig av webbplatser och tjänster där man, gratis eller mot betalning, kan få andra att lösa ens uppgifter.
5. Diskutera inte uppgifterna eller dela med dig av svar förrän tidigast dagen efter tentan.
6. 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 i Blackboard. (Gå till kursens sida i Blackboard, gå in i mappen Hemtentor, och välj den rätta tentan. Där kan man sedan välja att skicka in sin lösning. Då blir bedömningen anonym.)
7. Om det skulle bli problem med Blackboard, kan man i nödfall skicka in svaren antingen som ett kursmeddelande i Blackboard eller via vanlig e-post (thomas.padron-mccarthy@oru.se), senast vid tentatidens slut. Då blir bedömningen inte anonym.
8. I Blackboard ser du att du skickat in din lösning. Om du i stället skickade in med e-post, och 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.
9. 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.
10. 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.
11. 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.
12. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
13. 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.
14. Maximal poäng är 35. För godkänt betyg krävs minst 20 poäng.
15. Resultat meddelas senast 15 arbetsdagar efter tentamensdatum. Eftersom svaren skickas in elektroniskt scannas tentorna inte för retur.

Information från institutionen angående fusk

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)

Ange antalet tal: 5
Ange tal nummer 1: 10
Ange tal nummer 2: 20
Ange tal nummer 3: 10
Ange tal nummer 4: -4
Ange tal nummer 5: 100
Genomsnitt: 27.200000

Programmet, som visas nedan, är tyvärr inte helt korrekt, och när vi försöker bygga och köra det får vi de angivna fel- och varningsmeddelandena. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna?

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

#include <stdio.h>

int start(void) {
    int antal;
    printf("Ange antalet tal: ");
    scanf("%d", &antalet);
    Int summa = 0;
    for (int i = 0; i < antal; ++i) {
        int talet = "0"
        printf("Ange tal nummer %d: ",
               i + 1);
        scanf("%d", talet);
        summa += 3talet;
    }
    printf("Genomsnitt: %f\n",
           1.0 * summa div antal);
}

(1) undefined reference to "main"


(2) error: "antalet" undeclared
(3) error: unknown type name "Int"
(4) warning: "antal" is used uninitialized
(5) warning: initialization of "int" from "char *"
(6) error: expected "," or ";" before "printf"

(7) Segmentation fault (core dumped)
(8) error: invalid suffix "talet" on integer constant


(9) error: expected ")" before "div"
(10) warning: control reaches end of non-void function

Uppgift 2 (5 p)

if (x * y == z * t * t) {
    x = y;
    while (z < t) {
        x = y * z * t;
        y = z * t;
    }
    x = y;
}
else {
    z = t;
}
t = x;

Ö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 de övriga uppgifterna

Vi ska skapa ett inmatningsspråk för att ange vilka klasser som finns på en skola, och vilka elever som går i dem. I språket kan man ge de här kommandona:

• Kommandot klass, som används för att ange att det finns en klass. Kommandot består av ordet klass, följt av namnet på klassen inom citationstecken, och avslutas med ett semikolon. Exempel: klass "1a";
• Kommandot elev, som anger att det finns elever, och vilken klass de går i. Kommandot består av ordet elev, följt av ett eller flera elevnamn inom citationstecken, med kommatecken mellan namnen, följt av i vilken klass dessa elever går, och avslutas med ett semikolon. Exempel: elev "Anna Alm", "Bodil Berg" i klass "1a";
• En alternativ form av elev-kommandot anger att det finns elever, men som inte blivit placerade i någon klass. Kommandot består av ordet elev, följt av ett eller flera elevnamn inom citationstecken, med kommatecken mellan namnen, och avslutas med ett semikolon. Exempel: elev "Cecilia Citron", "Donald D. Duck";
• Kommandot klart, som avslutar inmatningen. Exempel: klart;

En komplett inmatning i språket består av noll eller flera klass- och elev-kommandon, följt av ett klart-kommando. Kommandona kan skriva i godtycklig ordning, utom klart-kommandot som måste komma sist i inmatningen. Kommandon kan skrivas på fritt format, dvs att man kan stoppa in godtyckliga mellanslag och radbrytningar, utom inuti namnen som avgränsas med citationstecken. Exempel på en komplett inmatning:

klass "1a";
elev "Anna Andersson" i klass "1a";
klass "2a";
elev "Bengt Bengtsson" i klass "2a";
elev "Conny C Cornström III",
     "Hosianna Davidsson"
     i klass "1a";
klass "2b";
klass "2 reserv";
elev "Eru Ilúvatar", "Filip Filipsson";
klart;

Uppgift 3 (4 p)

b) Det kan hända att en eller flera av terminalerna inte har fixa lexem, utan kan se ut på olika sätt. Skriv i så fall reguljära uttryck som beskriver hur de får se ut.

Uppgift 4 (4 p)

Uppgift 5 (5 p)

Uppgift 6 (4 p)

elev "Anna Alm" i klass "3b";
elev "Bob Berg", "Conny C Cornström III", "Napoleon";
klart;

Uppgift 7 (8 p)