• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara 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. Gjorda antaganden får inte förändra den givna uppgiften.

Uppgift 1: Kontextfri grammatik (5 p)

Exempel på sökfraser:

• bil
  Jag vill hitta information om bilar.
• bil or traktor
  Jag vill hitta information som handlar om bilar eller om traktorer.
• bil and not traktor
  Jag söker efter webbsidor som innehåller ordet bil, men inte innehåller ordet traktor.
• bio and pirater and Örebro or teater and (Gnesta or Ånge)
  Jag vill antingen se en piratfilm i Örebro, eller så vill jag gå på teater i Gnesta eller Ånge.

Uppgift 2: Top-down-parsning (15 p)

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

a) Ange tio olika strängar som ingår i det språk som beskrivs av grammatiken ovan.

b) Grammatiken lämpar sig inte för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser). Ange vilka problem det är, vad i grammatiken som orsakar problemen, och vad som händer i parsern.

c) Använd de transformationer som tagits upp i kursen för att omvandla grammatiken till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Ange de generella transformationsregler som du använder, och visa vad resultatet blir för den här grammatiken.

d) 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 3: Lexikalisk analys (3 p)

a) Ange det uttrycket.

b) Ange en grammatik som inte kan ersättas med ett reguljärt uttryck, och förklara varför det inte går!

Uppgift 4: Mellankodsgenerering (9 p)

while (i < x + y) {
  if (x > 0) {
    y = y - 1;
  }
  else {
    a = b * c + d * e;
    d = e;
    f = h - i - j;
  }
}

a) ett abstrakt syntaxträd

b) postfixnotation

c) treadresskod

Uppgift 5: Syntaxstyrd översättning (5 p)

Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av while-satsen till stackmaskinkod. Antag att översättningsschemat ska implementeras i bottom-up-parsningmiljö med en stack, som i Yacc och Bison. Utgå från din grammatikregel ovan, som dock kanske måste modifieras. Förklara införda attribut och eventuella funktioner och instruktioner som används. Ange alla dina antaganden.

Uppgift 6: Typkontroll (7 p)

Exempel:

variable s : string;
variable i : number;

i = 17;
i + i;		// Resultat: talet 34
i + 3;		// Resultat: talet 20

s = "foo";
s + s;		// Resultat: strängen "foofoo"
s + "hej";	// Resultat: strängen "foohej"

s = 17;		// typfel: s ska innehålla en sträng
s = i + 47;	// typfel: s ska innehålla en sträng
"foo" + 17;	// typfel: sträng + tal ej tillåtet
s + i;		// typfel: sträng + tal ej tillåtet
s + 47;		// typfel: sträng + tal ej tillåtet

P -> Ds Ss
Ds -> Ds D | empty
Ss -> Ss S | empty
D -> "variable" id ":" T ";"
T -> "string" | "number"
S -> E ";" | id "=" E ";"
E -> id | string-constant | number-constant | E "+" E

Uppgift 7: Aktiveringsposter (4 p)