Lambdaカクテル

京都在住Webエンジニアの日記です

Invite link for Scalaわいわいランド

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

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

インストール

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

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

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

基本的な流れ

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

パーサの適用

(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")

$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) ぽぽぽぽぽ))))

簡単にパーサが作れたね!util.matchと組み合わせたら加工もしやすそう.ここからの発展形として,HTMLに変換して出力するなどが考えられる.gauche.parseoptモジュールを使ってコマンドラインを処理すれば,手製のコマンドをパパッと書くことだってできそうだ.

参考文献

blog.shin1x1.com

*1:「後続のパターンがマッチしない場合に一つ前のパターンに戻って、別のマッチ方法を試行するのをバックトラック(backtracking)と呼びます」 パフォーマンスを意識して正規表現を書く - Shin x Blog

★記事をRTしてもらえると喜びます
Webアプリケーション開発関連の記事を投稿しています.読者になってみませんか?