Re: Detection of ambiguous grammar

ulf.schwekendiek@googlemail.com <ulf.schwekendiek@googlemail.com> wrote:
> Hello,
>
> I am thinking of a special case in GLR parsing. I am wondering whether
> it is possible to check if a grammar is ambiguous. For example if I am
> using GNU Bison as a parser generator it detects Shift-Reduce and
> Reduce-Reduce conflict, however with the GLR feature it is possible to
> parse most of the grammars. Now a special case could happen: More than
> one parsing stack at the end is still alive and Bison would execute by
> default the different semantic action stacks. However the Bison manual
> states that the programmer can provide a special "merge" function
> which resolves from this problem. I want to ask you if there is any
> algorithm that can check if such case can happen for a given grammar
> or not.


This is an undecidable problem, so there is no algorithm that can
always tell whether a given grammar is ambiguous or not.


However, you can compute conservative approximmations to ambiguity.
Building the LR table and looking for conflicts is one way. Another
way is described in the paper "Analyzing Ambiguity of Context-Free
Grammars", by Claus Brabrand, Robert Giegerich, and Olivier Danvy.


    <http://www.brics.dk/RS/07/10/BRICS-RS-07-10.pdf>








--
Neel R. Krishnaswami
neelk@cs.cmu.edu

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