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

• Item type: Symposium(1)
• 公開日: 2008-01-08
• タイトル: 正規表現における非包含オペレータの提案
• タイトル / 言語: en
• タイトル: Absent Operator for Regular Expression
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 産業技術総合研究所情報技術研究部門
• 著者所属(英): en
• 著者所属(英): Information Technology Research Institute, National Institute of Advanced Industrial Science and Technology (AIST)
• 著者名: 田中, 哲
• 著者名(英): Akira, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正規表現の拡張として非包含オペレータを提案する。正規表現は昨今スクリプト言語等で活用されているが、もともと形式言語理論により定義されたものである。形式言語理論においては、正規言語における補集合の閉方性が証明されており、ある正規表現から導出できない文字列すべてだけを導出できる正規表現が存在することが知られている。補集合はC言語のコメントやCR LF終端の行などを表現するのに役に立つが、現実にそのような正規表現を構成するのは繁雑であり難しい。そこで正規表現エンジンで補集合オペレータを直接サポートすることが考えられるが、これはPerl, Ruby等の既存の正規豹変エンジンで採用されているバックトラッキングを用いるアルゴリズムでは効率よく実装できない。また、既存の正規表現の拡張には最短一致の繰り返し、バックトラックの抑制、否定先読みなど容易な記述を可能とするものもあるが、それらは理論による適切な意味付けができない。そこで本論文では、既存のバックトラック型の正規表現エンジン上で容易に効率よく実装でき、かつ、形式言語理論による適切な意味付けが可能は非包含オペレータを提案する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌情報: 第49回プログラミング･シンポジウム予稿集; 巻 2008, p. 55-64, 発行日 2008-01-08
• 出版者 / 言語: ja
• 出版者: 情報処理学会