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

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

måndag 18 oktober 2004 kl 8:00 - 13:00 i L0001

Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 54.
För betyget 3 krävs 27 poäng.
För betyget 4 krävs 36 poäng.
För betyget 5 krävs 45 poäng.
Resultat: Meddelas på kursens hemsida senast måndag 8 november 2004.
Visning och frågestund: Meddelas senare.
Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.

LYCKA TILL!

Uppgift 1: Kontextfri grammatik (6 p)

En robot ska styras med enkla kommandon som talar om vart roboten ska åka. Målet anges med en x- och en y-koordinat separerade med ett komma. Man kan också ange flera olika mål, separerade med semikolon, för att få roboten att åka mellan flera olika punkter.

Skriv en grammatik för kommandospråket. Grammatiken ska hantera ett enda kommando, med ett eller flera mål. Det är inget krav att grammatiken ska lämpa sig för någon viss typ av parsning, men den ska vara entydig.

Exempel på kommandon som grammatiken ska klara:

Exempel på otillåtna kommandon:

Uppgift 2: Parse-träd (3 p)

Rita upp parse-träden för följande två kommandon:

Uppgift 3: Top-down-parsning (13 p)

Skriv en prediktiv recursive-descent-parser för grammatiken i uppgift 1. Använd 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.

Om den grammatik du gjorde i uppgift 1 inte lämpar sig för implementation av en prediktiv recursive-descent-parser, så gör först om den till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Beskriv vad du gör, och varför.

Uppgift 4: Lexikalisk analys (3 p)

Går kommandospråket i uppgift 1 att beskriva med ett reguljärt uttryck (engelska: regular expression)?

Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.

Uppgift 5: Mellankodsgenerering (10 p)

i = 1;
j = 0;
while (i > j) {
  if (i < 10)
    i = i + 1;
  else
    j = 10 - i - j;
}
Översätt ovanstående programavsnitt till

a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod

Uppgift 6: Semantik (3 p)

Om vi antar en normal semantik för språket som ska översättas i uppgiften ovan, så kommer loopen som ges som exempel inte att terminera, utan programmet kommer att fortsätta i oändlighet. Vilken inverkan har det på syntaxträdet i deluppgift a? Motivera svaret!

Uppgift 7: Kontextfri grammatik, igen (6 p)

Skriv en grammatikregel för switch-satsen i C. Den behöver inte stämma exakt med hur switch-satsen verkligen definieras i den riktiga C-grammatiken, för det är för hemskt, men den ska kunna hantera switch-satser som den här: 
switch (i - j - k) {
  case 1: i = i + 2; break;
  case 2: i = i + 3; break;
  case 3: i = 19; break;
  case k + 7: i = 19; break;
  default: i = 19; break;
}
När du skriver regeln kan du anta att icke-terminalerna Statement och Expression finns, och terminalerna switch, case, break, default, (, ), {, }, : och ;.

Du kan använda dig av den här regeln för en case-gren:

Branch -> case Expression : Statement break ;

Uppgift 8: Exekvering av syntaxträd (10 p)

Vi tänker oss att switch-satsen i föregående uppgift översätts till ett syntaxträd med hjälp av ett syntaxstyrt översättningsschema. För switch-satsen i exemplet ser syntaxträdet ut så här:

Ett syntaxträd för switch-satsen i exemplet

Använd ett språk som åtminstone liknar C, Java eller Pascal, och skriv funktionen execute_switch, som exekverar switch-satsen. Den ska ta en pekare till en trädnod som argument.

Det finns redan en funktion, execute, som tar en pekare till en trädnod som argument. Den kan användas för att beräkna uttryck och utföra satser (utom, tyvärr, just switch-satsen).

Trädnoderna är av typen TreeNode. Du kan anta att trädnoderna har ett typfält som heter type, och som bland annat kan ha värdena SWITCH, CASE och DEFAULT. Noderna har pekare till de underliggande subträden i en array som heter args. Om pekaren p pekar på en trädnod, kan man nå det vänstra subträdet under den noden med uttrycket p->args[0].