如何使用ANTLR4创建AST？如何使用ANTLR4创建AST？(How to create AST

2019-05-10 12:10发布

站内文章 / 后端开发
251 0 0

我一直在寻找这个了很多，我无法找到任何有用的东西，真正帮助我建立一个AST。 我已经知道ANTLR4不建立AST像ANTLR3用来做什么。 大家说：“嘿，旅客使用！”，但我无法找到我怎么能做到这一点的任何例子或者更详细的解释...

我有一个语法必须像C，但写在葡萄牙每个命令（portuga编程语言）。 我可以用ANTLR4容易产生解析树。 我的问题是：我现在需要做什么来创建一个AST？

顺便说一句，我使用Java和IntelliJ ...

EDIT1：我可以用这个话题的答案获得最近有没有使用antlr4创建从Java源代码和提取方法，变量和注释的AST的一个简单的例子？ 但只打印的访问方法的名称..

由于第一次尝试并没有为我工作，我预期，我试图用这个教程从ANTLR3，但我无法弄清楚如何使用，而不是ST StringTamplate ...

读这本书权威ANTLR 4参考我也找不到相关的AST的任何东西。

EDIT2：现在我有一个类来创建DOT文件，我只需要弄清楚如何正确使用人次

Answer 1:

好吧，让我们建立一个简单的数学例子。 构建AST是这样的任务完全矫枉过正，但它显示的原理的好方法。

我会做它在C＃中，但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())
        };
    }
}

正如你所看到的，它只是一个使用访客创造出一个CST节点的AST节点的问题。 该代码应该是相当不言自明的（好吧，也许除了VisitFuncExpr的东西，但它只是线了代表对的合适方法的快速方法System.Math类）。

在这里，你有AST建筑的东西。 这是一个的所需的全部。 单从CST提取相关信息，并保持它在AST。

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

在这里，我把C＃的优势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();
        }
    }
}

现在，我们终于可以用它玩：



Answer 2:

我创建了一个小型的Java项目，使您可以通过编辑内存由ANTLR生成的词法和语法分析器立即测试您的ANTLR语法。 你可以通过它传递给解析器只是解析字符串，它会自动生成它的一个AST，然后可以在应用程序中使用。

为了降低AST规模的目的，你可以使用一个NodeFilter到你可以添加你想构建AST时要考虑非终端的产生式规则的名称。

代码和一些代码示例，可以发现https://github.com/julianthome/inmemantlr

希望该工具是有用的;-)



文章来源: How to create AST with ANTLR4?
标签： java compiler-construction antlr abstract-syntax-tree antlr4
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~