正規表現における非包含オペレータの提案

情報処理学会

書誌事項

タイトル別名
  • Absent Operator for Regular Expression
公開日
2008-01-08
資源種別
conference paper
公開者
情報処理学会

説明

正規表現の拡張として非包含オペレータを提案する。正規表現は昨今スクリプト言語等で活用されているが、もともと形式言語理論により定義されたものである。形式言語理論においては、正規言語における補集合の閉方性が証明されており、ある正規表現から導出できない文字列すべてだけを導出できる正規表現が存在することが知られている。補集合はC言語のコメントやCR LF終端の行などを表現するのに役に立つが、現実にそのような正規表現を構成するのは繁雑であり難しい。そこで正規表現エンジンで補集合オペレータを直接サポートすることが考えられるが、これはPerl, Ruby等の既存の正規豹変エンジンで採用されているバックトラッキングを用いるアルゴリズムでは効率よく実装できない。また、既存の正規表現の拡張には最短一致の繰り返し、バックトラックの抑制、否定先読みなど容易な記述を可能とするものもあるが、それらは理論による適切な意味付けができない。そこで本論文では、既存のバックトラック型の正規表現エンジン上で容易に効率よく実装でき、かつ、形式言語理論による適切な意味付けが可能は非包含オペレータを提案する。

This paper proposes a new operator, absent operator, for regular expressions. Recently, regular expressions are widely used with scripting languages. There are several usages which is too difficult to write down in a regular expression: a comment in C language, CR LF terminated lines, etc. They are possible to represented by a regular expression because the formal language theory proves complement of a regular language is also regular. The absent operator eases them. The operator is easy to implement on a backtracking regular expression engine and it has proper semantics on the theory unlike lazy match, atomic grouping, negative lookahead.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