Re: detecting ambiguous grammars

Le Harusada <ki3084lx@ecs.cmc.osaka-u.ac.jp>
15 Dec 2005 03:22:14 -0500

          From comp.compilers

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)
| List of all articles for this month |

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
Posted-Date: 15 Dec 2005 03:22:14 EST

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.