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

情報処理学会 Web Site

書誌事項

タイトル別名
  • アトミックグループ デ カクチョウ サレタ セイキ ヒョウゲン ノ オートマトン エ ノ ヘンカン
  • Translating Regular Expressions Extended with Atomic Grouping to Automata

この論文をさがす

抄録

プログラミング言語における正規表現の拡張の1つとしてアトミックグループがある．アトミックグループとは，一度構文内でのマッチが成功し構文を抜けると，構文内へのバックトラックを禁止する構文である．本論文では，アトミックグループで拡張された正規表現のオートマトンへの変換を構成し，その正当性を証明する．拡張された正規表現の意味はSakumaらによるリストモナドを用いた定義により与える．アトミックグループで拡張された正規表現の表す言語を定義するために，集合モナドを用いた非決定構文解析器を定義する．アトミックグループによるマッチングは，オプションモナドを用いた決定性構文解析器によって表現する．この非決定性構文解析器と決定性構文解析器は相互再帰的な等式となっており，それによって拡張された正規表現の表す言語を表現する．この相互再帰的な等式をもとに，それと等価な先読み付きオートマトンを構成する．先読み付きオートマトンは先読みなしのオートマトンに変換することができるため，拡張された正規表現の表す言語は正則であるといえる．本研究で与えた変換をOCamlを用いて実装し，アトミックグループを含む正規表現をDFAに変換する実験を行った．実験には，PerlライブラリのアーカイブであるCPANで使用されている正規表現，およびMastering Regular Expressions 3rd Editionに収録されている正規表現を用いた．

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.

収録刊行物

関連プロジェクト

もっと見る

キーワード

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

問題の指摘

ページトップへ