LL grammar



Formal definition

Finite case

Given a natural number,
a context-free grammar
is an LL grammar if
  • for each terminal symbol string of length up to symbols,
  • for each nonterminal symbol, and
  • for each terminal symbol string,
there is at most one production rule such that for some terminal symbol strings,
  • the string can be derived from the start symbol,
  • can be derived from after first applying rule, and
  • the first symbols of and of agree.
An alternative, but equivalent, formal definition is the following:
is an LL grammar if, for arbitrary derivations
;
when the first symbols of agree with those of, then.
Informally, when a parser has derived, with its leftmost nonterminal and already consumed from the input, then by looking at that and peeking at the next symbols of the current input, the parser can identify with certainty the production rule for.
When rule identification is possible even without considering the past input, then the grammar is called a strong LL grammar. In the formal definition of a strong LL grammar, the universal quantifier for is omitted, and is added to the "for some" quantifier for.
For every LL grammar, a structurally equivalent strong LL grammar can be constructed.
The class of LL languages forms a strictly increasing sequence of sets: LL ⊊ LL ⊊ LL ⊊ …. It is decidable whether a given grammar G is LL, but it is not decidable whether an arbitrary grammar is LL for some k. It is also decidable if a given LR grammar is also an LL grammar for some m.
Every LL grammar is also an LR grammar. An ε-free LL grammar is also an SLR grammar. An LL grammar with symbols that have both empty and non-empty derivations is also an LALR grammar. An LL grammar with symbols that have only the empty derivation may or may not be LALR.
LL grammars cannot have rules containing left recursion. Each LL grammar that is ε-free can be transformed into an equivalent LL grammar in Greibach normal form.

Regular case

Let be a terminal alphabet. A partition of is called a regular partition if for every the language is regular.
Let be a context free grammar and let be a regular partition of. We say that is an LL grammar if, for arbitrary derivations
;
such that it follows that.
A grammar G is said to be LL-regular if there exists a regular partition of such that G is LL. A language is LL-regular if it is generated by an LL-regular grammar.
LLR grammars are unambiguous and cannot be left-recursive.
Every LL grammar is LLR. Every LL grammar is deterministic, but there exists a LLR grammar that is not deterministic. Hence the class of LLR grammars is strictly larger than the union of LL for each k.
It is decidable whether, given a regular partition, a given grammar is LL. It is, however, not decidable whether an arbitrary grammar G is LLR. This is due to the fact that deciding whether a grammar G generates a regular language, which would be necessary to find a regular partition for G, can be reduced to the Post correspondence problem.
Every LLR grammar is LR-regular, but there exists an LR grammar that is not LLR.
Historically, LLR grammars followed the invention of the LRR grammars. Given a regular partition a Moore machine can be constructed to transduce the parsing from right to left, identifying instances of regular productions. Once that has been done, an LL parser is sufficient to handle the transduced input in linear time. Thus, LLR parsers can handle a class of grammars strictly larger than LL parsers while being equally efficient.
Despite that the theory of LLR does not have any major applications. One possible and very plausible reason is that while there are generative algorithms for LL and LR parsers, the problem of generating an LLR/LRR parser is undecidable unless one has constructed a regular partition upfront. But even the problem of constructing a suitable regular partition given grammar is undecidable.

Simple deterministic languages

A context-free grammar is called simple deterministic, or just simple, if
A set of strings is called a simple deterministic, or just simple, language, if it has a simple deterministic grammar.
The class of languages having an ε-free LL grammar in Greibach normal form equals the class of simple deterministic languages.
This language class includes the regular sets not containing ε. Equivalence is decidable for it, while inclusion is not.

Applications

LL grammars, particularly LL grammars, are of great practical interest, as they are easy to parse, either by LL parsers or by recursive descent parsers, and are designed to be LL for this reason. Languages based on grammars with a high value of k have traditionally been considered to be difficult to parse, although this is less true now given the availability and widespread use of parser generators supporting LL grammars for arbitrary k.