Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 39

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Boolean Expressions

In programming languages, boolean expressions have two primary purposes:

  • compute logical values such as x = a < b && d > e
  • conditional expressions in flow-of-control statements

Consider the grammar for Boolean expressions

E → E or E
| E and E
| not E
| ( E )
| id relop id
| true
| false

We will implement the translation for boolean expressions by flow of control method, i.e., representing the value of a boolean expression by a position reached in the program.
Here are the syntax directed translation for the grammar rules

grammar rules

grammar rules1

Example: Consider the expression

a < b or c < d and e < f

Suppose the true and false exits for the entire expression are Ltrue and Lfalse. The syntax directed translation scheme will generate the code

if a < b goto Ltrue
goto L1
L1: if c < d goto L2
goto Lfalse
L2: if e < f goto Ltrue
goto Lfalse

Example: Consider the while statement

while a < b
if c < d then
x = y + z
x = y – z

The translation scheme will generate the following code:

L1: if a < b goto L2
goto Lnext
L2: if c < d goto L3
goto L4
L3: t1 = y + z
x = t1
goto L1
L4: t2 = y – z
x = t2
goto L1
Lnext: nop

Implementation of Syntax-directed Translation

The easiest way to implement syntax-directed definitions is to use two passes: construct a syntax tree for the input in the first pass and then walk the tree in depth-first order evaluating attributes and emitting code. We would like to use only one pass if possible. The problem in generating three-address code in one pass is that we may not know the labels that the control must go to when we generate jump statements. However, by using a technique called back-patching, we can generate code in one pass.

As we generate code, we will generate the jumps (conditional or unconditional) with targets temporarily left unspecified. Each such statement will be put on a list of goto statements that have targets missing. We will fill the labels when the proper label can be determined; this is the backpatching step. Backpatching is especially suited for bottom-up parsers.

Assume that the quadruples are put into a simple array. Labels will be indices into this array.

To manipulate list of goto labels, we will use three functions:

  1. makelist(i)
    creates and returns a new list containing only i, the index of quadruple
  2. merge(p1, p2)
    concatenates lists pointed to by p1 and p2 and returns the concatenated list.
  3. backpatch(p, i)
    inserts i as the target label for each of the goto statements on list pointed to by p

We now construct a translation scheme suitable for producing quads (IR) for boolean expressions during bottom-up parsing. The grammar we use is

E → E1 or M E2
| E1 and M E2
| not E1
| ( E1 )
| id1 relop id2
| true
| false
M → ε

We will associate synthesized attributes truelist and falselist with the nonterminal E.
Incomplete jumps will be placed on these list.

We associate the semantic action

{ M.quad = nextquad() }

with the production M → ε. The function nextquad() returns the index of the next quadruple to follow. The attribute quad will record this index.

1. E → E1 and M E2
backpatch(E1.truelist, M.quad);
E.truelist = E2.truelist;
E.falselist = merge(E1.falselist, E2.falselist);

Let’s look at the mechanics. If E1 is false, E is false because of the and clause. If E1 is true, we need to evaluate E2. The start of E1, i.e., the index of the first quad for E1 is recorded by M.quad; in a bottom up parse, the reduction M → ε will occur before reduction to E2. The backpatch sets the targets of goto’s in E1.truelist to the start of E2.

backpatch sets

6. E → true
E.truelist = makelist(nextquad());
emit(‘goto _’ );
7. E → false
E.falselist = makelist(nextquad());
emit(‘goto _’ );