Re: LR(1) Parsing : Error Handling & Recovery

Hans Aberg <haberg-news@telia.com>
Sat, 19 Jul 2014 15:29:21 +0200

          From comp.compilers

Related articles
[5 earlier articles]
Re: LR(1) Parsing : Error Handling & Recovery ivan@ootbcomp.com (Ivan Godard) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery gneuner2@comcast.net (George Neuner) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-18)
Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-18)
Re: LR(1) Parsing : Error Handling & Recovery monnier@iro.umontreal.ca (Stefan Monnier) (2014-07-18)
Re: LR(1) Parsing : Error Handling & Recovery DrDiettrich1@aol.com (Hans-Peter Diettrich) (2014-07-19)
Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-07-19)
Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-07-20)
Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-07-20)
Re: LR(1) Parsing : Error Handling & Recovery gneuner2@comcast.net (George Neuner) (2014-07-20)
Re: LR(1) Parsing : Error Handling & Recovery arnold@skeeve.com (2014-07-20)
Re: LR(1) Parsing : Error Handling & Recovery monnier@iro.umontreal.ca (Stefan Monnier) (2014-07-20)
Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-20)
[14 later articles]
| List of all articles for this month |

From: Hans Aberg <haberg-news@telia.com>
Newsgroups: comp.compilers
Date: Sat, 19 Jul 2014 15:29:21 +0200
Organization: A noiseless patient Spider
References: 14-07-023 14-07-024 14-07-030 14-07-031
Keywords: parse, theory
Posted-Date: 19 Jul 2014 11:36:52 EDT

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.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.