Örebro University
School of Science and Technology
Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se)






Exam

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.




GOOD LUCK!!

Formulas

1. Eliminating left recursion

A left-recursive grammar can be transformed to a grammar that is not left recursive. Assume that the grammar contains a rule (or, more correctly, two productions) like this:
A -> A x | y
A is a non-terminal, but x and y are any constructions consisting of terminals and non-terminals.

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

2. Left factorization

Assume that the grammar contains this rule (two productions):
A -> x y | x z
A is a non-terminal, but x, y and z are any constructions consisting of terminals and non-terminals.

Replace with these three productions:

A -> x R
R -> y | z

Task 1 (5 p)

A very bad algorithm to find the square root of a number, let's call the number x, is to start with a guess, let's call it g, of what the square root is. Then we repeat, until the guess g squared equals the number x:

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

Task 2 (7 p)

a) In the sequence of phases, the scanner comes before the parser. Why?

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!

Task 3 (6 p)

Here is a program segment written in a C-like language:
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.

Scenario for task 4-8

We are creating adventure games, and to make the work easier we are using a special language to design "maps", where the players can walk around in a number of rooms.

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 ;

Task 4 (4 p)

a) Which terminals are needed to write a grammar for the input language in the scenario?

b) Out of these terminals, some will not have fixed lexemes. Write regular expressions for each such terminal.

Task 5 (4 p)

Write a grammar for the input language. The start symbol should be input, which represents a complete input as described in the scenario above.

Task 6 (4 p)

Given your grammar, draw a parse tree (also called a concrete syntax tree) for the following input:

map "Another map";
room "T004";
room "T122";
exit "down" from "T122" to "T004";
end;

Task 7 (2 p)

Last time I was at the university and looked, there was no hole in the floor in the computer room T122 that leads down to the room T004. How will this affect the scanner and the parser?

Task 8 (8 p)

Write a predictive recursive-descent parser for the input language, in a language that is at least similar to C, C++, C# or Java. You do not have to write exactly correct program code, but it should be clear which procedures exist, how they call each other, and what comparisons with token types are made. You can assume there is a function called scan, which returns the type of the next token, and a function called error, which you can call when something went wrong and which prints an error message and terminates the program.