Re: grammars

Carl Cerecke <cdc25@it.canterbury.ac.nz>
10 Aug 2003 10:55:01 -0400

          From comp.compilers
Related articles
grammars prerna_sethi@lycos.com (2003-08-04)
Re: grammars Ralf.Laemmel@cwi.nl (Ralf Laemmel) (2003-08-10)
Re: grammars cdc25@it.canterbury.ac.nz (Carl Cerecke) (2003-08-10)
Re: grammars rda@lemma-one.com (Rob Arthan) (2003-08-10)
| List of all articles for this month |
From: Carl Cerecke <cdc25@it.canterbury.ac.nz>
Newsgroups: comp.compilers
Date: 10 Aug 2003 10:55:01 -0400
Organization: TelstraClear
References: 03-08-016
Keywords: parse, theory
Posted-Date: 10 Aug 2003 10:55:01 EDT

Buddy wrote:
> Can all ambiguous grammars be changed into unambiguous grammars?
>
> [Well, sure, you can delete stuff until it's not ambiguous any more.
> But I presume the question you're asking is whether there's always an
> unambiguous grammar that recognizes the same language as an ambigous
> one. -John]


:-)


Assuming Context Free Grammars (CFGs), there are languages which can
be described by an (ambiguous) CFG for which no unambiguous CFG
exists. Such languages are called "inherently ambiguous".


An example is the language:
a^n b^n c^n d^n , n > 0 (i.e. n a's followed by n b's followed by ..)


Google with "inherently ambiguous" reveals much more.


Cheers,
Carl.

Post a followup to this message

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