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 text files written in the computer language defined by the BNF grammar.

There are other types of parser generators, such as SLR, LR, and LL 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. In practice, LALR offers a good solution, because LALR(1) grammars are more powerful than SLR(1) and 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.

History

Frank DeRemer invented LALR parsers with his PhD dissertation, called "Practical LR(k) Translators", in 1969, at MIT. This was an important break through, 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 computers systems in the 1960's and 70's.

One of the first LALR parser generators was called the XPL compiler generator, created by Bill McKeeman, in 1972, at Stanford University. Another early LALR parser generator and probably the most popular one for many years was called "yacc", and was created by Stephen Johnson, in 1975, at AT&T Labs. Another early LALR parser generator was called "TWS", created by Frank DeRemer and Tom Pennello.

Today, there are many LALR parser generators available. See Comparison of parser generators for a more complete list, which also includes LL, SLR, and LR parser generators.