Compilers and Interpreters
for Dataingenjörsprogrammet, and others
Thursday January 5, 2023
Exam for:
DT135G Kompilatorer och interpretatorer, provkod A001
Aids: | No aids. |
Score requirements: |
Maximum score is 40.
To pass, at least 22 points are required. |
Results: | Announced no later than 15 working days after the exam. |
Return of the exams: | Electronically through the student portal "Studenttjänster". |
Examiner and teacher on call: | Thomas Padron-McCarthy, phone 070-73 47 013. |
A is a non-terminal, but x and y are any constructions consisting of terminals and non-terminals.A -> A x | y
The rule is replaced by the following two rules (or, more correctly, three productions), that describe the same language, but are not left recursive:
A -> y R R -> x R | empty
A is a non-terminal, but x, y and z are any constructions consisting of terminals and non-terminals.A -> x y | x z
Replace with these three productions:
A -> x R R -> y | z
We write a program to do this. Unfortunately, we have made some errors in our code. In which phase of the compiler, or at which other times, are the following errors detected?
Program | Error |
---|---|
#include <stdio.h> #include <math.h> int main(void) { printf("What is x: "); double x; scanf("%lf", x); printf("Guess the square root: "); scanf("%lf", &g); while (g * g != x) { printf("Guess: %f\n", g); if g * g > x g = g * 0.99; else g = g * 1.01; else break; } printf("Result: %f\n, g); |
Segmentation fault (core dumped) 'g' undeclared expected '(' before 'g' 'else' without a previous 'if' missing terminating " character expected declaration or statement at end of input |
b) In the sequence of phases, the scanner comes before the parser. Does that mean that the work of the scanner is completely finished before the work of the parser starts? Explain!
c) In the sequence of phases, the machine-independent code optimizer comes before the machine-dependent code optimizer. Could it be done the other way around? Explain!
a = 1; b = 2; while (a < b + c + d * 3) { if (a < b) { a = a + 4; b = b - 5; } c = c * (d + 6); }
Translate the program segment to two of the following three types of representations. (Should you answer with all three, the one with the highest points will be discarded.)
a) an abstract syntax tree (by drawing it)
b) postfix code for a stack machine
c) three-address code
Note: Two of the three types, not all three.
Here is an example of how this language looks:
map "Main map"; room "The Church"; room "The Village Green"; room "The Shop"; exit "south" from "The Church" to "The Village Green"; exit "east" from "The Village Green" to "The Shop"; end; |
The input above describes a map called "Main map", that contains three rooms (or places) called "The Church", "The Village Green" and "The Shop". There is an exit leading south from "The Church" to "The Village Green", and an exit leading east from "The Village Green" to "The Shop".
This map-design language contains four commands: map, which starts a map and gives it a name, room, which defines a room with a name, exit, which lets you create passages between the rooms, and end, which marks the end of the input.
The double-quoted strings that are used for names and directions can only contain letters, numbers and spaces.
A complete input in this language should start with a map command, followed by any number of room and exit commands in any order, and end with the end command.
It should be possible to write the input in free format, except for inside the double-quoted strings, so the following input should be equivalent to the one above:
map "Main map" ; room "The Church" ; room "The Village Green" ; room "The Shop" ; exit "south" from "The Church" to "The Village Green" ; exit "east" from "The Village Green" to "The Shop" ; end ; |
b) Out of these terminals, some will not have fixed lexemes. Write regular expressions for each such terminal.
map "Another map"; room "T004"; room "T122"; exit "down" from "T122" to "T004"; end; |