GolangでS式の簡易パーサを書いてみた
言語処理100本ノック 2015のQ59でS式の解析の問題に出会ったので、パーサの自作なるものにチャレンジしたく、書いてみました。
前提
タスク
以下のS式を多分木にパースします。
(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))
わかりやすいように改行を入れると以下のようになります。
(a
(b
(d
(i)
(j)
)
(e)
(f
(k)
)
)
(c
(g)
(h
(l
(n)
)
(m)
)
)
)
木にすると以下なイメージです。
実装
Tree
まず、多分木を以下のように定義します。
type Tree struct {
Parent *Tree
Child []*Tree
Value string
}
root node
root nodeは親を持たないので、便宜的に自分自身を親として、コンストラクタを書きます。
func NewTree() *Tree {
t := &Tree{}
t.Parent = t
return t
}
実装
パーサの実装は以下です。
gistb526d47b5f834803b8d69ce4ccecbc63
Install
githubにあげてあるので以下でInstallできます。
# go get github.com/cipepser/goSExpression-sample/gose
Usage
以下のようにParse()でパースできます。
s := `(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))`
t, err := gose.Parse(s)
if err != nil {
log.Fatal(err)
}
結果の表示は簡易的ですが、以下のようにWalk()でできるようにしました。
// t.Walk() I am ' a ' my parent is ' a ' ------- I am ' b ' my parent is ' a ' ------- I am ' d ' my parent is ' b ' ------- I am ' i ' my parent is ' d ' ------- I am ' j ' my parent is ' d ' ------- I am ' e ' my parent is ' b ' ------- I am ' f ' my parent is ' b ' ------- I am ' k ' my parent is ' f ' ------- I am ' c ' my parent is ' a ' ------- I am ' g ' my parent is ' c ' ------- I am ' h ' my parent is ' c ' ------- I am ' l ' my parent is ' h ' ------- I am ' n ' my parent is ' l ' ------- I am ' m ' my parent is ' h ' -------
