Google ColaboratoryでANTLRを動かして、構文木の画像生成してみる

こんにちは！アルダグラムでレポートチームのエンジニアをしている志茂です。

レポートチームでは、お客様が利用されているExcelファイルをKANNA上にアップロードし、webから編集できるような機能をKotlinとSpring Bootで開発しております。

Excelファイルを読み込み編集できるようにするためには、色々な考慮事項があるのですが、
今回はその中でもExcel関数の読み込みで利用している、ANTLRという構文解析を行うためのツールをGoogle Colaboratory上で動作させ、解析した結果を構文木の画像として生成する方法をご紹介します。

構文解析ツールを使わないと大変？

単純な例を挙げながらお話しすると、Excelやプログラミング言語で、1+2*3という計算式があった場合、実行すると7という計算結果が得られます。これは1+2*3を単なるStringの文字列ではなく、1+2*3の文字列のパターンを数式として評価して、各数式に応じた計算を行ったからです。

この要素から意味をなす最小の単位まで分解し(字句解析)、各字句ごとの意味を解釈する(構文木の生成)処理を構文解析といいます。

上記の処理を構文解析ツールを利用せずに行うとKotlinで以下のような実装になります。
ここに/``**``-などの基本的な数式や、Excelの関数を扱うために改修するには、各数式の実行順序を意識しながら、追加改修するのはかなり大変です。

fun calc(formula: String): Double {
    val additionIndex = formula.indexOf("+")
    if (additionIndex != -1) {
        val left = formula.substring(0, additionIndex)
        val right = formula.substring(additionIndex + 1)
        return calc(left) + calc(right)
    }

    val multiplicationIndex = formula.indexOf("*")
    if (multiplicationIndex != -1) {
        val left = formula.substring(0, multiplicationIndex)
        val right = formula.substring(multiplicationIndex + 1)
        return calc(left) * calc(right)
    }
    return formula.toDouble()
}

ANTLRとは

上記の文字列を意味のある式として、評価するためにANTLRというパーサージェネレータを使用しています。文法の詳細の説明は割愛しますが、以下のような文法定義から構文解析器（パーサー）を生成するためのツールです。

+ *を解析するためのパーサーを生成する

grammar Expr;
prog:   expr EOF;
expr:   expr op=('*'|'/') expr   #MulDiv
    |   expr op=('+'|'-') expr   #AddSub
    |   INT                      #Int
    |   '(' expr ')'             #Parens
    ;
INT :   [0-9]+;
WS  :   [ \t\r\n]+ -> skip;

ANTLRはJVM上で動作し、生成したパーサーは、Java、Kotlin、Scala以外にもPython、JavaScript、Goなど複数のプログラミング言語に対応しております。
https://www.antlr.org/tools.html

Google ColaboratoryでANTLRを動かしてみる

そして本題ですが、ANTLRの文法を理解や実行確認のために、ブラウザ上で実行し、構文木の画像を生成して、意図した構文解析を行えているか確認するツールを作成してみました。

Google ColaboratoryでANTLRを動かして、Pythonのパーサーを生成して、入力した文字列から、構文木を作成できるようにしていきたいと思います。

Google Colaboratoryから新規のノートブックを作成し、各コードブロックを追加していきます。

ANTLRの文法を記載し、Expr.g4に保存する

%%writefile Expr.g4
grammar Expr;
prog:   expr EOF;
expr:   expr op=('*'|'/') expr   #MulDiv
    |   expr op=('+'|'-') expr   #AddSub
    |   INT                      #Int
    |   '(' expr ')'             #Parens
    ;
INT :   [0-9]+;
WS  :   [ \t\r\n]+ -> skip;

JVMとANTLRをインストールして、パーサを生成する

# 必要なツールとライブラリのインストール
!apt-get update -qq
!apt-get install openjdk-11-jdk-headless -qq > /dev/null
!pip install antlr4-python3-runtime

