A lookahead LR parser (LALR) generator is a software tool that reads a
BNF grammar and creates an
LALR parser which is capable of parsing files written in the
computer language defined by the BNF grammar.
LALR parsers are desirable because they are very fast and small in comparison to other types of parsers.
There are other types of
parser generators, such as
Simple LR parser,
LR parser,
GLR parser,
LL parser
In computer science, an LL parser (Left-to-right, leftmost derivation) 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 ...
and
GLL parser generators. What differentiates one from another is the type of BNF grammar which they are capable of accepting and the type of parsing algorithm which is used in the generated parser. An LALR parser generator accepts an LALR grammar as input and generates a parser that uses an LALR parsing algorithm (which is driven by LALR parser tables).
In practice, LALR offers a good solution, because LALR(1) grammars are more powerful than SLR(1), and can parse most practical LL(1) grammars. LR(1) grammars are more powerful than LALR(1), but canonical LR(1) parsers can be extremely large in size and are considered not practical. Minimal LR(1) parsers are small in size and comparable to LALR(1) parsers.
History
Frank DeRemer invented LALR parsers with his PhD dissertation, called "Practical LR(k) Translators", in 1969, at MIT. This was an important breakthrough, because LR(k) translators, as defined by
Donald Knuth in his 1965 paper, "On the Translation of Languages from Left to Right", were much too large for implementation on computer systems in the 1960s and 70's.
An early LALR parser generator and probably the most popular one for many years was "
yacc
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a com ...
" (Yet Another Compiler Compiler), created by
Stephen Johnson in 1975 at AT&T Labs.
Another, "TWS", was created by Frank DeRemer and Tom Pennello. Today, there are many LALR parser generators available, many inspired by and largely compatible with the original Yacc, for example
GNU bison
GNU Bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification in the BNF notation (a context-free language), warns about any parsing ambiguities, and generates a parser that reads sequence ...
, a pun on the original Yacc/
Yak
The domestic yak (''Bos grunniens''), also known as the Tartary ox, grunting ox or hairy cattle, is a species of long-haired domesticated cattle found throughout the Himalayan region of the Indian subcontinent, the Tibetan Plateau, Kachin Sta ...
. See
Comparison of deterministic context-free language parser generators for a more detailed list.
Overview
The LALR parser and its alternatives, the SLR parser and the
Canonical LR parser, have similar methods and parsing tables; their main difference is in the mathematical grammar analysis algorithm used by the parser generation tool. LALR generators accept more grammars than do SLR generators, but fewer grammars than full LR(1). Full LR involves much larger parse tables and is avoided unless clearly needed for some particular computer language. Real computer languages can often be expressed as LALR(1) grammars. In cases where they can't, a LALR(2) grammar is usually adequate. If the parser generator allows only LALR(1) grammars, the parser typically calls some hand-written code whenever it encounters constructs needing extended lookahead.
Similar to an
SLR parser
In computer science, a Simple LR or SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. As with other types of LR(1) parser, an SLR parser is quite efficient at finding the single correct ...
and Canonical LR parser generator, an LALR parser generator constructs the LR(0) state machine first and then computes the lookahead sets for all rules in the grammar, checking for ambiguity. The Canonical LR constructs full lookahead sets. LALR uses merge sets, that is it merges lookahead sets where the LR(0) core is the same. The SLR uses
FOLLOW
Follow may refer to:
* ''Follow'' (album), the third album by Pakho Chau
*Follow (dancer), one member of a partner dance
*"Follow", a song by Jerry Merrick, popularized by Richie Havens on his 1966 album ''Mixed Bag''
*"Follow", a song by Drowning ...
sets as lookahead sets which associate the right hand side of a LR(0) core to a lookahead terminal. This is a greater simplification than that in the case of LALR because many conflicts may arise from LR(0) cores sharing the same right hand side and lookahead terminal, conflicts which are not present in LALR. This is why SLR has less language recognition power than LALR with Canonical LR being stronger than both since it does not include any simplifications.
See also
*
Comparison of parser generators for a more complete list, which also includes LL, SLR, GLR and LR parser generators.
References
* Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. ''
Compilers: Principles, Techniques, and Tools'' Addison—Wesley, 1986. (AKA
The Dragon Book, describes the traditional techniques for building LALR(1) parsers.)
* Richard Bornat ''
Understanding and Writing Compilers
Understanding is a psychological process related to an abstract or physical object, such as a person, situation, or message whereby one is able to use concepts to model that object.
Understanding is a relation between the knower and an object ...
'', Macmillan, 1979. (Describes the principles of automated left-to-right parsing and how to construct the parser tables, what a follow set is, etc., ''in English, not mathematics'' – available freely from the author's page a
)
Further reading
*
*
Efficient Computation Of LALR(1) Look-Ahead Sets, DeRemer and Pennello, TOPLAS (1982)
{{Parsers
Parser generators