Re: Detection of ambiguous grammar

Neelakantan Krishnaswami <neelk@cs.cmu.edu>
Mon, 20 Aug 2007 05:48:01 +0000 (UTC)

          From comp.compilers

Related articles
Detection of ambiguous grammar ulf.schwekendiek@googlemail.com (ulf.schwekendiek@googlemail.com) (2007-08-18)
Re: Detection of ambiguous grammar neelk@cs.cmu.edu (Neelakantan Krishnaswami) (2007-08-20)
Re: Detection of ambiguous grammar torbenm@app-2.diku.dk (2007-08-20)
Re: Detection of ambiguous grammar idbaxter@semdesigns.com (2007-08-24)
| List of all articles for this month |

From: Neelakantan Krishnaswami <neelk@cs.cmu.edu>
Newsgroups: comp.compilers
Date: Mon, 20 Aug 2007 05:48:01 +0000 (UTC)
Organization: Carnegie Mellon Univ. -- Computer Science Dept.
References: 07-08-052
Keywords: parse
Posted-Date: 20 Aug 2007 09:49:04 EDT

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



Post a followup to this message

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