Java Jacc，AST和递归访问者

Question

我正在尝试使用Jacc(解析器生成器)制作一个简单的计算器。我首先需要创建一个 AST 并访问它的节点以制作它的 Graphviz 图，然后对其进行评估。

在我的 Jacc 文件中，我不能使用优先级指令，所以我创建了一个左递归语法：

%{
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());
}

Value生产可以是DoubleLiteral也可以是AddExpr以适应括号表达式，因此我创建了一个名为Expr的接口，使所有 AST 类"实现"它：

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)
{
}
}

因此，在我的访客中，我需要从Expr类转换为具体类：

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 += "Calcn";
calc.accept(this);
}
public void visit(AddExpr expr)
{
output += "AddExprn";
expr.accept(this);
}
public void visit(ModExpr expr)
{
output += "ModExprn";
expr.accept(this);
}
public void visit(IntDivExpr expr)
{
output += "IntDivExprn";
expr.accept(this);
}
public void visit(MultExpr expr)
{
output += "MultExprn";
expr.accept(this);
}
public void visit(UnaryExpr expr)
{
output += "UnaryExprn";
expr.accept(this);
}
public void visit(ExpExpr expr)
{
output += "ExpExprn";
expr.accept(this);
}
public void visit(Value value)
{
output += "Valuen";
value.accept(this);
}
public void visit(DoubleLiteral literal)
{
output += "DoubleLiteral: " + literal.getValue().toString() + "n";
}
}

我是否以错误的方式构建我的 AST？我是否误解了访客模式？浇筑到混凝土类型似乎丑陋而错误。

Answer 1

正如我在 Java 中的评论中提到的，类可以实现多个接口，因此您也可以VisitorExpr类。

这样，您现在可以将所有方法移动到DotVisitor类的专用节点内。

请看以下内容作为示例：

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 += "Calcn";
calc.accept(this);
}
}

请注意，现在访问参数calc是一个Expr而不是类。

这样做可以摆脱检查和投射对象的访问方法。

顺便说一下，它也应该与方法重载一起使用，但我认为从设计的角度来看，将代码放在适当的类附近更有效。

如果你想添加新类型的节点，你只需要实现正确的类，并让解析器知道这些节点，程序的其他部分应该保持不变。