アトミックグループで拡張された正規表現のオートマトンへの変換

• Item type: Trans(1)
• 公開日: 2013-01-24
• タイトル: アトミックグループで拡張された正規表現のオートマトンへの変換
• タイトル / 言語: en
• タイトル: Translating Regular Expressions Extended with Atomic Grouping to Automata
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] 正規表現，オートマトン，モナド
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻
• 著者所属: 筑波大学システム情報系情報工学域
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Division of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba
• 著者名: 杉山, 聡; 南出, 靖彦
• 著者名(英): Satoshi, Sugiyama; Yasuhiko, Minamide
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: プログラミング言語における正規表現の拡張の1つとしてアトミックグループがある．アトミックグループとは，一度構文内でのマッチが成功し構文を抜けると，構文内へのバックトラックを禁止する構文である．本論文では，アトミックグループで拡張された正規表現のオートマトンへの変換を構成し，その正当性を証明する．拡張された正規表現の意味はSakumaらによるリストモナドを用いた定義により与える．アトミックグループで拡張された正規表現の表す言語を定義するために，集合モナドを用いた非決定構文解析器を定義する．アトミックグループによるマッチングは，オプションモナドを用いた決定性構文解析器によって表現する．この非決定性構文解析器と決定性構文解析器は相互再帰的な等式となっており，それによって拡張された正規表現の表す言語を表現する．この相互再帰的な等式をもとに，それと等価な先読み付きオートマトンを構成する．先読み付きオートマトンは先読みなしのオートマトンに変換することができるため，拡張された正規表現の表す言語は正則であるといえる．本研究で与えた変換をOCamlを用いて実装し，アトミックグループを含む正規表現をDFAに変換する実験を行った．実験には，PerlライブラリのアーカイブであるCPANで使用されている正規表現，およびMastering Regular Expressions 3rd Editionに収録されている正規表現を用いた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Atomic grouping is one of the extensions of regular expressions used in programing languages. When a word is matched against an atomic group, the construct disables backtracking into the group. In this paper, we translate regular expressions extended with atomic grouping into finite automata and prove the correctness of the translation. The semantics of extended regular expressions is given as a nondeterministic parser defined with the list monad. Then, the language of an extended regular expression is represented by using mutually recursive functions: a nondeterministic parser defined with the set monad and a deterministic parser defined with the option monad. We construct finite automata with regular lookahead based on their definitions and translate them into finite automata without lookahead by a standard construction. We have implemented this translation in OCaml, and conducted experiments of translating regular expressions containing atomic groups into DFA. For the experiments, we use regular expressions that appear in CPAN (Comprehensive Perl Archive Network) and Mastering Regular Expressions 3rd Edition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 6, 号 1, p. 17-26, 発行日 2013-01-24
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会