SRE とパーサコンビネータ

文字列にマッチする正規表現は広く使われていますが、それをより広く、何らかの列に対しても行えるようにする提案を読みました。

- [正規表現エンジンの原始的なやつ](https://qiita.com/nakataSyunsuke/items/32f52a31a09010f6deef)
- [正規表現エンジンの原始的なやつ ― 拡張: 汎用の要素クラス、汎用の位置指定メタ要素](https://qiita.com/nakataSyunsuke/items/c5d65a69cc484f0d8e3f)
- [正規表現エンジンの原始的なやつ ― 拡張: 後方参照](https://qiita.com/nakataSyunsuke/items/d3051ebdbda5f6ba21b3)

これが特徴的なのは

- 条件をＳ式で表す
- 対象が文字列とは限らない
- 条件に通常の手続きを埋め込むことが出来る

という点だと思います。

私はこの特徴が SRE やパーサコンビネータと似ていると感じたので紹介することにしました。 以下を踏まえればより発展させられる余地があると考えます。

# SRE

いわゆる正規表現をＳ式で表す試みとして知られているのは Olin Shivers 氏が提案した [SRE](https://scsh.net/docu/post/sre.html) です。 [Scsh](https://scsh.net/) という処理系で始まりました。

SRE はほぼそのまま [SRFI-115](https://srfi.schemers.org/srfi-115/srfi-115.html) に取り込まれています。 これの有力な実装は Alex Shinn 氏の [IrRegex](http://synthcode.com/scheme/irregex/) です。 (というよりも IrRegex を元に SRFI-115 を記述したといった方がより実態に即した表現かもしれません。)

SRE はあくまでも正規表現をＳ式表現に置き換えただけのものであり、機能を拡張するものではありませんが、 Scheme (またはその他の LISP 系言語) で柔軟に条件を記述するには文字列よりもやりやすい場合は多いでしょう。

ちなみに、後方参照の機能は含んでいます。

今のところは SRFI-115 をすぐに利用できる (処理系のインストールパッケージに含んでいる) 処理系は [Larceny](http://www.larcenists.org/) と [Sagittarius](http://ktakashi.github.io/) と [Chibi](http://synthcode.com/wiki/chibi-scheme) があります。

Sagittarius でちょっとした利用例を書いてみます。

```scheme
(import (rnrs)
        (srfi :115))

(define uy-text
  "父が言った「うちはうち、よそはよそぢゃけー」。")

(define uy-regex
  (rx (-> uchi-yoso (or "よそ" "うち")) "は" (backref uchi-yoso)))

(let* ((m (regexp-search uy-regex uy-text))
       (m-r (list 
             (regexp-match-submatch-start m 0)
             (regexp-match-submatch-end m 0)))
       (m-a (regexp-match->list m)))
  (display "match-range: ")
  (write m-r)
  (newline)

  (display "match-text: ")
  (display (regexp-match-submatch m 0))
  (newline)

  (display "submatch-range: ")
  (write (list (regexp-match-submatch-start m 'uchi-yoso)
               (regexp-match-submatch-end m 'uchi-yoso)))
  (newline)

  (display "submatch-text: ")
  (display (regexp-match-submatch m 'uchi-yoso))
  (newline))
```

# パーサコンビネータ

文法の定義の仕方としては文法を表現するのには [BNF](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95) を使っているのを目にしたことはあると思いますが、実際にそれのパーサを実装するにはどんな方法があるでしょうか？ もちろん、素直にプログラムを書き下したり、 LALR パーサジェネレータとしてよく知られている [Yacc](http://dinosaur.compilertools.net/yacc/index.html) のように BNF とアクションからソースコードを生成するという方法はありますが、パーサコンビネータもよく使われています。

パーサコンビネータというのは、ごく小さな、たとえば「次は××の条件を満たす一文字を受け付ける」といったような単純な機能のパーサを高階関数やマクロを利用して組み立てて全体として文法を表現しようとするものです。 特に [PEG](https://ja.wikipedia.org/wiki/Parsing_Expression_Grammar) という形式を基礎にしたパーサコンビネータが良く使われています。

PEG は BNF よりも単純です。 BNF で `|` で表される文法、つまり「これらの内のどれか」は PEG では `/` で表し「先に書かれている方で貪欲にマッチする」という規則です。 この規則によって、曖昧さが排除され、唯一無二の構文木を決定できます。 そのかわり、 (私は学問的な背景には明るくないので正確なところを知りませんが) BNF ほどには複雑な文法を表現できないようです。

パーサコンビネータは正規表現とは少し異なりますが、構造を持った文字列を処理するには手軽で強力な方法として選択肢に上げても良いでしょう。

ざっと Scheme での実装を探してみると以下のようなものが見つかります。

- Guile の [`(ice-9 peg)`](https://www.gnu.org/software/guile/manual/html_node/PEG-Parsing.html#PEG-Parsing)
- Chicken の [`Prcc`](http://wiki.call-cc.org/eggref/4/prcc)
- Racket の [`peg/peg`](https://docs.racket-lang.org/peg/index.html)
- Gauche の [`parser.peg`](https://github.com/shirok/Gauche/blob/master/ext%2Fpeg%2Fpeg.scm)

私は Gauche に慣れているので Gauche の PEG パーサコンビネータを用いて、先の例にあてはめてみましょう。 `"うちはうち"` または `"よそはよそ"` が最初に見つかった場所で文字列を分割するようなものはこう書くことが出来ます。

```scheme
(use parser.peg)

(define %uy
  ($do (x ($or ($try ($string "うち")) ($string "よそ")))
       (y ($char #\は))
       (z ($string (rope->string x)))
       ($->rope ($return
                 (list x y z)))))

(define parser
  ($do (before ($->rope ($many-till anychar %uy)))
       (body %uy)
       (after ($->rope ($many-till anychar eof)))
       ($return (list before body after))))

(define uy-text
  "父が言った「うちはうち、よそはよそぢゃけー」。")

(write (peg-parse-string parser uy-text))
```

実行結果はこのようになるはずです。

```
("父が言った「" "うちはうち" "、よそはよそぢゃけー」。")
```

そしてパーサコンビネータの考え方は文字列以外にも適用可能です。  リスト内の奇数を `*` に置き換えるような文法はこのように書けます。

```scheme
(use parser.peg)

(define hide-odd-numbers-syntax
  ($many
   ($or ($seq ($satisfy odd? "odd number") ($return '*))
        anychar)))

(define ns '(48 82 33 73 86 80 21 84 3 15 92 59 61 49 64 33 52 84 58 77))

(write (peg-run-parser hide-odd-numbers-syntax ns))
```

結果はこのようになります。

```
(48 82 * * 86 80 * 84 * * 92 * * * 64 * 52 84 58 *)
```

残念ながら現時点での Gauche の `parser.peg` モジュールはドキュメントが用意されていません。 非公式扱いとなっています。 将来的に使い方が少し変更される可能性もあります。 ただ、このモジュールはコメントを除くと五百数十行程度の小さなプログラムなので、読み解くのはそれほど難しくはありません。 パーサコンビネータを理解するための教材としてはとても良いと思います。

# Packrat

余談ですが、 [Packrat](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%83%E3%82%AF%E3%83%A9%E3%83%83%E3%83%88%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90) という構文解析アルゴリズムもあります。 Packrat は PEG に基づいた構文解析をするものですが、解析途中の結果をあらゆる箇所でメモ化することでバックトラックを抑制します。 バックトラックが抑制されるので解析にかかる時間が線形時間になるという特徴があります。

時間オーダーが線形になるとは言うものの、途中結果を保存する処理のために相応の時間がかかること、また、当然ながら保存のためにメモリを消費することもあって、オーダーを抑える以上に係数が膨れ上がってしまうようです。 かなり複雑な文法に対しては効果的なこともあるようですが、処理時間の短縮に繋がる場面は限られるかもしれません。

実際、 JSON のパーサでベンチマークを取ってみたことがあるのですが、 Packrat を適用するとパースにかかる時間が 20 倍～ 30 倍程度になってしまいました。 (JSON は LL(1) 文法なので元々バックトラックがほとんど発生しません。 これはメモ化処理が全て無駄になる場合の事例と考えて良いと思います。)