Re: detecting ambiguous grammars

Thant Tessman <thant@acm.org>
26 Mar 2001 13:43:17 -0500

          From comp.compilers

Related articles
[4 earlier articles]
Re: detecting ambiguous grammars henry@spsystems.net (2001-03-04)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-04)
Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-03-08)
Re: detecting ambiguous grammars dlester@cs.man.ac.uk (2001-03-10)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-12)
Re: detecting ambiguous grammars christian.bau@isltd.insignia.com (2001-03-22)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-26)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-26)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-27)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-31)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-31)
[6 later articles]
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 26 Mar 2001 13:43:17 -0500
Organization: XMission http://www.xmission.com/
References: 01-02-080 01-03-020 01-03-032 01-03-078 01-03-084 01-03-102
Keywords: parse
Posted-Date: 26 Mar 2001 13:43:17 EST

Christian Bau wrote:


[...]


> If you wrote a program in a language defined by an ambigous
> grammar, what can happen: Either the compiler will find all
> possible ways to parse your code (or at least find out if
> there are two or more ways to parse the code) or it won't.
> In the first case, you could still use the language for
> programming, as long as you avoid programs that are actually
> ambiguous. If the compiler actually detects and rejects all
> ambiguous programs then you have the strange effect that the
> language that it accepts is actually unambiguous, but
> different from the language defined by the grammar.


[...]


There is another option. In lex, if a string of letters matches more
than one rule, the rule that occurs first in the rule section is
chosen. A grammar specification could work the same way. Although
ambiguities wouldn't be explicitly enumerated, it is always clear how
to disambiguate.


The interesting question is whether such a grammar specification would
tend to match the programmer's intentions. A bigger worry is that
grammar ambiguities may be a sign that there are perfectly valid
semantic constructs within a language for which there may be no
syntactic expression. To rephrase my question: Does the advantage of
addressing ambiguities up front outweigh the advantage of potentially
more expressive grammars? (In practice, it doesn't seem like languages
are designed with these considerations in mind. Nevertheless it is the
argument I'm having with myself as I get my DFA-generating code into
shape...)


-thant
[I've used Earley parsers that preferred the derivation that used fewer
rules, so you could add special case rules that overrode general ones.
It worked OK. -John]





Post a followup to this message

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