Kompilatorer och interpretatorer: Tentamen 2025-08-14

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

Exam

Compilers and Interpreters

Thursday August 14, 2025

Exam for:

DT501A Kompilatorer och interpretatorer för civilingenjörer, provkod A001

Aids:	No aids.
Score requirements:	Maximum score is 40. To pass, at least 24 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.

Answer in English or Swedish.
Write clearly. Solutions that can't be read can of course not give any points. Unclear or ambiguous wording will be misinterpreted.
Write the personal exam code on each sheet submitted. Do not write your name on the sheets.
Only write on one side of the paper.
Do not use a red pen.
When handing in, please organize pages in the correct order.
Assumptions beyond those given in the problems must be stated.
You are allowed to explain your solutions. Even an incorrect answer may give some points, if the key ideas were right.
Do not write answers in the booklet with the exam questions, and don't hand it in. Keep it or throw it away. The teacher already knows what the questions were.

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 (8 p)

Here is a program segment written in a C-like language:

w = x + y * z / t;
w = (x + y) * (z / t);
if (w < x) {
    w = x;
    w = y;
}
else {
    if (w > y)
        x = z;
    else
        x = t;
}

Translate the program segment to two of the following three types of representations.

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. Should you answer with all three, the one with the highest points will be discarded.

Task 2 (6 p)

a) Give an example of an error in a C program that is detected by the first phase in a compiler, the lexical analyzer.

b) Give an example of an error in a C program that is detected by the second phase in a compiler, the syntactical analyzer, and explain why it can't be detected by the lexical analyzer.

c) Give an example of an error in a C program that is detected by the third phase in a compiler, the semantic analyzer, and explain why it can't be detected by the lexical analyzer or the syntactical analyzer.

Task 3 (5 p)

Explain the following compiler-related terms.

a) ambiguous grammar (in Swedish: tvetydig grammatik)
b) FIRST() conflict (Swedish: FIRST()-konflikt)
c) call sequence (Swedish: anropskonventioner)
d) activation record (Swedish: aktiveringspost)
e) symbol table (Swedish: symboltabell)

Scenario for task 4-7

Barvel Comics is a new competitor to the more well-known Marvel Comics. They hope to sell comic books and movies based on a new line of superheroes, such as Byronman and Captain Bamerica, and make at least some money before they are sued by Marvel Comics and have to stop.

To keep track of their superheroes and supervillains they need a program with a special input language. Here is an example of how the input language looks:

superheroes Captain Barvel, Baredevil;
supervillains Boctor Boom, Bagneto,
    Boctor Boctopus;  
superheroes Black Bidow;
superheroes Biderman;
friends Boctor Boom, Bagneto;
enemies Boctor Boctopus, Biderman;
done;

In the input you can use the commands superheroes, supervillains, friends and enemies, plus the command done that is used to end the input. Commands end with a semicolon, and each of the commands except done takes a comma-separated list of one or more superperson names, which all consist of one or more words, as arguments.

(Yes, you can be friends and enemies just with yourself, and if you list more than two superpersons as argument to enemies, they all hate each other.)

It should be possible to write the input in free format, such as in most common programming languages, for example like this:

superheroes Captain Barvel , Baredevil ; supervillains Boctor Boom ,
Bagneto , Boctor Boctopus ; superheroes Black Bidow ; superheroes

                 Biderman ; friends Boctor Boom   
, Bagneto ; enemies Boctor Boctopus ,

Biderman ; done             ;

Task 4 (4 p)

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

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

Task 5 (5 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:

superheroes Black Bidow, Bulk;
supervillains Boki;
done;

Task 7 (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.