Ответ 1

Хорошо, пусть построит простой пример математики. Построение АСТ полностью переборщило с такой задачей, но это хороший способ показать принцип.

Я сделаю это на С#, но версия Java будет очень похожа.

Грамматика

Во-первых, напишите очень основную математическую грамматику для работы с:

grammar Math;

compileUnit
    :   expr EOF
    ;

expr
    :   '(' expr ')'                         # parensExpr
    |   op=('+'|'-') expr                    # unaryExpr
    |   left=expr op=('*'|'/') right=expr    # infixExpr
    |   left=expr op=('+'|'-') right=expr    # infixExpr
    |   func=ID '(' expr ')'                 # funcExpr
    |   value=NUM                            # numberExpr
    ;

OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';

NUM :   [0-9]+ ('.' [0-9]+)? ([eE] [+-]? [0-9]+)?;
ID  :   [a-zA-Z]+;
WS  :   [ \t\r\n] -> channel(HIDDEN);

Довольно простой материал, у нас есть одно правило expr, которое обрабатывает все (правила приоритета и т.д.).

Узлы AST

Затем определим некоторые AST-узлы, которые мы будем использовать. Они полностью настраиваются, и вы можете определить их так, как вы хотите.

Вот узлы, которые мы будем использовать для этого примера:

internal abstract class ExpressionNode
{
}

internal abstract class InfixExpressionNode : ExpressionNode
{
    public ExpressionNode Left { get; set; }
    public ExpressionNode Right { get; set; }
}

internal class AdditionNode : InfixExpressionNode
{
}

internal class SubtractionNode : InfixExpressionNode
{
}

internal class MultiplicationNode : InfixExpressionNode
{
}

internal class DivisionNode : InfixExpressionNode
{
}

internal class NegateNode : ExpressionNode
{
    public ExpressionNode InnerNode { get; set; }
}

internal class FunctionNode : ExpressionNode
{
    public Func<double, double> Function { get; set; }
    public ExpressionNode Argument { get; set; }
}

internal class NumberNode : ExpressionNode
{
    public double Value { get; set; }
}

Преобразование CST в AST

ANTLR создал для нас узлы CST (классы MathParser.*Context). Теперь нам нужно преобразовать их в узлы AST.

Это легко сделать с посетителем, и ANTLR предоставляет нам класс MathBaseVisitor<T>, поэтому давайте работать с ним.

internal class BuildAstVisitor : MathBaseVisitor<ExpressionNode>
{
    public override ExpressionNode VisitCompileUnit(MathParser.CompileUnitContext context)
    {
        return Visit(context.expr());
    }

    public override ExpressionNode VisitNumberExpr(MathParser.NumberExprContext context)
    {
        return new NumberNode
        {
            Value = double.Parse(context.value.Text, NumberStyles.AllowDecimalPoint | NumberStyles.AllowExponent)
        };
    }

    public override ExpressionNode VisitParensExpr(MathParser.ParensExprContext context)
    {
        return Visit(context.expr());
    }

    public override ExpressionNode VisitInfixExpr(MathParser.InfixExprContext context)
    {
        InfixExpressionNode node;

        switch (context.op.Type)
        {
            case MathLexer.OP_ADD:
                node = new AdditionNode();
                break;

            case MathLexer.OP_SUB:
                node = new SubtractionNode();
                break;

            case MathLexer.OP_MUL:
                node = new MultiplicationNode();
                break;

            case MathLexer.OP_DIV:
                node = new DivisionNode();
                break;

            default:
                throw new NotSupportedException();
        }

        node.Left = Visit(context.left);
        node.Right = Visit(context.right);

        return node;
    }

    public override ExpressionNode VisitUnaryExpr(MathParser.UnaryExprContext context)
    {
        switch (context.op.Type)
        {
            case MathLexer.OP_ADD:
                return Visit(context.expr());

            case MathLexer.OP_SUB:
                return new NegateNode
                {
                    InnerNode = Visit(context.expr())
                };

            default:
                throw new NotSupportedException();
        }
    }

    public override ExpressionNode VisitFuncExpr(MathParser.FuncExprContext context)
    {
        var functionName = context.func.Text;

        var func = typeof(Math)
            .GetMethods(BindingFlags.Public | BindingFlags.Static)
            .Where(m => m.ReturnType == typeof(double))
            .Where(m => m.GetParameters().Select(p => p.ParameterType).SequenceEqual(new[] { typeof(double) }))
            .FirstOrDefault(m => m.Name.Equals(functionName, StringComparison.OrdinalIgnoreCase));

        if (func == null)
            throw new NotSupportedException(string.Format("Function {0} is not supported", functionName));

        return new FunctionNode
        {
            Function = (Func<double, double>)func.CreateDelegate(typeof(Func<double, double>)),
            Argument = Visit(context.expr())
        };
    }
}

