GolangでS式の簡易パーサを書いてみた

言語処理100本ノック 2015のQ59でS式の解析の問題に出会ったので、パーサの自作なるものにチャレンジしたく、書いてみました。

前提

  • リテラルstringのみであるとする
  • パースした結果は多分木に格納する1

タスク

以下の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)
    )
  )
)

木にすると以下なイメージです。

f:id:cipepser:20170826135824p:plain

実装

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 '
-------

Reference


  1. あとで思えば抽象構文木にしたほうがよかった