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. |
Exempel på sökfraser:
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.
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!
Översätt ovanstående programavsnitt tillwhile (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
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.
Exempel:
Här är en grammatik för språket: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
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.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
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
torsdag 5 juni 2003 kl 14:00 - 19:00
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 68.
För betyget 3 krävs 34 poäng. För betyget 4 krävs 45 poäng. För betyget 5 krävs 57 poäng. |
Resultat: | Meddelas på kursens hemsida senast torsdag 12 juni 2003. |
Visning och frågestund: |
Torsdag 12 juni 2003 kl 12:00-13:00 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
Exempel på uttryck som grammatiken ska klara:
Följande terminaler kan användas i grammatikreglerna: integer, comma, left_bracket, right_bracket, identifier, intersection, union, minus, left_parenthesis, right_parenthesis.
S -> a X | a Y X -> X b | c Z Y -> a | d Z -> e Z | f
a) Rita upp parse-trädet för strängen aceeef.
b) Ange tio andra strängar som ingår i det språk som beskrivs av grammatiken ovan.
c) 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.
d) 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.
e) 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.
b) När är tvetydighet ett problem i en grammatik? När är det det inte? Visa med exempel!
Översätt ovanstående programavsnitt tillx = 0; while (x < 10) { y = y + 2; while (y < 3 + 2 * x) { z = z + x + y; y = y + 1; } x = x + 1; }
a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av if-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.
b) Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.
c) Ofta vill man felsöka program med en symbolisk debugger, som till exempel kan stega fram programmet en rad i taget och visa innehållet i variabler. Vilka problem kan det innebära att felsöka ett optimerat program i en symbolisk debugger? Förklara hur de problemen uppstår.
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
tisdag 16 mars 2004 kl 08:00 - 13:00 i L0001
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 70.
För betyget 3 krävs 35 poäng. För betyget 4 krävs 46 poäng. För betyget 5 krävs 58 poäng. |
Resultat: | Meddelas på kursens hemsida senast tisdag 30 mars 2004. |
Visning och frågestund: |
Tisdag 30 mars 2004 kl 12:00-13:30 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
a) Ange vilka det är, och förklara kort vad varje fas gör. Vad har varje fas för in- och utdata?
b) En viktig del av en kompilator är felhantering. Kompilatorn ska upptäcka, och rapportera, de fel som smugit sig in i källprogrammet. Vilka typer av fel kan upptäckas, och i vilken fas upptäcks varje typ av fel?
Exempel på uttryck som grammatiken ska klara:
Följande terminaler kan användas i grammatikreglerna: +, -, *, /, (, ), sin, cos och number. En terminal av typen number är ett reellt tal.
S -> a X X -> Y | Z Y -> b Y b | a Z -> Z c | c
a) Rita upp parse-trädet för strängen acc.
b) Rita upp parse-trädet för strängen abbbabbb.
c) Det finns minst ett problem med grammatiken som gör att den inte lämpar sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser). Ange vilket eller vilka problem det är, vad i grammatiken som orsakar problemen, och vad som händer i parsern.
d) 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.
e) 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.
Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.
b) Ge exempel på en tvetydig grammatik.
c) När är tvetydighet ett problem i en grammatik? När är det det inte? Visa med exempel!
Översätt ovanstående programavsnitt tillif (x - 3 > y + z) { x = x - y - 1; y = 3 - 2 * z; } else { x = z; }
a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Statement -> for identifier = Expression to Expression do Statement
Statement och Expression är icke-terminaler. for, identifier, =, to och do är terminaler.
Exempel: Satsen
for i = 2 to 5 do Writeln(i)
ger utskriften
2 3 4 5
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av for-satsen till treadresskod. Antag att översättningsschemat ska implementeras i bottom-up-parsningmiljö med en stack, som i Yacc och Bison. Utgå från grammatikregeln. Förklara införda attribut och eventuella funktioner och instruktioner som används. Ange alla dina antaganden.
b) Referensräkning har problem med en viss sorts datastrukturer. Förklara med ett exempel.
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. |
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:
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.
Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.
Översätt ovanstående programavsnitt tilli = 1; j = 0; while (i > j) { if (i < 10) i = i + 1; else j = 10 - i - j; }
a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
När du skriver regeln kan du anta att icke-terminalerna Statement och Expression finns, och terminalerna switch, case, break, default, (, ), {, }, : och ;.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; }
Du kan använda dig av den här regeln för en case-gren:
Branch -> case Expression : Statement break ;
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].
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. |
a) den lexikaliska analysen ("scannern")
b) den syntaktiska analysen ("parsern")
c) den semantiska analysen
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.
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.
Det reguljära uttrycket a*b[cd] beskriver ett språk som består av strängar som:
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.
Översätt ovanstående programavsnitt tillif (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
Ett exempel, där vi först deklarerar de tre variablerna f, i och s:
Här är en grammatik för språket: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
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.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
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
måndag 9 januari 2006 kl 08:00 - 13:00 i L0003
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 58.
För betyget 3 krävs 29 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 30 januari 2006. |
Visning och frågestund: |
Onsdag 1 februari 2006 kl 12:00-12:30 i mitt rum (T2220)
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
#include <stdio.h> int main(void) { int i = 17; float f = 3.14; char c = 'x'; char* s = "foo; (1) missing terminating " character s = f; (2) error: incompatible types in assignment printf("f = %f\n", i); (3) warning: double format, different type arg (arg 2) c s; (4) error: syntax error before "s" return; (5) warning: `return' with no value, in function returning non-void }
Ange för vart och ett av de fem meddelandena i vilken fas i kompilatorn det felet upptäcktes!
S -> A | B | x A -> x | y B -> B z | t
a) (2p) Rita upp parse-trädet för strängen tzz.
b) (4p) Vilka strängar, förutom tzz, 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!
Som exempel kan följande sekvens av kommandon ge upphov till rörelserna i figuren nedan.
start; spring till 5, 3; spring till 9, 3; hoppa tillbaka; spring till 4, 6; hoppa till 1, 6; spring tillbaka; spring till 10, 8; stopp;
a) (3p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för kommandospråket.
b) (5p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Startsymbolen ska heta S.
c) (3p) Om grammatiken från b-uppgiften inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, så transformera den så den passar. (Om den redan är lämplig, behöver du inte göra om den, utan du får 3 poäng på den här deluppgiften i alla fall.)
d) (8p) 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 redan finns en funktion som heter scan, och att den returnerar typen på nästa token.
#include <stdlib.h> int a; int b; void f(int c, int d) { int e; int* p = malloc(sizeof(int)); e = 13; *p = 14; // Här! } void g(int h) { int i; int* p = malloc(sizeof(int)); i = 15; *p = 16; f(h, 17); } int main(void) { int k; k = 18; a = 19; b = 20; g(k); return 0; }
Funktionen main anropar funktionen g, som i sin tur anropar funktionen f. När programexekveringen i funktionen f kommer fram till raden med kommentaren "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.
I minnet kommer det då att finnas ett antal lagringsutrymmen för heltal, som innehåller talen 13-20. Rita upp en skiss över dessa variabler, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".
Översätt ovanstående programavsnitt tillif (a + b > c) { d = 14; while (d < e - f - g) { d = d - 1; } } else { a = x + 2 * y - z + t; b = x + 3; c = x; d = 14; }
a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
b) Referensräkning har problem med en viss sorts datastrukturer. Förklara med ett exempel.
c) Hur kan man lösa det problemet?
Med vissa rättelser.
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
måndag 16 oktober 2006 kl 08:00 - 13:00 i L001
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 40.
För betyget 3 krävs 20 poäng. För betyget 4 krävs 27 poäng. För betyget 5 krävs 34 poäng. |
Resultat: | Meddelas på kursens hemsida senast måndag 6 november 2006. |
Visning och frågestund: |
Måndag 13 november 2006 kl 12:00-12:30 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.) |
Startsymbolen är hälsning.hälsning -> god tidsspecifikation tidsspecifikation -> morgon tidsspecifikation -> middag tidsspecifikation -> kväll tidsspecifikation -> god
(a) (2p)
Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.
Visa hur du fick fram svaret.
(b) (2p)
I ett annat språk ska man kunna skriva godtyckligt många hälsningar (som beskrivs av hälsning i grammatiken för det förra språket) efter varandra, åtskilda med semikolon. Med "godtyckligt många" menas noll, en eller flera.
Skriv en grammatik för detta språk. Glöm inte att ange vad som är startsymbol. Grammatiken ska vara entydig.
(c) (1p)
I deluppgiften ovan stod det att grammatiken skulle vara entydig. Det är motsatsen till att grammatiken är tvetydig. Förklara med exempel vad som menas med att en grammatik är entydig respektive tvetydig.
Men hur ser de data som skickas mellan faserna ut? Beskriv för var och en av de fem kopplingarna mellan faserna vilka data som överförs.
%d-specificerare kan innehålla en fältbredd, som skrivs mellan procenttecknet och d:et. En negativ fältbredd betyder att talet ska vänsterjusteras i fältet.
%f-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av en precision (antal decimaler som ska skrivas ut).
%s-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av ett största antal tecken som får skrivas ut.
Här är några exempel på tillåtna formatsträngar:
S -> a T | b T U T -> T U | U U -> c d | c d d
a)
Gör eventuella transformationer av grammatiken som krävs för att den ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).
b)
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.
sats -> for ( uttryck1 ; uttryck2 ; uttryck3 ) sats1
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av for-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.
Tips: Dessa två loopar kan betraktas som ekvivalenta:
for (i = 0; i < 10; ++i) { whatever(); } i = 0; while (i < 10) { whatever(); ++i; }
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.r = 0; s = 100; while (r < s) { if (s > 0) s = s - (s - r) / 2; else s = 0; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
b) Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.
#include <stdlib.h> int x; void g(int x, int y) { int* p; p = malloc(sizeof(int)); *p = x; // Här! } void f(int y, int z) { int t; t = x; x = y; g(x, x); } int main(void) { int y; x = 1; y = 2; f(3, y); }
Funktionen main anropar funktionen f, som i sin tur anropar funktionen g. När programexekveringen i funktionen g kommer fram till raden med kommentaren "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.
I minnet kommer det då att finnas ett antal lagringsutrymmen för heltal, som innehåller några olika värden. Rita upp en skiss över dessa variabler, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".
Vilka fördelar och nackdelar har den, jämfört med referensräkning?
Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.) |
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
måndag 16 oktober 2006 kl 08:00 - 13:00 i L001
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 40.
För betyget 3 krävs 20 poäng. För betyget 4 krävs 27 poäng. För betyget 5 krävs 34 poäng. |
Resultat: | Meddelas på kursens hemsida senast måndag 6 november 2006. |
Visning och frågestund: |
Måndag 13 november 2006 kl 12:00-12:30 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.) |
Startsymbolen är hälsning.hälsning -> god tidsspecifikation tidsspecifikation -> morgon tidsspecifikation -> middag tidsspecifikation -> kväll tidsspecifikation -> god
(a) (2p)
Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.
Visa hur du fick fram svaret.
(b) (2p)
I ett annat språk ska man kunna skriva godtyckligt många hälsningar (som beskrivs av hälsning i grammatiken för det förra språket) efter varandra, åtskilda med semikolon. Med "godtyckligt många" menas noll, en eller flera.
Skriv en grammatik för detta språk. Glöm inte att ange vad som är startsymbol. Grammatiken ska vara entydig.
(c) (1p)
I deluppgiften ovan stod det att grammatiken skulle vara entydig. Det är motsatsen till att grammatiken är tvetydig. Förklara med exempel vad som menas med att en grammatik är entydig respektive tvetydig.
Men hur ser de data som skickas mellan faserna ut? Beskriv för var och en av de fem kopplingarna mellan faserna vilka data som överförs.
%d-specificerare kan innehålla en fältbredd, som skrivs mellan procenttecknet och d:et. En negativ fältbredd betyder att talet ska vänsterjusteras i fältet.
%f-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av en precision (antal decimaler som ska skrivas ut).
%s-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av ett största antal tecken som får skrivas ut.
Här är några exempel på tillåtna formatsträngar:
S -> a T | b T U T -> T U | U U -> c d | c d d
a)
Gör eventuella transformationer av grammatiken som krävs för att den ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).
b)
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.
sats -> for ( uttryck1 ; uttryck2 ; uttryck3 ) sats1
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av for-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.
Tips: Dessa två loopar kan betraktas som ekvivalenta:
Kom ihåg att dessa
for (i = 0; i < 10; ++i) { whatever(); } i = 0; while (i < 10) { whatever(); ++i; }
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.r = 0; s = 100; while (r < s) { if (s > 0) s = s - (s - r) / 2; else s = 0; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
b) Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.
#include <stdlib.h> int x; void g(int x, int y) { int* p; p = malloc(sizeof(int)); *p = x; // Här! } void f(int y, int z) { int t; t = x; x = y; g(x, x); } int main(void) { int y; x = 1; y = 2; f(3, y); }
Funktionen main anropar funktionen f, som i sin tur anropar funktionen g. När programexekveringen i funktionen g kommer fram till raden med kommentaren "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.
I minnet kommer det då att finnas ett antal lagringsutrymmen för heltal, som innehåller några olika värden. Rita upp en skiss över dessa variabler, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".
Vilka fördelar och nackdelar har den, jämfört med referensräkning?
Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.) |
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
måndag 8 januari 2007 kl 08:00 - 13:00 i L001
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 30.
För betyget 3 krävs 15 poäng. |
Resultat: | Meddelas på kursens hemsida senast måndag 29 januari 2007. |
Visning och frågestund: |
Tisdag 30 januari 2007 kl 15:00-15:30 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, tel: Mellankod (5 p)efon 070-7347013. |
Startsymbolen är S.S -> a T | a U T -> b c U -> c d
(a) (2p)
Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.
Visa hur du fick fram svaret.
(b) (1p)
I ett annat språk ska man kunna skriva godtyckligt många förekomster av strängen a b c. Med "godtyckligt många" menas noll, en eller flera. Exempel på strängar som ska accepteras:
Skriv en grammatik för detta språk. Glöm inte att ange vad som är startsymbol. Grammatiken ska vara entydig.
(c) (1p)
I deluppgiften ovan stod det att grammatiken skulle vara entydig. Det är motsatsen till att grammatiken är tvetydig. Förklara med exempel vad som menas med att en grammatik är entydig respektive tvetydig.
(d) (1p)
Skriv ett reguljärt uttryck som beskriver språket i deluppgift a.
Gör eventuella transformationer av grammatiken i deluppgift 1 a som krävs för att den ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).
b)
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.
Skriv en grammatikregel för while-satsen i C.
b)
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av while-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.if (a - b - c > d + e + f) { g = 100; h = 200; } else { while (i < 20) { i = i + 1; } j = 300; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
a) Antag att vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?
b) Vilka av objekten kommer att tas bort i sopfasen?
c) Antag att vi i stället använder referensräkning. Kan situationen som visas på bilden uppstå? (Vi antar att vi inte är mitt i en uppstädning.)
d) Vi använder fortfarande referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
e) Vi använder fortfarande referensräkning. Vi sätter de båda pekarna som pekar ut ur rotmängden (dvs i dataobjekt 2 och 3) till NULL. Beskriv vad som händer.
Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
fredag 24 augusti 2007 kl 08:00 - 12:00 i L001
Gäller som tentamen för:
TDK104 Kompilatorer och interpretatorer, provkod 0100
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 30.
För betyget 3 krävs 15 poäng. |
Resultat: | Meddelas på kursens hemsida senast måndag 10 september 2007. |
Visning och frågestund: |
Tisdag 11 september 2007 kl 12:00-12:30 i mitt rum (T2220).
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
Startsymbolen är S.S -> a T | b U T -> b c U e U -> c d
(a) (2p)
Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.
Visa hur du fick fram svaret.
(b) (1p)
I ett annat språk ska man kunna skriva godtyckligt många förekomster av strängen a a, följt av strängen bc. Med "godtyckligt många" menas noll, en eller flera. Exempel på strängar som ska accepteras:
Skriv en grammatik för detta språk. Glöm inte att ange vad som är startsymbol. Grammatiken ska vara entydig.
(c) (1p)
I deluppgiften ovan stod det att grammatiken skulle vara entydig. Det är motsatsen till att grammatiken är tvetydig. Förklara med exempel vad som menas med att en grammatik är entydig respektive tvetydig.
(d) (1p)
Skriv ett reguljärt uttryck som beskriver språket i deluppgift a.
a) Vilka andra faser finns det, och i vilken ordning kommer de?
b) I en nyare upplaga av "drakboken" har man delat in optimeringsfasen i två olika faser: maskinoberoende optimering och maskinberoende optimering. Varför har man gjort den uppdelningen?
Gör eventuella transformationer av grammatiken i deluppgift 1 a som krävs för att den ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).
b)
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.
Skriv en grammatikregel för if-satsen i C.
b)
Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av while-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.while (a + (b + c) < a + b + c) { if (i > j) { a = 200; } else { c = b * c + a * j; j = j + 1; } a = j + 1; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
a) Antag att vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?
b) Vilka av objekten kommer att tas bort i sopfasen?
c) Antag att vi i stället använder referensräkning. Kan situationen som visas på bilden uppstå? (Vi antar att vi inte är mitt i en uppstädning.) Motivera svaret.
d) Vi använder fortfarande referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
e) Nu använder vi mark and sweep. Vi sätter de tre pekarna som pekar ut ur rotmängden från dataobjekt 1 och 2 till NULL. Beskriv vad som händer vid nästa skräpsamling.