Algorithm to eliminate left recursion
- Assign an ordering A1,…,An to the nonterminals of the grammer
- for i:=1 to n do begin
for j:=1 to i−1
do begin replace each production of the form Ai→Aiɣ by the productions Ai ->δ1ɣ | δ2ɣ |…..| δkɣ where Aj -> δ1 | δ2 |…..| δk are all the current Aj productions;
end for eliminate the intermediate left recursion among the Ai-productions end for
Example 1 : Consider the following grammar,
E->E+T/T
T->T*F/F
F->(E)/id Eliminate immediate left recursion from above grammar then we obtain,
E->TE’
E’->+TE’ | ε
T->FT’
T’->*FT’ | ε
F->(E) | id