Eliminating Immediate Left RecursionLeft recursive productions can cause recursive descentparsers to loop forever. Therefore, we consider how toeliminate left recursion from a grammar.Consider the productions A → Aα | β where α and β aresequences of terminals and nonterminals that do not startwith A. These productions can be used to generate thefollowing strings:β βα βαα βααα βαααα etc.Note that the same language can be generated by theproductionsA → β RR → α R | εwhere R is a new nonterminal. Note that the R-productionis right recursive, which implies that we might havealtered the associativity of an operator. We will discusshow to handle this possibility later.In general, immediate left recursion (as we have above) maybe removed as follows. Suppose we have the A-productionsA → Aα1 | Aα2 | ... | Aαn | β1 | β2 | ... | βmwhere no βi begins with A. We replace the A-productions byA →β1A' | β2A' | ... | βmA'A'→α1A' | α2A' | ... | αnA' | εwhere A' is a new nonterminal.Let's eliminate left recursion from the grammar below (noteaccompanying parse tree for a + a + a):E → E + T | TT → T * F | FF → ( E ) | aNote how the parse tree grows down toward the left,indicating the left associativity of +.Eliminating left recursion we get the following grammar.Note parse tree for a + a + a:E → TE'E' → +TE' | εT → FT'T' → *FT' | εF → ( E ) | aNote how the parse tree grows down toward the right,indicating that operator + is now right associative.Algorithm for Eliminating General Left RecursionArrange nonterminals in some order A1, A2, ... , An.for i := 1 to n do begin for j := 1 to i - 1 do begin Replace each production of the form Ai -> Ajβ by the productions:Ai → α1β | α2β | ... | αkβ whereAj → α1 | α2 | . . . | αk are all the current Aj productions. end { for j } Remove immediate left recursion from the Ai productions, if necessary.end { for i }Example: S → Aa | bA → Ac | Sd | ε• Let's use the ordering S, A (S = A1, A = A2).• When i = 1, we skip the "for j" loop and remove immediateleft recursion from the S productions (there is none).• When i = 2 and j = 1, we substitute the S-productions inA → Sd to obtain the A-productionsA → Ac | Aad | bd | ε• Eliminating immediate left recursion from the Aproductions yields the grammar:S → Aa | bA → bdA' | A'A' → cA' | adA' | εLeft FactoringLeft factoring is a grammar transformation that is usefulfor producing a grammar suitable for top-down parsing. Thebasic idea is that when it is not clear which of twoalternative productions to use to expand a nonterminalA, we may be able to rewrite the A-productions to defer thedecision until we have seen enough of the input to make theright choice.To illustrate, consider the productionsS → if E then S | if E then S else Son seeing the input token if, we cannot immediately tellwhich production to choose to expand S.In general, if A → αβ1 | αβ2 are two A-productions, andthe input begins with a nonempty string derived from α, wedo not know whether to expand to αβ1 or to αβ2. Instead,the grammar may be changed. The formal technique is tochangeA → αβ1 | αβ2toA → αA'A' → β1 | β2Thus, we can rewrite the grammar for if-statement as:S → if E then S ElsePartElsePart → else S |