LL grammar

File:Parsing a C program that needs 2 token lookahead.svg grammar{{sfn|Kernighan|Ritchie|1988|loc=Appendix A.13 "Grammar", p.193 ff. The top image part shows a simplified excerpt in an EBNF-like notation.}} is not LL(1): The bottom part shows a parser that has digested the tokens "int v;main(){" and is about to choose a rule to derive the nonterminal "Stmt". Looking only at the first lookahead token "v", it cannot decide which of both alternatives for "Stmt" to choose, since two input continuations are possible. They can be discriminated by peeking at the second lookahead token (yellow background).]]

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.

Formal definition

=Finite case=

Given a natural number $k \geq 0$ ,

a context-free grammar $G = (V, \Sigma, R, S)$

is an LL(k) grammar if

for each terminal symbol string $w \in \Sigma^*$ of length up to $k$ symbols,
for each nonterminal symbol $A \in V$ , and
for each terminal symbol string $w_1 \in \Sigma^*$ ,

there is at most one production rule $r \in R$ such that for some terminal symbol strings $w_2, w_3 \in \Sigma^*$ ,

the string $w_1 A w_3$ can be derived from the start symbol $S$ ,
$w_2$ can be derived from $A$ after first applying rule $r$ , and
the first $k$ symbols of $w$ and of $w_2 w_3$ agree.{{harvtxt|Rosenkrantz|Stearns|1970|page=227}}. Def.1. The authors do not consider the case k=0.

An alternative, but equivalent, formal definition is the following:

$G = (V, \Sigma, R, S)$ is an LL(k) grammar if, for arbitrary derivations

; $\begin{array}{ccccccc} S & \Rightarrow^L & w_1 A \chi & \Rightarrow & w_1 \nu \chi & \Rightarrow^* & w_1 w_2 w_3 \\ S & \Rightarrow^L & w_1 A \chi & \Rightarrow & w_1 \omega \chi & \Rightarrow^* & w_1 w'_2 w'_3, \\ \end{array}$

when the first $k$ symbols of $w_2 w_3$ agree with those of $w'_2 w'_3$ , then $\nu = \omega$ .where " $\Rightarrow^L$ " denotes derivability by leftmost derivations, and $w_1,w_2,w_3,w'_2,w'_3 \in \Sigma^*$ , $A \in V$ , and $\chi, \nu, \omega \in (\Sigma \cup V)^*$ {{harvtxt|Waite|Goos|1984|page=123}} Def. 5.22

Informally, when a parser has derived $w_1 A w_3$ , with $A$ its leftmost nonterminal and $w_1$ already consumed from the input, then by looking at that $w_1$ and peeking at the next $k$ symbols $w$ of the current input, the parser can identify with certainty the production rule $r$ for $A$ .

When rule identification is possible even without considering the past input $w_1$ , then the grammar is called a strong LL(k) grammar.{{harvtxt|Rosenkrantz|Stearns|1970|page=235}} Def.2 In the formal definition of a strong LL(k) grammar, the universal quantifier for $w_1$ is omitted, and $w_1$ is added to the "for some" quantifier for $w_2, w_3$ .

For every LL(k) grammar, a structurally equivalent strong LL(k) grammar can be constructed.{{harvtxt|Rosenkrantz|Stearns|1970|page=235}} Theorem 2

The class of LL(k) languages forms a strictly increasing sequence of sets: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊ ….{{harvtxt|Rosenkrantz|Stearns|1970|page=246–247}}: Using " $+$ " to denote "or", the string set $\{ a^n(b^k d + b + cc)^n: n \geq 1 \}$ has an $LL(k+1)$ , but no ε-free $LL(k)$ grammar, for each $k \geq 1$ . It is decidable whether a given grammar G is LL(k), but it is not decidable whether an arbitrary grammar is LL(k) for some k. It is also decidable if a given LR(k) grammar is also an LL(m) grammar for some m.{{harvtxt|Rosenkrantz|Stearns|1970|pages=254–255}}

Every LL(k) grammar is also an LR(k) grammar. An ε-free LL(1) grammar is also an SLR(1) grammar. An LL(1) grammar with symbols that have both empty and non-empty derivations is also an LALR(1) grammar. An LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1).{{harvtxt|Beatty|1982}}

LL grammars cannot have rules containing left recursion.{{harvtxt|Rosenkrantz|Stearns|1970|pages=241}} Lemma 5 Each LL(k) grammar that is ε-free can be transformed into an equivalent LL(k) grammar in Greibach normal form (which by definition does not have rules with left recursion).{{harvtxt|Rosenkrantz|Stearns|1970|page=242}} Theorem 4

=Regular case=

Let $\Sigma$ be a terminal alphabet. A partition $\pi$ of $\Sigma^*$ is called a regular partition if for every $R \in \pi$ the language $R$ is regular.

Let $G = (V, \Sigma, R, S)$ be a context free grammar and let $\pi = \{ R_1, \dotso, R_n \}$ be a regular partition of $\Sigma^*$ . We say that $G$ is an LL( $\pi$ ) grammar if, for arbitrary derivations

; $\begin{array}{ccccccc} S & \Rightarrow^L & w_1 A \chi_1 & \Rightarrow & w_1 \nu \chi_1 & \Rightarrow^* & w_1 x\\ S & \Rightarrow^L & w_2 A \chi_2 & \Rightarrow & w_2 \omega \chi_2 & \Rightarrow^* & w_2 y, \\ \end{array}$

