-
- TAKAHASHI Kazuya
- School of Computing, Tokyo Institute of Technology
-
- MINAMIDE Yasuhiko
- School of Computing, Tokyo Institute of Technology
Bibliographic Information
- Other Title
-
- 拡張正規表現マッチングの計算量解析
- カクチョウ セイキ ヒョウゲン マッチング ノ ケイサンリョウ カイセキ
Search this article
Abstract
<p>Regular expression matching often used for searching and replacing strings are mostly implemented with backtracking. This causes that matching may not be completed in linear time in the length of a string. Previous works developed analyses to detect such regular expressions based on ambiguity analysis of nondeterrministic finite automata and growth rate analysis of string-to-tree transducers. We incorporate the techniques developed in the previous works and extend the analysis for extended regular expressions including lookahead and back-reference. We have also improved the core part of the analysis and implemented our analysis tool in Scala. It is shown that our tool can analyze more regular expressions than the existing tool of Weideman et al.</p>
Journal
-
- Computer Software
-
Computer Software 38 (2), 2_53-2_70, 2021-04-23
Japan Society for Software Science and Technology
- Tweet
Details 詳細情報について
-
- CRID
- 1390288457807459328
-
- NII Article ID
- 130008055711
- 40022575654
-
- NII Book ID
- AN10075819
-
- NDL BIB ID
- 031471027
-
- ISSN
- 02896540
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- NDL
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed