Re: Ambiguities from Special-Case Productions

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.


Also,
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.


Cheer

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