BinaryDevelop
  1. ホーム
  2. java

[解決済み] ANTLR4でASTを作成するには？

2023-07-31 11:15:17

質問

この件についていろいろと検索してみましたが、ASTを構築するのに本当に役立つものは見つかりませんでした。ANTLR4 が ANTLR3 が行っていたような AST を構築できないことはすでに知っています。しかし、どのようにしてこれを行うかについての例やより詳細な説明を見つけることができませんでした...。

私はC言語のような文法を持っていますが、すべてのコマンドはポルトガル語（portugaプログラミング言語）で書かれています。ANTLR4 を使用して簡単に解析ツリーを生成することができます。私の質問は、AST を作成するために今何をする必要があるかということです。

ところで、私はJavaとIntelliJを使用しています...

EDIT1です。 このトピックの回答を使うのが一番近かったです。 javaのソースコードからASTを作成し、メソッド、変数、コメントを抽出するためにantlr4を使用する簡単な例はありますか？ しかし、それは訪問したメソッドの名前を印刷するだけです....

最初の試みは私の期待通りに動かなかったので、私は このチュートリアル をANTLR3から取得しようとしましたが、STの代わりにStringTamplateを使用する方法がわかりませんでした...。

本を読む ANTLR 4リファレンスの決定版 も、ASTに関連するものは見つかりませんでした。

EDIT2です。 これでDOTファイルを作成するクラスが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);

かなり基本的なことですが、1つの 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をトラバースするために、AST訪問者の基底クラスを構築する必要があります。と同じようなことをやってみましょう。 AbstractParseTreeVisitor<T> と同じようなことをしましょう。 

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 キーワードを利用して、1行のコードでダブルディスパッチを実行しています。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();
        }
    }
}

そして、いよいよ遊べるようになりました。

関連

最新

おすすめ

について
/
プライバシー・ポリシー
/
お問い合わせ
© 2022 BinaryDevelop. すべての権利は、それぞれの所有者に帰属します