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

S -> a | AB

A -> Aab| ASb | Bb

B -> b

4.4.2 The LL Grammar Class Before choosing to use recursive descent as a parsing strategy for a compiler or other program analysis tool, one must consider the limitations of the approach, n terms of gramm their possible solutions. ar restrictions. This section discusses these restrictions and for One simple grammar characteristic that causes a catastrophic problem LL parsers is left recursion. For example, consider the following rule: AA + B 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 now here (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 Aai, I IAAn I 1 I 2 1 1 Pn where none of the 's begins with A 2. Replace the original A-rules with A' !A' | 2A' | .xl Note that 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 F (E) I id For the E-rules, we have | = +T and = T, so we replace the E-rules with ETE' For the T-rules, we have = * F and = F, so we replace the T-rules with T' *FT' |