|
Parsing conflicts in top-down parsers are common, and some ways to modify a grammar to eliminate conflicts are known.
A simple and natural one is left-factoring. Look again at the grammar that led to a parsing conflict.
| 1. L | → | ε |
| 2. L | → | N |
| 3. N | → | E |
| 4. N | → | E, N |
| 5. E | → | n |
Two productions, N → E and N → E , N, begin with the same prefix. A top-down parser can never predict which one to use in that situation. So you factor out the common prefix, introducing a new nonterminal to represent what comes after the common prefix. Calling that nonterminal R yields the following modified grammar.
| 1. L | → | ε |
| 2. L | → | N |
| 3. N | → | E R |
| 4. R | → | ε |
| 5. R | → | , N |
| 6. E | → | n |
That is the grammar that did not lead to any parsing conflicts.
|