CODEWITHSUNDEEP
antlrantlr3antlrworks
Freddy
Freddy

Reputation: 472

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 | ;

Upvotes: 0

Views: 90

Answers (1)

Freddy
Freddy

Reputation: 472

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) |;

Upvotes: 0

Related Questions