15 May 1998 22:33:53 -0400

Related articles |
---|

Ambiguity for subsets of CFL? csdayton+usenet@cs.uchicago.edu (Soren Dayton) (1998-05-12) |

Re: Ambiguity for subsets of CFL? torbenm@diku.dk (Torben Mogensen) (1998-05-15) |

From: | Torben Mogensen <torbenm@diku.dk> |

Newsgroups: | comp.compilers |

Date: | 15 May 1998 22:33:53 -0400 |

Organization: | Compilers Central |

Keywords: | theory |

Soren Dayton wrote:

*>I was wondering if there were any results (and then implementations)*

*>that given:*

*>*

*> some C a subset of CFL that includes the regular languages and*

*> some grammar G with suitable restrictions and L(G) in C,*

*>*

*>tells us whether or not G is ambiguous?*

*>*

*>That is, are there restrictions on C and the structure of G such that*

*>the question of G's ambiguity is decidable?*

*>*

*>And then, assuming that there are theorems of relevance to the question,*

*>are there any free and implemented parsers for grammars like these?*

There are various known restrictions to grammars that not only makes

the ambiguity question decidable, but actually guarantees

non-ambiguous grammars. The best known of these are LL(k) an LR(k)

grammars. For both of these, the easiest way to determine if a grammar

is in the requisite class is to make a parsetable for the parser

method in question. If the table is without conflicts, then the

grammar is non-ambiguous. However, a table with conflicts does not

imply that the grammar is ambiguous, only that it is not in the class

of grammars that the parsing method can handle unambiguously.

Torben Mogensen (torbenm@diku.dk)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.