Compilers and Interpreters
for Dataingenjörsprogrammet, and others
Monday October 29, 2018
Exam for:
DT125G Kompilatorer och interpretatorer, provkod 0100
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
→ This exam is also available in a Swedish version.
Aids: | No aids. |
Score requirements: |
Maximum score is 36.
To pass, at least 18 points are required. |
Results: | Announced on the course website or by e-mail by Monday November 19, 2018. |
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
if (a < b) { while (c > d) { b = a + 1; a = c * (b + c); a = a + 1; d = c * (b + c); } b = a + 1; } c = a + 1;
a) Translate the program segment to either a abstract syntax tree (by drawing the tree) or postfix code for a stack machine. (Not both!)
b) Translate the program segment to three-address code. Identify the basic blocks and draw the flow graph. (The flow graph, with the three-address code in it, is sufficent as answer.)
c) Show an optimization that can be done within one of these basic blocks.
Soon it's Halloween, and the children make a "candy round" where they walk around to the neighbors and ask "trick or treat". To document their activities they need a special Halloween language, where a complete input might look like this:
began candy round; treat: three candies; trick: made some ghostly sounds; treat: one kilo of chocolate; treat: a carrot; trick: set fire to the neighbors car; went home;
The input describes a candy round. It starts with began candy round; and ends with went home;. In between, there are zero or more notes about trick or treat. Such a note begins with either trick or treat, a colon (:), one or more words that indicate what happened, and a semicolon (;).
It should be possible to write the input in free format, such as in most common programming languages, for example like this:
began candy round ; treat : three candies ; trick : made some ghostly sounds ; treat : one kilo of chocolate ; treat : a carrot ; trick : set fire to the neighbors car ; went home ;
b) (2p) Which other terminals, except word, are needed to write a grammar for the language?
began candy round; treat: one chewing gum; went home;