15 Dec 2005 03:22:14 -0500

Related articles |
---|

[15 earlier articles] |

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

Re: detecting ambiguous grammars kenarose@earthlink.net (Ken Rose) (2001-03-31) |

Re: detecting ambiguous grammars vbdis@aol.com (2001-03-31) |

Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-04-04) |

Re: detecting ambiguous grammars world!bobduff@uunet.uu.net (Robert A Duff) (2001-04-10) |

Re: detecting ambiguous grammars ki3084lx@ecs.cmc.osaka-u.ac.jp (Le Harusada) (2005-12-15) |

From: | Le Harusada <ki3084lx@ecs.cmc.osaka-u.ac.jp> |

Newsgroups: | comp.compilers |

Date: | 15 Dec 2005 03:22:14 -0500 |

Organization: | Compilers Central |

Keywords: | parse |

Chris F Clark <cfc@world.std.com> wrote:

*> For the general class of CFLs, i.e. just an arbitrary grammar whose*

*> rules are not otherwise constrained, the answer is there is no*

*> algorithm to determine whether the grammar is ambiguous or*

*> unambiguous.*

*> [...]*

*> There are algorithms which can detect*

*> subsets on one class--e.g. find a set of grammars such that all*

*> grammars in the class are [un]ambiguous--but where there are grammars*

*> outside the class may still be either ambiguous or not.*

So; there may be a way for my algorithm to be right. I'm implementing

an algorithm that (completely) detect the grammars that is "NOT of ANY

LR(k)". This set is surely a subset of unambiguous grammar set.

I devide the CFG set into 3 subsets:

- LR(k): grammars for what, there exist a LR(k) parser with a definite k

- "Ambiguous CFG": CFGs with what, there exist string that can be

generated in more than one way

- LR(~): grammars that is neither LR(k) nor ambiguous CFG

To me, the last 2 classes "ambiguous CFG" and LR(~) are the same

because they both cannot be recognized in linear time. Thus, I just

have to check if a given grammar is LR(k) or not.

The idea for my algorithm is very simple that, if a grammar is LR(k),

all the conflicts MUST disapear after k lookaheads; otherwise, there

SHOULD(*) be a loop of lookaheads. So, the algorithm is simply to

generate lookaheads whenever a conflict is met, and then (the hardest

part is to) detect the lookahead loop.

*) I said "should" because I have not proved it yet, but I believe so!

However I want to be sure that, with my "weaker" classification of

CFG, the detection problem is solvable (in theory). I don't want to

waste my time into a theorically unsolvable problem.

Regards.

- Halsade -

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.