Re: Ambiguities from Special-Case Productions

Cleo Saulnier <cleos@nb.sympatico-dot-ca.remove>
15 Sep 2005 01:50:25 -0400

          From comp.compilers

Related articles
Ambiguities from Special-Case Productions (Evangelos Drikos) (2005-09-14)
Re: Ambiguities from Special-Case Productions cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-09-15)
Re: Ambiguities from Special-Case Productions (Ivan Boldyrev) (2005-09-17)
Re: Ambiguities from Special-Case Productions (Hans-Peter Diettrich) (2005-09-17)
Re: Ambiguities from Special-Case Productions (Evangelos Drikos) (2005-09-22)
| List of all articles for this month |

From: Cleo Saulnier <cleos@nb.sympatico-dot-ca.remove>
Newsgroups: comp.compilers
Date: 15 Sep 2005 01:50:25 -0400
Organization: Aliant Internet
References: 05-09-049
Keywords: parse
Posted-Date: 15 Sep 2005 01:50:24 EDT

Evangelos Drikos wrote:
> Hi all,
> I need some help to figure out which parsers can process grammars like the
> one below.
> I found this grammar in a popular compilers book (Ambiguities from
> Special-Case Productions):
> E -> E sub E sup E
> E -> E sub E
> E -> E sup E
> E -> { E }
> E -> c
> I think according to this grammar the string "c sub c sup c" has three
> interpretations (3 parse trees).
> Which GLR Parser should I select to take all the correct interpretations of
> such a string?
> Any references of how such ambiguities are handled in a GLR or is it a
> simple & usual case for such a parser?
> Thanks in advance,
> Ev. Drikos

Well, I know this won't work with LL because of left-recursion, so with
LR parsers, you're left with the ever popular dangling else problem as
it's commonly known. I only see 2 parse tree, but it doesn't matter much.

As you may or may not know, in LR parsers and all it's variants, you
don't know what production you're on until there's a reduction. That's
what makes it a bottom up parser.

With "c sub c sup c", you'd get a possibility of these two production up
until after the second 'c'.

E -> E sub E sup E
E -> E sub E

Now comes the question, do we reduce to E with the second production, or
do we shift the next token and eventually reduce to the 1st production.
    This is what is called a shift/reduce conflict. Many LR parsers
automatically choose to shift in preference of reducing so that the
dangling else problem can be resolved. But it is a special
consideration of the grammar... not the normal way things are done.

Hope this explains some of it.

Oh, you wanted to know what kind of parsers can handle this grammar.
Look for a LR (or a variant like SLR or LALR whatever you're into) that
handles dangling else situations. All straight up LR (or variant)
parser will give you a shift/reduce conflict error.

E -> E sub E sup E
E -> E sup E

both end the same way... most LR parser will not like this. That's a
reduce/reduce conflict and won't work.


Post a followup to this message

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