Complexity Analysis of Extended Regular Expression Matching
Complexity Analysis of Extended Regular Expression Matching
复制标题
扩展正则表达式匹配的复杂度分析
DOI：
10.11309/jssst.38.2_53
复制
发表时间：
2021
影响因子：
--
通讯作者：
南出靖彦
中科院分区：
文献类型：
--
作者：
高橋和也;南出靖彦
文字列の検索等に広く用いられる正規表現マッチングはその多くがバックトラックに基づくアルゴリズムで実装されており, 対象文字列の長さに対して線形時間でマッチングを完了できない場合がある. これを事前に検知するために, マッチングに要する計算量を静的解析する手法が複数の先行研究によって提案されている. 本研究では先行研究を拡張し, 先読みや後方参照など, 現実のソフトウェアで使用されている拡張された正規表現に対しても解析が行える手法を提案する. さらに, 既存の解析アルゴリズムを高速化し, より実用的な速度で解析を行える手法を提案する. そして, これらの改良を施した計算量解析のツールを Scala で実装し, Weideman らによる既存のツールよりも多くの正規表現が解析できることを実験により確認した.