KOI: Exercise 9: Lecture 9, 11 and 12

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

Preparations

Before this exercise you should have:

Question 1: Syntax Trees

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

    if (a < b) {
        while (c > d * 2) {
            b = a + 1;
            a = c * (b + c + d);
            a = a + 1;
            d = c * (b + c + d);
        }
        b = a + 1;
    }
    c = a + 1;

Translate the program segment to an abstract syntax tree (by drawing the tree).

Remember that a concrete syntax tree, or parse tree, contains nodes for all productions that were used to reduce the input string to the start symbol. With a grammar similar to some that we have seen in the course, a parse tree for the input 2 + 2 might look like this:

A parse tree for the input 2+2

An abstract syntax tree, or just syntax tree, is a simplified version of the parse tree, where nodes that are not needed have been remove or folded into each other:

A syntax tree for the input 2+2

Question 2: Stack Machine Code

Translate the program segment in the question above to postfix code for a stack machine.

Question 3: Three-Address Code

a) Translate the program segment to three-address code.

b) Identify the basic blocks and draw the flow graph. (The flow graph, with the three-address code in it, is sufficent as answer to both a and b.)

Question 4: Optimization

a) In the source code above, there is a while loop, and in the body of the loop there are four lines. The three-address code corresponding to those four lines will form one basic block. Show which block-local optimizations can be done within that basic block.

b) Are there any non-block-local optimizations (optimizations that involve several basic blocks) that can be done?

There are some solutions to some of the questions, but try to solve them yourself first.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) December 1, 2021