# ANTLRのJARファイルをダウンロード
!wget -q https://www.antlr.org/download/antlr-4.13.0-complete.jar

# ANTLRでPythonファイルを生成
!java -jar antlr-4.13.0-complete.jar -Dlanguage=Python3 -visitor Expr.g4

# 生成されたファイルを確認
!ls -l ExprLexer.py ExprParser.py ExprVisitor.py

入力した数式を解析し、その構文木を生成する。
EvalVisitorクラスで構文木を処理し、その結果をGraphvizを用いてDOT形式のデータから構文木の画像を生成する。

from antlr4 import *
from ExprLexer import ExprLexer
from ExprParser import ExprParser
from ExprVisitor import ExprVisitor

class EvalVisitor(ExprVisitor):
    def visitProg(self, ctx):
        return self.visit(ctx.expr())

    def visitMul(self, ctx):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(1))
        return ('Mul', left, right)

    def visitDiv(self, ctx):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(1))
        return ('Div', left, right)

    def visitAdd(self, ctx):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(1))
        return ('Add', left, right)

    def visitSub(self, ctx):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(1))
        return ('Sub', left, right)

    def visitInt(self, ctx):
        return int(ctx.INT().getText())

    def visitParens(self, ctx):
        return self.visit(ctx.expr())

# 解析したい入力
input_expr = input("解析したい構文を入力してください (例: (1 + 2) * 3): ")

# 入力をストリームに変換
input_stream = InputStream(input_expr)

# レキサーとパーサーを作成
lexer = ExprLexer(input_stream)
token_stream = CommonTokenStream(lexer)
parser = ExprParser(token_stream)

# 構文解析を実行
tree = parser.prog()

# ビジターを使って構文木を取得
visitor = EvalVisitor()
result = visitor.visit(tree)

# 構文木をテキスト形式で表示
print(tree.toStringTree(recog=parser))

# 構文木をDOT形式に変換
from antlr4.tree.Trees import Trees

def tree_to_dot(tree, parser):
    def escape(s):
        return s.replace('"', '\"')

    buf = []
    buf.append('digraph ParseTree {\n')
    buf.append('  node [shape=plaintext]\n')

    count = [0]

    def walk(t):
        node_name = 'node{}'.format(count[0])
        count[0] += 1
        s = escape(Trees.getNodeText(t, recog=parser))

        buf.append('  {} [label="{}"];\n'.format(node_name, s))

        for i in range(t.getChildCount()):
            child = t.getChild(i)
            child_name = walk(child)
            buf.append('  {} -> {};\n'.format(node_name, child_name))

        return node_name

    walk(tree)
    buf.append('}\n')
    return ''.join(buf)

# DOT形式の文字列を取得
dot_str = tree_to_dot(tree, parser)

# Graphvizのインストールと画像の生成
!apt-get install graphviz -qq
!pip install graphviz

import graphviz
from IPython.display import Image

# DOTデータを画像に変換
graph = graphviz.Source(dot_str)
graph.format = 'png'
graph.render('parse_tree', view=False)

画像を表示
Image(filename='parse_tree.png')

上記のコードを設定し、1+2*3をパラメータとして渡して実行すると以下のような結果が得られました。

完成したコードはgistに保存してありますので、利用されたい方は是非ご活用ください。
https://gist.github.com/seamoooo/19fe48fc090b23421b5b7aa0ea226c91

最後に

以上、Google ColaboratoryでANTLRを動かして、構文木の画像生成してみる話でした。

ちなみにIntelliJやvscodeを利用している方は、ANTLR Pluginのプラグインを利用しても、上記と同じような実行確認をすることもできます。是非お試しください。
https://plugins.jetbrains.com/plugin/7358-antlr-v4
https://marketplace.visualstudio.com/items?itemName=mike-lischke.vscode-antlr4

もっとアルダグラムエンジニア組織を知りたい人、ぜひ下記の情報をチェックしてみてください！