• 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.
• Lös bara en uppgift per blad. 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.

Uppgift 1: Faser (6 p)

a) den lexikaliska analysen ("scannern")

b) den syntaktiska analysen ("parsern")

c) den semantiska analysen

Uppgift 2: Grammatiker och parse-träd (12 p)

S -> X Y Z
X -> a | b
Y -> Z | c
Z -> d

a) (2p) Rita upp parse-trädet för strängen bdd.

b) (3p) Vilka strängar, förutom bdd, kan genereras av denna grammatik?

c) (1p) Vad innebär det att en grammatik är tvetydig (engelska: "ambiguous")?

d) (2p) Är grammatiken ovan tvetydig? Motivera svaret!

e) (2p) Just den här grammatiken definierar ett språk som också kan beskrivas med ett reguljärt uttryck. Skriv ett reguljärt uttryck som beskriver språket!

f) (2p) Skulle man kunna beskriva samma språk med ett annat reguljärt uttryck?
Om ja: Ange ett sådant alternativt reguljärt uttryck.
Om nej: Förklara varför man inte kan det.

Uppgift 3: Grammatiktransformationer (8 p)

b) (2p) Visa med ett exempel hur man kan eliminera, dvs ta bort, vänsterrekursion från en grammatik.

c) (1p) Hur påverkas det språk som grammatiken beskriver av att man tar bort vänsterrekursionen från den grammatiken?

d) (2p) I vilka sammanhang behöver man ta bort vänsterrekursion? Varför behöver man göra det?

e) (2p) Man kan ha semantiska aktioner instoppade i grammatiken. Förklara, med exempel, hur man hanterar dessa vid eliminering av vänsterrekursion.

Uppgift 4: Parsning (10 p)

Det reguljära uttrycket a*b[cd] beskriver ett språk som består av strängar som:

• Börjar med noll, ett eller flera a
• Sen kommer ett b
• Sen kommer antingen ett c eller ett d

b) (7p) Skriv den prediktiva recursive-descent-parsern i ett språk som åtminstone liknar C, Java eller Pascal. 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, och att den returnerar typen på nästa token.

Uppgift 5: Mellankodsgenerering (10 p)

  if (x < 7 + y) {
    x = 9 - x - y;
  }
  else {
    while (x > 10) {
      z = x + 1;
      x = 2 * x * (y - 1);
    }
  }

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

b) (3p) postfixkod för en stackmaskin

c) (4p) treadresskod

Uppgift 6: Aktiveringsposter (4 p)

Uppgift 7: Typkontroll (10 p)

Ett exempel, där vi först deklarerar de tre variablerna f, i och s:

f : flyttal;
i : heltal;
s : sträng;

i = 17;
i + i;		// Resultat: heltalet 34
i + 3;		// Resultat: heltalet 20
2 + 5;		// Resultat: heltalet 7
14;		// Resultat: heltalet 14

f = 3.14;
f + f;		// Resultat: flyttalet 6.28
2.1 + f;	// Resultat: flyttalet 5.24

f = 17;		// typfel: f ska innehålla ett flyttal
f = "hej";	// typfel: f ska innehålla ett flyttal
3.5 + 12;	// typfel: flyttal + heltal ej tillåtet
i + 0.5;	// typfel: heltal + flyttal ej tillåtet
"hej" + "hopp"  // typfel: sträng + sträng ej tillåtet

S -> Deklarationslista Satslista
Deklarationslista -> Deklarationslista Deklaration | empty
Satslista -> Satslista Sats | empty
Deklaration -> id ":" Typ ";"
Typ -> "flyttal" | "heltal" | "sträng"
Sats -> Uttryck ";" | id "=" Uttryck ";"
Uttryck -> Konstant | id | Uttryck "+" Uttryck
Konstant -> heltalskonstant | flytalskonstant | strängkonstant