Ambiguous Grammar using antlr4

Question

I have a big problem generating my parser using antlr4.1 The grammar is composed by the following 2 files:

grammar Common;

identifierNum: hostId DOT observableId DOT method ':Num';
identifierString: hostId DOT observableId DOT method  ':String';


hostId: ID;
observableId: ID;
method: ID'('')';

MUL: '*';
DIV: '/'; 
ADD: '+';
SUB: '-';
DOT: '.';
MIN: '<';
MAX: '>';


ID: [a-zA-Z0-9]+;
STRING: '\''[a-zA-Z0-9]+ '\'';
DIGIT: [0-9]+ ;
DOUBLE: [0-9]* DOT [0-9]+ ;


WS: [ \n\t]+ -> skip;

and this file

grammar Expression;
import Common;

expression:     stringExpr                      # StringExpression
    |           numExpr                         # NumExpression
    ;     

stringExpr:     stringExpr ADD stringExpr   # Concat
    |           STRING                      # BaseStr 
    |           identifierString            # IdString     
    |           '(' stringExpr ')'          # ParensString
    ;

numExpr:    numExpr op=(MUL|DIV) numExpr                # MulDiv
    |       numExpr op=(ADD|SUB) numExpr                # AddSub
    |       DIGIT                                       # Int
    |       DOUBLE                                      # Double
    |       identifierNum                               # IdNum      
    |       '(' numExpr ')'                             # ParensNum 
    ;

I generated the visitors using the antlr Tool

antlr_grammars/Expression.g4 -o src/test -no-listener -visitor -package test.antlr_grammars

and I created this class

public class Visitor extends ExpressionBaseVisitor<Value> {

    @Override
    public Value visitIdentifierString(IdentifierStringContext ctx) {
        System.out.println("visit idString");
        String i = "aaa";
        return new Value(i);
    }

    @Override
    public Value visitIdentifierNum(IdentifierNumContext ctx) {
        System.out.println("visit identifierNum");
        System.out.println("visit " + ctx.getText());
        String i = "100";
        if (i.contains(".")){
            double value = Double.parseDouble(i);
            return new Value(value);
        }
        else {
            int value = Integer.parseInt(i);
            return new Value(value);
        }
    }


    @Override
    public Value visitNumExpression(NumExpressionContext ctx) {
        System.out.println("visit NumExpr");
        System.out.println("visit" + ctx.getText());
        return visit(ctx.numExpr());
    }

    @Override
    public Value visitStringExpression(StringExpressionContext ctx) {
        System.out.println("visit StringExpr");
        return visit(ctx.stringExpr());
    }

    @Override
    public Value visitDouble(DoubleContext ctx) {
        System.out.println("visit double");
        System.out.println("visit" + ctx.getText());
        String str = ctx.getText();
        double i = Double.parseDouble(str);
        return new Value(i);
    }

    @Override
    public Value visitInt(IntContext ctx) {
        System.out.println("visit Int");
        System.out.println("visit " + ctx.getText());
        String str = ctx.getText();
        Integer i = Integer.parseInt(str);
        return new Value(i);
    }

    @Override
    public Value visitBaseStr(BaseStrContext ctx) {
        System.out.println("visit baseString");
        String str = ctx.getText();
        return new Value(str);

    }

