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

Compilers and Interpreters

for Dataingenjörsprogrammet, and others

Thursday January 9, 2025

Exam for:

DT135G Kompilatorer och interpretatorer, provkod A001 
















Aids:

No aids.




Score requirements:

Maximum score is 37.


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


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




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








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


Here is a C program:







#include <stdlib.h>
#include <stdio.h>

int a = 1, b = 2;

void f(int c) {
    int *p;
    int b;
    p = malloc(sizeof(int));
    *p = c;
    b = 3;
    if (c < 3)
        f(c + 1);
    else
        printf("Here!\n");
}

int main(void) {
    int a;
    a = 4;
    b = 5;
    f(1);
}








When the execution reaches the line which prints "Here!",
we stop the program and examine its memory.




In the program's memory there will be some integer variables
and other spaces for storing integers.
Draw a picture of those variables and spaces, with their contents.
Explain what you are showing.
Your explanation should probably use the terms
"static data", "stack", "heap", "activation record" and "parameters".










Task 3 (5 p)


A simple C program reads numbers
until the user enters the number zero,
and then prints their sum.
This is how an interaction with the program might look like,
with the user's input in bold:









Enter numbers,
end with zero:
30
10
100
0
Sum = 140










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




#include <stdoi.h>

int main(void) {
    int numbers[3];
    int n = 0;
    printf("Enter numbers,\n);
    print("end with zero:\n");
    int current_number;
    scanf("%d", &this_number);
    while (this_number #= 0) {
        numbers[n++] = this_number;
        scanf("%d", &this_number;
    }
    int sum = 0;
    for (int i = 0; i < n)
        sum += numbers[i];
    printf("Sum = %d\n", sum);


 

error: stdoi.h: No such file or directory




error: missing terminating " character
error: undefined reference to "print"
warning: unused variable "current_number"
error: "this_number" undeclared
error: stray "#" in program

error: expected ")" before ";" token


error: expected ";" before ")" token


error: expected declaration or statement at end of input
*** stack smashing detected ***
















Scenario for task 4-7


It is now a couple of weeks after Christmas,
and some people are unhappy with the Christmas presents they received.









To facilitate exchanging presents with each other,
and maybe find ones they like better,
they need a program with a special input language for presents.
Here is an example of how the input language looks:






I have: A coffee mug with Donald Trump
I want: A coffee mug with Nancy Pelosi
I have: A Playstation 5
I want: A Vectrex video game console
done










The input consists of pairs of lines starting with "I have"
and "I want", showing one present I have and want to get rid of,
and another present that I want in exchange for it.
The input ends with the keyword "done".




Since the input should be organized as pairs of lines,
we can not write it in free format.










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:







I have: A failing grade
I want: A passing grade
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.