Back-tracking and Left Recursion
Back-tracking
It means if one derivation of a production fails, the syntax analyzer restarts the process using different rules of same production.
This technique may process the i/p string more than once to determine the right production.
Left Recursion
A grammar ‘G’ is said to be left recursive if it has a non-terminal ‘A’ such that there is a derivation A+ → Aα for some α.
It gives infinite loop
A* ⟶ Aα
A ⟶ Aαα
A ⟶ Aααα
Left recursive grammar should be eliminated.
To come out of infinite loop, we need to make changes.
A ⟶ Aα/β
A ⟶ βA’
A’ ⟶ αA’/є
Let ‘G’ be a CFG, having production rules
A ⟶ Aα/β
A ⟶ βA’
A’ ⟶ αA’/є
A left recursive grammar causes a top-down parser to go into an infinite loop.
Thus, we eliminate the left recursion by revisiting the production as
A ⟶ βA’
A’ ⟶ αA’/є
Reference Link