Kompilatorer och interpretatorer
onsdag 11 januari 2023
Gäller som tentamen för:
DT501A Kompilatorer och interpretatorer för civilingenjörer, provkod A001
| Hjälpmedel: | Ordbok för översättning. |
| Poängkrav: |
Maximal poäng är 41.
För godkänt betyg krävs totalt minst 22 poäng. |
| Resultat: | Meddelas senast 15 arbetsdagar efter tentamensdatum. |
| Återlämning av tentor: | Elektroniskt via webbportalen Studenttjänster. |
| Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070 - 73 47 013. |
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> A x | y
Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:
A -> y R R -> x R | empty
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> x y | x z
Skriv om till dessa tre produktioner:
A -> x R R -> y | z
Ange ett tal: 5 Ange ett tal: 6 Genomsnitt: 5.500000 |
Programmet, som visas nedan, är tyvärr inte helt korrekt, och när vi försöker bygga och köra det får vi de angivna fel- och varningsmeddelandena. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna?
(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)
| Programmet | Meddelanden |
|---|---|
#include <stdio.h>
ibt main(void) {
int tal1 tal2;
printf("Ange ett tal: ");
scanf("%d", &tal1);
printf("Ange ett tal: ");
scanf("%d", &tal1)
double snitt = 1.0 * (tal1 + tal2) / 2;
print("Genomsnitt: %f\n", snitt);
}
|
(1) unknown type name "ibt" (2) expected "=", "," or ";" before "tal2" (3) expected ";" before "double" (4) "tal2" is used uninitialized (5) undefined reference to "print" |
S -> a b T | c d U
T -> T e | f
U -> g
a) Grammatiken är inte lämplig för att implementeras med en prediktiv recursive-descent-parser med en token lookahead (en LL(1)-parser). Förklara varför! Vad skulle hända om vi försökte?
b) Visa hur inmatningen a b f e e e parsas av en bottom-up-parser med en stack. Visa vilka skift- och reduce-operationer som utförs, och hur stacken ser ut efter varje operation.
(1) t1 = y * 2 (2) t2 = z * 3 (3) t3 = t1 + t2 (4) if x >= t3 goto (11) (5) t4 = u * 4 (6) u = t4 + 3 (7) t5 = u * 4 (8) t = t5 + 5 (9) t6 = u * 4 (10) v = t6 + 6 (11) t7 = u * 4 (12) w = t7 + 7 |
a) En del av koden verkar onödigt lång, med alla dessa temporära variabler som t1, t2 och så vidare. Kunde inte de tre första instruktionerna ersättas med en enda instruktion, t3 = y * 2 + z * 3? Om inte, varför?
b) Vilka basic blocks finns det?
c) Visa en optimering som går att göra på koden!
Därför vill Örebro kommun skapa en databas för att lagra data om de problem som uppstår. För att underlätta arbetet med databasen skapar vi ett särskilt inmatningsspråk för att mata in problemen. Här är ett exempel på en inmatning:
Inmatningen ovan säger att 24 december 2022 klockan 10:22 var det en elskoter som stod i vägen, och 10 januari 2023 klockan 13:11 var det en som var slängd i en snödriva.
Hela inmatningen ska avslutas med ett klart-kommando, enligt ovan, och innan det kan man skriva noteringar om problem. En notering om ett problem börjar med ett datum på formatet ÅÅÅÅ-MM-DD, ett klockslag på formatet HH:MM, ett kolon, därefter ett antal ord som beskriver vad som hänt, och sist ett semikolon. Ord består av bokstäver och skiljs åt av mellanslag eller andra blanktecken.
Inmatningen kan skrivas på fritt format. Exempelvis är nedanstående inmatning syntaktiskt ekvivalent med den i exemplet ovan.
2022-12-24 10:22: stod i vägen ; 2023-01-10 13:11 : slängd i en snödriva ; klart ;
b) En del av terminalerna har inte fixa lexem, utan kan se olika ut. Skriv, för varje sådan terminal, ett reguljärt uttryck som beskriver hur den får se ut!