北航马帅团队 | 综述: 正则表达式正确性保证
正则表达式是对字符串操作的一种逻辑公式，许多程序设计语言都支持利用正则表达式进行字符串操作。在最近的六十年中，正则表达式逐渐从模糊而深奥的数学概念，发展成为在计算机各类工具和软件包应用中的主要功能。若正则表达式的定义出现错误，则可能导致使用它们的应用程序失败。因此，保证正则表达式的正确性是其实际应用的重要前提。北京航空航天大学马帅教授团队系统综述了正则表达式正确性保证的相关研究。相关成果已发表于IJAC，全文免费下载！
图片来自Springer (点击上图下载全文)
正则表达式(Regular expressions)具有较强的表达能力和灵活的定义方式，在计算机科学的许多领域具有广泛应用。其最早用于构造编译器的词法分析程序，近年来应用范围扩大至网络协议分析(network protocol analysis)、MySQL注入防御(MySQL injection prevention)、网络入侵检测(network intrusion detection)、XML数据模式描述(XML data specification)以及数据库查询(database querying)等，甚至在计算机领域以外也有正则表达式的应用，如在生物信息学领域使用正则表达式进行DNA序列比对。
正则表达式常用于计算机程序中的模式搜索(pattern searching)和字符串匹配(string matching)，是几乎所有现代编程语言的核心组件，经常出现在软件源代码中。研究表明，超过三分之一的JavaScript和Python项目至少包含一个正则表达式。
然而，最近的研究发现正则表达式很难理解、编写，并且容易出错。确实如此，由于正则表达式语法比较紧凑，并且使用大量元字符，导致开发人员在定义和使用时容易出错。即使是对于非常短的正则表达式，也很难读懂和理解其语义，对于可能包含100个字符或超过10个嵌套级别的复杂正则表达式来说，难度会更大。这都是软件开发人员面临的真实情况。例如，在一个备受开发者们欢迎的编程知识分享和学习网站上(stackoverflow.com)，超过20万个问题被标记为"regex"(正则表达式)。
若正则表达式的定义出现错误，则可能导致使用它们的应用程序出现缺陷。因此，保证正则表达式的正确性是其应用于实际的重要前提。事实上，一些研究者们也已经认识到该问题的重要性。然而，一项实证研究表明，在实际项目开发中使用的正则表达式有约80%未经测试，而在经过测试的正则表达式中，约有一半仅仅只使用了一个测试字符串。因此，亟需系统有效的方法和技术来确保正则表达式的正确性，以提高相应软件系统的质量。
本文综述了正则表达式正确性保证的相关研究，将现有工作分为不同类别，包括实证研究、测试串生成、自动合成与学习、静态检查与验证、可视化表示与解释及修复。针对每一类别，分别综述了主要的研究成果，比较了不同的方法，并且讨论了各自的优缺点。
本文其余部分组织如下：第2节介绍了正则表达式相关的基本知识，包括其不同方言、正确性含义和有限自动机。第3-8节基于不同的分类，分别对正则表达式正确性保证的相关工作进行了回顾。第9节总结并讨论了未来的研究方向。
Ensuring the Correctness of Regular Expressions: A Review
Li-Xiao Zheng, Shuai Ma, Zu-Xi Chen, Xiang-Yu Luo
https://link.springer.com/article/10.1007/s11633-021-1301-4
http://www.ijac.net/article/doi/10.1007/s11633-021-1301-4
特别感谢马帅教授团队对以上内容的审阅和修改！本文作者依次为华侨大学Zheng Li-Xiao(副教授)、北京航空航天大学马帅(教授)、华侨大学Chen Zu-Xi(讲师)、华侨大学Luo Xiang-Yu(副教授)。
特别推荐
专题征稿 | 智能系统的安全性 (12月10日截稿)中国科学院自动化研究所高层次人才招聘启事 | 长期有效【前沿】全球首个！自动化所研发图文音三模态预训练模型
重磅 | 全球计算机领域Top1000期刊 & 科学家榜单发布@全体科研人，"十四五"规划圈出了攻关重点！直播回放 | 公茂果主讲：深度神经网络的结构优化
回放 & PPT | 澳科学院院士Brian Anderson最新报告
IJAC 2020高被引论文 & 优秀审稿人重磅 | 2021年国际学术会议参考列表
全球前列！IJAC"世界期刊影响力指数(WJCI)"喜人
最新 | 《2020全球工程前沿》全文
最新 | 2020研究前沿及热点解读
好文聚焦
陈伟能团队 | 综述: 面向复杂网络中社会传播问题的演化计算方法韩清龙团队| 综述: 动态事件触发的控制与估计毋立芳团队 | 综述：视频中的群体行为识别基于神经架构搜索技术(NAS)的2D&3D掌纹和掌静脉识别
张笑钦团队 | 综述：基于深度学习的视觉跟踪方法进展
基于机器学习探秘神经科学，解码思想、记忆、情绪......高效+高精度 | 汽车尾气排放趋势预测新框架
综述 | 进化计算在大规模多目标优化问题中的进展公茂果团队 | 综述：计算智能在遥感图像配准中的应用新模型！模拟人眼预测图像质量，失真也不怕新兴技术 | 经典CNN对2D&3D掌纹及掌静脉识别的性能评估
点击"阅读原文"下载全文