    @Override
    public Value visitAddSub(AddSubContext ctx) {
        System.out.println("visit addSub");
        System.out.println("visit" + ctx.getText());
        Value leftVal = visit(ctx.numExpr(0));
        Value rightVal = visit(ctx.numExpr(1));
        if (ctx.op.getType() == ExpressionParser.ADD) {
            if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "INT") {
                int left = visit(ctx.numExpr(0)).intVal();
                int right = visit(ctx.numExpr(1)).intVal();
                return new Value(left + right);
            } else if (leftVal.getType().toString() == "DOUBLE"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left + right);
            } else if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = (double) visit(ctx.numExpr(0)).intVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left + right);
            } else {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = (double) visit(ctx.numExpr(1)).intVal();
                return new Value(left + right);
            }
        } else {
            if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "INT") {
                int left = visit(ctx.numExpr(0)).intVal();
                int right = visit(ctx.numExpr(1)).intVal();
                return new Value(left - right);
            } else if (leftVal.getType().toString() == "DOUBLE"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left - right);
            } else if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = (double) visit(ctx.numExpr(0)).intVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left - right);
            } else {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = (double) visit(ctx.numExpr(1)).intVal();
                return new Value(left - right);
            }
        }
    }



    @Override
    public Value visitMulDiv(MulDivContext ctx) {
        System.out.println("visit MulDiv");
        System.out.println("visit" + ctx.getText());
        Value leftVal = visit(ctx.numExpr(0));
        Value rightVal = visit(ctx.numExpr(1));
        if (ctx.op.getType() == ExpressionParser.MUL) {
            if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "INT") {
                int left = visit(ctx.numExpr(0)).intVal();
                int right = visit(ctx.numExpr(1)).intVal();
                return new Value(left * right);
            } else if (leftVal.getType().toString() == "DOUBLE"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left * right);
            } else if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = (double) visit(ctx.numExpr(0)).intVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left * right);
            } else {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = (double) visit(ctx.numExpr(1)).intVal();
                return new Value(left * right);
            }
        } else {
            if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "INT") {
                int left = visit(ctx.numExpr(0)).intVal();
                int right = visit(ctx.numExpr(1)).intVal();
                return new Value(left / right);
            } else if (leftVal.getType().toString() == "DOUBLE"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left / right);
            } else if (leftVal.getType().toString() == "INT"
                    && rightVal.getType().toString() == "DOUBLE") {
                double left = (double) visit(ctx.numExpr(0)).intVal();
                double right = visit(ctx.numExpr(1)).doubleVal();
                return new Value(left / right);
            } else {
                double left = visit(ctx.numExpr(0)).doubleVal();
                double right = (double) visit(ctx.numExpr(1)).intVal();
                return new Value(left / right);
            }
        }
    }

    @Override
    public Value visitConcat(ConcatContext ctx) {
        System.out.println("visit Concat");
        String string1 = visit(ctx.stringExpr(0)).stringVal();
        String string2 = visit(ctx.stringExpr(1)).stringVal();
        return new Value(string1.concat(string2));
    }

    @Override
    public Value visitIdString(IdStringContext ctx) {
        return visit(ctx.identifierString());
    }

    @Override
    public Value visitIdNum(IdNumContext ctx) {
        System.out.println("visit idNum");
        System.out.println("visit " + ctx.getText());
        return visit(ctx.identifierNum());
    }

    @Override
    public Value visitParensString(ParensStringContext ctx) {
        System.out.println("visit parensString");
        return visit(ctx.stringExpr());
    }

    @Override
    public Value visitParensNum(ParensNumContext ctx) {
        System.out.println("visit parensNum");
        return visit(ctx.numExpr());
    }

}

The problem is that probably my grammar is ambiguos because if I write some operations I receive only the following message "no viable alternative at input..." In reality I found another way to solve this problem (adding :Num and :String to differentiate the different kind of input) but I want to use this kind of semantic.

My main is the following

  public static void main(String args[]) {
    String expr1 = "10" ;
    System.out.println("Result = " + parse(expr1));
  }

  private static final String parse(String expression) {
    ANTLRInputStream input = new ANTLRInputStream(expression);
    ExpressionLexer lexer = new ExpressionLexer(input);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    ExpressionParser testParser = new ExpressionParser(tokens);
    ParseTree parseTree = testParser.expression();
    Visitor visitor = new Visitor();
    return String.valueOf(visitor.visit(parseTree));
  }

}

I don't understand where is the mistake. Thanks for your help =)

Answer 1

There are a lot of things going wrong in your Java code:

leftVal.getType().toString() == "DOUBLE"

Never do string equality checks using ==!

Read this: How do I compare strings in Java?, and truly understand it.

But you shouldn't compare the strings to begin with. Compare the integer types instead:

leftVal.getType() == ExpressionParser.DOUBLE

And this makes little sense to me:

String i = "100";
if (i.contains(".")){ 
    ...

The fact that you get a no viable alternative message is because your input "10" is being tokenized as an ID. This is because the ID token matches only digits, just like the DIGIT rule:

ID: [a-zA-Z0-9]+;
...
DIGIT: [0-9]+ ;

and since ID is defined before DIGIT, it get precedence. Either include ID as an numExpr alternative, or let the ID token start with a letter:

ID: [a-zA-Z] [a-zA-Z0-9]*;