|
A top-down parser cannot handle left recursive productions. To understand why not, let's take a very simple left-recursive grammar.
| 1. S | → | a |
| 2. S | → | S a |
There is only one token, a, and only one nonterminal, S. So the parsing table has just one entry. Both productions must go into that one table entry.
The problem is that, on lookahead a, the parser cannot know if another a comes after the lookahead. But the decision of which production to use depends on that information.
It is always possible to convert left recursion to right recursion.
Suppose that a particular nonterminal N has one or more left-recursive productions. List the productions, with the left-recursive ones first, where none of β1, …, βn begin with N.
| N → N α1 |
| … |
| N → N αm |
| N → β1 |
| … |
| N → βn |
You can see that those productions allow you to derive a sequence βiαα…α, where i ∈ {1, …, n} and each occurrence of α is one of α1, …, αm.
But the same sequences can be generated by a right-recursive grammar. Replace the productions for N by the following, where R is a new nonterminal.
| N → β1 R |
| … |
| N → βn R |
| R → ε |
| R → α1 R |
| … |
| R → αn R |
The method just shown works for simple left-recursive grammars, but not for more complicated ones. The problem is that there can be indirect left recursion. Look at the following grammar.
| S | → | a |
| S | → | T a |
| T | → | S |
There is no direct left recursion, but S ⇒ T a ⇒ S a, and indirect left recursion is just as bad as direct left recursion.
The dragon book (page 212) describes an algorithm that always eliminates left recursion, including indirect left recursion.
|