LALR parser generator: Difference between revisions

Revision as of 09:32, 15 July 2021

Latest revision as of 12:53, 30 July 2024

(6 intermediate revisions by 6 users not shown)

Line 1:

{{Refimprove|date=August 2011}}

A '''lookahead left-to-rightLR parser (LALR) parser 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 [[Simple LR parser]], [[LR parser]], [[GLR parser]], [[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. 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), 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==

Line 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. 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.

|archive-date=2011-07-11

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

|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 30 ⟶ 34:

{{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 [httphttps://www.cseis.mdx.ac.uk/staffpages/r_bornat/#vanitypublishing].)

==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 | url = http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | access-date = 29 May 2011 | archive-url = https://web.archive.org/web/20120315152151/http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | archive-date = 15 March 2012 | url-status = dead | doi-access = free }}

* {{cite thesis

|type=Ph.D.