A parser determines whether a sequence of tokens is legal given a grammar
A grammar in which each nonterminal appears only once on the LHS of a production can easily be transformed into a recursive descent parser:
Each nonterminal becomes a separate function.
Terminals in the RHS become calls to match which consumes an input token
Nonterminals in the RHS become calls to their functions.
Points to consider:
Obviously, there are problems with left recursion and common prefixes.
Most grammars have more than one production with a given nonterminal on the LHS, so we need to be able to predict which one to take based on current input token.
See p. 123 in textbook.
To refactor a grammar containing left recursion to one that does not contain left recursion, consider:
A → A a
→ B
where a and B are strings of terminals and nonterminals and B does not begin with an A.
Rewrite the grammar by replacing the original rule with a new rule that generates B first, and a new rule that generates 0 or more copies of a, using right recursion.