模式识别与人工智能
Thursday, Apr. 3, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2006, Vol. 19 Issue (2): 173-178    DOI:
Papers and Reports Current Issue| Next Issue| Archive| Adv Search |
An AND/OR TreeBased Algorithm for Checking Pestilent Ambiguity in Regular Expressions
DENG XuBin1, ZHU YangYong2,3
1.School of Information, Zhejiang University of Finance and Economics, Hangzhou 310018
2.Department of Computing and Information Technology, Fudan University, Shanghai 200433
3.Shanghai Center for Bioinformation Technology, Shanghai 201203

Download: PDF (394 KB)   HTML (1 KB) 
Export: BibTeX | EndNote (RIS)      
Abstract  During the construction of regular expressions (REs) for applications, introducing some beneficial ambiguities may simplify RE construction, while leaving some pestilent ambiguities in the RE will harm the correctness of matching. In order to treat these two categories of ambiguities in different ways, an algorithm based on AND/OR tree that checks and locates the pestilent ambiguities in REs is proposed. The algorithm is helpful to reducing the workload of debugging REs. Experiments show that the algorithm outperforms the present ambiguitychecking algorithm based on automaton not only in time and space behaviors, but also in practicality. A visualized RE editing and debugging environment based on the algorithm has been applied to build the first online integrated biological data warehouse of China.
Key wordsRegular Expression (RE)      Matching      Ambiguity      AND/OR Tree     
Received: 12 November 2004     
ZTFLH: TP311.11  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
DENG XuBin
ZHU YangYong
Cite this article:   
DENG XuBin,ZHU YangYong. An AND/OR TreeBased Algorithm for Checking Pestilent Ambiguity in Regular Expressions[J]. , 2006, 19(2): 173-178.
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2006/V19/I2/173
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn