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

概要

ANTLR ってのは,いわゆるパーサジェネレーターです. 去年の年末に出たバージョン 4.6 からターゲットに Go が追加されました 🙌 . かなり昔に使ったことあったんですが,v4 になってだいぶ整理されて洗練された感じになってました.

この記事は結構適当にやってしまっていると思うので,ちゃんとやりたいならリファレンスを読んだ方がよさそうです(ぉ.

The Definitive ANTLR 4 Reference

The Definitive ANTLR 4 Reference

ANTLR の簡単な紹介

入力のあるプログラム書いていると,入力が well-formed であるかどうかをチェックする必要があることがあります. 正規表現とか使って自分で入力が正しいかどうかチェックする程度の時は良いんですけど,複雑になってくると フルスクラッチで書いてメンテしていくのはつらい感じになってきます.

そんなときのための,そういった parser を作るフレームワークANTLR です.

ANTLR 自体は Java で書かれていますが,生成する parser は

に対応しています.JavaScript とかかなりクールだと思うのですが,まったく詳しくないので 気になる記事だけ貼っておきます. きっと JavaScripter の id:takuya-a =san がそのうちなんかやってくれると思います.

ANTLR and the web: a simple example - Federico Tomassetti - Software Architect

ANTLR を特におすすめするのは,作った文法を試しながら修正したりできるというところです. v4 より前までは ANTLR Works という IDE が別に作られていたんですけど,v4 は EclipseIntelliJ 用のプラグインが配布されています. 勘のよい方ならお気づきかもしれませんが,IntelliJプラグイン使えるんなら Gogland でも使えて,Go の開発はかどるんじゃないかと思ったら, まさにいけました ╭( ・ㅂ・)و ̑̑ グッ !.

f:id:ikawaha:20170318161618p:plain:w300

インストール

ANTLR

本家でダウンロードするか,mac だったら brew でも入ります.

今回は Go をターゲットにするので,Go 用のプラグインをダウンロードします.もちろん go get でいけます

go get github.com/antlr/antlr4/runtime/Go/antlr

ここで注意しなきゃいけないのは,go get した ライブラリにタグが振ってあるので,こいつを 4.6 に合わせておかなければいけない ということです.これでずいぶんハマりました.ベンダリングして管理するのが吉かもしれません.

✔ ~/go/src/github.com/antlr/antlr4 [master ↓·57|…1]
$ git checkout tags/4.6

Gogland

いまは Eary Build が出てるのでこれをインストールしてください.

www.jetbrains.com

ANTLRプラグインを追加する

Gogland で ANTLR 用のプラグインを追加します.

preferenes >> plugins から ANTLR プラグインを選択するだけです.簡単.

f:id:ikawaha:20170318163636p:plain:w300

文法を書く

では,ANTLR で文法を書いてみましょう.四則演算を受理する簡単な文法を書いてみます.

ファイル名は grammar で指定する文法名と同じにする必要があります.下の例だと Calc.g4 としてください.

grammar Calc;

prog:   expr NEWLINE*;
expr:   '(' expr_=expr ')'
    |   left=expr op=('*'|'/') right=expr
    |   left=expr op=('+'|'-') right=expr
    |   atom=INT
    ;

NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

パーサーを生成する

Gogland から Go で書かれたパーサーを生成できます. まずは,ALTLR の 設定をしておきます.

f:id:ikawaha:20170318200209p:plain:w300

f:id:ikawaha:20170318200555p:plain:w300

Language のところに出力言語である Go を指定します.出力されるコードのパッケージは parser がデフォルトのパッケージ名になるので, 出力パスを parser として適当なところに出力させます.ListenerVisitorチェックボックスは後で説明しますが,とりあえずチェックしておいてください.

この状態で,Generate ANTLR Recognizer を選ぶとコードが出力されます.

パーサーを使ってみる

上の設定だと parser フォルダ以下にファイルが出力されます.

package main

import (
    "fmt"

    "github.com/antlr/antlr4/runtime/Go/antlr"

    "github.com/ikawaha/antlr/parser"
)

func main() {
    input := antlr.NewInputStream("12+3*4") // ← 入力

    lexer := parser.NewCalcLexer(input)
    stream := antlr.NewCommonTokenStream(lexer, 0)
    p := parser.NewCalcParser(stream)
    tree := p.Prog()  // ← ルールのトップに対応する関数が用意されてるのでそれを起動すると解析して解析木を返す

    fmt.Println(tree.ToStringTree([]string{}, p)) ← 解析木を LISP-style で表示する,最初の文字列配列をなぜ与えるのかはよく分からん
}

出力

(prog (expr (expr 12) + (expr (expr 3) * (expr 4))))

Listener と Visitor

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

解析しながら式を計算するように Listener を用意してみます.基本的には parser フォルダ以下のファイルは編集しなくて良いはずです. Listener はノードに入るときと出るときにあわせてメソッドが用意されているので,それを上書きして処理を書きます.

parser 下にできる calc_base_listener.go がそれです.

type CalcListener interface {
        antlr.ParseTreeListener

        // EnterProg is called when entering the prog production.
        EnterProg(c *ProgContext)

        // EnterExpr is called when entering the expr production.
        EnterExpr(c *ExprContext)

        // ExitProg is called when exiting the prog production.
        ExitProg(c *ProgContext)

        // ExitExpr is called when exiting the expr production.
        ExitExpr(c *ExprContext)
}

こいつを利用して処理を書きます.自前の CalcListener を用意してみます. (Antlr4 で電卓を作る : 0xdeadbeef を参考にさせていただきました)

package main

import (
    "fmt"
    "strconv"

    "github.com/ikawaha/antlr/parser" // ← ここは生成したコードがある場所を指定
)

type CalcListener struct {
    *parser.BaseCalcListener // ← こいつを上書きして処理を書く
    Stack []int // ← 計算用のスタック
    Error error // ← エラーの記録用(こうするのが正しいのかはよく分かってない)
}

func NewCalcListener() *CalcListener {
    return &CalcListener{Stack: []int{}}
}

func (l *CalcListener) ExitExpr(ctx *parser.ExprContext) { // 解析木の expr ノードを出るときに呼ばれる
    if l.Error != nil {
        return
    }
    if ctx.GetExpr_() != nil {
        return
    }
    if ctx.GetOp() != nil {
        rhs := l.Stack[len(l.Stack)-1]
        l.Stack = l.Stack[:len(l.Stack)-1]
        lhs := l.Stack[len(l.Stack)-1]
        l.Stack = l.Stack[:len(l.Stack)-1]

        switch ctx.GetOp().GetText() {
        case "*":
            l.Stack = append(l.Stack, lhs*rhs)
        case "+":
            l.Stack = append(l.Stack, lhs+rhs)
        case "/":
            l.Stack = append(l.Stack, lhs/rhs)
        case "-":
            l.Stack = append(l.Stack, lhs-rhs)
        default:
            l.Error = fmt.Errorf("unknown op, %v", ctx.GetOp().GetText())
        }
        return
    }
    if ctx.GetAtom() != nil {
        i, err := strconv.Atoi(ctx.GetAtom().GetText())
        if err != nil {
            l.Error = fmt.Errorf("invalid value, %v", err)
        }
        l.Stack = append(l.Stack, i)
        return
    }
}

main.go をチョット書き換える.

package main

import (
    "fmt"

    "github.com/antlr/antlr4/runtime/Go/antlr"

    "github.com/ikawaha/antlr/parser"
)

func main() {
    input := antlr.NewInputStream("1+(2+3)*4-5")

    lexer := parser.NewCalcLexer(input)
    stream := antlr.NewCommonTokenStream(lexer, 0)
    p := parser.NewCalcParser(stream)

    listener := NewCalcListener() // Listener を parser にセットする
    p.AddParseListener(listener)

    tree := p.Prog()
    fmt.Println(tree.ToStringTree([]string{}, p))
    fmt.Printf("---> %+v\n", listener.Stack) // Listener の中身を出力する
}

結果

$ go run *.go
(prog (expr (expr (expr 1) + (expr (expr ( (expr (expr 2) + (expr 3)) )) * (expr 4))) - (expr 5)))
---> [16]

Visitor を使えばもっと凝ったことができると思います.使い方はおおむね Listener と同じです. Vistor や Listener を使う場合には,結果としての解析木を構築しなくてもいいわけなので,これを off にする方法が提供されています. parser の BuildParseTreesfalse にセットしてください.

Gogland で ANTLR preview を使う

GUI で任意の入力をあたえてインタラクティブに解析木をチェックすることができます. チョットわかりにくいのは,文法ファイルを開いて,テストの対象とするノードを選択することです. これが選択されてないと赤字で select from navigator or grammar とエラーが出ると思います.

ノードを選択したら,入力欄に好きなように文字列を入れてください.右側にどんどん解析木が組み上がってくと思います.

f:id:ikawaha:20170319000506p:plain:w300

僕もチョット触ってみただけで,たいしたこと書いてない割に長くなってしまいましたが,いろいろ遊べるツールだと思うので,是非リファレンスをあたってみてください.#そして便利な使い方を教えて欲しい

Happy Hacking !