• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• 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.

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)

#include <stdlib.h>
#include <stdio.h>

int a, b, c;

void f(int d) {
    int a;
    int* p;

    a = 1;
    b = 2;
    c = 3;
    p = malloc(sizeof(int));
    *p = d;

    if (d < 1)
        f(d + 1);

    printf("Här!\n");
}

int main(void) {
    int a;
    int* p;

    a = 4;
    b = 5;
    c = 6;
    p = malloc(sizeof(int));
    *p = 8;
    f(0);
}

När programexekveringen för första gången kommer fram till raden med utskriften "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.

I minnet kommer det då att finnas ett antal heltalsvariabler och andra lagringsutrymmen för heltal, som innehåller olika tal. Rita upp en skiss över dessa variabler och lagringsutrymmen, med innehåll, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".

Uppgift 2 (5 p)

a = 1;
if (b < a - b - c * d) {
    while (i * 2 > j * 3) {
        if (i % 4 == 5)
             i = i + 6;
        b = 7;
    }
    a = 8;
}

a) ett abstrakt syntaxträd (genom att rita upp trädet!)

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 3 (3 p)

a) Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.

b) Vilka av dataobjekten kommer att tas bort?

c) Antag att vi i stället använder skräpsamling med mark-and-sweep. Vilka av dataobjekten kommer att tas bort av skräpsamlaren?

Scenario till uppgift 4-7

Inmatningsspråket består av något vi kan kalla "köp", som består av nyckelordet start, följt av noll eller flera varurader, följt av nyckelordet klart. En varurad består av ett tal (eventuellt med en decimaldel, som då avskiljs med decimalkomma), följt av en enhet (till exempel liter) som kan utelämnas, följt av en textsträng som anger vilken vara man köpt. Exempel på en komplett inmatning av ett köp:

start
1 liter "mjölk"
2,3 kg "ekologiska morötter"
1 "apelsin"
19 "Coca-Cola 33 cl"
klart

Uppgift 4 (3 p)

b) (2p) Vilka andra terminaler, förutom textsträng, behövs för att man ska kunna skriva en grammatik för köpen?

Uppgift 5 (4 p)

Uppgift 6 (3 p)

start
1 "apelsin"
2 "äpple"
klart

Uppgift 7 (8 p)

Uppgift 8 (20 p)