LL grammar

In formal language theory, an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser that constructs a rightmost derivation). A language that has an LL grammar is known as an LL language. These form subsets of deterministic context-free grammars (DCFGs) and deterministic context-free languages (DCFLs), respectively. One says that a given grammar or language "is an LL grammar/language" or simply "is LL" to indicate that it is in this class. LL parsers are table-based parsers, similar to LR parsers. LL grammars can alternatively be characterized as precisely those that can be parsed by a predictive parser – a recursive descent parser without backtracking – and these can be readily written by hand. This article is about the formal properties of LL grammars; for parsing, see LL parser or recursive descent parser. Given a natural number , a context-free grammar is an LL(k) 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(k) 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(k) grammar. In the formal definition of a strong LL(k) grammar, the universal quantifier for is omitted, and is added to the "for some" quantifier for .