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.) |