Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end From: Ivan Godard Newsgroups: comp.compilers Subject: Re: LR(1) Parsing : Error Handling & Recovery Date: Thu, 17 Jul 2014 13:57:00 -0700 Organization: A noiseless patient Spider Lines: 39 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-07-029@comp.compilers> References: <14-07-023@comp.compilers> <14-07-024@comp.compilers> <14-07-026@comp.compilers> <14-07-027@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: miucha.iecc.com 1405704930 68826 2001:470:1f07:1126:0:676f:7373:6970 (18 Jul 2014 17:35:30 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Fri, 18 Jul 2014 17:35:30 +0000 (UTC) Keywords: LR(1), parse, comment Posted-Date: 18 Jul 2014 13:35:29 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1319 On 7/17/2014 1:03 PM, Ivan Godard wrote: > [The problem with LALR error recovery is that the generated parser > combines states that are the same if your program is valid, but they > are from different grammar rules, so you'd want to produce different > error messages. The size of LR(1) parser tables was an issue on a 64K > PDP-11, but they're trivial now, and I don't know of any reason other > than inertia to use LALR rather than LR(1). -John] > This suggests that LALR with sufficient error handling is of the same size as LR(1), so I'll rephrase my question in those terms: what is the ruleset size difference between good and no error handling for the same language? I am concerned with ruleset size here, not table size. Ruleset size matters to the language designer, which I have repeatedly been in my career. Too large a ruleset makes a language intellectually intractable and impractical to extend; one of the charges against Algol68 was that it was too big, compared to Algol60; the WG2.1 group of then should see the C++ spec we have now :-( In my recursive descent compilers, I have always done semantic analysis on the fly while doing the parse, which lets me give semantically apt diagnostics where appropriate rather than "left parenthesis expected", or, worse, the "right bracket cannot appear here" kind of diagnostic. Doing semantics on the fly also permits a language to have a semantic-directed grammar, where what can follow "foo" depends on what "foo" is. Such grammars have much greater expressiveness than pure BNF-style syntax, although that beauty may be in the eye of the beholder. [Error rules in yacc parsers are really for error recovery, not error reporting. They let the parser resynchronize at a boundary such as a semicolon between statements. LALR can only tell you that the parse failed, and it can give you a set of tokens that would be valid where the parse failed, but that set is often too large due to the way the states are created. It's certainly easier to produce diagnostics in a RD parser. What's hard is to verify that the language it accepts is the language you want, and that it correctly catches any invalid input. -John]