LL parser

related topics
{math, number, function}
{language, word, form}
{system, computer, user}
{law, state, case}
{school, student, university}

An LL parser is a top-down parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser). The class of grammars which are parsable in this way is known as the LL grammars.

The remainder of this article describes the table-based kind of parser, the alternative being a recursive descent parser which is usually coded by hand (although not always; see e.g. ANTLR for an LL(*) recursive-descent parser generator).

An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. If such a parser exists for a certain grammar and it can parse sentences of this grammar without backtracking then it is called an LL(k) grammar. A language that has an LL(k) grammar is known as an LL(k) language. There are LL(k+n) languages that are not LL(k) languages[1]. A corollary of this is that not all context-free languages are LL(k) languages.

LL(1) grammars are very popular because the corresponding LL parsers only need to look at the next token to make their parsing decisions. Languages based on grammars with a high value of k have traditionally been considered[who?] to be difficult to parse, although this is less true now given the availability and widespread use[citation needed] of parser generators supporting LL(k) grammars for arbitrary k.

An LL parser is called an LL(*) parser if it is not restricted to a finite k tokens of lookahead, but can make parsing decisions by recognizing whether the following tokens belong to a regular language (for example by use of a Deterministic Finite Automaton).

There is contention between the "European school" of language design, who prefer LL-based grammars, and the "US-school", who predominantly prefer LR-based grammars.[citation needed] This is largely due to teaching traditions and the detailed description of specific methods and tools in certain text books; another influence may be Niklaus Wirth at ETH Zürich in Switzerland, whose research has described a number of ways of optimising LL(1) languages and compilers.

Contents

Full article ▸

related documents
Algebraically closed field
Expander graph
Stokes' theorem
Integer factorization
Associative array
Document Type Definition
Topology
Parameter
Optimization (mathematics)
Line integral
Banach space
Henri Lebesgue
Even and odd permutations
Cauchy's integral formula
Universal quantification
A* search algorithm
Morphism
Topological vector space
B-spline
Weak topology
Yoneda lemma
Stone–Weierstrass theorem
Free group
Positive-definite matrix
Haskell (programming language)
Solvable group
Boolean algebra (structure)
Finite difference
Normal space
Hypercomplex number