LALR parser generator: Difference between revisions

Revision as of 17:53, 10 July 2012

Latest revision as of 12:53, 30 July 2024

(40 intermediate revisions by 25 users not shown)

Line 1:

<!-- Please do not remove or change this AfD message until the issue is settled -->

{{Article for deletion/dated|page=LALR parser generator|timestamp=20120629185237|year=2012|month=June|day=29|substed=yes}}

<!-- 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 -->

{{Refimprove|date=August 2011}}

AnA '''LALRlookahead LR parser (LALR) generator''' is a software tool that reads a [[BNFcontext-free grammar]] (CFG) and creates an [[LALR parser]] which is capable of parsing files written in the [[computercontext-free language]] defined by the BNF grammarCFG. [[LALR parser]]s are desirable because they are very fast and small in comparison to other types of parsers.

There are other types of [[parser generator]]s, such as SLR[[Simple LR parser]], [[LR parser]], [[GLR andparser]], [[LL parser]] and [[GLL parser]] generators. What differentiates one from another is the type of BNF grammarCFG which they are capable of accepting and the type of parsing algorithm which is used in the generated parser. Obviously, anAn 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,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]]" (Yet Another Compiler Compiler), created by [[Stephen C. Johnson|Stephen Johnson]] in 1975 at AT&T Labs.<ref>{{Citecite web

|title=Yacc: Yet Another Compiler-Compiler

|author=Stephen C. Johnson

Line 20 ⟶ 16:

|year=1975

|url=http://dinosaur.compilertools.net/yacc/

|access-date=2012-07-02

}}</ref> Another, "TWS", was created by Frank DeRemer and Tom Pennello.

|archive-date=2011-07-11

|archive-url=https://web.archive.org/web/20110711231228/http://dinosaur.compilertools.net/yacc/

Today, there are many LALR parser generators available, for example [[GNU bison]], a pun on the original Yacc/[[Yak]].

|url-status=dead

}}</ref> 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 parser generators#Deterministic context-free languages|Comparison of deterministic context-free language parser generators]] for a more detailed list.

==Overview==

Line 28 ⟶ 26:

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]] 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 [[LR(1)#FIRST and FOLLOW sets|FOLLOW]] 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 confictsconflicts may arise from LR(0) cores sharing the same right hand side and lookahead terminal, conflicts thatwhich 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]]{{spaced -ndash}} Forfor a more complete list, which also includes LL, SLR, GLR and LR parser generators.

==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)]

== References ==

{{Reflist}}

* Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. ''[[Compilers: Principles, Techniques, and Tools]]'' Addison—Wesley, 1986. (AKA [[Compilers: Principles, Techniques, and Tools|The Dragon Book]], describes the traditional techniques for building LALR(1) parsers.)

* Richard Bornat ''[[Understanding and Writing Compilers]]'', 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 at [https://www.eis.mdx.ac.uk/staffpages/r_bornat/].)

==Further reading==

{{refbegin}}

* {{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = On the translation of languages from left to right | doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access = }}

* {{cite thesis

|type=Ph.D.

|title=Practical Translators for LR(k) languages

|url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf

|first=Franklin L.

|last=DeRemer

|publisher=MIT

|year=1969

|access-date=2013-08-19

|archive-url=https://web.archive.org/web/20130819012838/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf

|archive-date=2013-08-19

|url-status=dead

}}

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

{{refend}}

{{Parsers}}

[[Category:Parser generators]]