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

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.

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