• 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.

Formulas

1. Eliminating left recursion

A -> A x | y

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

A -> x y | x z

Replace with these three productions:

A -> x R
R -> y | z

Task 1 (6 p)

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

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 2 (5 p)

In which phase of the compiler, or at which other times, are the following errors detected?

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

variable "a" is set but not used
unexpected end parenthesis


unknown operator "$"

"else" without a previous "if"


variable "x" undeclared

Task 3 (5 p)

We try to create a grammar for the language, with the following result. The start symbol is S, which represents a complete expression.

S -> S * T | T
T -> T ^ U | U
U -> U + number | number

a) Given this grammar, what is the precedence of the three operators?

b) Given this grammar, what is the associativity of the three operators?

c) Using the normal rules for precedence and associativity, the expression
12 + 13 * 14 ^ 15 * 16 would be interpreted as 12 + ((13 * (14 ^ 15)) * 16), or, as a syntax tree:

Draw the syntax tree for this expression when parsed using the grammar above!

Scenario for task 4-7

Unfortunately, for a while we have to wash our carpets a lot:

To keep track of our carpets, and when we have washed them, we design a program with a special input language. Here is an example of how this input language will look:

carpet 1 1.2;
carpet 2 2;
cleaned carpet 1 on 2023-10-23;
carpet 3 0.6;
cleaned carpet 2 on 2023-10-23;
cleaned carpet 1 on 2023-10-24;
carpet 4 1.2 * 2.0;
carpet 5 1.2 * 5;
done;

As we can se, there are three commands that can be given: carpet, which defines a carpet with a number and an area, cleaned, which says that we have cleaned a certain carpet on a certain day, and done, which signals the end of the input.

The area of a carpet can be given as a single number, with or without decimals, or as a simple expression using the length and width of the carpet, as shown in the example above.

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

carpet 1 1.2 ; carpet 2 2 ; cleaned carpet 1 on 2023-10-23 ; carpet 3
0.6 ; cleaned carpet 2 on 2023-10-23 ; cleaned carpet 1 on 2023-10-24
; carpet 4 1.2 * 2.0 ; carpet 5 1.2 * 5 ; done ;

Task 4 (4 p)

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

Task 5 (5 p)

Task 6 (4 p)

carpet 17 3.0;
carpet 18 3 * 4;
done;

Task 7 (8 p)