|[15 earlier articles]|
|Re: detecting ambiguous grammars firstname.lastname@example.org (Thant Tessman) (2001-03-31)|
|Re: detecting ambiguous grammars email@example.com (Chris F Clark) (2001-03-31)|
|Re: detecting ambiguous grammars firstname.lastname@example.org (Ken Rose) (2001-03-31)|
|Re: detecting ambiguous grammars email@example.com (2001-03-31)|
|Re: detecting ambiguous grammars firstname.lastname@example.org (Joachim Durchholz) (2001-04-04)|
|Re: detecting ambiguous grammars email@example.com (Robert A Duff) (2001-04-10)|
|Re: detecting ambiguous grammars firstname.lastname@example.org (Le Harusada) (2005-12-15)|
|From:||Le Harusada <email@example.com>|
|Date:||15 Dec 2005 03:22:14 -0500|
Chris F Clark <firstname.lastname@example.org> 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
> 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.
- Halsade -
Return to the
Search the comp.compilers archives again.