## Eliminating Left Recursion from SDT\'s

**Introduction**: When the grammar is part of an SDT, we also know that how the actions are handled. First, consider the simple case, in which the only thing we care about is the order in which the actions in an SDT are performed. For example, if each action simply prints a string, we care only about the order in which the strings are printed. In this case, the following principle can guide us:

When transforming the grammar, treat the actions as if they were terminal symbols.

This principle is based on the idea that the grammar transformation preserves the order of the terminals in the generated string. The actions are therefore executed in the same order in any left-to-right parse, top-down or bottom-up.

The "trick" for eliminating left recursion is to take two productions

A ->• Aa | (3

that generate strings consisting of a j3 and any number of en's, and replace them by productions that generate the same strings using a new nonterminal R (for "remainder") of the first production:

A^j3R

R —»• aR | e

If (3 does not begin with A, then A no longer has a left-recursive production. In regular-definition terms, with both sets of productions, A is defined by 0(a)*. See Section 4.3.3 for the handling of situations where A has more recursive or non-recursive productions.

**Example:** Consider the following E-productions from an SDT for translating infix expressions into postfix notation:

E -> E i T { print(' '); }

E -> T

If we apply the standard transformation to E, the remainder of the left-recursive

production is

a = T { print('-r'); }

and the body of the other production is T. If we introduce R for the remainder

of E, we get the set of productions:

E T R

R - T {printC-h'); } R

R ->• e

When the actions of an SDD compute attributes rather than merely printing output, we must be more careful about how we eliminate left recursion from a grammar. However, if the SDD is S-attributed, then we can always construct an SDT by placing attribute-computing actions at appropriate positions in the new productions.

We shall give a general schema for the case of a single recursive production, a single non-recursive production, and a single attribute of the left-recursive nonterminal; the generalization to many productions of each type is not hard, but is notationally cumbersome. Suppose that the two productions are

A A±Y {A.a = g(A1.a,Y.y)}

A -> X {A.a = f(X.x)}