LALR parser generator: Difference between revisions

Revision as of 11:12, 2 July 2012

Revision as of 04:41, 3 July 2012

Line 3:

<!-- For administrator use only: {{Old AfD multi|page=LALR parser generator|date=29 June 2012|result='''keep'''}} -->

<!-- End of AfD message, feel free to edit beyond this point -->

{{UnreferencedRefimprove|date=August 2011}}

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 parser]]s are desirable because they are very fast and small in comparison to other types of parsers.

Line 14:

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.<ref >{{Cite web

|title=Yacc: Yet Another Compiler-Compiler

|author=Stephen C. Johnson

Line 29:

==External links==

* [http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf On the translation of languages from left to right, Knuth, D.E., Information and Control 8, 607-639 (1965)]

* [http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf Practical Translators for LR(k) Languages, DeRemer, F.L., PhD Dissertation, M.I.T. (1969)]

* [http://dl.acm.org/citation.cfm?id=357187 Efficient Computation Of LALR(1) Look-Ahead Sets, DeRemer and Pennello, TOPLAS (1982)]