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

Compilers and Interpreters

Monday August 21, 2023

Exam for:

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
















Aids:

No aids.




Score requirements:

Maximum score is 41.


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


A simple C program reads two numbers and prints their sum.
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?
(We may have to fix some of the errors before we get some of the others.)







Program Error




#insert <stdio.h>

int main(void) {
    int x, z, t;
    printf("What is x: );
    scanf("%d", x)
    printf("What is y: ");
    scan("%d", &z);
    printf("The sum of %d and %d is %d.\n",
           x, y, x + y);
    return "ok!";
}


 

invalid preprocessing directive #insert


unused variable 't'
missing terminating " character
Segmentation fault (core dumped)
expected ';' before 'printf'
undefined reference to 'scan'

'y' undeclared
mismatched return type











Task 3 (6 p)


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




x = 1;
if (y == z) {
    while (y < t * 2 * 3 + 4 * w) {
        y = y + 1;
        t = 2 * t / 3 / 4;
    }
}
else {
    y = 2;
}
x = 2;








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


In Sörbybacken ("South village hill"?), close to the university,
there are some long and steep stairs that runners sometimes use for training.
Here is a photo taken from Sörbybacken on April 15, 2022:




View from Sörbybacken






To keep track of our training i Sörbybacken,
we will create a special input language.
Here is an example of how this language looks:







2022-04-15 1:43
2022-04-17 1:42 2:09 1:44 1:55
2022-04-18 2:22 1:39
done








The input above says that on April 15, 2022,
we ran up the hill once,
and it took 1 minute and 43 seconds.
On April 17, we ran four times, taking 1:42, 2:09, 1:44 and 1:55.
Finally, on April 18, we ran two times, taking 2:22 and 1:39.




We should be able to enter any number of lines,
each consisting of a date and one or more times,
where a time consists of minutes, a colon, and seconds.
The keyword done marks the end of the input.










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:







2023-08-21 3:09
2023-08-22 2:09 2:08
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.