LALR parser generator

An LALR parser 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 SLR, LR, GLR, LL 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), however, 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.

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" (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, a pun on the original Yacc/Yak. See Comparison of deterministic context-free language parser generators for a more detailed list.

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.

...
Wikipedia