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

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.

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