How to resolve "The following alternatives can never be matched"

Question

I have been struggling to resolve a "multiple alternatives" error in my parser for a couple of days now but with no success. I have been converting Bart Kiers excellent Tiny Language(TL) tutorial code to C# using Sam Harwell's port of ANTLR3 and VS2010. Kudos to both these guys for their excellent work. I believe I have followed Bart's tutorial accurately but as I am a newbie with ANTLR I can't be sure.

I did have the TL code working nicely on a pure math basis i.e. no "functions" or "if then else" or "while" (see screenshot of a little app)

but when I added the code for the missing pieces to complete the tutorial I get a parsing error in "functionCall" and in "list" (see the code below)

grammar Paralex2;

options {
    language=CSharp3;
    TokenLabelType=CommonToken;
    output=AST;
    ASTLabelType=CommonTree;
}

tokens {
  BLOCK;
  RETURN;
  STATEMENTS;
  ASSIGNMENT;
  FUNC_CALL;
  EXP;
  EXP_LIST;
  ID_LIST;
  IF;
  TERNARY;
  U_SUB;
  NEGATE;
  FUNCTION;
  INDEXES;
  LIST;
  LOOKUP;
}

@lexer::namespace{Paralex2}
@parser::namespace{Paralex2}

/*
 * Parser Rules
 */

@parser::header {using System; using System.Collections.Generic;}

@parser::members{

public SortedList<string, Function> functions = new SortedList<string, Function>();

  private void defineFunction(string id, Object idList, Object block) {

    // `idList` is possibly null! Create an empty tree in that case. 
    CommonTree idListTree = idList == null ? new CommonTree() : (CommonTree)idList;

    // `block` is never null.
    CommonTree blockTree = (CommonTree)block;

    // The function name with the number of parameters after it the unique key
    string key = id + idListTree.Children.Count();
    functions.Add(key, new Function(id, idListTree, blockTree));
  }

}

public parse
  :  block EOF -> block
  ;

block
  :  (statement | functionDecl)* (Return exp ';')?  -> ^(BLOCK ^(STATEMENTS statement*) ^(RETURN exp?))
  ;

statement
  :  assignment ';'   -> assignment
  |  functionCall ';' -> functionCall
  |  ifStatement
  |  forStatement
  |  whileStatement
  ;

assignment
  :  Identifier indexes? '=' exp 
     -> ^(ASSIGNMENT Identifier indexes? exp)
  ;

functionCall
  :  Identifier '(' expList? ')' -> ^(FUNC_CALL Identifier expList?)
  |  Assert '(' exp ')'    -> ^(FUNC_CALL Assert exp)
  |  Size '(' exp ')'      -> ^(FUNC_CALL Size exp)
  ;

ifStatement
  :  ifStat elseIfStat* elseStat? End -> ^(IF ifStat elseIfStat* elseStat?)
  ;

ifStat
  :  If exp Do block -> ^(EXP exp block)
  ;

elseIfStat
  :  Else If exp Do block -> ^(EXP exp block)
  ;

elseStat
  :  Else Do block -> ^(EXP block)
  ;

functionDecl
  :  Def Identifier '(' idList? ')' block End 
     {defineFunction($Identifier.text, $idList.tree, $block.tree);}
  ;

forStatement
  :  For Identifier '=' exp To exp Do block End 
     -> ^(For Identifier exp exp block)
  ;

whileStatement
  :  While exp Do block End -> ^(While exp block)
  ;

idList
  :  Identifier (',' Identifier)* -> ^(ID_LIST Identifier+)
  ;


expList
  :  exp (',' exp)* -> ^(EXP_LIST exp+)
  ;

exp 
  :  condExp  
  ;  

condExp  
  :  (orExp -> orExp)   
  |  ( '?' a=exp ':' b=exp -> ^(TERNARY orExp $a $b)
  |  In exp         -> ^(In orExp exp)
  )?  
  ;  

orExp  
  :  andExp ('||'^ andExp)*  
  ;  

andExp  
  :  equExp ('&&'^ equExp)*  
  ;  

equExp  
  :  relExp (('==' | '!=')^ relExp)*  
  ;  

