Editing LL parser (section)

=== Solutions to LL(1) conflicts ===

==== Left factoring ====

A common left-factor is "factored out".
 A -> X | X Y Z
becomes
 A -> X B
 B -> Y Z | ε
Can be applied when two alternatives start with the same symbol like a FIRST/FIRST conflict.

Another example (more complex) using above FIRST/FIRST conflict example:
 S -> E | E 'a'
 E -> 'b' | ε
becomes (merging into a single non-terminal)
 S -> 'b' | ε | 'b' 'a' | 'a'
then through left-factoring, becomes
 S -> 'b' E | E
 E -> 'a' | ε

==== Substitution ====
Substituting a rule into another rule to remove indirect or FIRST/FOLLOW conflicts.
Note that this may cause a FIRST/FIRST conflict.

==== Left recursion removal ====
: ''See <ref>[https://books.google.com/books?id=zkpFTBtK7a4C&q=%22left+recursion%22 Modern Compiler Design], Grune, Bal, Jacobs and Langendoen</ref>''

For a general method, see [[Left recursion#Removing left recursion|removing left recursion]].
A simple example for left recursion removal:
The following production rule has left recursion on E
 E -> E '+' T
 E -> T
This rule is nothing but list of Ts separated by '+'. In a regular expression form T ('+' T)*.
So the rule could be rewritten as 
 E -> T Z
 Z -> '+' T Z
 Z -> ε
Now there is no left recursion and no conflicts on either of the rules.

However, not all context-free grammars have an equivalent LL(k)-grammar, e.g.:
 S -> A | B
 A -> 'a' A 'b' | ε
 B -> 'a' B 'b' 'b' | ε
It can be shown that there does not exist any LL(k)-grammar accepting the language generated by this grammar.