著者

山本 篤 山口 和紀

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.7, pp.1756-1765, 2003-07-15

---

正規表現は,パターンマッチングを行うためのツールとして広く利用されている.しかし,さまざまな応用で拡張されてきたのにともない,次のような問題が出てきている.1)標準的に使われている正則集合による意味づけでは,後方参照がうまく定義できていない,2)オートマトンを用いたパターンマッチングの実装において,状態数やバックトラックの回数が爆発することがある,3)正規表現の積や差を直接的に利用できない.本研究では,このような問題を解決するために,正規表現関数と呼ぶ関数を導入する.正規表現関数は,記号列集合を入出力とする関数であり,マッチする記号列を消費して出力するものである.たとえば,正規表現 a* が a の繰返しにマッチすることは,その正規表現関数が,a*({ab aa b}) = {ab b aa a ε} という入出力関係を持つことで表される.これを拡張し,変数を扱えるようにすることで,後方参照も含めた正規表現を定義することができる.また,正規表現関数を用いたパターンマッチングの実装が可能であり,後方参照のない場合には計算量の爆発を避けることができ,比較実験でも優位なケースを確認した.さらに,正規表現の積と差を導入し,これらが正規表現関数によって簡単に実装できることを示す.最後に,正規表現の積や差を用いる応用例としてHTMLなどへのパターンマッチングをあげる.