Re: detecting ambiguous grammars

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 -

Return to the comp.compilers page.
Search the comp.compilers archives again.