antlrantlr3antlrworks

Antlr3 Non-recursive / leftfactorized grammar for expressions with a nice AST


I have defined the following production rules for expressions. The grammar is not allowed to have backtracking and k better or equal to 3. The current version seams to have some ambiguity, but I can't figure out where. I've removed the AST rules here, but the grammar is supposed to create a nice AST where operations are presented according to their priority as well as showing the left associativity of operations.

Antlr 3.2.1 with Antlerworks 1.5.1

disjunctionExpresion
    :   (conjunctionExpresion Disjunction conjunctionExpresion disjunctionExpresionDash) | conjunctionExpresion;

disjunctionExpresionDash
    :   (Disjunction conjunctionExpresion disjunctionExpresionDash) |;

conjunctionExpresion
    :   (relationalExpresion Conjunction relationalExpresion conjunctionExpresionDash) | relationalExpresion;

conjunctionExpresionDash
    :   (Conjunction relationalExpresion conjunctionExpresionDash)|;
    
relationalExpresion
    :   (addExpresion RelationalOperator addExpresion relationalExpresionDash) | addExpresion;

relationalExpresionDash
    :   (RelationalOperator addExpresion relationalExpresionDash)|;

addExpresion
    :   (multiExpresion addOperator multiExpresion addExpresionDash)| multiExpresion;
    
addExpresionDash
    :   (addOperator multiExpresion addExpresionDash)|;

multiExpresion
    :   (unaryExpresion MultiOperator unaryExpresion multiExpresionDash) | unaryExpresion;

multiExpresionDash
    :   (MultiOperator unaryExpresion multiExpresionDash) | ;   

unaryExpresion 
    :   (unaryOperator basicExpr)->^(unaryOperator basicExpr) | basicExpr -> basicExpr;

basicExpr
    :   Number | var basicExprDash  | ('(' expr ')')->expr;

basicExprDash
    :   'touches' var | ;

Solution

  • With @kaby76's hint of using EBNF and looking up example grammars, I have ended up with something similar to this C++ Antlr3 example. The Antrl3 Documentations for Tree construction was also very helpful.

    The "^" quick operator allowed me to create the desired AST.

    expr    :   disjunctionExpression;
    
    disjunctionExpression
        :   conjunctionExpression (Disjunction^ conjunctionExpression)*;
    
    /*equal to:
    disjunctionExpression
        :   (a=conjunctionExpression->$a) (o=Disjunction b=conjunctionExpression -> ^($o $disjunctionExpression $b) )*;
        
    */
    conjunctionExpression
        :   relationalExpression (Conjunction^ relationalExpression)*;
    
    relationalExpression
        :   additiveExpression (relationalOperator^ additiveExpression)*;
    
    additiveExpression
        :   multiExpression (addOperator^ multiExpression)*;
    
    multiExpression
        :   unaryExpression (multiOperator^ unaryExpression)*;
    
    unaryExpression
        :   (unaryOperator^)? basicExpr;
    
    basicExpr
    :   Number | var ('touches'^ var)? | '(' expr ')' -> expr;
    

    Which is actually the compact version of what I had before:

    expr    :   disjunctionExpresion;
    
    disjunctionExpresion
        :   conjunctionExpresion disjunctionExpresionDash;
    
    disjunctionExpresionDash
        :   (Disjunction conjunctionExpresion disjunctionExpresionDash) |;