LL parser

Key takeaways

LL parser belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect LL parser to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of LL parser from memory before moving on to harder problems.

Reference excerpt

In computer science, an LL parser is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL(k) grammar if an LL(k) parser can be constructed from it. A formal language is called an LL(k) language if it has an LL(k) grammar. The set of LL(k) languages is properly contained in that of LL(k+1) languages, for each k ≥ 0. A corollary of this is that not all context-free languages can be recognized by an LL(k) parser. An LL parser is called LL-regular (LLR) if it parses an LL-regular language. The class of LLR grammars contains every LL(k) grammar for every k. For every LLR grammar there exists an LLR parser that parses the grammar in linear time. Two nomenclative outlier parser types are LL(*) and LL(finite). A parser is called LL(*)/LL(finite) if it uses the LL(*)/LL(finite) parsing strategy. LL(*) and LL(finite) parsers are functionally closer to PEG parsers. An LL(finite) parser can parse an arbitrary LL(k) grammar optimally in the amount of lookahead and lookahead comparisons. The class of grammars parsable by the LL(*) strategy encompasses some context-sensitive languages due to the use of syntactic and semantic predicates and has not been identified. It has been suggested that LL(*) parsers are better thought of as TDPL parsers. Against the popular misconception, LL(*) parsers are not LLR in general, and are guaranteed by construction to perform worse on average (super-linear against linear time) and far worse in the worst-case (exponential against linear time). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers may be table-based, i.e. similar to LR parsers, but LL grammars can also be parsed by recursive descent parsers. According to Waite and Goos (1984), LL(k) grammars were introduced by Stearns and Lewis (1969).

Overview For a given context-free grammar, the parser attempts to find the leftmost derivation. Given an example grammar G:

S → E {\displaystyle S\to E}

E → ( E + E ) {\displaystyle E\to (E+E)}

E → i {\displaystyle E\to i}

the leftmost derivation for w = ( ( i + i ) + i ) {\displaystyle w=((i+i)+i)} is:

S ⇒ ( 1 ) E ⇒ ( 2 ) ( E + E ) ⇒ ( 2 ) ( ( E + E ) + E ) ⇒ ( 3 ) ( ( i + E ) + E ) ⇒ ( 3 ) ( ( i + i ) + E ) ⇒ ( 3 ) ( ( i + i ) + i ) {\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)}

Generally, there are multiple possibilities when selecting a rule to expand the leftmost non-terminal. In step 2 of the previous example, the parser must choose whether to apply rule 2 or rule 3:

S ⇒ ( 1 ) E ⇒ ( ? ) ? {\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}

To be efficient, the parser must be able to make this choice deterministically when possible, without backtracking. For some grammars, it can do this by peeking on the unread input (without reading). In our example, if the parser knows that the next unread symbol is (, the only correct rule that can be used is 2. Generally, an LL(k) parser can look ahead at k symbols. However, given a grammar, the problem of determining if there exists a LL(k) parser for some k that recognizes it is undecidable. For each k, there is a language that cannot be recognized by an LL(k) parser, but can be by an LL(k + 1) parser. We can use the above analysis to give the following formal definition: Let G be a context-free grammar and k ≥ 1. We say that G is LL(k), if for any two leftmost derivations:

S ⇒ ⋯ ⇒ w A α ⇒ ⋯ ⇒ w β α ⇒ ⋯ ⇒ w u {\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with LL parser

Start with the simplest possible case. Write down what LL parser claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to LL parser before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about LL parser ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of LL parser

In research: LL parser appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses LL parser in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: LL parser is common in secondary-school and first-year university syllabi. It links to neighbouring topics Parsing algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for LL parser outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study LL parser in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what LL parser means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain LL parser out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is LL parser in simple terms?

In computer science, an LL parser is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.

Why does LL parser matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study LL parser?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on LL parser.