Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Hidenori

ANTLR4をC#から使ってみる #05 Visitorで計算機を作るための試行錯誤

Posted at

前回で、ANTLR4のListenerで計算機を作ることができた。
それより前にVisitorを少し触ったが、使い方はまだわかっていない。
今回でVisitorについて学ぶ。

最初のプログラム

文法はListenerで計算機を作ったのと同じ。

Calculator.g4
grammar Calculator;

PLUS : '+';
MINUS: '-';
MULTI: '*';
DIV  : '/';
NUMBER : [0-9]+;
WHITESPACE : [ \r\n\t]+ -> skip;

expression 
	: NUMBER						# Number
	| '(' expression ')'			# Parentheses
	| expression MULTI expression	# Multiplication
	| expression DIV expression		# Division
	| expression PLUS expression	# Addition
	| expression MINUS expression	# Subtraction
;
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Antlr4.Runtime;

namespace Calculator02_1
{
    class Program
    {
        static void Main(string[] args)
        {
            string parsedString;
            if (args.Length == 0)
            {
                Console.WriteLine("引数に数式を指定してください");
                return;
            }
            else
            {
                parsedString = args[0];
            }
            var inputStream = new AntlrInputStream(parsedString);
            var lexer = new CalculatorLexer(inputStream);
            var commonTokenStream = new CommonTokenStream(lexer);
            var parser = new CalculatorParser(commonTokenStream);
            var graphContext = parser.expression();
            Console.WriteLine(graphContext.ToStringTree());
        }
    }
}

Visitorクラスを作成

CalculatorBaseVisitorを継承した、CalculatorVisitorクラスを作成。
各メソッドの内容は、VisualStudioが自動的に書き出した内容に、適当にConsole.WriteLineを書き足したもの。
前回との違いは、文法に代替テキストを使っていること。それによりVisitorで利用できるメソッドが増えた。

CalculatorVisitor.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Antlr4.Runtime.Misc;
using Antlr4.Runtime.Tree;
using System.Reflection;

namespace Calculator02_1
{
    class CalculatorVisitor : CalculatorBaseVisitor<object>
    {
        public override object Visit([NotNull] IParseTree tree)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0}", tree.GetText());
            return base.Visit(tree);
        }
        public override object VisitExpression([NotNull] CalculatorParser.ExpressionContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0}", context.GetText());
            return base.VisitExpression(context);
        }
        public override object VisitAddition([NotNull] CalculatorParser.AdditionContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0} , Node:{1}", context.GetText(), context.PLUS());
            return base.VisitAddition(context);
        }
        public override object VisitChildren([NotNull] IRuleNode node)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0}", node.GetText());
            return base.VisitChildren(node);
        }
        public override object VisitDivision([NotNull] CalculatorParser.DivisionContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0} , Node:{1}", context.GetText(), context.DIV());
            return base.VisitDivision(context);
        }
        public override object VisitMultiplication([NotNull] CalculatorParser.MultiplicationContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0} , Node:{1}", context.GetText(), context.MULTI());
            return base.VisitMultiplication(context);
        }
        public override object VisitSubtraction([NotNull] CalculatorParser.SubtractionContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0} , Node:{1}", context.GetText(), context.MINUS());
            return base.VisitSubtraction(context);
        }
        public override object VisitParentheses([NotNull] CalculatorParser.ParenthesesContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0}", context.GetText());
            return base.VisitParentheses(context);
        }
        public override object VisitNumber([NotNull] CalculatorParser.NumberContext context)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0} , Node:{1}", context.GetText(), context.NUMBER());
            return base.VisitNumber(context);
        }
        public override object VisitTerminal([NotNull] ITerminalNode node)
        {
            Console.WriteLine("{0}", MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("\tGetText():{0}", node.GetText());
            return base.VisitTerminal(node);
        }
    }
}

main()の最後のConsole.WriteLineの直前に2行追加

