Use the algorithm described in Section 4.4.2 of Sebesta to remove direct left recursion from the following grammar:

S Sa | a | SA | b

A bA | aS

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Here is the Section 4.4.2

4.4.2 The LL Grammar Class Before choosing to use recursive descent as a parsingstrategy for a compiler or other program analysis tool, one must consider the limitations of the approach, in terms of grammar restrictions. This section discusses these restrictions and their possible solutions One simple grammar characteristic that causes a catastrophic problem for LL parsers is left recursion. For example, consider the following rule: A recursive-descent parser subprogram for A immediately calls itself to parse the first symbol in its RHS. That activation of the A parser subprogram then immediately calls itself again, and again, and so forth. It is easy to see that this leads nowhere (except to a stack overflow The left recursion in the rule A A B is called direct left recursion, because it occurs in one rule. Direct left recursion can be eliminated from a grammar by the following process For each nonterminal, A, 1. Group the A-rules as A Aa 1, I... IAom l B1 B2 l Bn where none of the B's begins with A 2. Replace the original A-rules with A BIA' B2A. A' A' 02A Note that e specifies the empty string. A rule that has as its RHS is called an erasure rule, because its use in a derivation effectively erases its LHS from the sentential form. Consider the following example grammar and the application of the above process E E T T T T F F For the E-rules, we have a +T and B T, so we replace the E-rules with E TE' E' TE For the T-rules, we have F and B F, so we replace the T-rules with T FT