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