Java Jacc, AST и рекурсивный посетитель - PullRequest
Новая
       41

Java Jacc, AST и рекурсивный посетитель

0 голосов
/ 19 марта 2019

Я пытаюсь сделать простой калькулятор, используя 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?Я неправильно понимаю модель посетителей?Приведение к конкретным типам кажется уродливым и неправильным.

1 Ответ

1 голос
/ 19 марта 2019

Как уже упоминалось в моем комментарии в 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, а не класс.

Таким образом вы можете избавиться от метода посещения, где вы проверяете и приводите свои объекты.

Кстати, он должен работать с перегрузкой метода какхорошо, но я думаю, что размещение кода рядом с правильным классом намного эффективнее с точки зрения проектирования.

Если вы хотите добавить новый тип узлов, вам просто нужно реализовать соответствующий класс и иметьЕсли парсер знает о таких узлах, остальная часть программы должна оставаться нетронутой.

...