13 Oct 2002 16:02:24 -0400

Related articles |
---|

[10 earlier articles] |

Re: LR Grammars not in LALR(1) or LR(1) thp@cs.ucr.edu (2002-09-25) |

Re: LR Grammars not in LALR(1) or LR(1) Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2002-09-25) |

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

From: | "Chris F Clark" <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | 13 Oct 2002 16:02:24 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

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 |

Keywords: | parse |

Posted-Date: | 13 Oct 2002 16:02:23 EDT |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.