Compilers: Principles and Practice by Pearson

Syntax Analyzer 79

We cannot have a grammar with left recursion for Top-down parsing. Consider a production

T -> T * a

Because Top-down parsing involves leftmost derivation, we shall always replace the T on the RHS by

“T * a” and thus we shall have an infinite loop. We shall have to rewrite any left-recursive grammar as

either right recursive or right iterative. How do we do this conversion? The general rules are as follows:

left recursion to EBNF: A → Aa | β ⇒ A → β{a}

right recursion to EBNF: A → aA | β ⇒ A → {a}β

common sub-expr: A → aβ | a ⇒ A → a[β]

Here, β ∈ (V

N

∪ V

T

)* not starting with A.

Within the class LL(k) there are sub-classes, with ...