antlr4

https://www.antlr.org/
antlr4((ANother Tool for Language Recognitionのversion4の頭文字です)は与えられたテキストに対してルールを設定し、それに応じた処理への振り分けを行うパッケージです。大分ざっくり言うと自作のプログラミング言語(DSL:Domain-Specific Language)を作ることができます。
ただ、antlr4が構文を解析した後の各パーツに対応する処理は自分で書かなければいけません。go言語でこの部分を作る機会があったのでその例を紹介したいと思います。
今回は四則演算のstringを処理して計算結果を返すようなparser(生成された構文解析器)を作ろうと思います。

環境構築

vscodeの拡張機能を入れれば、すぐに使えます。以下の記事を参考にしました。
https://qiita.com/i-tanaka730/items/4eeaae247f70895c3456

grammarファイル

antlr4に読み込ませるinputファイルです。
ここに、構成要素や演算子となる文字列を定義したり、文法を設定したりします。

Calc.g4

grammar Calc;

//Tokens
MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';
NUMBER: [0-9]+;
WHITESPACE: [ \r\n\t]+ -> skip;

//Rules
start: expression EOF;

expression
    : expression op=(MUL|DIV) expression # MulDiv
    | expression op=(ADD|SUB) expression # AddSub
    | NUMBER                             # Number
    ;

このCalc.g4で構成要素となるNUMBER,MUL, DIV, ADD,SUB, WHITESPACEと文法start,MulDiv,AddSub,Numberが定義されました。
expressionの部分は四則演算が出てくるうちは再起呼び出しになっていて、最終的にNUMBERの処理が呼ばれます。

grammar/Calc.g4にこのファイルがあるとして、以下のコマンドを実行すると、-Dlanguageで指定した言語の構文解析パッケージが生成されます。

antlr4 -Dlanguage=Go -visitor -o ../parser -package parser grammar/Calc.g4

このコマンドで生成されたparserディレクトリは以下のようになります。

.
├── grammar
│   └── Calc.g4
└── parser
    ├── Calc.interp
    ├── Calc.tokens
    ├── CalcLexer.interp
    ├── CalcLexer.tokens
    ├── calc_base_listener.go
    ├── calc_base_visitor.go
    ├── calc_lexer.go
    ├── calc_listener.go
    ├── calc_parser.go
    └── calc_visitor.go

この中にcalc_base_visitor.goというファイルがあり、その中身は以下のようになっています。

calc_base_visitor.go

// Code generated from grammar/Calc.g4 by ANTLR 4.13.1. DO NOT EDIT.

package parser // Calc
import "github.com/antlr4-go/antlr/v4"

type BaseCalcVisitor struct {
	*antlr.BaseParseTreeVisitor
}

func (v *BaseCalcVisitor) VisitStart(ctx *StartContext) interface{} {
	return v.VisitChildren(ctx)
}

func (v *BaseCalcVisitor) VisitNumber(ctx *NumberContext) interface{} {
	return v.VisitChildren(ctx)
}

func (v *BaseCalcVisitor) VisitMulDiv(ctx *MulDivContext) interface{} {
	return v.VisitChildren(ctx)
}

func (v *BaseCalcVisitor) VisitAddSub(ctx *AddSubContext) interface{} {
	return v.VisitChildren(ctx)
}

このBaseCalcVisitorオブジェクトのメンバ関数にそれぞれ行いたい処理を書き込めばいい訳です。しかし、DO NOT EDIT.と書いてありますし、このテンプレートを直接編集するのではなく、これをコピーしたオブジェクトを作ってそれを使うことにします。myvisit/ディレクトリ下に以下のファイルを作ります。(以下のブログを見て書きました。https://blog.gopheracademy.com/advent-2017/parsing-with-antlr4-and-go/)

myvisit.go

package myvisit

import (
	"./parser"
	"fmt"
	"strconv"

	"github.com/antlr4-go/antlr/v4"
)

// copy template of visitor object in calc_base_visitor.go

// object of the process when the target context hits.
type calcListener struct {
	*parser.BaseCalcListener

	stack []int
}

// Push operation for stack
func (l *calcListener) push(i int) {
	l.stack = append(l.stack, i)
}

// Pop operation for stack
func (l *calcListener) pop() int {
	if len(l.stack) < 1 {
		panic("stack is empty unable to pop")
	}

	// Get the last value from the stack.
	result := l.stack[len(l.stack)-1]

	// Remove the last element from the stack.
	l.stack = l.stack[:len(l.stack)-1]

	return result
}

// Process for MUL or DIV tokens
func (l *calcListener) ExitMulDiv(c *parser.MulDivContext) {
	right, left := l.pop(), l.pop()

	switch c.GetOp().GetTokenType() {
	case parser.CalcParserMUL:
		l.push(left * right)
	case parser.CalcParserDIV:
		l.push(left / right)
	default:
		panic(fmt.Sprintf("unexpected op: %s", c.GetOp().GetText()))
	}
}

// Process for ADD or SUB tokens
func (l *calcListener) ExitAddSub(c *parser.AddSubContext) {
	right, left := l.pop(), l.pop()

	switch c.GetOp().GetTokenType() {
	case parser.CalcParserADD:
		l.push(left + right)
	case parser.CalcParserSUB:
		l.push(left - right)
	default:
		panic(fmt.Sprintf("unexpected op: %s", c.GetOp().GetText()))
	}
}

// process for NUMBER
func (l *calcListener) ExitNumber(c *parser.NumberContext) {
	i, err := strconv.Atoi(c.GetText())
	if err != nil {
		panic(err.Error())
	}

	l.push(i)
}

// CalcQuery parses the input query & calclate the formula
func CalcQuery(input string) int {
	// Setup the input
	is := antlr.NewInputStream(input)

	// Create the Lexer
	lexer := parser.NewCalcLexer(is)
	stream := antlr.NewCommonTokenStream(lexer, antlr.TokenDefaultChannel)

	// Create the Parser
	p := parser.NewCalcParser(stream)

	// Finally parse the expression
	var listener calcListener
	antlr.ParseTreeWalkerDefault.Walk(&listener, p.Start_())
	return listener.pop()
}

stackを使って出てきたNUMBERを溜めておき、四則演算が呼ばれたときに、その演算の前後のNUMBERを取り出して計算したものをまたstackに戻すという処理になっています。（parser下に生成された関数もいろいろと使っています。）

これを使ってみましょう。

main.go

package main

import (
    "./myvisit"
    "fmt"
)

func main() {
    input := "20 + 12/5 - 4*3"
    output := myviit.CalcQuery(input)
    fmt.Println(output)
}

ターミナルで

$ go mod tidy
$ go mod init

を行うと最終的に以下のようなファイル構成になります。

.
├── go.mod
├── go.sum
├── grammar
│   └── Calc.g4
├── main.go
├── myvisit
│   └── myvisit.go
└── parser
    ├── Calc.interp
    ├── Calc.tokens
    ├── CalcLexer.interp
    ├── CalcLexer.tokens
    ├── calc_base_listener.go
    ├── calc_base_visitor.go
    ├── calc_lexer.go
    ├── calc_listener.go
    ├── calc_parser.go
    └── calc_visitor.go

main.goを実行すると、

$ go run maingo
10

となり、先の20 + 12/5 - 4*3の答えが返ってきました。(除算は余りが切り捨て)

注意点

myvisit.goで呼び出すantlr4のパッケージはgithub.com/antlr4-go/antlr/v4を使ってください。go mod tidyで自動読み込みすると大抵github.com/antlr/antlr4/runtime/Go/antlrの方がimportされますが、こっちだとコードが動きません。myvisit.CalcQuery関数内の

myvisit.go

	lexer := parser.NewCalcLexer(is)

の部分でエラーが出てきます。

参考文献