Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)








Ordinarie tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

tisdag 18 mars 2003 kl 14:00 - 19:00








Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 48.
För betyget 3 krävs 24 poäng.
För betyget 4 krävs 32 poäng.
För betyget 5 krävs 40 poäng.
Resultat och lösningar: Meddelas på kursens hemsida senast tisdag 1 april 2003.
Visning: Onsdag 2 april 2003 kl 12:00-13:00 i T2220.
Därefter kan tentor hämtas på expeditionen.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.



LYCKA TILL!


Uppgift 1: Kontextfri grammatik (5 p)

Skriv en grammatik för sökfraser i en sökmotor på webben. En sökfras består av ett eller flera sökord, som kan bindas ihop med de binära operatorerna and och or, och med den unära operatorn not, och som dessutom kan grupperas med parenteser. Not har högst prioritet, och and har högre prioritet än or.

Exempel på sökfraser:

Grammatiken ska klara det angivna språket, och operatorernas prioritet ska bli rätt. Detta ska göras med hjälp av själva grammatiken, och inte med %prec-konstruktionen från Yacc. Såväl and som or är kommutativa, så deras associativitet är godtycklig.

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

I följande grammatik är S, X och Y icketerminaler. a, b, c och d är terminaler. S är startsymbol.
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)

Grammatiken i uppgift 2 kan, visar det sig, även beskrivas med ett reguljärt uttryck (engelska: regular expression).

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;
  }
}
Översätt ovanstående programavsnitt till

a) ett abstrakt syntaxträd

b) postfixnotation

c) treadresskod

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

Ge en grammatikregel för en while-sats i ett högnivåspråk.

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)

Ett enkelt programmeringsspråk innehåller två datatyper: tal och strängar. Man kan deklarera variabler, och man kan addera två värden av samma typ.

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
Här är en grammatik för språket:
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
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.

Uppgift 7: Aktiveringsposter (4 p)

Vad är en aktiveringspost?
Vad används den till?
Hur kan den se ut?
Var i minnet placeras den?