KOI: Exercise 7: Lecture 9-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?

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) October 10, 2021