1

I'm writing a small parser to recognize a subset of Java and I've run into an issue that I believe is called the dangling else problem.

My grammar for matching if-else statements started off like this:

statement:
block |
emptystatement |
ifstatement |
whilestatement |
statementexpression SEMICOLON |
OUTPUT LPAREN addexprlist RPAREN SEMICOLON
;

ifstatement:
IF LPAREN conditionalexpr RPAREN statement |
IF LPAREN conditionalexpr RPAREN statement ELSE statement

But I was receiving shift/reduce errors and wanted to fix those without just silencing them like most recommend.

I've modified my grammar to this one, which got rid of the shift/reduce errors, but now, it's not parsing the else statements correctly.

ifstatement:
matched |
unmatched
;

matched:
IF LPAREN conditionalexpr RPAREN matched ELSE matched 
;

unmatched: 
IF LPAREN conditionalexpr RPAREN matched |
IF LPAREN conditionalexpr RPAREN unmatched |
IF LPAREN conditionalexpr RPAREN matched ELSE unmatched |
/* empty */
;

I've been stuck on this for days now and can't wrap my head around how to fix it.

Here's an example of something it should parse:

if( n <= 0 )
       output(x);
 else {  //breaks on this else statement
   while( i < 0 ) {
       x = input();
       sum = sum + x;
       ++i;
   }
Palec
  • 12,743
  • 8
  • 69
  • 138
momonkey
  • 41
  • 1
  • 7
  • That cannot be your entire grammar because it could not parse `if (n<=0) output(x);`. Your grammar requires either `if '(' conditional ')' matched` or `if '(' conditional ')' unmatched`, but `output(x);` is (presumably) an `statementexpression` and that is not in either `matched` nor `unmatched`, at least as shown in your question. "What am I doing wrong" questions are hard to answer if it is not possible do see "What I am doing". – rici Apr 14 '16 at 04:34
  • If you can get your S/R conflicts down to just the dangling-else ambiguity you are done, as *yacc* will process it correctly, i.e. as expected. – user207421 Apr 14 '16 at 05:19

0 Answers0