著者

山本 篤 山口 和紀

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

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

参考文献数

14

---

正規表現は,パターンマッチングを行うためのツールとして広く利用されている.しかし,さまざまな応用で拡張されてきたのにともない,次のような問題が出てきている.1)標準的に使われている正則集合による意味づけでは,後方参照がうまく定義できていない,2)オートマトンを用いたパターンマッチングの実装において,状態数やバックトラックの回数が爆発することがある,3)正規表現の積や差を直接的に利用できない.本研究では,このような問題を解決するために,正規表現関数と呼ぶ関数を導入する.正規表現関数は,記号列集合を入出力とする関数であり,マッチする記号列を消費して出力するものである.たとえば,正規表現 a* が a の繰返しにマッチすることは,その正規表現関数が,a*({ab aa b}) = {ab b aa a ε} という入出力関係を持つことで表される.これを拡張し,変数を扱えるようにすることで,後方参照も含めた正規表現を定義することができる.また,正規表現関数を用いたパターンマッチングの実装が可能であり,後方参照のない場合には計算量の爆発を避けることができ,比較実験でも優位なケースを確認した.さらに,正規表現の積と差を導入し,これらが正規表現関数によって簡単に実装できることを示す.最後に,正規表現の積や差を用いる応用例としてHTMLなどへのパターンマッチングをあげる.Regular expressions have been used widely for pattern matching.However the following problems are getting serious in some applications.1) The definition of regular expressions cannot be extended to back reference,which is a popular extension of regular expressions.2) The implementations of pattern matching in automata suffer from the explosion of time or space complexity for some regular expression patterns.3) In the conventional regular expressions,we cannot use intersection and difference operators, which are useful in some applications.In this paper, we introduce a ``regular expression function'' from a set of strings to a set of strings.This function eliminates matching prefixes with given regular expressions from the input strings and outputs the remaining postfixes.For example, a({ab,aa,b})={ab,b,aa,a,ε}.This function can be extended to give a semantics to regular expressions with back references.Then,we show that we can perform pattern matching by interpreting the regular expression function directly without the explosion of time and/or space complexity,which is confirmed by our preliminary implementation.We also introduce intersection and difference operators and show that the regular expression function can be extended to handle these operators easily.Finally, we briefly show some possible applications of the operators.