Re: An "open" letter to Karsten Nyblad (and other compiler compiler implementors)

Sylvain Schmitz <schmitz@i3s.unice.fr>
26 Jun 2005 11:18:16 -0400

          From comp.compilers

Related articles
[3 earlier articles]
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk) (2005-06-23)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-23)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im wyrmwif@tsoft.org (SM Ryan) (2005-06-24)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im vtsikoza@yahoo.com (2005-06-24)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im wyrmwif@tsoft.org (SM Ryan) (2005-06-24)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-24)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-06-26)
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 26 Jun 2005 11:18:16 -0400
Organization: Compilers Central
References: 05-06-119 05-06-121
Keywords: LR(1), theory

SM Ryan wrote:
> More accurately, any deterministic language has an LR(1) grammar. But
> there is no algorithm to convert any LR(k), k>1, grammar to an LR(1)
> grammar.
See:
M. D. Mickunas, R. L. Lancaster and V. B. Schneider. Transforming LR(k)
Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars.
Journal of the ACM, Volume 23, Issue 3 (July 1976).


The real problems with grammar transformations like the ones presented
above are
* how to handle semantic rules properly, and
* how to avoid grammar size explosion.
The authors discuss these issues.


On the syntax level, there is also a risk of generating a different
language if one is not careful.


--
      Sylvain


Post a followup to this message

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