0

I wrote a grammar in ANTLR for a Java-like if statement as follows:

if_statement
    :   'if' expression
        (statement | '{' statement+ '}')
        ('elif' expression (statement | '{' statement+ '}'))*
        ('else' (statement | '{' statement+ '}'))?
    ;

I've implemented the "statement" and "expression" correctly, but the if_statement is giving me the following error:

Decision can match input such as "'elif'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
 |---> ('elif' expression (statement | '{' statement+ '}'))*

warning(200): /OptDB/src/OptDB/XL.g:38:9: 
Decision can match input such as "'else'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
 |---> ('else' (statement | '{' statement+ '}'))?

It seems like there are problems with the "elif" and "else" block. Basically, we can have 0 or more "elif" blocks, so I wrapped them with * Also we can have 0 or 1 "else" block, so I wrapped it it with ?.

What seems to cause the error?



========================================================================

I'll also put the implementations of "expression" and "statements":

statement
    :   assignment_statement
    |   if_statement
    |   while_statement
    |   for_statement
    |   function_call_statement
    ;


term
    :   IDENTIFIER
    |   '(' expression ')'
    |   INTEGER
    |   STRING_LITERAL
    |   CHAR_LITERAL
    |   IDENTIFIER '(' actualParameters ')'
    ;

negation
    :   'not'* term
    ;

unary
    :   ('+' | '-')* negation
    ;

mult
    :   unary (('*' | '/' | 'mod') unary)*
    ;

add
    :   mult (('+' | '-') mult)*
    ;

relation
    :   add (('=' | '/=' | '<' | '<=' | '>=' | '>') add)*
    ;

expression
    :   relation (('and' | 'or') relation)*
    ;

actualParameters
    :   expression (',' expression)*
    ;
user2436815
  • 3,455
  • 5
  • 27
  • 40

1 Answers1

2

Because your grammar allows for statement block without being grouped by {...}, you've got yourself a classic dangling else ambiguity.

Short explanation. The input:

if expr1 if expr2 ... else ...

could be parsed as:

Parse 1

if expr1
    if expr2
        ...
    else
        ...

but also as this:

Parse 2

if expr1
    if expr2
        ...
else
    ...

To eliminate the ambiguity, either change:

(statement | '{' statement+ '}')

into:

'{' statement+ '}'
// or
'{' statement* '}'

so that it's clear by looking at the braces to which if the else belongs to, or add a predicate to force the parser to choose Parse 1:

if_statement
 : 'if' expression statement_block
   (('elif')=> 'elif' expression statement_block)*
   (('else')=> 'else' statement_block)?
 ;

statement_block
 : '{' statement* '}'
 | statement
 ;
Community
  • 1
  • 1
Bart Kiers
  • 166,582
  • 36
  • 299
  • 288
  • +1: classic problem, classic solution, excellent answer including canonical reference. I wish I could add something. – david.pfx Apr 10 '14 at 14:51
  • The 3rd solution is using something like the `NoShortIf` rules present in the Java Language Specification, shown [here in Chapter 19](http://docs.oracle.com/javase/specs/jls/se8/html/jls-19.html) (search for rules ending with `NoShortIf`). – Sam Harwell Apr 10 '14 at 19:05