正規表現に見切りをつけるとき

Perl, Rubyなど手軽に使えるプログラミング言語に慣れてくると、あらゆるテキストデータの処理に正規表現(regular expression)を使ってしまいがちです。

けれど実は、正規表現の処理能力を超えるフォーマットというのが存在します。その典型的な例が、XMLやJSONのように、入れ子になったデータフォーマットです。

例えば、

(a, b, (c, d))

(a, b, (c, (d, e)))

というように、括弧がどんどん入れ子になっていく構造は、括弧のネストの深さを数えないと正しく解釈できません 。正規表現でも、一番外側の括弧の対応をとらえるために、/\(.*\)/、/\([^)]*\)/ などとはは書けますが、常に正しい括弧の対応をとっているとは限りませんし、もしうまくいったとしても、さらに内部の括弧をとらえるために、外側の括弧を取り除き、また同様の正規表現を内部の文字列に対して繰り返して適用する必要があります。

そして問題なのが、

(a, (b, c)), d, (e, f)

という文字列の場合。/\(.*\)/という正規表現では、以下のように色のついた範囲を拾ってしまいます。

(a, (b, c)), d, (e, f)

正規表現では、このようにちょっとしたデータ構造すら上手く構文解析できません。したがって、正規表現だけで文字列を処理する場合は、何らかの方法で括弧が2重、3重にならないように工夫する必要があります。（あるいは括弧内を再帰的に処理するプログラムを書くなど。）バイオ系のデータフォーマットでも、この正規表現の能力の限界を知らないがために、正規表現で処理できない入れ子になったデータを平気で書いてしまう人が多いので、手軽に処理したい場合は要注意です。（他にも2重引用符で囲まれた文字列の扱いも、正規表現では面倒な例です）

構文解析

では、正規表現の能力を超えるデータはどう扱えばいいのか？一番のお勧めは、ANTLRを使って字句解析(lexer)、構文解析(parser)するプログラムを生成する方法です。一昔前なら、lex/yacc、flex/bison, JavaCCなどしか選択肢がなかったのですが、今は断然ANTLRが便利です。ここでは、JSONを例にとって説明します。以下は、JSONで書かれた配列の中に配列がある構造です。

[0, [1, 2]]

字句解析では、これを、

LBracket([), Number(0), Comma(,), LBracket([), Number(1), Comma(,), Number(2), RBracket(]), RBracket(])

というようにトークン（文字列の単位, lexer ruleとして記述）に分解していきます。そして、これらのトークンにマッチする文法（parser rule)を定義します（以下の例は、説明のために他のデータ型については省いて簡潔に書きました）

array: LBracket Value (Comma Value)* RBracket;

value: Number | array;

ここでは、括弧 [ ] の中に、ValueをComma(,)でつなげて複数個書けるルールを定義しています。Valueとしては、数字(Number)以外に配列(array)も使えるので、配列の中に配列があるような入れ子になったデータ構造もこれで解析できます。

参考までに、僕がANTLRで作成したJSONの文法を紹介します。ANTLRの記述を覚えるコストはかかりますが、1ページ分の記述量でJSONのように構文が複雑なものも処理できるようになります。以下に挙げるのは、ANTLRのリファレンス（英語）と、その背景にある理論の教科書で、コンピューターサイエンスの学科では講義によく使われていてどれもお勧めです。Aho, Ullman先生らのドラゴンブック第2版（Ullman先生の息子さんがCGで表紙を作ったとか）は読みごたえ十分ですし、Apel先生の本ではVisitorパターンの使いどころのような、実装に近い話題にも触れられていて読みやすいです。稲葉君絶賛のParsing Techniquesなどもあります。

構文解析の実践としては、ANTLRをダウンロードするとサンプルの文法がたくさん付いてくるので、それを真似して書くのも習得への早道かと思います。一度ANTLRで文法を書くと、Perl/Ruby/C/C#/Javaなどの言語用のlexer/parserを生成できるようになるので、どの言語を使っている人にもお勧めです。しかし、まだ日本語のリファレンスがないのが構文解析の敷居を高くしている原因でしょう。この記事が素晴らしき構文解析の世界への足がかりになればいいなと思います。

（実用上の補足）

正規表現の中に自己を含めて循環定義できるRubyやPerlなどの処理系なら、入れ子もなんとか処理できるみたいです。以下はPerlのコード例。(「詳細 正規表現 第3版」を参考にしました）

$str = "(a (b, c)), (d), (e, f)";
$paren = qr/\([^()]*(?:(??{$paren})[^()]*)*\)/;
while ($str =~ /($paren)/g) {
print $1, "\n";
}

実行結果

(a (b, c))
(d)
(e, f)

括弧のパターンにマッチすると、その都度中身の正規表現がlazyに変わっていくというトリッキーな技です。このような正規表現は以下に述べるような形式言語理論上の正規表現の定義には含まれないのでご注意あれ。ただ、Perlで処理できるとしても、二重引用符とか、様々な括弧の種類に対応するように再帰型正規表現を書いていくと、ANTLRのparser ruleを書くのと似た状況になるとは思います。(追記）Perl6のRulesという機能では、ANTLRのような文法定義を書けるとか！ 入れ子が必要なときは、これを使いましょう、ということですね。

(コンピューターサイエンス的な補足）

細かい話をすると、正規表現は文脈自由文法というクラスのサブセットで、入れ子の構造をもった文法は、文脈自由だけれど正規表現ではありません。これは、pumping lemmaを使って証明できます。情報系の学科なら、計算量理論などの講義で習うはず。オートマトンにスタックをつけたプッシュダウンオートマトン（文脈自由文法と同じ表現能力を持つ）なら、このような入れ子をうまく処理できます。このあたりの話は「計算理論の基礎」という教科書に丁寧に書かれてあって（大学院入試の勉強のときにかなりお世話になりました）、コンピュータサイエンスの基礎のうち、オートマトン、NP完全問題など計算量にかかわる部分について学ぶのに優れた本です。（最近は第2版もでているようですが、3冊に分かれてしまって少々買いにくくなってしまいました。分けた方が持ちやすいのかな？）