I am trying to make a simple calculator using Jacc (a parser generator). I first need to create an AST and visit its nodes to make a Graphviz graph of it and later evaluate it.
In my Jacc file I can't use precedence directives so I created a left recursive grammar:
%{
import java.io.*;
import java.lang.Math;
%}
%class Parser
%interface ParserTokens
%semantic Expr
%token DOUBLE DIV MOD
%%
Calc : /* empty */
| AddExpr { ast = new Calc($1); }
;
AddExpr : ModExpr
| AddExpr '+' ModExpr { $$ = new AddExpr($1, $3, "+"); }
| AddExpr '-' ModExpr { $$ = new AddExpr($1, $3, "-"); }
;
ModExpr : IntDivExpr
| ModExpr MOD IntDivExpr { $$ = new ModExpr($1, $3); }
;
IntDivExpr : MultExpr
| IntDivExpr DIV MultExpr { $$ = new IntDivExpr($1, $3); }
;
MultExpr : UnaryExpr
| MultExpr '*' UnaryExpr { $$ = new MultExpr($1, $3, "*"); }
| MultExpr '/' UnaryExpr { $$ = new MultExpr($1, $3, "/"); }
;
UnaryExpr : ExpExpr
| '-' UnaryExpr { $$ = new UnaryExpr($2, "-"); }
| '+' UnaryExpr { $$ = new UnaryExpr($2, "+"); }
;
ExpExpr : Value
| ExpExpr '^' Value { $$ = new ExpExpr($1, $3); }
;
Value : DoubleLiteral
| '(' AddExpr ')' { $$ = new Value($2); }
;
DoubleLiteral : DOUBLE { $$ = $1; }
;
%%
public Calc ast;
private Lexer lexer;
public Parser(Reader reader)
{
lexer = new Lexer(reader);
}
public void yyerror(String error)
{
System.err.println("Error: " + error);
}
public static void main(String args[])
{
System.out.println("Interactive evaluation:");
Parser parser = new Parser(
new InputStreamReader(System.in));
DotVisitor visitor = new DotVisitor();
parser.lexer.nextToken();
parser.parse();
visitor.visit(parser.ast);
System.out.println(visitor.getOutput());
}
The Value production can be either a DoubleLiteral or an AddExpr to accommodate for parenthesized expressions so I created an interface called Expr making all AST classes 'implement' it:
interface Expr
{
public void accept(DotVisitor visitor);
}
abstract class BinExpr implements Expr
{
protected Expr left;
protected Expr right;
protected String op;
public Expr getLeft()
{
return left;
}
public Expr getRight()
{
return right;
}
public String getOp()
{
return op;
}
BinExpr(Expr left, Expr right, String op)
{
this.left = left;
this.right = right;
this.op = op;
}
public void accept(DotVisitor visitor)
{
visitor.visit(left);
visitor.visit(right);
}
}
class Calc implements Expr
{
Expr ast;
public Expr getAst()
{
return ast;
}
Calc(Expr ast)
{
this.ast = ast;
}
public void accept(DotVisitor visitor)
{
visitor.visit(ast);
}
}
class AddExpr extends BinExpr
{
AddExpr(Expr left, Expr right, String op)
{
super(left, right, op);
}
}
class ModExpr extends BinExpr
{
ModExpr(Expr left, Expr right)
{
super(left, right, "Mod");
}
}
class IntDivExpr extends BinExpr
{
IntDivExpr(Expr left, Expr right)
{
super(left, right, "IntDiv");
}
}
class MultExpr extends BinExpr
{
MultExpr(Expr left, Expr right, String op)
{
super(left, right, op);
}
}
class UnaryExpr implements Expr
{
private Expr value;
private String sign;
public Expr getValue()
{
return value;
}
UnaryExpr(Expr value, String sign)
{
this.value = value;
this.sign = sign;
}
public void accept(DotVisitor visitor)
{
visitor.visit(value);
}
}
class ExpExpr extends BinExpr
{
ExpExpr(Expr left, Expr right)
{
super(left, right, "^");
}
}
class Value implements Expr
{
private Expr literal;
private Expr getLiteral()
{
return literal;
}
Value(Expr literal)
{
this.literal = literal;
}
public void accept(DotVisitor visitor)
{
visitor.visit(literal);
}
}
class DoubleLiteral implements Expr
{
private String value;
public String getValue()
{
return value;
}
DoubleLiteral(String value)
{
this.value = value;
}
public void accept(DotVisitor visitor)
{
}
}
Because of this in my Visitor I needed to cast from Expr to concrete classes:
public class DotVisitor implements Visitor
{
private String output = "";
public String getOutput()
{
return output;
}
public void visit(Expr expr)
{
if(expr instanceof AddExpr)
{
visit((AddExpr) expr);
}
else if (expr instanceof MultExpr)
{
visit((MultExpr) expr);
}
else if (expr instanceof DoubleLiteral)
{
visit((DoubleLiteral) expr);
}
// ...
}
public void visit(Calc calc)
{
output += "Calc\n";
calc.accept(this);
}
public void visit(AddExpr expr)
{
output += "AddExpr\n";
expr.accept(this);
}
public void visit(ModExpr expr)
{
output += "ModExpr\n";
expr.accept(this);
}
public void visit(IntDivExpr expr)
{
output += "IntDivExpr\n";
expr.accept(this);
}
public void visit(MultExpr expr)
{
output += "MultExpr\n";
expr.accept(this);
}
public void visit(UnaryExpr expr)
{
output += "UnaryExpr\n";
expr.accept(this);
}
public void visit(ExpExpr expr)
{
output += "ExpExpr\n";
expr.accept(this);
}
public void visit(Value value)
{
output += "Value\n";
value.accept(this);
}
public void visit(DoubleLiteral literal)
{
output += "DoubleLiteral: " + literal.getValue().toString() + "\n";
}
}
Am I building my AST the wrong way? Am I misunderstanding the visitor pattern? Casting to concrete types seems ugly and wrong.
As mentioned in my comment in Java a class can implements multiple interfaces, so you can have your Expr classes to be Visitor too.
Doing so, you can move all methods now in the DotVisitor class, inside the specialized node.
Please have a look at the following as an example:
class Calc implements Expr, Visitor
{
Expr ast;
public Expr getAst()
{
return ast;
}
Calc(Expr ast)
{
this.ast = ast;
}
public void accept(DotVisitor visitor)
{
visitor.visit(ast);
}
public void visit(Expr calc)
{
output += "Calc\n";
calc.accept(this);
}
}
Notice that now the visit parameter calc is an Expr and not the class.
Doing so you can get rid of the visit method where you check and cast your objects.
By the way it should work with the method overloading as well, but I think putting the code near the proper class is much more effective by a design point of view.
If you want to add new kind of nodes you just need to implement the proper class, and have the parser to know about such nodes, the other part of the program should stay untouched.