gauche/schemeのparser.pegモジュールを使ってSlackの会話をパースした

Gaucheのパーサジェネレータ parser.peg の使い方のメモ．

インストール
基本的な流れ
パーサの適用
パーサの生成 (パーサコンビネータの使用)
- $char
- $one-of
- $many
- $seq
- $do
- $lift
- $sep-by
- $alternate
- $between
- $or
試作 - Slack会話のパース
参考文献

インストール

投稿時点の最新バージョンであるGauche 0.9.5ではparser.pegは標準添付されている．

Gaucheは拡張が豊富なことで人気のscheme処理系である．作者はハワイ在住の日本人エンジニアshiro kawai氏で，日本語・UTF-8に対応しており頼もしい．

$ brew install gauche
$ gosh
gosh> (use parser.peg)
#<undef>
gosh> ^D
$

基本的な流れ

パーサコンビネータを利用してパーサを生成する
peg-parse-string もしくは peg-parse-port を使ってパーサに文字列(ポート)を適用する
パース結果が得られる

パーサの適用

(use parser.peg)
; TODO: implement parser...
(print (peg-parse-string PARSER "string")) ; => parsed result

peg-parse-port を使うと文字列ではなくポートに対してパースができる．

パーサの生成 (パーサコンビネータの使用)

各コンビネータの詳細はソースファイルをあたることで参照できる．

以下，よく使うパーサコンビネータを紹介する．サンプルコードでは全て冒頭で(use parser.peg) を宣言しているものとする．

`$char`

ある文字にマッチし，その文字を返す．

コンビネータにマッチしないときはエラーとなる．他のパーサコンビネータでも同様である．

