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

Tom Payne wrote:


> Hmmmmm. Suppose we have a YACC input that uses disambiguation rules.
> Does the standard way of removing the precedence and associativity
> ambiguities by introducing new nonterminals and grammar rules always
> yield an LALR(1) grammar? It would be nice if that were so.


Joachim Durcholz replied:


> The original grammar is ambiguous, hence not LR-anything. So this
> question doesn't make much sense to me.


Presuming Tom is asking the question "Can a question with precedence
and associativity directives as in most yacc derivatives be
transformed into an LALR grammar with no directives?" the question
does make sense, but does not have a known answer as far as I can
recall.


From the theoretical results that I know. Here are some of the known
facts. I hope I get them all right. Some of the facts are very
subtle and non-intuitive.


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.


2) There is no algorithm that can find the LR(1) grammar given an
      arbitrary DCFL. I presume that is also true even if you have a
      non-LR(1) DCFG for the DCFL. (This means if you thing you have an
      alogorithm an omnisicient being can find a grammar that your
      algorithm will not work correctly upon.)


3) Not every DCFL has an LALR(1) grammar.


4) There is no algorithm then can tell if an aribtrary grammar is
      unambiguous.


5) There are algorithms that can tell if specific grammars are
      unambiguous.


6) Every LR(k) grammar is unambiguous.


7) Every DCFL has an unambiguous grammar (i.e the LR(1) grammar for
      the DCFL is an unambiguous one).


8) Precedence and associativity directives allow parsing an ambiguous
      grammar deterministically (by eliminating the ambiguous parses and
      potentially some non-ambiguous ones). (The original paper on the
      topic was called "Deterministic Parsing of Ambiguous Grammars". It
      is easy to read and worth finding in my opinion.)


9) The pressence of a conflict in a LR grammar does not necessarily
      mean that the grammar is ambiguous (only that the LR parser
      generator cannot tell whether the grammar is ambiguous or not).


10) Any ambiguous grammar will have LR conflicts.


Form 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).


However, given all of this, from the practical point of view, I think
the common transformations can be expected to reliably generate an
LALR grammar from the ambiguous one for any grammar you are likely to
encounter.


One point which has been discussed in some of the related threads,
transforming a grammar often destroys its structure. Thus, even if
one could mechanically generate an unambiguous LALR grammar from one
with precedence and associativity declarations, it is not clear that
one would want to, since doing so might change the non-terminals
sufficiently that one could not decorate the grammar the way one would
like. (Note also that the grammar with the directives is probably
smaller, faster running, and easier to read than the unambiguous
grammar.)


Joachim Durcholz also replied:


> It's too easy to "disambiguate" a grammar into something that
> accepts a language that's different from the intended one.


This is a truth. Careless use of precedence and associativity
directives can hide problems in the grammar where the directives apply
not only in the one conflict where they were intended to apply, but
also in other states where they eliminate a path that would have lead
to a correct parse.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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