Talk:LALR parser

Initial comments

Talk moved; was originally on head page.

((This is rubbish, I will try to write something at the weekend (2001-08-18). --drj. Immediate issues: LALR is an algorithm for generating tables for a table driven LR shift reduce parser. It is not a parser (ooh except maybe the Natural Language community think it is). pretty sure the derivation of each of the letters is wrong.))

Hmmm. Looking at an old copy of the Dragon Book (which I've heard is pretty well respected in the field, but I may be wrong):

"These parsers are called LR parsers because they scan the input from left-to-right and construct a rightmost derivation in reverse ... The third method, called lookahead LR (LALR for short) ... the LALR parser of Fig. 6.13 ..." -- Principles of Compiler Design, Aho and Ullman

So there's some precedent for calling something an "LALR parser" since they did it throughout the book and there are five citations, some of them multi-page, in the index for that phrase. I didn't create the initial entry, but I was kinda irked at the tone of the comment --loh

Okay. I am intending to use my Dragon Book when I write the article so no doubt I would've found all this out anyway. "Recursing on the rightmost non-terminal in any grammar rule" is not really a good definition of producins a rightmost derivation BTW. --drj

Well, I guess my definition was not TOTAL RUBBISH, as drj seemed to imply. I agree recursing isn't the best way to describe it. Hm.. maybe I should go look at the stuff I said was rubbish and make sure I wasn't wrong.

OK, I looked at my Dragon Book (2nd ed, BTW) and wrote the articles LR parser (which was longish) and LALR parser (which was short). But my email at home is busted so I can't put it here yet. *sigh*. LALR stands for Lookahead LR and is a method for producing LR parsers. LR stands for Left-to-right scan, Rightmost derivation. 2nd ed Dragon does not use the term LALR parser, and neither do I so I'm not sure what one is; I assume it is an LR parser produced by the LALR method? Sorry I used the term "rubbish" because the original entry certainly is not. --drj

A parser constructed by the LALR technique has tables the size of an LR(0) parser, yet is far more powerful and useful, which I think makes it a legitimate parser classification. It is also common enough (being produced by YACC) that the classification is useful in practice. The term "LALR parser" is also unambiguous, and (above all else) is in common usage, and so I think the objection to its use in Wikipedia is somewhat pedantic. --Doradus 16:33, Sep 17, 2004 (UTC)

Your source material link (to an Oberlin CS lecture) is dead. :( --utopianheaven 11:31, Jan 30, 2006 (UTC)

How about some information on DFA and state transition? Maybe a comparison to LL and LR parsing techniques? Niklaus Wirth states (in his book "Compiler Construction", ISBN 0-201-40353-6, p. 24) that the "LL" and "LR" naming convention was introduced by Knuth. Might also mention that the "LR" in stands for "L" = "Left-to-Right" and "R" = "Rightmost production", and explain what that means. BTW, the "Gold", "Anagram", etc., software packages are LALR. You might want to add some references: http://www.devincook.com/goldparser/, http://www.parsifalsoft.com/, etc.12.110.196.19 21:26, 7 February 2007 (UTC)

---

I just rewrote most of the article, trying to keep the previous text in the article when appropriate. This is a confusing subject for many people and I would like to have an accurate and precise article in Wikipedia, so that people can use it to understand the subject. I have about 30 years of experience implementing an LALR parser generator, so I have first hand knowledge of this subject. It was a long hard learning experience and I offer my explanations for the benefit of others.

About the detailed discussion of the LALR parser table construction algorithms ... I think that should belong to the LALR parser gernerator page that I created for Wikipedia. Afterall, an LALR parser is not concerned with the computation of LALR(1) look-ahead sets.

About LR parser versus LALR parser ... The parsing algorithm for an LALR parser is actually different than the parsing algorithm for an LR parser. An LALR parser has to save the reductions it makes in case of error recovery, whereas an LR parser does not have to save the reductions (it does not make any erroneous reductions). However, an SLR parser algorithm is the same as an LALR parser algorithm.

Finally ... LALR parsers can be used for context-sensitive languages, like C++, if the parser generator has advanced capability for integrating symbol-table lookups with dynamic grammar symbols. I'm pretty sure ANTLR has this capability. I know that my parser generator has this advanced feature. So I don't think Wikipedia should say that LALR is not good for C++ type languages.

Paul B Mann

---

—Preceding unsigned comment added by Paulbmann (talk • contribs) 22:12, 9 September 2009 (UTC)

Merger proposal

The following is a closed discussion of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the proposal was no consensus to merge.
--Yellowdesk (talk) 14:05, 24 November 2011 (UTC)

---

There's no need to have one page for LALR parser and another for LALR parser generator. Once fully developed, these two articles are certain to have more similarities than differences. --Doradus (talk) 02:39, 23 February 2010 (UTC)

• I think it's OK to have a separate page for LALR parser generator. A program that generates a parser is quite different from a parser. People have a lot of trouble figuring out this concept, computer generated software. If the two drastically different programs are combined into one page, the people will be more confused than ever. -- Paul B Mann

• I think the parser generator can be a section here. Sae1962 (talk) 12:27, 8 March 2011 (UTC)

• Oppose parser generators are distinct from, have quite different use cases, and have a very different history. If we develop these articles to a size where they'll cover the same ground, they'll also have enough detail to be even more distinct. Andy Dingley (talk) 00:10, 23 August 2011 (UTC)

The above discussion is preserved as an archive of the proposal. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

From my talk page. As the merge was rejected, the generator article has no been prodded.

The time has come.

• LALR parser generator (edit | talk | history | protect | delete | links | watch | logs | views)
• Talk:LALR parser#Merger proposal

I almost just redirected it, given that it's at the very least a valid alternative title and currently largely a duplicate article. But after I checked "what links here" and found the merger discussion I thought that I'd instead let you know that your opportunity to shine, and to demonstrate what you envisaged last year, has come. ☺ Uncle G (talk) 14:17, 29 June 2012 (UTC)

This is not an alternative name. No question about it. The two concepts are quite different: one is a tool, the another is a different tool, used to make examples of the first (it's easier to do it this way). There is no justification to merge because they're "the same thing" or "alternate names". That's simply incorrect.

There is an argument (which I don't support, but I do recgonise it) that these are very closely related. One indeed cannot exist without the other. If we also recognise that the current article state (NB, current article state, not topic or potential state) explains little difference, then there is an argument on that narrow basis alone for merging. The resultant article would have to have two enormous sections within it that are quite separate. You might argue (with some justification) that this is the most readable article structure -- however these are still two different topics, on two different tools, and need to be treated as such.

The literature on these is vast, and there is no issue of sourcing. Andy Dingley (talk) 15:26, 29 June 2012 (UTC)

Andy, you're splitting hairs. LALR parsers most definitely do not have different history from LALR parser generators. They were both invented in theory in 1969 by Frank DeRemer, and in practice during the 1970s. They also do not have distinct use cases because nobody writes LALR parsers by hand except when working out textbook examples: every LALR parser is produced by an LALR parser generator, and every LALR parser generator produces LALR parsers. Most importantly, an LALR parser, an SLR parser, and an NQLALR parser are all identical pieces of software differing only in the edges in their automata, and those differences all arise from the manner in which the parsers were generated, so there is nothing interesting to be said about LALR parsers besides how they are generated. I still think merging these articles makes more sense than keeping them separate. --Doradus (talk) 01:11, 2 August 2014 (UTC)

What's LALR(1)?

The article gives some idea of what an LALR parser is (well, this is obvious enough when the acronym is expanded). But LALR(1) and LALR(2) are then mentioned — what are these? 89.217.239.233 (talk) 15:10, 24 December 2010 (UTC)

The number in parenthesis is the lookahead. --Allen3 ^talk 12:50, 8 March 2011 (UTC)

Earliest?

The article used to read "The original and most widely known parser generator was yacc, developed on the UNIX operating system." The "LALR Parser Generator" article (LALR_parser_generator) gave dates for XPL as 1970 and yacc as 1975. I changed the date for XPL there to 1968 to correspond to the original FJCC paper, but in either case yacc is not the "original" unless an earlier date is established, so I deleted this sentence. I'd accept "most widely known," except that now there are lots, starting with Gnu Bison. Peter Flass (talk) 19:26, 6 October 2011 (UTC)

DeRemer implemented the first LALR parser generator as part of his thesis that invented LALR. He then turned that parser generator into the core component of a proprietary compiler writing system called Metaware, sold and supported by his company of that name. Metaware was coded in their own dialect of Pascal. Yacc, written in C, was developed by Stephen Johnson of AT&T Bell Labs, from published articles and maybe DeRemer's excellent thesis. I don't know if the early Metaware generator preceded or followed the initial implementation of yacc.

The confusion about XPL's date is because the initial implementation of XPL used a different parser generator based on "extended mixed strategy precedence", a type of precedence parser. XPL switched over to the more powerful LALR methods a few years later. That happened at UC Santa Cruz, so DeRemer was very likely involved in the coding of that generator (written in XPL) also. DBSand (talk) 04:18, 9 May 2012 (UTC)

Are you sure DeRemer wrote an LALR parser generator for his 1969 thesis? I can't find a reference to that in the dissertation. --Doradus (talk) 01:15, 2 August 2014 (UTC)

PDA is not a data structure

PDA is not a data structure. In addition, I don't like "based on a finite-state-automata concept" in the first sentence. I suggest for the first two sentences: "In computer science, an LALR parser (or look-ahead LR parser) is a type of LR parser based on Finite-state machines (FSM). The Model of computation used in the LALR parsers is the pushdown automaton (PDA)." Ginandi (talk) 12:18, 2 February 2012 (UTC)

Please make the introductory explanation of LALR parser....introductory

I am making this request because Wikipedia is for public consumption, not just for us compugeeks. The terminology and the complexity of the sentences in the introduction that a normal person would probably go catatonic trying to figure out what it meant and, if that didn't happen, they'd spend the next 6 years learning all the terminology necessary just to start to understand it. A bit of hyperbole, actually, but I think you get my point. PLEASE "dumb down" the explanation for the mere mortals. Thanks!!!!ReveurGAM (talk) 13:16, 26 February 2012 (UTC)

Not a bad idea. Somehow describe what an LALR parser does rather than what it is (i.e. why would I be interested in this), then get to the technical stuff in a later paragraph.Peter Flass (talk) 13:53, 26 February 2012 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on LALR parser. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20100804231352/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht to http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht
• Added archive https://web.archive.org/web/20100723153301/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht to http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 07:35, 14 December 2017 (UTC)

Pronunciation of "LALR"

I've always heard it pronounced "laller" rather than "el-ay-el-ar" but it is hard to get a reference for this either way. 198.91.146.14 (talk) 01:43, 10 February 2019 (UTC)