WEKO3
-
RootNode
アイテム
正規表現関数による正規表現の拡張とそのパターンマッチングへの応用
https://ipsj.ixsq.nii.ac.jp/records/11191
https://ipsj.ixsq.nii.ac.jp/records/1119164e5f010-cf1a-4d34-9725-76f7499a726b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL4407011.pdf (202.1 kB)
|
Copyright (c) 2003 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2003-07-15 | |||||||
| タイトル | ||||||||
| タイトル | 正規表現関数による正規表現の拡張とそのパターンマッチングへの応用 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Regular Expression Function for Extending Regular Expressions and Its Application to Pattern Matching | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| その他タイトル | ||||||||
| その他のタイトル | 自然言語 | |||||||
| 著者所属 | ||||||||
| 東京大学大学院総合文化研究科広域科学専攻広域システム科学系 | ||||||||
| 著者所属 | ||||||||
| 東京大学大学院総合文化研究科広域科学専攻広域システム科学系 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Graphic and Computer Sciences, Graduate School of Arts and Sciences, The University of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Graphic and Computer Sciences, Graduate School of Arts and Sciences, The University of Tokyo | ||||||||
| 著者名 |
山本, 篤
山口, 和紀
× 山本, 篤 山口, 和紀
|
|||||||
| 著者名(英) |
Atsushi, Yamamoto
Kazunori, Yamaguchi
× Atsushi, Yamamoto Kazunori, Yamaguchi
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 正規表現は，パターンマッチングを行うためのツールとして広く利用されている．しかし，さまざまな応用で拡張されてきたのにともない，次のような問題が出てきている．1)標準的に使われている正則集合による意味づけでは，後方参照がうまく定義できていない，2)オートマトンを用いたパターンマッチングの実装において，状態数やバックトラックの回数が爆発することがある，3)正規表現の積や差を直接的に利用できない．本研究では，このような問題を解決するために，正規表現関数と呼ぶ関数を導入する．正規表現関数は，記号列集合を入出力とする関数であり，マッチする記号列を消費して出力するものである．たとえば，正規表現 a* が a の繰返しにマッチすることは，その正規表現関数が，a*({ab aa b}) = {ab b aa a ε} という入出力関係を持つことで表される．これを拡張し，変数を扱えるようにすることで，後方参照も含めた正規表現を定義することができる．また，正規表現関数を用いたパターンマッチングの実装が可能であり，後方参照のない場合には計算量の爆発を避けることができ，比較実験でも優位なケースを確認した．さらに，正規表現の積と差を導入し，これらが正規表現関数によって簡単に実装できることを示す．最後に，正規表現の積や差を用いる応用例としてHTMLなどへのパターンマッチングをあげる． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 44, 号 7, p. 1756-1765, 発行日 2003-07-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
