Kompilatorer och interpretatorer: Tentamen 2024-01-03

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

Exam

Compilers and Interpreters

for Dataingenjörsprogrammet, and others

Wednesday January 3, 2024

Exam for:

DT135G Kompilatorer och interpretatorer, provkod A001

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

Write clearly. Solutions that can't be read can of course not give any points. Unclear and ambiguous wording will be misinterpreted.
Write the personal exam code on each sheet submitted. Do not write your name on the sheets.
Write on only one side of the paper. Do not use a red pen.
Assumptions beyond those in the given 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.

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

A compiler's work is usually divided into a number of phases. Which are those phases? Explain briefly what each phase does. What is the input and the output of each phase?

Task 2 (6 p)

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

    a = b * c * d + e + f * (h + i);
    if (j * (k + l) < m) {
        while (n < o) {
            p = q + r * s;
        }
        t = u;
    }
    v = w;
    x = y;

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.

Task 3 (5 p)

Show, with examples, some optimizations that can be done on three-address code.

Scenario for task 4-7

The university needs a system to schedule exams. We have created a special input language to enter courses and exams. Here is an example of how this input language will look:

course DT135G;
course DT105G;
course ZORRO;
exam DT135G 2023-01-03;
exam DT105G 2023-01-11;
exam DT105G 2023-01-12;
exam DT105G 2023-03-13;
forget DT105G 2023-01-12;
forget ZORRO;
done;

As we can se, there are four commands that can be given: course, which states that a course with a given course code exists, exam, which says that there is an exam for a certain course on a certain day, the command forget, which can be used to remove a course or an exam that was entered by mistake, and the command done, which signals the end of the input.

It should be possible to write the input in free format, so the following input should be equivalent to the one above:

  course DT135G  ; course
DT105G   ; course ZORRO
; exam DT135G 2023-01-03      ; exam
DT105G
  2023-01-11; exam DT105G 2023-01-12; exam DT105G 2023-03-13;
  forget DT105G 2023-01-12; forget ZORRO; 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:

course DT135H;
forget DT135H;
course DT135G;
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.