Как вы можете видеть, это просто вопрос создания AST node из CST node с помощью посетителя. Код должен быть довольно понятным (ну, может быть, за исключением материала VisitFuncExpr, но это просто быстрый способ подключить делегат к подходящему методу System.Math).

И здесь у вас есть строительный материал AST. Это все, что нужно. Просто извлеките соответствующую информацию из КНТ и сохраните ее в АСТ.

Посетитель AST

Теперь давайте немного поиграем с АСТ. Нам нужно создать базовый класс посетителя AST, чтобы пройти его. Позвольте просто сделать что-то похожее на AbstractParseTreeVisitor<T>, предоставленное ANTLR.

internal abstract class AstVisitor<T>
{
    public abstract T Visit(AdditionNode node);
    public abstract T Visit(SubtractionNode node);
    public abstract T Visit(MultiplicationNode node);
    public abstract T Visit(DivisionNode node);
    public abstract T Visit(NegateNode node);
    public abstract T Visit(FunctionNode node);
    public abstract T Visit(NumberNode node);

    public T Visit(ExpressionNode node)
    {
        return Visit((dynamic)node);
    }
}

Здесь я использовал ключевое слово С# dynamic, чтобы выполнить двойную отправку в одной строке кода. В Java вам нужно будет сделать проводку самостоятельно с помощью следующих выражений if:

if (node is AdditionNode) {
    return Visit((AdditionNode)node);
} else if (node is SubtractionNode) {
    return Visit((SubtractionNode)node);
} else if ...

Но я просто пошел на ярлык для этого примера.

Работа с AST

Итак, что мы можем сделать с деревом математического выражения? Оцените это, конечно! Пусть реализует средство оценки выражений:

internal class EvaluateExpressionVisitor : AstVisitor<double>
{
    public override double Visit(AdditionNode node)
    {
        return Visit(node.Left) + Visit(node.Right);
    }

    public override double Visit(SubtractionNode node)
    {
        return Visit(node.Left) - Visit(node.Right);
    }

    public override double Visit(MultiplicationNode node)
    {
        return Visit(node.Left) * Visit(node.Right);
    }

    public override double Visit(DivisionNode node)
    {
        return Visit(node.Left) / Visit(node.Right);
    }

    public override double Visit(NegateNode node)
    {
        return -Visit(node.InnerNode);
    }

    public override double Visit(FunctionNode node)
    {
        return node.Function(Visit(node.Argument));
    }

    public override double Visit(NumberNode node)
    {
        return node.Value;
    }
}

Довольно просто, когда у нас есть AST, не так ли?

Объединяя все это

И последнее, но не менее важное: мы должны написать основную программу:

internal class Program
{
    private static void Main()
    {
        while (true)
        {
            Console.Write("> ");
            var exprText = Console.ReadLine();

            if (string.IsNullOrWhiteSpace(exprText))
                break;

            var inputStream = new AntlrInputStream(new StringReader(exprText));
            var lexer = new MathLexer(inputStream);
            var tokenStream = new CommonTokenStream(lexer);
            var parser = new MathParser(tokenStream);

            try
            {
                var cst = parser.compileUnit();
                var ast = new BuildAstVisitor().VisitCompileUnit(cst);
                var value = new EvaluateExpressionVisitor().Visit(ast);

                Console.WriteLine("= {0}", value);
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }

            Console.WriteLine();
        }
    }
}

И теперь мы можем, наконец, сыграть с ним:

Ответ 2

Я создал небольшой проект Java, который позволяет вам мгновенно протестировать вашу ANTLR-грамматику, скомпилировав лексер и парсер, сгенерированные ANTLR в памяти. Вы можете просто разобрать строку, передав ее в синтаксический анализатор, и она автоматически сгенерирует AST, который затем может быть использован в вашем приложении.

Чтобы уменьшить размер AST, вы можете использовать NodeFilter, к которому вы могли бы добавить имена производственного правила для нетерминалов, которые вы хотели бы рассмотреть при построении AST.

Код и некоторые примеры кода можно найти по адресу https://github.com/julianthome/inmemantlr

Надеюсь, что инструмент полезен; -)