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. 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 k ≥ 0 {displaystyle kgeq 0} , a context-free grammar G = ( V , Σ , R , S ) {displaystyle G=(V,Sigma ,R,S)} is an LL(k) grammar if there is at most one production rule r ∈ R {displaystyle rin R} such that for some terminal symbol strings w 2 , w 3 ∈ Σ ∗ {displaystyle w_{2},w_{3}in Sigma ^{*}} , Informally, when a parser has derived w 1 A w 3 {displaystyle w_{1}Aw_{3}} , with A {displaystyle A} its leftmost nonterminal and w 1 {displaystyle w_{1}} already consumed from the input, then by looking at that w 1 {displaystyle w_{1}} and peeking at the next k {displaystyle k} symbols w {displaystyle w} of the current input, the parser can identify with certainty the production rule r {displaystyle r} for A {displaystyle A} . When rule identification is possible even without considering the past input w 1 {displaystyle w_{1}} , then the grammar is called a strong LL(k) grammar. In the formal definition of a strong LL(k) grammar, the universal quantifier for w 1 {displaystyle w_{1}} is omitted, and w 1 {displaystyle w_{1}} is added to the 'for some' quantifier for w 2 , w 3 {displaystyle w_{2},w_{3}} .For every LL(k) grammar, a structurally equivalent strong LL(k) grammar can be constructed. An alternative, but equivalent, formal definition is the following: G = ( V , Σ , R , S ) {displaystyle G=(V,Sigma ,R,S)} is an LL(k) grammar if, for arbitrary derivations when the first k {displaystyle k} symbols of w 2 w 3 {displaystyle w_{2}w_{3}} agree with those of w 2 ′ w 3 ′ {displaystyle w'_{2}w'_{3}} , then ν = ω {displaystyle u =omega } . Allowing ε-rules increases the expressive power of a grammar: For every ε-free LL(k+1) grammar, there exists a LL(k) grammar with ε-rules that generates the same language. Commonly, ε-free LL(k) grammars are used for LL(k) parsers.