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