vol.1と言いつつvol.2を執筆しないと定評の高いerukitiです。こんにちは。(全文検索やrxjsの続き書こうと思いつつ…)
今日はGolangとPEGを使って、言語処理系を作る話の第一弾として、pointlander/peg の解説をします。
PEG?
PEGでぐぐると、胃ろうとかいうのがヒットしますがそれじゃなくて、Parsing Expression Grammar です。簡単に言うとlexとyaccを足したみたいなジャンルの処理系で、字句解析付きのコンパイラコンパイラとか言えばピンと来るかもしれません。RFCを読んでる人ならBNFとか身近だと思うんですが、まぁその手の言語ルールを形式化したものの一種ですね。僕には学術的説明をするほどの知識はないので、厳密な話を知りたい人はいろいろぐぐってみてください。
expression <- additive
additive <- multitive ('+' multitive / '-' multitive)*
multitive <- value ('*' value / '/' value)*
value <- [0-9]+ / '(' expression ')'
これはよくPEGのサンプルで紹介される四則演算定義です。まず、PEGでは定義名 <- 定義内容という形で定義を書いていきます。一般的に一番上に書かれてる定義がルートとなる定義になります。
expression <- additive
一行目のここではexpression(というルート定義)はadditiveだよという定義をしています。
additive <- multitive ('+' multitive / '-' multitive)*
multitive <- value ('*' value / '/' value)*
additiveは、multitiveのうしろに、+という文字とmultitiveもしくは-という文字とmultitiveが0〜n個くっついたものという定義がされています。PEG処理系によっては細かい部分は異なりますが、''あるいは""で文字リテラルを定義します。
おそらく見慣れない書き方が / ではないでしょうか。例えばyaccで言うところの | に似ています。この行では足し算もしくは引き算の定義がなされていますが、| と決定的に違うのが曖昧性が排除されている点で、/ で並べた要素のうち、もしも前者にヒットするのであれば必ず前者にヒットします。つまり並べた要素は前の要素が優先されます。
value <- [0-9]+ / '(' expression ')'
ここでまたexpressionが登場しています。PEGではこのように再帰的に書くことができます。ただし、これは'('と')'という新たな要素が付いているから再帰できるだけです。単純に value <- expression のような定義であれば、無限ループになってしまいます。
PEGで使用される要素は割と少ないです。あとはWikipediaの記事を読むと大体わかると思います。
GolangでPEG
golang PEGで、ぐぐるとpointlander/pegがトップにヒットすると思います。他にもいくつかGo向けのPEG処理系はあるのですが今回はこれを紹介します。
$ go get -d github.com/pointlander/peg
で、pegというコマンドがインストールされると思います。pegコマンドを使ってpeg定義ファイルをgoのファイルにコンパイルします。
package main
type Parser Peg {
Calc
}
root <- expression
expression <- additive
additive <- multitive (
'+' multitive {p.PushOpe("+")} /
'-' multitive {p.PushOpe("-")}
)*
multitive <- value (
'*' value {p.PushOpe("*")} /
'/' value {p.PushOpe("/")}
)*
value <-
<[0-9]+> {p.PushDigit(text)} /
'(' expression ')'
このソースをcalc.pegという名前で保存し、コマンドラインでpeg calc.pegを実行すると、calc.peg.goというソースが生成されます。このpegファイルは書式が決まっていて、Goのソースとよく似た、package定義、type定義をしてから、PEGの定義をしていくことになります。type定義された型の中にCalcとだけ書かれていますが、別ファイルで定義したCalc構造体をそのまま入れるというGoの記法です。
さっき説明した四則演算のPEG定義の中には見られなかったものが二つ増えています。一つ目は<と>で囲まれた定義でマッチした文字列を取り込むというものです。{と}で囲まれたブロックはマッチ時に実行するGoのコードが書かれています。このコード内では、特定の変数にのみアクセスができます。
- p
- text
- begin
- end
pはtype定義した構造体のインスタンスです。今回はpはpegコマンドが生成するメソッドおよび、Calcのメソッドが使えます。Calc構造体に、パーサーが使うデータ群の定義、Calcのメソッドに、それらの操作をするメソッドを定義するといいでしょう。
textは<と>で囲まれた定義でマッチしたテキストが、beginはバッファ内のtextの開始位置、endは終了位置です。バッファはパーサーの初期化時に渡すものです。
次はParserを使うGoのコードを見てみましょう。Calcの定義も行います。
package main
import (
"fmt"
"strconv"
)
type Calc struct {
OpeStack []string
DigitQueue []int
}
func (c *Calc) PushOpe(ope string) {
a := c.popDigit()
b := c.popDigit()
switch ope {
case "+":
fmt.Printf("%d+%d\n", b, a)
c.pushDigit(b + a)
case "-":
fmt.Printf("%d-%d\n", b, a)
c.pushDigit(b - a)
case "*":
fmt.Printf("%d*%d\n", b, a)
c.pushDigit(b * a)
case "/":
fmt.Printf("%d/%d\n", b, a)
c.pushDigit(b / a)
}
}
func (c *Calc) PushDigit(digit string) {
n, _ := strconv.Atoi(digit)
c.pushDigit(n)
}
func (c *Calc) pushDigit(n int) {
c.DigitQueue = append(c.DigitQueue, n)
}
func (c *Calc) popDigit() int {
var n int
n, c.DigitQueue = c.DigitQueue[len(c.DigitQueue)-1], c.DigitQueue[:len(c.DigitQueue)-1]
return n
}
func (c *Calc) Compute() {
fmt.Printf("result: %d\n", c.popDigit())
}
func main() {
parser := &Parser{Buffer: "1+2*3-(4+5)"}
parser.Init()
err := parser.Parse()
if err != nil {
fmt.Println(err)
} else {
parser.Execute()
parser.Compute()
}
}
このGoのソースをcalc.goで保存したとすれば、
$ peg calc.peg
$ go run calc.go calc.peg.go
を実行すると、
2*3
1+6
4+5
7-9
result: -2
というような結果が帰ってきます。計算順番に従って計算している途中結果と、最終結果が表示されています。
本当は計算するだけであればpushDigit(), popDigit()のようなメソッドは必要なかったのですが、言語処理系として作るのであれば変数を認識してASTを作るために、こういうような操作が必要になるためここまで作っています。
ひとまずGoで四則演算をして、その途中の演算過程と結果を表示するプログラムができあがりました。このプログラムにはいくつか問題があります。
エラー検出
初期化時にBufferに渡している式をでたらめなモノに変えてみたとします。現時点のコードで実行すると正常な部分までだけがパースされ、残りは捨てられます。
EOT(end of text) を検出する
PEGのイディオムの一つにEOTがあります。EOT <- !. という定義を加えてみましょう
root <- expression EOT
EOT <- !.
これで正しくない式が渡されればエラーが出るようになります。err := parser.Parse() でエラーが帰るようになります。
ただ、残念な事にこのPEG処理系で生成されるパーサーはエラーの原因に関しては無頓着なようです。parse error というのがいっぱい出力されるかもしれませんが、メッセージを見てもさっぱりわかりません。せめてエラーの出た位置だけでも知ることが出来ればいいのですが。
エラーを検出する
root <-
expression EOT /
expression <.+> {p.Err(begin, buffer)} EOT /
<.+> {p.Err(begin, buffer)} EOT
rootの定義をこのように変更します。まずexpression EOTにマッチしようとして失敗をするので、次のexpression <.+> EOTに行きます。たとえば正しくない式が途中までは正しいものであれば、この時点でマッチします。p.Errメソッドには、エラーの位置と全体のバッファが渡されるので、それを元にエラー表示を行えばよいですね。最初から正しくないものが渡されていた場合は三つ目にマッチしますが、この場合はErrメソッド呼び出しの引数(begin)は0と同じですね。
package main
import (
"fmt"
"strconv"
"strings"
)
type Calc struct {
OpeStack []string
DigitQueue []int
IsError bool
}
func (c *Calc) PushOpe(ope string) {
a := c.popDigit()
b := c.popDigit()
switch ope {
case "+":
fmt.Printf("%d+%d\n", b, a)
c.pushDigit(b + a)
case "-":
fmt.Printf("%d-%d\n", b, a)
c.pushDigit(b - a)
case "*":
fmt.Printf("%d*%d\n", b, a)
c.pushDigit(b * a)
case "/":
fmt.Printf("%d/%d\n", b, a)
c.pushDigit(b / a)
}
}
func (c *Calc) PushDigit(digit string) {
n, _ := strconv.Atoi(digit)
c.pushDigit(n)
}
func (c *Calc) pushDigit(n int) {
c.DigitQueue = append(c.DigitQueue, n)
}
func (c *Calc) popDigit() int {
var n int
n, c.DigitQueue = c.DigitQueue[len(c.DigitQueue)-1], c.DigitQueue[:len(c.DigitQueue)-1]
return n
}
func (c *Calc) Err(pos int, buffer string) {
fmt.Println("")
a := strings.Split(buffer[:pos], "\n")
row := len(a) - 1
column := len(a[row]) - 1
lines := strings.Split(buffer, "\n")
for i := row - 5; i <= row; i++ {
if i < 0 {
i = 0
}
fmt.Println(lines[i])
}
s := ""
for i := 0; i <= column; i++ {
s += " "
}
ln := len(strings.Trim(lines[row], " \r\n"))
for i := column + 1; i < ln; i++ {
s += "~"
}
fmt.Println(s)
fmt.Println("error")
c.IsError = true
}
func (c *Calc) Compute() {
if !c.IsError {
fmt.Printf("result: %d\n", c.popDigit())
}
}
func main() {
parser := &Parser{Buffer: "1+2*3-(4++5)"}
parser.Init()
err := parser.Parse()
if err != nil {
fmt.Println(err)
} else {
parser.Execute()
parser.Compute()
}
}
buffer内での行番号・カラム番号を割り出して、いい感じに表示するとこんな感じになります。本当は言語処理系としてはもっと詳細なエラーを出せればいいのでしょうけど、わりと面倒そうな予感がしています。いい方法を知っている人がいたら是非教えてください。
今回のところはひとまずここまでにしようと思います。