Institutt for Informatikk
Universitetet i Bergen
I 125 - Innføring i Programoversettelse


Voluntary Exercise Set 12 (Gruppeøvelser. 12)

  1. (Derived from oppgave 1 on the mai 1999 exam.)

    1. Given the alphabet {0, 1}, derive a regular expression for all binary integers that do not contain any leading zeros. For example, the numbers 0, 1, 100 and 10010 belong to this set, but the numbers 000, 01, 0100 and 0010010 do not.
    2. Using Thompson's construction, construct an NFA (nondeterministic finite automata) for your regular expression from part (a).
    3. Convert your NFA from part (b) into an equivalent DFA (deterministic finite automata) using subset construction.
    4. Apply the state minimization algorithm to convert your DFA from part (c) into an equivalent DFA with a minimum number of states.

  2. (Derived from oppgave 2 on the mai 1999 exam.) Consider the grammar G given below.

    (1) L -> L E nl
    (2) L -> L nl
    (3) L -> emptySet
    (4) E -> T + E
    (5) E -> T
    (6) T -> ( E * T )
    (7) T -> id

    1. Augment G and convert it to an equivalent LL(1) grammar G'.
    2. Compute the FIRST and FOLLOW sets for all non-terminals in the new grammar G'.
    3. Construct the DFA of LR(0) items for this grammar.
    4. Construct the SLR(1) parsing table.
    5. Show the parsing stack and the actions of an SLR(1) parser for input string id + id nl

  3. (This question has to do with code generation and optimization as covered this semester.) Consider the following C- program.

    int main(void)
    {

    int A; int y;
    input(y);
    while (y > 0)
    {
    A = (2 + 123) * 6;
    y = y / A;
    }
    }

    1. Show either BVM-like intermediate code or P-code for the C- program. Don't worry about the exact syntax of BVM code or P-code. Just use reasonable instructions that are close to those available in either BVM or P-code. If you use an instruction that is not obvious, explain it.
    2. Show the basic blocks in the intermediate code from part (a).
    3. Pick two peephole optimizations. Explain the optimizations and apply each to your intermediate code.
    4. Show the results of performing the Constant-Folding local optimization on your intermediate code.
    5. Show the results of performing the Reduction-in-Strength local optimization on your intermediate code.
    6. Show the results of performing the Code-Motion global optimization on your intermediate code.

  4. Suggest a question or type of question for the exam. This is meant to give you a chance to describe a type of question that you think would best help you to demonstrate that you understand the material in this course. All suggestions will be posted on the web so that every student gets an equal opportunity to study from the suggestions. Reasonable suggestions will be taken into consideration in making up the exam.