Compilers and Interpreters
for Dataingenjörsprogrammet, and others
Monday October 28, 2019
Exam for:
DT125G Kompilatorer och interpretatorer, provkod 0100
Aids: | No aids. |
Score requirements: |
Maximum score is 36.
To pass, at least 8 points are required on task 1, and at least 20 points in total. |
Results: | Announced on the course website or by e-mail by Monday November 18, 2019. |
Return of the exams: | Electronically through Studentforum. |
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 langugage, 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
#include <stdio.h> int main(void) { prontf("Starting...\n"); // 1: undefined reference to `prontf' int a = 17zzz; // 2: invalid suffix on integer constant int b = ; // 3: expected expression before ';' token int c = 0; if (c == 0) { int d = a / c; // 4: math exception int e, f, g; int h // 5: expected '=', ',' or ';' before 'e' e = 17; // 6: variable 'e' set but not used f = g; // 7: 'g' may be used uninitialized printf("d = %d, f = %d\n", d, f); } return "Done!"; // 8: return makes integer from pointer }
x = 0; y = z * 2 - t - 2 * 2; while (x < y) { if (x < 5) { x = x + 1; } else { x = x + 2; y = y + 1; } }
a) Translate the program segment to an abstract syntax tree (by drawing it).
b) Translate the program segment to either postfix code for a stack machine or three-address code. (Not both!)
Some biologists are making an inventory of the anmials in an area, and they need a language to write down and process their observations. The language should allow them to first declare a number of species, and then a number of observations of individual animals of those species. A complete input in this language might look like this:
species rabbit species lion declarations done observation rabbit 1 observation lion 30 observation rabbit 3 observations done
This means that the animals we observe are rabbits and lions, and we have observed first a rabbit, then thirty lions, and finally three more rabbits. After listing the species, the "declarations" part of the input is ended with declarations and done. After listing the observations, the "observations" part of the input is ended with observations and done.
Animal names are single words that consist of lower-case letters.
It should be possible to write the input in free format, such as in most common programming languages, for example like this:
species rabbit species lion declarations done observation rabbit 1 observation lion 30 observation rabbit 3 observations done
b) (2p) Out of the terminals, some will not have fixed lexemes. Write regular expressions for each such terminal.