The easiest way to implement the syntax-directed definitions for boolean expressions is to use two passes. First, construct a syntax tree for the input, and then walk the tree in depth-first order, computing the translations.

**BACKPATCHING**

The easiest way to
implement the syntax-directed definitions for boolean expressions is to use two
passes. First, construct a syntax tree for the input, and then walk the tree in
depth-first order, computing the translations. The main problem with generating
code for Boolean expressions and flow-of-control statements in a single pass is
that during one single pass we may not know the labels that control must go to
at the time the jump statements are generated. Hence, series of branching
statements with the targets of the jumps left unspecified is generated. Each
statement will be put on a list of goto statements whose labels will be filled
in when the properlabel can be determined. We call this subsequent filling in
of labels backpatching.

To manipulate lists of labels, we use three
functions :

1.
makelist(i) creates a new list
containing only i, an index into the array of quadruples; makelist returns a
pointer to the list it has made.

2.
merge(p1,p2) concatenates the lists
pointed to by p1 and p2, and returns a pointer to the concatenated list.

3.
backpatch(p,i) inserts i as the target
label for each of the statements on the list pointed to by p.

**Boolean Expressions:**

We now construct a
translation scheme suitable for producing quadruples for boolean expressions
during bottom-up parsing. The grammar we use is the following:

Synthesized attributes
truelist and falselist of nonterminal E are used to g for boolean expressions.
Incomplete jumps with unfilled labels are placed on lists pointed to by
E.truelist and E.falselist. Consider production E->E1 and M E2. If E1 is
false, then E is also alse. So the tatements on E1.falselist become part of
E.falselist. If E1 is true, then we must next test E2, so the target for the
statements E1.truelist must be the beginning of the code generated for E2. This
target is obtained using marker nonterminal M.

Attribute M.quad
records the number of the first statement of E2.code. With the production Mɛwe
associate the semantic action { M.quad : = nextquad }. The variable nextquad
holds the index of the next quadruple to follow. This value will be backpatched
onto the E1.truelist when we have seen the remainder of the production E->E1
ans M E2. The translation scheme is as
follows:

**Flow-of-Control Statements:**

A translation scheme is developed for statements
generated by the follow

Here S denotes a
statement, L a statement list, A an assignment statement, and E a boolean
expression. We make the tacit assumption that the code that follows a given
statement in execution also follows it physically in the quadruple array. Else,
an explicit jump must be provided.

**Scheme to implement the Translation:**

The nonterminal E has
two attributes E.truelist and E.falselist. L and S also need a list of unfilled
quadruples that must eventually be completed by backpatching. These lists are
pointed to by the attributes L..nextlist and S.nextlist. S.nextlist is a
pointer to a list of all conditional and unconditional jumps to the quadruple
following the statement S in execution order, and L.nextlist is defined
similarly.

The semantic rules for the revised grammar are as
follows:

(1)
S->ifEthenM1S1NelseM2 S2

{ backpatch (E.truelist, M1.quad);

backpatch
(E.falselist, M2.quad);

S.nextlist
: = merge (S1.nextlist, merge (N.nextlist, S2.nextlist)) }

We backpatch the jumps
when E is true to the quadruple M1.quad, which is the beginning of the code for
S1. Similarly, we backpatch jumps when E is false to go to the beginning of the
code for S2. The list S.nextlist includes all jumps out of S1 and S2, as well
as the jump generated by N.

(5)
S->whileM1 EdoM2 S1

{ backpatch( S1.nextlist, M1.quad); backpatch(
E.truelist, M2.quad);

(7)
S->A { S.nextlist : = nil }

The assignment S.nextlist : = nil initializes
S.nextlist to an empty list.

(8)
L->L1;M S { backpatch( L1.nextlist,
M.quad); L.nextlist : = S.nextlist }

The statement following
L1 in order of execution is the beginning of S. Thus the L1.nextlist list is
backpatched to the beginning of the code for S, which is given by M.quad.

(9)
L->S { L.nextlist : = S.nextlist }

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.