Backpatching

When transforming a translation scheme into a YACC program we saw how to forward inherited attriutes (by using markers). This solves the problem of implementing L-attributed syntax-directed definitions in YACC. However we need sometimes to face more general situations.

THE GENERAL PROBLEM. Let A  $\longmapsto$  X₁ ^... X_n be a production used in a parse tree. We consider the case where for a grammar symbol X_i in the rigth side of the production possesses an inherited attriute X_i.in which cannot be given value before the subtree rooted at A is completely visited.

AN EXAMPLE AND ITS SOLUTION.

• Boolean expressions are usually translated using the jump method since this is convenient for optimization.
• However, more than a single pass may be needed in order to generate code for boolean expressions and flow of control during bottom-up parsing!
• Indeed, when translating forward jumps, at the time we generate the code we do not know the (numerical) address of the label we want to branch to.

The solution is to generate a sequence of branching statements where the addresses of the jumps are temporarily left unspecified.

1. For each boolean expression E we maintain two lists
   • E.truelist which is the list of the (addresses of the) jump statements appearing in the translation of E and forwarding to E.true.
   • E.falselist which is the list of the (addresses of the) jump statements appearing in the translation of E and forwarding to E.false.
2. When the label E.true (resp. E.false) is eventually defined we can walk down the list, patching in the value of its address.

In the translation scheme below

• We use emit to generate code that contains place holders to be filled in later by the backpatch procedure.
• The attributes E.truelist, E.falselist are synthesized.
• When the code for E is generated, addresses of jumps corresponding to the values true and false are left unspecified and put on the lists E.truelist and E.falselist, respectively.
• A marker non-terminal M is used to capture the numerical address of a statement we want to branch to.
• nextaddr is a global variable that stores the number of the next statement to be generated. In all examples we assume that nextaddr is initialized to 100.
• makelist is a function which creates a new list from one item.
• merge is a function which creates a sorted list of addresses from two such lists.

	Production	Semantic Rule
1	E  $\longmapsto$  E1 $\bf or$ M E2	{ backpatch( E1.falselist, M.quad)
		E.truelist := merge( E1.truelist, E2.truelist)
		E.falselist := E2.falselist }
2	E  $\longmapsto$  E1 $\bf and$ M E2	{ backpatch( E1.truelist, M.quad)
		E.truelist := E2.truelist
		E.falselist := merge( E1.falselist, E2.falselist) }
3	E  $\longmapsto$  $\bf not$ E1	{ E.truelist := E1.falselist
		E.falselist := E1.truelist }
4	E  $\longmapsto$  (E1)	{ E.truelist := E1.truelist
		E.falselist := E1.falselist }
5	E  $\longmapsto$  $\bf id_{1}^{}$ $\bf relop$ $\bf id_{2}^{}$	{ E.truelist := makelist(nextaddr)
		nextaddr := nextaddr + 1
		E.falselist := makelist(nextaddr)
		nextaddr := nextaddr + 1
		emit('if' $\bf id_{1}^{}$.place $\bf relop$ $\bf id_{2}^{}$.place 'goto __')
		emit('goto __') }
6	E  $\longmapsto$  $\bf true$	{ E.truelist := makelist(nextaddr) }
7	E  $\longmapsto$  $\bf false$	{ E.falselist := makelist(nextaddr) }
8	M  $\longmapsto$  $\varepsilon$	{ M.quad := nextaddr }

Example 9   Let us consider again the expression

a < b

We only need to apply the above Production 5 leading to

100	if a < b goto __
101	goto __

Moreover this expression, say E₁, is associated with the lists

E₁.truelist  =  [100]

E₁.falselist  =  [101]

and nextaddr has value 102.

Example 10   Consider again the expression

a < b or c < d

During a bottom-up parsing we will apply twice Production 5 and one Production 1. Before performing the actions of Production 1 the generated code is

100	if a < b goto __
101	goto __
102	if c < d goto __
103	goto __

and the subexpressions E₁ = a < b and E₂ = c < d are associated with the lists

E₁.truelist  =  [100], E₁.falselist  =  [101]

E₂.truelist  =  [102], E₂.falselist  =  [103]

Moreover

• nextaddr has value 104
• M.quad has value 102.

After performing the actions of Production 1 the generated code is

100	if a < b goto __
101	goto 102
102	if c < d goto __
103	goto __

Moreover the expression E = a < b or c < d is associated with

E.truelist  =  [100, 102]

E.falselist  =  [103]

and nextaddr has value 104.

Example 11   Now consider the expression

a < b or (c < d and e < f)

During a bottom-up parsing we will apply

• three times Production 5
• one Production 2
• and finally once Production 1.

Before performing the actions of Production 1 the generated code is

100	if a < b goto __
101	goto __
102	if c < d goto 104
103	goto __
104	if c < d goto __
105	goto __

and the subexpressions E₁ = a < b and E₄ = c < d and e < f are associated with the lists

E₁.truelist  =  [100], E₁.falselist  =  [101]

E₄.truelist  =  [104], E₂.falselist  =  [103, 105]

Moreover

• nextaddr has value 106
• M.quad has value 102.

After performing the actions of Production 1 the generated code is

100	if a < b goto __
101	goto 102
102	if c < d goto 104
103	goto __
104	if c < d goto __
105	goto __

Moreover the expression E = a < b or (c < d and e < f) is associated with

E.truelist  =  [100, 104]

E.falselist  =  [103, 105]