Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!news-out.readnews.com!news-xxxfer.readnews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Eric Newsgroups: comp.compilers Subject: Re: LR(1) Parsing : Error Handling & Recovery Date: Wed, 16 Jul 2014 16:40:01 -0400 (EDT) Organization: Compilers Central Lines: 66 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-07-025@comp.compilers> References: <14-07-023@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 1405543201 75858 2001:470:1f07:1126:0:676f:7373:6970 (16 Jul 2014 20:40:01 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Wed, 16 Jul 2014 20:40:01 +0000 (UTC) Keywords: parse, errors Posted-Date: 16 Jul 2014 16:40:01 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:1315 Seima Rao wrote: > How far is impressive error handling & recovery possible by LR(1) parsers ? > > What would be good references for the subject? > > As an aside, do the famous compilers use LR(1) parsing ? I can take a crack at answering some of this. I built my own LALR1 parse generator and parser about 20 years ago. The parser had both Error Repair and Error Handler. I can describe how I implemented these. There are two mechanisms: Error Repair tries to fix the input token stream when a syntax error is detected. This was popular back when compiling was much more expensive and done as submitted batch jobs. The desire was to not abort a compile job or toss away source just because of some syntax error. Error Repair attempts to keep as much of the original input stream and find as many errors as possible in one pass. The basic repair mechanism tries to either Keep, Insert or Delete input stream tokens according to their cost. The "best" repair is the one with the minimum cost. Error Handling is a simpler mechanism and essentially works by tossing away tokens until a recognized state is reached. It can be used when Error Repair is not available or has failed. Error Handling is conceptually like an exception handler (this is just conceptual, it has nothing to do with C++ or operating system exceptions). The LALR1 parser pushes items on the stack. If it reaches a state where the next token cannot be consumed because there is no next state for it (a syntax error), then the parser does the equivalent of "throwing an exception". It scans backwards through the parse stack checking the state for a special terminal called ERROR. If it finds one it rolls back the parse stack to that point, pushes the ERROR terminal on the stack and calls the associated reduction routine as though a match on the input terminal ERROR had been found. That reduction action routine is expected to do clean up. For example statement : assignment_statement | if_statement | loop_statement | ERROR { action_error(); }; Say we are parsing "foo = a * b / / c;". At the second '/' token a syntax error is detected. The parse stack is scanned backwards until we find a state that can shift the ERROR token. That matches a production for "assignment" so the action_error() routine is called which reads input token stream until it consumes a ';'. (I'm glossing over grotty details like who cleans up the parse stack and how is memory recovered.) Finally the assignment production is pushed on the parse stack and we continue as if nothing had gone wrong. Anyway, that is the basic idea. I found Error Repair more interesting but is much more difficult. Most parsers seem to use Error Handling because it is much easier to implement and recompiling is cheap. Eric