($char #\!) ; !にマッチする
(peg-parse-string ($char #\!) "!") ; => #\!
(peg-parse-string ($char #\!) "?") ; => *** PARSE-ERROR: expecting #\! at 0, but got #\?

`$one-of`

文字集合のうちどれか一文字にマッチし，その文字を返す．

($one-of #[a-z]) ; abcdefghijklmnopqrstuvwxyz のどれかにマッチする
(peg-parse-string ($one-of #[a-z]) "g") ; => #\g

`$many`

コンビネータの繰り返しにマッチし，リストを返す．最小文字数と最大文字数を指定できる．

最大文字数を超過しても，パーサはエラーを返さないことに注意．パーサは最大文字数に到達したことで満足し，文字列を読み取るのを止める．正規表現と同じである．確実に最大文字数を守らせたいならば，コンビネータ eof を組み合わせるべきである．

($many ($one-of #[a-z])) ; a-zの繰り返しにマッチする
(peg-parse-string ($many ($one-of #[a-z])) "hoge") ; => (#\h #\o #\g #\e)
;; 最低5文字を要求する
(peg-parse-string ($many ($one-of #[a-z]) 5) "hoge") ; => *** PARSE-ERROR: expecting #[a-z] at 4, but got #<eof>
;; 5〜7文字を要求する
(peg-parse-string ($many ($one-of #[a-z]) 5 7) "hogera") ; => (#\h #\o #\g #\e #\r #\a)
;; 文字数を超過するとコンビネータは満足して探索をやめる．エラーにはならない
(peg-parse-string ($many ($one-of #[a-z]) 5 7) "hogerarara") ; => (#\h #\o #\g #\e #\r #\a #\r)

`$seq`

コンビネータが指示した順に並んでいるときにマッチする．順の最後のコンビネータの返り値を返す．

; $count: ちょうどその回数にマッチする
; digit: デフォルトで使用できるコンビネータ(文字集合ではないことに注意)．
;        任意の数字にマッチする．
;        newline, space, spaces, alnumなどの仲間もある
; $c: $charのエイリアス
($seq ($count digit 3) ($c #\-) ($count digit 4)) ; 郵便番号にマッチさせる
(peg-parse-string ($seq ($count digit 3) ($c #\-) ($count digit 4)) "123-4567") ; => (#\4 #\5 #\6 #\7)

`$do`

$return と組合せて使う．マッチしたコンビネータから値を取り出し，加工して取り出す．

コンビネータを名前に束縛する際，コンビネータであることが分かりやすいように接頭辞%を付している．

(define %head ($count digit 3))
(define %tail ($count digit 4))
(define %postal
  ($do
    [h %head] ; %headが返す値がhに束縛される
    [dash ($c #\-)]
    [t %tail] ; %tailが返す値がtに束縛される
    ($return (list (list->string h) #"~dash" (list->string t))))) ; h, dash, tを利用して値を作り出す．$returnした値が$doが返す値になる
(peg-parse-string %postal "123-4567") ; => ("123" "-" "4567")

`$lift`

$do のモナディックなシンタックスシュガー．

; ($lift f parser) == ($do [x parser] ($return (f x)))
(define %head ($lift list->string ($count digit 3))) ; 3文字の数字にマッチし，文字のリストを list->stringに渡し，得られた値を返す
(define %dash ($lift ($ list->string $ list $) ($c #\-))) ; $はパーサとは関係ないマクロ[1]
(define %tail ($lift list->string ($count digit 4)))
(define %postal
  ($lift list %head %dash %tail)) ; %head, %dash, %tail それぞれの値が3引数としてlistに渡され，その結果が返り値となる
(define %postal-naive
  ($do [h %head] [d %dash] [t %tail] ($return (list h d t)))) ; 上掲を$doで書き直したもの

(peg-parse-string %postal "123-4567") ; => ("123" "-" "4567")
(peg-parse-string %postal-naive "123-4567") ; => ("123" "-" "4567")

[1] Gauche ユーザリファレンス: 手続きを作る

`$sep-by`

デリミタとなるコンビネータで区切られた文字列にマッチし，デリミタを除いたリストを返す．

; $optionalは省略可能であることを示すコンビネータ．
(define %comma ($seq ($c #\,) ($optional space)))
(define %number ($lift ($ string->number $ list->string $) ($many digit 1)))
(define %comma-separated ($sep-by %number %comma))
(peg-parse-string %comma-separated "1, 2,3,4, 5, 6") ; => (1 2 3 4 5 6)

`$alternate`

おおむね$sep-byと同じ挙動だが，マッチしなかった場合の挙動が異なる．ちょっとこれは説明しづらい．マッチしなかったとき最後のデリミタの直前からバックトラック*1を行うので，デリミタが複数の意味で使われうるシチュエーションに適している．また，デリミタを捨てない．

(define %comma ($c #\,))
(define %period ($c #\.))
(define %word ($many upper 1))
(define %trailing-phrase ($do [us %word] [_ %comma] ($return (list->string us))))
(define %last-phrase ($do [_ space] [us %word] [_ %period] ($return (list->string us))))
(define %enumeration ($lift cons ($alternate %trailing-phrase space) %last-phrase))
(peg-parse-string %enumeration "VENI, VIDI, VICI.") ; => (("VENI" #\space "VIDI") . "VICI")

`$between`

2つのコンビネータに挟まれたものにマッチし，挟まれていた値を返す．

(define %number ($lift ($ string->number $ list->string $) ($many digit 1)))
(define %parenthesized-number ($between ($c #\() %number ($c #\))))
(peg-parse-string %parenthesized-number "(128)") ; => 128

`$or`

自明なので省略．他にも様々なコンビネータが用意されているので，コードを見て遊んでみてほしい．

試作 - Slack会話のパース

学んだことを形にしてみるために，parser.pegを使ってSlackのログパーサーを作ってみた．50行ほど．

ログはクライアントからコピペしてきた．ツールがうまく動かずに苦しんでいる様子が克明に記録されている．

github.com

(use parser.slack)
(print (slack-parse "windymelt [5:31 PM] 
ぽへー

[5:31]  
ちょっちQKしよ

windymelt [5:40 PM] 
ぽえ〜〜〜

[5:40]  
ぽよよよよ

[5:40]  
びー

windymelt [7:14 PM] 
ぽよ〜〜〜〜

[7:14]  
ぽぽぽぽぽ
"))

((windymelt
  (((5 31 PM) ぽへー)
   ((5 31 #f) ちょっちQKしよ)))
 (windymelt
  (((5 40 PM) ぽえ〜〜〜)
   ((5 40 #f) ぽよよよよ)
   ((5 40 #f) びー)))
 (windymelt
  (((7 14 PM) ぽよ〜〜〜〜)
   ((7 14 #f) ぽぽぽぽぽ))))