Talk:Canonical LR parser

I'm still not sure if the naming is correct here. When I read "The dragon book" I get the impression that all the LR(k) with k >= 0 parsers are canonical parsers. -- Jan Hidders 14:14 Aug 18, 2002 (PDT)

Canonicity

A canonical bottom-up parser reduces the leftmost phrase (aka the handle) of a sentential form. This is the case of most bottom-up parsing methods, including SLR(k), LALR(k) and LR(k) for k≥0. To be contrasted with noncanonical bottom-up parsers, where any phrase can be reduced (Tom Szymanski's PhD thesis is the best ressource I know on the subject available on the Internet).

I support the idea of having a separate page for LR(0), and suggest the Canonical LR page to be renamed LR(1) in consequence. -- Sylvain Schmitz 12:36 Aug 4, 2004 (GMT)

Not quite accurate

I think there's some confusion between canonical parsers and canonical parsing tables here. There are a number of algorithms for computing LR(k) parsing tables. The most general methods construct "canonical" parsing tables, faster methods build approximations, for example LALR(1).

Constructing LR(1) parsing tables

Where did this text come from? It looks cut-and-pasted. --Doradus 21:01, Dec 3, 2004 (UTC)

Yep. From http://www.cse.uconn.edu/~akiayias/cse244fa04/N244-4-LR-more.ppt -- Jan Hidders 13:04, 4 Dec 2004 (UTC)

And it seems to me that the construction given is simply wrong. I found a short reference at http://stackoverflow.com/a/14127281 — Preceding unsigned comment added by Krauthaufen (talk • contribs) 09:35, 18 May 2013 (UTC)

Same as/more than what?

The article is written as a comparison - "Goto is the same", "Reduce is more refined" etc. Same as what? More refined than what? IMO, those parts should be written as a full description perhaps followed by a comparison "This makes the reduce action more refined than the reduce operation in the <something>-parser". Perhaps the concept is most succinctly presented by comparison to other kinds of LR parsers rather than full description - but it should always be clear what you're comparing to. 85.194.50.194 11:19, 12 December 2006 (UTC)

Also, "for all b in FIRST(β a)", FIRST seems to be defined nowhere. —Preceding unsigned comment added by 59.178.55.254 (talk) 02:35, 6 June 2010 (UTC)

Needs more cowb- i mean hyperlinks

This article contains a LOT of highly domain-specific language that makes absolutely zero sense whatsoever to someone who hasn't studied the subject in depth beforehand. (And even less for someone who only studied maths in another language in their youth, then picked up english second-hand.) Please at least have the common decency to link words like "production" and "terminal" and anything else that isn't understandable from basic english with to their respective explaining wikipedia pages. --178.0.83.23 (talk) 21:12, 4 January 2011 (UTC)

Also not happy

This article suggests that the lookahead sets are computed from the grammar, which is what I learnt as LALR parsing. A full LR parser generator computes lookahead sets from the underlying LR(0) state machine. When a conflict is found in a state, multiple copies of that state are made, one for each transition into that state. Then again the lookahead sets are computed in the same way. If a conflict then occurs, the grammar is not LR. Then solong as the lookahead sets are equivalent the splitted states can be merged to save space. In this aspect full LR parsing requires more space than LALR. The first time I saw this was back in the eighties and was by David Spector, Full LR(1) Parser Generator ACM Sigplan Notices, 16(8), August 1981.

Another aspect which differs from LALR is that when a state is a pure reduce state, it's lookahead set is not discarded, so that the reduce only occurs if a subsequent shift can happen. In LALR one does not even bother to compute the reduce lookahead set, since a subsequent shift will detect the error.

An extension of full LR, also I think from Spector although I can't find the reference, is LAR parsing. In an LR parser with a shift/reduce conflict the underlying state machine is searched from the conflict point to construct a sequence of terminal symbols from which a regular expression and consequently a finte state machine is constructed. This is used to resolve the conflict. These techniques were used in the CAT system : Common Abstract Tree Language. R. Voeller & Uwe Schmidt, U Kiel, Germany 1983. Universal intermediate language, used by Norsk Data in their family of compilers. "A Multi-Language Compiler System with Automatically Generated Codegenerators, U. Schmidt et al, SIGPLAN Notices 19(6):202-2121 (June 1984).

BigRat (talk) 12:18, 1 December 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Canonical LR parser. Please take a moment to review my edit. You may add {{cbignore}} after the link to keep me from modifying it, if I keep adding bad data, but formatting bugs should be reported instead. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether, but should be used as a last resort. I made the following changes:

• Attempted to fix sourcing for http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf

Is the grammar sample confusing ?

The sample grammar illustrating this wikipedia entry is both left and right recursive : T → + T and T → T + n This grammar is not LR, and even a full featured LR(k) parser will end with a s/r conflict. When rewriting this article, it may be useful to choose a LR grammar. — Preceding unsigned comment added by Vgrenier (talk • contribs) 08:32, 7 February 2017 (UTC)

I agree, the sample grammar is not LR(1). (this can be verified with this online tool) This a major problem when trying to implement an LR(1) parser based on this page because it makes it impossible follow along and check your work. ImTehJoE (talk) 17:43, 13 December 2017 (UTC)

As of right now, 5 years later, this seems to still be the case. The above linked tool indicates a shift/reduce conflict in states 12 and 17, which I found out after trying to build a parser generator using the here provided information. While I don't understand many things, why hasn't anybody changed this yet? 2003:ED:BF29:5BBF:6486:9EF6:189B:4D46 (talk) 21:18, 19 February 2023 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Canonical LR 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 http://lrstar.tech/

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: 18 January 2022).

• 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) 08:22, 30 July 2017 (UTC)