Java Jacc，AST和递归访问者

问题描述 投票：0回答：1

我正在尝试使用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 += "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";
    }
}

我是以错误的方式构建我的AST吗？我误解了访客模式吗？铸造到混凝土类型似乎是丑陋和错误的。

java parsing abstract-syntax-tree parser-generator visitor-pattern
1个回答
1
投票

正如我在Java中的注释中提到的，类可以实现多个接口，因此您可以将Expr类设置为Visitor。

这样，您可以在专用节点内的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 += "Calc\n";
        calc.accept(this);
    }
}

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

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

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

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.