Re: [Compilers] grammars

Buddy wrote:
>
> Can all ambiguous grammars be changed into unambiguous grammars?
>
> [Well, sure, you can delete stuff until it's not ambiguous any more.
> But I presume the question you're asking is whether there's always an
> unambiguous grammar that recognizes the same language as an ambigous
> one. -John]


The hard problem is to know if a grammar is ambiguous in the first
place. In general, this is undecidable. As a consequence, in general,
there cannot be any algorithm which takes a possibly ambiguous grammar
and returns a necessarily unambiguous grammar that generates the same
language. A grammar which falls into LALR(1) or most other grammar
classes is unambiguous just because of the grammar class
restriction. So one practical way to go is to try to enforce a
reasonable grammar class condition. But this is maybe not what you
want. Then you can still try to find parts of the grammar that cause
ambiguities and then apply grammar refactoring [1] to improve on that.


In general, refactoring is also the way to go when a grammar class
must be established. Grammar refactoring including an example
disambiguation is exercised a bit in [2]. Then, still there is the
problem how you would actually spot those parts of the grammar that
cause ambiguities. Let us then make the assumption that we are using
a general parsing algorithm such as top-down infinite look-ahead or
generalised LR. Then you can find problematic parts in these ways. a)
You just parse code you have around, and you see if any ambiguities
show up. Then you look at the relevant grammar portions. b) You
generate large test sets [3,4] and fall back to a). c) You try
something like LR(k) with a larger k just to find areas with
conflicts. Getting rid of them and making k smaller will solve the
problem too.


Engineeringwise this is not completely established and worked out.
Something like this is indeed mentioned in our grammarware agenda [5].
Comments welcome on all the referenced material.


Regards,
Ralf


[1] Grammar Adaptation
        http://homepages.cwi.nl/~ralf/fme01/


[2] Semi-automatic Grammar Recovery
        http://www.cs.vu.nl/grammars/ge.html


[3] Grammar Testing
        http://homepages.cwi.nl/~ralf/fase01/


[4] Test case characterisation by regular path expressions
        http://homepages.cwi.nl/~ralf/fates01/


[5] Towards an engineering discipline for grammarware (Draft)
        http://www.cs.vu.nl/grammarware/agenda/


--
Ralf Laemmel
VU & CWI, Amsterdam, The Netherlands
http://www.cs.vu.nl/~ralf/
http://www.cwi.nl/~ralf/

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