SRE

いわゆる正規表現をＳ式で表す試みとして知られているのは Olin Shivers 氏が提案した SRE です。 Scsh という処理系で始まりました。

SRE はほぼそのまま SRFI-115 に取り込まれています。これの有力な実装は Alex Shinn 氏の IrRegex です。 (というよりも IrRegex を元に SRFI-115 を記述したといった方がより実態に即した表現かもしれません。)

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

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

今のところは SRFI-115 をすぐに利用できる (処理系のインストールパッケージに含んでいる) 処理系は Larceny と Sagittarius と Chibi があります。

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

(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 を使っているのを目にしたことはあると思いますが、実際にそれのパーサを実装するにはどんな方法があるでしょうか？もちろん、素直にプログラムを書き下したり、 LALR パーサジェネレータとしてよく知られている Yacc のように BNF とアクションからソースコードを生成するという方法はありますが、パーサコンビネータもよく使われています。

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

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

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

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

Guile の (ice-9 peg)
Chicken の Prcc
Racket の peg/peg
Gauche の parser.peg

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

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

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

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

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

(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 という構文解析アルゴリズムもあります。 Packrat は PEG に基づいた構文解析をするものですが、解析途中の結果をあらゆる箇所でメモ化することでバックトラックを抑制します。バックトラックが抑制されるので解析にかかる時間が線形時間になるという特徴があります。

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

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

SRE とパーサコンビネータ

SRE

パーサコンビネータ

Packrat