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: Hans Aberg Newsgroups: comp.compilers Subject: Re: LR(1) Parsing : Error Handling & Recovery Date: Sat, 19 Jul 2014 15:29:21 +0200 Organization: A noiseless patient Spider Lines: 22 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-07-038@comp.compilers> References: <14-07-023@comp.compilers> <14-07-024@comp.compilers> <14-07-030@comp.compilers> <14-07-031@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: miucha.iecc.com 1405784213 58003 2001:470:1f07:1126:0:676f:7373:6970 (19 Jul 2014 15:36:53 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 19 Jul 2014 15:36:53 +0000 (UTC) Keywords: parse, theory Posted-Date: 19 Jul 2014 11:36:52 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:1328 On 2014/07/18 21:41, William Clodius wrote: > I have memories that an LR(k) grammar can in principle be refactore to > LR(1), but that in general an LL(k) gramar cannot be refactored to > LL(1). For every LR(k) grammar there is an LR(1) grammar parsing the same language [1], but this result does not say what happens with the grammar rule actions. A GLR parser splits the parses in face of an ambiguity, which might be used instead. Bison supports this, but currently the actions during a parse split are not executed, and so cannot set context variables for the lexer, until the merge. Some other results from [1]: Every LL(k) grammar is LR(k); not all LR(k) grammars are LL(k). If one knows a grammar is LR(k) for some k, then there it is decidable whether it is LL(k') for some k'. 1. Waite & Goos, "Compiler Construction", p. 133.