relExp  
  :  addExp (('>=' | '<=' | '>' | '<')^ addExp)*  
  ;

addExp
  :  mulExp ((Add | Sub)^ mulExp)*
  ;

mulExp
  :  powExp ((Mul | Div)^ powExp)*
  ;

powExp  
  :  unaryExp ('^'^ unaryExp)*  
  ;

unaryExp
  :  Sub atom -> ^(U_SUB atom)
  | '!' atom -> ^(NEGATE atom)
  |  atom
  ;

atom
  :  Nmber
  |  Bool
  |  Null
  |  lookup
  ;

list
  :  '[' expList? ']' -> ^(LIST expList?)
  ;

lookup
  :  list indexes?              -> ^(LOOKUP list indexes?)
  |  functionCall indexes?      -> ^(LOOKUP functionCall indexes?)
  |  Identifier indexes?        -> ^(LOOKUP Identifier indexes?)
  |  String indexes?            -> ^(LOOKUP String indexes?)
  |  '(' exp ')' indexes?       -> ^(LOOKUP exp indexes?)
  ;

indexes
  :  ('[' exp ']')+ -> ^(INDEXES exp+)
  ;


/*
 * Lexer Rules
 */

Assert      : 'assert';
Size        : 'size';
Def         : 'def';
If          : 'if';
Else        : 'else';
Return      : 'return';
For         : 'for';
While       : 'while';
To          : 'to';
Do          : 'do';
End         : 'end';
In          : 'in';
Null        : 'null';

Or          : '||';  
And         : '&&';  
Equals      : '==';  
NEquals     : '!=';  
GTEquals    : '>=';  
LTEquals    : '<=';  
Pow         : '^';  
GT          : '>';  
LT          : '<';
Add         : '+';
Sub         : '-';
Mul         : '*';
Div         : '/';
Modulus     : '%';
OBrace      : '{';
CBrace      : '}';
OBracket    : '[';
CBracket    : ']';
OParen      : '(';
CParen      : ')';
SColon      : ';';
Assign      : '=';
Comma       : ',';
QMark       : '?';
Colon       : ':';

Bool
    :   'true'
    |   'false'
    ;

Nmber
    : Int ('.' Digit*)?
    ;

Identifier
  :  ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | Digit)*
  ;

String
@after {
  setText(getText().substring(1, getText().length()-1).replaceAll("\\\\(.)", "$1"));
}
  :  '"'  (~('"' | '\\')  | '\\' ('\\' | '"'))* '"' 
  |  '\'' (~('\'' | '\\') | '\\' ('\\' | '\''))* '\''
  ;

Comment
  :  '//' ~('\r' | '\n')* {Skip();}
  |  '/*' .* '*/'         {Skip();}
  ;

 Space
  :  (' ' | '\t' | '\r' | '\n' | '\u000C') {Skip();}
  ;

fragment Int  
  :  '1'..'9' Digit*  
  |  '0'  
  ;  

fragment Digit   
  :  '0'..'9'  
  ;

The error messages I get are

Decision can match input such as "CParen" using multiple alternatives: 1, 2 : Line 79:20

and

Decision can match input such as "CBracket" using multiple alternatives: 1, 2 : Line 176:10

The errors relate to the functionCall and list rules. I have examined the parser file in ANTLRWorks 1.5 and confirmed the same errors there. The syntax diagrams for the two rules look like this;

and this;

I have tried several changes to try to solve the problem but I don't seem to be able to get the syntax right. I would appreciate any help you guys could provide and can email the images if that would help.

Thanks in advance Ian Carson

Answer 1

You have an OR-operator too many in the condExp rule making the grammar ambiguous.

You have:

condExp  
  :  ( orExp               -> orExp)   
  |  ( '?' a=exp ':' b=exp -> ^(TERNARY orExp $a $b)
     |  In exp             -> ^(In orExp exp)
     )?  
  ;  

corresponding to:

But it should be:

condExp  
  :  ( orExp               -> orExp)
     ( '?' a=exp ':' b=exp -> ^(TERNARY orExp $a $b)
     |  In exp             -> ^(In orExp exp)
     )?  
  ;  

corresponding to: