Compilers and Interpreters
for Dataingenjörsprogrammet, and others
Tuesday October 25, 2022
Exam for:
DT135G Kompilatorer och interpretatorer, provkod A001
Aids: | No aids. |
Score requirements: |
Maximum score is 47.
To pass, at least 26 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
Program | Error |
---|---|
#include <stdio.h> #include <math.h> int Main(void) { printf("What is x: "); int x; scanf("%d", &x); printf("What is n: ); int *n; scanf("%d", n); for (int i = 1; i <= n; ++i) { int res = pow(x, i); printf("%d ** %d = %d\n", x, i, res; } } |
undefined reference to `main' missing terminating " character 'n' is used uninitialized comparison between pointer and integer undefined reference to .pow' expected ')' before ';' token |
if (x < y) { x = x + 1; z = x + y + z; } else { x = x / 2; z = x + y + z * 3 / 4; y = 0; }
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
(1) t1 = a + b (2) x = t1 / c (3) t2 = a + b (4) c = 4 * t2 (5) t3 = x + y (6) t4 = a + b (7) if t3 >= t4 goto (11) (8) c = c + x (9) a = a - 1 (10) goto (5) (11) ... |
a) Some of the code might seem unnecessarily long, with all these temporary variables t1, t2 and so on. For example, couldn't the first two instructions have been replaced by the single instruction x = (a + b) / c? Explain!
b) Which basic blocks are there?
c) Show an optimization that can be performed on the code!
S -> a T | a U
T -> b c
U -> b d
a) Why is this grammar not suitable for implementation in a top-down, predictive recursive-descent parser?
b) Show how the input a b c is parsed using a bottom-up parser with a stack. Show which shift and reduce operations are performed.
Here is an example of how this input language will look:
meeting 2022-10-25 10:00 12:00 T101 meeting 2022-10-25 13:00 15:00 Zoom lecture 2022-10-27 15:15 17:00 T131 lab 2022-10-28 08:15 12:00 T004 meeting 2022-10-26 10:00 12:00 Zoom done |
This input language should have four keywords: meeting, to schedule a meeting, lecture, to schedule a lecture, lab, to schedule a lab, and done, to mark the end of the input.
The commands meeting, lecture and lab require four arguments: a date, a starting time, an ending time, and a place. The place is a single word without spaces.
It should be possible to write the input in free format, so the following input should be equivalent to the one above:
meeting 2022-10-25 10:00 12:00 T101 meeting 2022-10-25 13:00 15:00 Zoom lecture 2022-10-27 15:15 17:00 T131 lab 2022-10-28 08:15 12:00 T004 meeting 2022-10-26 10:00 12:00 Zoom done |
b) (2p) Out of these terminals, some will not have fixed lexemes. Write regular expressions for each such terminal.