Editing LL parser (section)

== Conflicts ==

As described in the introduction, LL(1) parsers recognize languages that have LL(1) grammars, which are a special case of context-free grammars; LL(1) parsers cannot recognize all context-free languages. The LL(1) languages are a proper subset of the LR(1) languages, which in turn are a proper subset of all context-free languages.  In order for a context-free grammar to be an LL(1) grammar, certain conflicts must not arise, which we describe in this section.

=== Terminology ===

Let ''A'' be a non-terminal. FIRST(''A'') is (defined to be) the set of terminals that can appear in the first position of any string derived from ''A''. FOLLOW(''A'') is the union over:<ref>{{Cite web|title=LL Grammars|url=http://www.cs.uaf.edu/~cs331/notes/LL.pdf|url-status=live|archive-url=https://web.archive.org/web/20100618193203/http://www.cs.uaf.edu/~cs331/notes/LL.pdf|archive-date=2010-06-18|access-date=2010-05-11}}</ref>
# FIRST(''B'') where ''B'' is any non-terminal that immediately follows ''A'' in the right-hand side of a [[Formal grammar#The syntax of grammars|production rule]].
# FOLLOW(''B'') where ''B'' is any head of a rule of the form {{nowrap|''B'' → ''wA''}}.

=== LL(1) conflicts ===

There are two main types of LL(1) conflicts:

==== FIRST/FIRST conflict ====
The FIRST sets of two different grammar rules for the same non-terminal intersect.
An example of an LL(1) FIRST/FIRST conflict:
 S -> E | E 'a'
 E -> 'b' | ε
FIRST(''E'') = {''b'', ε} and FIRST(''E'' ''a'') = {{brace|''b'', ''a''}}, so when the table is drawn, there is conflict under terminal ''b'' of production rule ''S''.

===== Special case: left recursion =====

[[Left recursion]] will cause a FIRST/FIRST conflict with all alternatives.
 E -> E '+' term | alt1 | alt2

==== FIRST/FOLLOW conflict ====
The FIRST and FOLLOW set of a grammar rule overlap. With an [[empty string]] (ε) in the FIRST set, it is unknown which alternative to select.
An example of an LL(1) conflict:
 S -> A 'a' 'b'
 A -> 'a' | ε
The FIRST set of ''A'' is {''a'', ε}, and the FOLLOW set is {''a''}.

=== 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.