Algorithm to eliminate left recursion

Algorithm to eliminate left recursion

  1. Assign an ordering A1,…,An to the nonterminals of the grammer
  2. 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,


F->(E)/id Eliminate immediate left recursion from above grammar then we obtain,
E’->+TE’ | ε
T’->*FT’ | ε
F->(E) | id

Leave a Reply