Re: LR Grammars not in LALR(1) or LR(1)

"S÷nke Kannapinn" <ska1@snafu.de>
18 Oct 2002 23:29:22 -0400

          From comp.compilers

Related articles
[12 earlier articles]
Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) haberg@matematik.su.se (Hans Aberg) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-09-29)
Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-10-13)
Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (S├Ânke Kannapinn) (2002-10-18)
Re: LR Grammars not in LALR(1) or LR(1) joachim_d@gmx.de (Joachim Durchholz) (2002-10-20)
Re: LR Grammars not in LALR(1) or LR(1) clint@0lsen.net (Clint Olsen) (2002-10-24)
Re: LR Grammars not in LALR(1) or LR(1) ska1@snafu.de (S├Ânke Kannapinn) (2002-10-25)
| List of all articles for this month |

From: "S÷nke Kannapinn" <ska1@snafu.de>
Newsgroups: comp.compilers
Date: 18 Oct 2002 23:29:22 -0400
Organization: [Posted via] Inter.net Germany GmbH
References: 02-09-014 02-09-029 02-09-068 02-09-092 02-09-097 02-09-126 02-09-130 02-09-143 02-10-015
Keywords: parse
Posted-Date: 18 Oct 2002 23:29:22 EDT

Chris F Clark writes:


> 1) Any deterministic context-free language (DCFL) (that is a language
> that has at least one deterministic context free grammar (DCFG))
> has an LR(1) grammar.
>
> ...
>
> 3) Not every DCFL has an LALR(1) grammar.
>
> ...
>
> From what I understand of the theory, I believe points 2 & 3 are
> potential killers. Essentially I think they point to the existence of
> pathological grammars that are ambiguous but which have a
> deterministic (unambiguous) parse and for which it is not possible to
> algorithmically find the corresponding LALR grammar (if there even is
> one).


Just a minor correction concerning 3):


For k >= 0, any cfg G can be transformed into a structurally equivalent
cfg which is SLR(k) if and only if G is LR(k).
Therefore, for any fixed k >= 0, the families of LR(k) languages,
LALR(k) languages, and SLR(k) languages are all equal.


See Theorem 6.70 in chapter 6.6 of


        Seppo Sippu and Eljas Soisalon-Soininen:
        Parsing Theory. Vol.II: LR(k) and LL(k) Parsing
        EATCS Monographs on Theoretical Computer Science
        Springer-Verlag, 1990


which also contains a detailed proof (using the concept of a cfg
T_k(G) that right-to-right covers a cfg G).


Put another way, every DCFL has an LR(1), an LALR(1) and even an SLR(1)
grammar.


Regards,
Soenke.


Post a followup to this message

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