# LR to LL Grammer Conversion

Standard grammers, that are the most concise, do not work with top down
parsers. Top down grammers must be written such that each rule that
defines a given left hand symbol must have a unique set of first
symbols. This means that top down grammes can not have left recursive
rules, a rule where the left hand symbol is the first rule on the right
hand side. The following example shows how to convert a standard LR
grammer to one that can be used by the LL parsing algorithm.
1 EXP -> EXP + TERM
2 EXP -> EXP - TERM
3 EXP -> TERM
4 TERM -> TERM * FACTOR
5 TERM -> TERM / FACTOR
6 TERM -> FACTOR
7 FACTOR -> ( EXP )
8 FACTOR -> identifier

The first observation that one can make is that every EXP must start
with a TERM. This means that the three rules that define EXP, (rules
1-3), all start with the same set of input symbols. The first step is
to factor the common parts of the three rules into a single rule like:
1 EXP -> TERM EXP1
2 EXP1 -> + TERM
3 EXP1 -> - TERM

This makes each rule identifiable by the first symbol of the rule, but
it doesn't reproduce the left recursion of the original rules. This
version of the rules also requires that every expression have an
addition or subtraction clause which was not in the original rules
either. This can be corrected by adding a null deriving rule like:
1 EXP -> TERM EXP1
2 EXP1 -> + TERM EXP1
3 EXP1 -> - TERM EXP1
4 EXP1 ->

Now the EXP expression can be composed of a single TERM clause or it can
be followed by as many EXP1 clauses as need be. The same thing needs to
be done with the rules for TERM, giving the following transformed
grammer.
1 EXP -> TERM EXP1
2 EXP1 -> + TERM EXP1
3 EXP1 -> - TERM EXP1
4 EXP1 ->
5 TERM -> FACTOR TERM1
6 TERM1 -> * FACTOR TERM1
7 TERM1 -> / FACTOR TERM1
8 TERM1 ->
9 FACTOR -> ( EXP )
10 FACTOR -> identifier