Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Corrected Richard Bornat's home page URL |
||
(7 intermediate revisions by 7 users not shown) | |||
Line 1:
{{Refimprove|date=August 2011}}
A '''lookahead
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
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 22 ⟶ 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 conflicts may arise from LR(0) cores sharing the same right hand side and lookahead terminal, conflicts
==See also==
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 [
==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
* {{cite thesis
|type=Ph.D.
|