LALR parser generator
This article may have been previously nominated for deletion: Wikipedia:Articles for deletion/LALR parser generator exists. It is proposed that this article be deleted because of the following concern:
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "LALR parser generator" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|LALR parser generator|concern=Other than the reference to the BNF all of the information presented here is also included in the "LALR parser" article}} ~~~~Timestamp: 20120629081421 08:14, 29 June 2012 (UTC) Administrators: delete |
 |
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 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. Obviously, 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 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 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", 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, for example GNU bison.
See also
Comparison of parser generators - For a more complete list, which also includes LL, SLR, GLR and LR parser generators.