such that $x \equiv y \mod \pi$ it follows that $\nu=\omega$ .{{cite journal |last1=Poplawski |first1=David |title=Properties of LL-Regular Languages |date=1977 |publisher=Purdue University}}

A grammar G is said to be LL-regular (LLR) if there exists a regular partition of $\Sigma^*$ such that G is LL( $\pi$ ). 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(k) grammar is LLR. Every LL(k) grammar is deterministic, but there exists a LLR grammar that is not deterministic.{{cite report | url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1176&context=cstech | author=David A. Poplawski | title=Properties of LL-Regular Languages | institution=Purdue University, Department of Computer Science | type=Technical Report | number=77–241 | date=Aug 1977 }} Hence the class of LLR grammars is strictly larger than the union of LL(k) for each k.

It is decidable whether, given a regular partition $\pi$ , a given grammar is LL( $\pi$ ). 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 (LRR, the {{clarify span|corresponding|reason=This should better be fleshed out to a formal definition of LRR grammars.|date=August 2021}} equivalent for LR(k) grammars), but there exists an LR(1) 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(1) parser is sufficient to handle the transduced input in linear time. Thus, LLR parsers can handle a class of grammars strictly larger than LL(k) 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(k) and LR(k) 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,{{harvtxt|Korenjak|Hopcroft|1966}} or just simple,{{harvtxt|Hopcroft|Ullman|1979|page=229}} Exercise 9.3 if

it is in Greibach normal form (i.e. each rule has the form $Z \rightarrow aY_1 \ldots Y_n, n \geq 0$ ), and
different right hand sides for the same nonterminal $Z$ always start with different terminals $a$ .

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(1) grammar in Greibach normal form equals the class of simple deterministic languages.{{harvtxt|Rosenkrantz|Stearns|1970|page=243}}

This language class includes the regular sets not containing ε. Equivalence is decidable for it, while inclusion is not.

Applications

LL grammars, particularly LL(1) grammars, are of great practical interest, as they are easy to parse, either by LL parsers or by recursive descent parsers, and {{clarify span|many computer languages|reason=Which ones? Many languages are 'mostly LL(1)', but not completely (e.g. C).|date=February 2019}} are designed to be LL(1) for this reason. Languages based on grammars with a high value of k have traditionally been considered {{Citation needed|date=August 2009}} to be difficult to parse, although this is less true now given the availability and widespread use {{Citation needed|date=August 2009}} of parser generators supporting LL(k) grammars for arbitrary k.

Notes

Sources

{{Cite journal | title = On the relationship between LL(1) and LR(1) grammars

| last = Beatty | first = J. C.

| journal = Journal of the ACM

| year = 1982 | volume = 29 | issue = 4 (Oct) | pages = 1007–1022

| url = https://cs.uwaterloo.ca/research/tr/1979/CS-79-36.pdf

| doi = 10.1145/322344.322350

| s2cid = 14700480 }}

{{cite book| title = Introduction to Automata Theory, Languages, and Computation

| last1 = Hopcroft | first1 = John E.

| last2 = Ullman | first2 = Jeffrey D.

| year = 1979

| publisher = Addison-Wesley

| url = https://archive.org/details/introductiontoau00hopc | url-access = registration

| isbn = 978-0-201-02988-8

}}

{{cite book| title = The C Programming Language | edition = 2nd

| last1 = Kernighan | first1 = Brian W.

| last2 = Ritchie | first2 = Dennis M.

| publisher = Prentice Hall | location = Englewood Cliffs/NJ

| series = Prentice Hall Software Series

| url = https://archive.org/details/cprogramminglang00bria | url-access = registration

| date = April 1988

| isbn = 978-013110362-7

}}

{{cite book| chapter = Simple deterministic languages

| last1 = Korenjak | first1 = A.J.

| last2 = Hopcroft | first2 = J.E.

| year = 1966

| title = IEEE Conf. Rec. 7th Ann. Symp. on Switching and Automata Theory (SWAT)

| volume = 16-C-40 | series = IEEE Pub. No.

| pages = 36–46

| doi = 10.1109/SWAT.1966.22

}}

{{Cite journal | title = LL(*): The Foundation of the ANTLR Parser Generator

| last1 = Parr | first1 = T.

| last2 = Fisher | first2 = K.

| journal = ACM SIGPLAN Notices

| year = 2011 | volume = 46 | issue = 6 | pages = 425–436

| url = http://www.antlr.org/papers/LL-star-PLDI11.pdf

| doi = 10.1145/1993316.1993548

}}

{{cite journal | title = Properties of Deterministic Top Down Grammars

| last1 = Rosenkrantz | first1 = D. J.

| last2 = Stearns | first2 = R. E.

| journal = Information and Control

| year = 1970 | volume = 17 | issue = 3 | pages = 226–256

| doi = 10.1016/s0019-9958(70)90446-8

| doi-access = free

}}

{{cite book| title = Compiler Construction

| last1 = Waite | first1 = William M.

| last2 = Goos | first2 = Gerhard

| year = 1984

| publisher = Springer | location = Heidelberg

| series = Texts and Monographs in Computer Science

| isbn = 978-3-540-90821-0

}}