Institutionen för teknik Department of Engineering
Thomas Padron-McCarthy ( thomas.padron-mccarthy@oru.se ) Thomas Padron-McCarthy ( thomas.padron-McCarthy @ oru.se )
Kompilatorer och interpretatorer Compilers and Interpreters
för Dataingenjörsprogrammet m fl for Computer Engineering Program, etc.
lördag 30 oktober 2010 Saturday, October 30, 2010
Gäller som tentamen för: Does the exam:
DT3004 Datateknik C, Kompilatorer och interpretatorer, provkod 0100 DT3004 Computer Engineering C, Compilers and Interpreters, sample code 0100
→ This exam is also available in an English version. → This exam is also available in an English version.
| Hjälpmedel: Accessibility: | Inga hjälpmedel. No aids. |
| Poängkrav: Score requirements: | Maximal poäng är 32. Maximum score is 32. För godkänt betyg (3 respektive G) krävs 16 poäng. To pass (3 or G) required 16 points. |
| Resultat: Results: | Meddelas på kursens hemsida eller via e-post senast lördag 20 november 2010. Announced on the course website or e-mail by Saturday 20 November 2010. |
| Återlämning av tentor: Return of the exams: | Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning. After that the result announced exams can be downloaded from the university's central examination extradition. |
| Examinator: Examiner: | Thomas Padron-McCarthy Thomas Padron-McCarthy |
- Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas. Write clearly. Solutions that can not be read can obviously not give any points. Unclear and ambiguous wording will be misinterpreted.
- Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen. Enter the personal exam code on each sheet submitted. Do not write names or numbers on the leaves.
- Skriv bara på en sida av papperet. Använd inte röd skrift. Write only on one side of the paper. Do not use red letters.
- Antaganden utöver de som står i uppgifterna måste anges. Assumptions beyond those contained in the data must be entered.
- Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt. Please write explanations about how you thought. Even an answer that is wrong can give points, if there is a statement that the key ideas were right.
Uppgift 1: Faser (3 p) Task 1: Phases (3 credits)
När vi kompilerar följande försök till C-program, ger kompilatorn de kursiverade fel- och varningsmeddelandena: When we compile the following attempts to C programs, gives the compiler the italicized error and warning messages:En kompilators arbete brukar delas in i flera faser. I vilka faser upptäcks de olika felen? A compiler's work is usually divided into several phases. In which phases detected the errors?#include <stdio.h> # Include <stdio.h> int main(void) { int main (void) { int a; int a; printf("Hej!\n ); error: missing terminating " character printf ("Hello \ n); error: missing terminating" character printf("Ange ett tal: "); printf ("Enter a number:"); scanf("%d", &a ; error: expected ')' before ';' token scanf ("% d", & a; error: Expected ')' Before ',' token printf("Talet var: %d\n", a); printf ("The speech was:% d \ n", a); return "Kalle"; warning: return makes integer from pointer without a cast return "Donald", warning: return makes integer from pointer Without a cast } }
Uppgift 2: Scanning och reguljära uttryck (5 p) Task 2: Scanning and regular expressions (5 points)
a) (2p) Skriv reguljära uttryck ("regexpar") för följande: a) (2 credits) Write regular expressions ("regexp") for the following:- årtal med fyra siffror (dvs från år 1000 till år 9999) year with four digits (ie from year 1000 to year 9999)
- klädstorlekar (som kan vara XS , S , M , L och XL ) clothes sizes (which can be XS, S, M, L and XL)
b) (2p) Skriv ett reguljärt uttryck för svenska personnummer (som till exempel 631211-1658 ). Uttrycket ska matcha alla giltiga personnummer. Det är besvärligt att skriva ett reguljärt uttryck som inte också matchar vissa otillåtna personnummer, så det gör inget om ditt svar gör det. Men förklara minst en kontroll som inte görs av ditt reguljära uttryck. b) (2 credits) Write a regular expression for the Swedish personal identity number (for example 631211-1658). The term will match all valid social security number. It is difficult to write a regular expression that does not also match certain unauthorized personal, so it does not matter if your response does. But stay at least one control that is not made by your regular expressions.
c) (1p) Vad är det för skillnad på en token och ett lexem? c) (1 pt) What is the difference between a token and a lexeme?
Uppgift 3: Grammatiker (10 p) Task 3: Grammar (10 points)
Här är tre saker som kan vara problematiska i en grammatik: Here are three things that are problematic in a grammar: a) vänsterrekursion a) vänsterrekursion
b) FIRST()-konflikter b) FIRST () conflict
c) tvetydighet c) ambiguity
Ge för var och en av dessa saker exempel på en grammatik som uppvisar problemet. Förklara också för var och en av dessa grammatiker hur problemet visar sig i praktiken. (Dvs: vad är det som inte fungerar, på grund av det problemet?) Visa också hur man löser problemet. Provide for each of these things examples of a grammar that exhibits the problem. Explain also for each of these grammars how the problem manifests itself in practice. (That is: what is it that does not work, because of the problem?) View also how to solve the problem.
Uppgift 4: Mellankod (5 p) Task 4: Intermediate (5 points)
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod. Translate the above programs section to two of the three types of intermediate code.x = 1; x = 1; y = 2; y = 2; z = 3; z = 3; while (y == 2) { while (y == 2) { if (z > 4) { if (z> 4) { y = y - 1 - 1; y = y - 1 - 1; } } else { else { z = z + y * z + z; z = z + y * z + z; t = t + 2; t = t + 2; } } } }
a) ett abstrakt syntaxträd (genom att rita upp trädet!) a) an abstract syntax tree (by drawing up the tree!)
b) postfixkod för en stackmaskin b) postfixkod for a stack machine
c) treadresskod 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.) Note: There are three sub-tasks in the task above. Select and answer (at most) two of them. (If you answer all three, count it with maximum points off.) |
Uppgift 5: Några termer (9 p) Problem 5: Some Terms (9 p)
Förklara kort vad följande begrepp från kompilatortekniken innebär: Explain briefly what the following concepts from compiler technology means: a) målspråk a) target language
b) målprogram b) target programs
c) front end c) front-end
d) Yacc d) Yacc
e) symboltabell e) symbol table
f) shift-reduce-konflikt f) Shift reduced-conflict
g) deterministisk ändlig tillståndsmaskin g) deterministic finite state machine
h) reserverat ord h) the reserved word
i) anropskonventioner (på engelska: call sequence) i) calling convention (in English: call sequence)
