アトミックグループで拡張された正規表現のオートマトンへの変換
スポンサーリンク
概要
- 論文の詳細を見る
プログラミング言語における正規表現の拡張の1つとしてアトミックグループがある.アトミックグループとは,一度構文内でのマッチが成功し構文を抜けると,構文内へのバックトラックを禁止する構文である.本論文では,アトミックグループで拡張された正規表現のオートマトンへの変換を構成し,その正当性を証明する.拡張された正規表現の意味はSakumaらによるリストモナドを用いた定義により与える.アトミックグループで拡張された正規表現の表す言語を定義するために,集合モナドを用いた非決定構文解析器を定義する.アトミックグループによるマッチングは,オプションモナドを用いた決定性構文解析器によって表現する.この非決定性構文解析器と決定性構文解析器は相互再帰的な等式となっており,それによって拡張された正規表現の表す言語を表現する.この相互再帰的な等式をもとに,それと等価な先読み付きオートマトンを構成する.先読み付きオートマトンは先読みなしのオートマトンに変換することができるため,拡張された正規表現の表す言語は正則であるといえる.本研究で与えた変換をOCamlを用いて実装し,アトミックグループを含む正規表現をDFAに変換する実験を行った.実験には,PerlライブラリのアーカイブであるCPANで使用されている正規表現,およびMastering Regular Expressions 3rd Editionに収録されている正規表現を用いた.
- 2013-01-24
著者
関連論文
- Rubyプログラムの制御フロー解析とその健全性の証明
- 特集「プログラミング及びプログラミング言語」の編集にあたって(プログラミング及びプログラミング言語)
- 実行可能なコンパイラの形式化と検証
- 実行可能なコンパイラの形式化と検証
- 実行可能なコンパイラの形式化と検証
- 「情報処理学会論文誌 : プログラミング」の編集について
- 多相レコード型に基づくRubyプログラムの型推論
- Cプログラムの検証ツールCaduceus(ソフトウェア紹介)
- POPL '96会議報告
- アトミックグループで拡張された正規表現のオートマトンへの変換
- 参照カウントに対応したソフトウェアトランザクショナルメモリの実装