10 Aug 2003 10:59:44 -0400

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

From: | Rob Arthan <rda@lemma-one.com> |

Newsgroups: | comp.compilers |

Date: | 10 Aug 2003 10:59:44 -0400 |

Organization: | Lemma 1 Ltd. |

References: | 03-08-016 |

Keywords: | parse, theory |

Posted-Date: | 10 Aug 2003 10:59:44 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]*

And if that's what Buddy meant and if he's talking about context-free

grammars, then the answer is no. An example is given by the following

context-free grammar for the language of all strings comprising some

'a's followed by some 'b's followed by some 'c's subject to the

constraint that either the number of 'a's is equal to the number of

'b's or the number of 'b's is equal to the number of 'c's (or possibly

all three numbers are equal).

S = AB, C | A, BC;

AB = | `a`, AB, `b`;

C = | C, `c`;

A = | A, `a`;

BC = | `b`, BC, `c`;

Languages like this are called inherently ambiguous. They are all

likely to have this kind of flavour, because the problem arises from

the very limited ability of a push-down automaton to count.

In parser design, what tends to matter more than the theory is the

amount of effort involved in trying to find an unambiguous grammar for

awkward constructs that may or may not be inherently ambiguous

theoretically. In practice, it is typically acceptable to parse using

a grammar for a slightly larger language (in the above example the

language you get by dropping the numerical constraints) and then check

that the phrase you parsed belongs to the desired sublanguage after

parsing.

Rob.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.