2

I am trying to write a simple compiler using Flex for scanner and a special tool named PGen to define grammars.

Now, I am trying to solve unambiguous grammar for dangling else. I have searched for this.

This is a grammar with dangling else problem:

S → if E then S
  | if E then S else S
  | OTHER

This is a grammar that solves this problem (via slides from Berkeley):

S → MIF            /* all then are matched */
  | UIF            /* some then are unmatched */
MIF → if E then MIF else MIF
    | OTHER
UIF → if E then S
    | if E then MIF else UIF

But this grammar is still not LL1 and is still ambiguous.

When I tried to solve this ambiguity and make it LL1, I faced the dangling else problem again.

Can anyone please help me find an unambiguous LL1 grammar for nested if?

I have read in a Q&A on Stack Overflow that this grammar can't become LL1. But I can't realize how I can solve this ambiguity.

Palec
  • 12,743
  • 8
  • 69
  • 138
Linda
  • 251
  • 1
  • 6
  • 16
  • The grammar with MIF and UIF is unambiguous. What makes you think otherwise? However, it is certainly not LL(1) and I seriously doubt that an LL(1) grammar exists for the language. (That's what Aho, Sethi & Ullman say, so it must be true :) ). As they point out, it is easy enough to parse, even though it is ambiguous. But that doesn't help you generate a parser with an LL(1) tool. Why don't you use an LALR(1) tool such as bison? – rici Apr 23 '15 at 01:33
  • @rici thanks for your comment dear. It's a project which should be done by a tool named PGen. It is developed by an Iranian professor and uses syntax graphs to make parser. what is LALR(1)? – Linda Apr 23 '15 at 05:41
  • http://en.wikipedia.org/wiki/LALR_parser LALR parsing can handle a different and more useful set of languages. If you need to use a specific tool, and that tool is LL(1), and it requires an unambiguous grammar, then I think you are out of luck. Although the language is easy to parse. You just need to always shift the `else` if there is one. – rici Apr 23 '15 at 05:45

0 Answers0