• Answer in English or Swedish.
• 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 (5 p)

• If g squared is greater than x, let the new g be 0.99 times the old g.
• If g squared is less than x, let the new g be 1.01 times the old g.

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?

#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)

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)

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

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)

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

Task 5 (4 p)

Task 6 (4 p)

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

Task 7 (2 p)

Task 8 (8 p)