Program.cs
略
        static void Main(string[] args)
        {
略
            CalculatorVisitor visitor = new CalculatorVisitor();
            visitor.Visit(graphContext);
略

>Calculator02_1.exe 1+2*3
Visit
        GetText():1+2*3
VisitAddition
        GetText():1+2*3 , Node:+
VisitChildren
        GetText():1+2*3
VisitNumber
        GetText():1 , Node:1
VisitChildren
        GetText():1
VisitTerminal
        GetText():1
VisitTerminal
        GetText():+
VisitMultiplication
        GetText():2*3 , Node:*
VisitChildren
        GetText():2*3
VisitNumber
        GetText():2 , Node:2
VisitChildren
        GetText():2
VisitTerminal
        GetText():2
VisitTerminal
        GetText():*
VisitNumber
        GetText():3 , Node:3
VisitChildren
        GetText():3
VisitTerminal
        GetText():3
([] ([0] 1) + ([18] ([0 18] 2) * ([12 18] 3)))

メモ

  • VisitorのVisit***もListenerのExit***も、親→左下→右下と辿る。

  • Visit***は(このコードでは)各ノードを最初に訪れた順に起動する。

  • Exit***は各ノードを1度訪れたあと、それより親に戻る際に起動する。
    tree.png

  • このページの2つ目の図では、終端ではVisitが起きないように書かれているが、終端でもVisitが起きた。理由はわからない。

このコードで、VsitorのVisit***を呼んでいるのは誰？

ANTLR のターゲットに Go が追加されたので Gogland とあわせて遊んでみるによると、

ANTLR では，構文解析木を作ってから解析をするのではなくて，Listener や Visitor と呼ばれるものをあらかじめ Parser にセットしておいて解析しながら処理を行うことができる仕組みがあります．Listener は解析木を深さ優先で処理していく場合に使い，解析木の形に合わせてたどるノードを変えたい場合には Visitor を使います． Listener も Visitor もひな形ができているのでそれを使うだけです．

Antlr4 - Visitor vs Listener Patternによると

  1. Listener methods are called automatically by the ANTLR provided walker object, whereas visitor methods must walk their children with explicit visit calls. Forgetting to invoke visit() on a node’s children means those subtrees don’t get visited
  1. Listener methods can’t return a value, whereas visitor methods can return any custom type. With listener, you will have to use mutable variables to store values, whereas with visitor there is no such need.
  2. Listener uses an explicit stack allocated on the heap, whereas visitor uses call stack to manage tree traversals. This might lead to StackOverFlow exceptions while using visitor on deeply nested ASTs

DeepL翻訳では

  1. リスナーメソッドはANTLRが提供するwalkerオブジェクトによって自動的に呼び出されますが、ビジターメソッドは明示的なvisit呼び出しで子ノードを巡回しなければなりません。ノードの子に対して visit() を呼び出し忘れた場合は、それらのサブツリーは訪問されないことを意味します。
  1. リスナーメソッドは値を返すことができませんが、ビジターメソッドは任意のカスタム型を返すことができます。リスナーでは、値を格納するためにミューテータブル変数を使用する必要がありますが、ビジターではその必要がありません。
  2. リスナーではヒープ上に確保された明示的なスタックを使用しますが、ビジターではツリートラバースの管理にコールスタックを使用します。このため、深くネストしたASTでvisitorを使用するとStackOverFlowの例外が発生する可能性があります。

Visitorでは明示的に子ノードを巡回するとあるが、今回はmain()から1回visit()した以外は自動的にvisit()されている。

上記のプログラムのスタックトレースをgraphvizで視覚化した。

1.png

すると、CalculatorVisitor.VisitNumberの場合は
return base.VisitNumber(context);
を起点に、

  • override元の同名のメソッド(CalculatorBaseVisitor.VisitNumber)を起動。
  • CalculatorVisitor.VisitChildrenを起動
  • Antlr4.Runtime.Tree.AbstractParseTreeVisitor`1.VisitChildrenを起動
  • これが、下記のような次の呼び出し先に応じたクラスのAcceptを起動
  • CalculatorParser.AdditionContext.Accept[TResult]
  • CalculatorParser.NumberContext.Accept[TResult]
  • ここから、VisitNumberやVisitAdditionを起動

のように、VisualStudioが自動的に書き出したreturn文が子要素のvisitを起動している。

何をreturnするか。どのように木をwalkするかは、プログラムの都合で上書きするのだろうと想定する。
今回は計算機を作るので次回以後で、+ / 等の演算子のノードのvisitから、左辺と右辺のvisitを呼び出す。
また、+ /等のノードのvisitは、それ以下の計算結果の数値をreturnする。と上書きする。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?