Ö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

måndag 17 oktober 2005 kl 08:00 - 13:00 i L0001








Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 60.
För betyget 3 krävs 30 poäng.
För betyget 4 krävs 40 poäng.
För betyget 5 krävs 50 poäng.
Resultat: Meddelas på kursens hemsida senast måndag 7 november 2005.
Visning och frågestund: Måndag 7 november 2005 kl 12:00-12:30 i T2220.
Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.



LYCKA TILL!

Uppgift 1: Faser (6 p)

Välj ett programmeringsspråk som du är van vid, till exempel C, C++ eller Java, och ge konkreta (dvs med utdrag ur programkoden) exempel på fel i ett källprogram som kan upptäckas i:

a) den lexikaliska analysen ("scannern")

b) den syntaktiska analysen ("parsern")

c) den semantiska analysen

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

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

a) (1p) Vad innebär vänsterrekursion?

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)

Vi har terminalerna a, b, c och d.

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

a) (3p) Skriv en kontextfri grammatik som beskriver samma språk som det reguljära uttrycket ovan. Startsymbolen ska vara S. Grammatiken ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).

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

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)

Vad är en aktiveringspost?
Vad används den till?
Vad innehåller den?
Var i minnet brukar den placeras?

Uppgift 7: Typkontroll (10 p)

Ett enkelt programmeringsspråk innehåller tre datatyper: heltal, flyttal och strängar. Man kan deklarera variabler, och man kan addera två heltal eller två flyttal, men inte två strängar.

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