支持计数与无序的扩展表达式的理论问题与应用研究

Extended regular expressions with counting and interleaving are widely used in practice. However the related theoretical studies for this kind of expressions currently cannot meet the need of practical work. This project will study several most important problems in the theoretical studies for extended expressions. One of the main objectives of this project is to develop syntax definitions for extended deterministic expressions and their subclasses, hope to completely solve the long-standing problem that there are no syntax definitions for this kind of expressions, which has become an important reason for restricting the use of extended expressions. Meanwhile, many applications had been impossible before due to lack of syntax definitions, and we will investigate the applications of the syntax definitions that are important in practice. Since the current researches on practical subclasses of extended expressions have some shortcomings, we will use new methods in the research, and hope to get new subclasses and their inference algorithms. We will study the problem of deciding determinism of extended expressions, and hope to get algorithms based on the original expressions. We will study practical algorithms for the basic decision problems of extended expressions, and algorithms for such problems suited for subclasses of extended expressions. By researching the applications of the above algorithms in practice, we hope to find algorithms that are valuable in practice. For some important decision problems in extended deterministic languages, we will try to investigate theoretical properties and develop new algorithms, and get some computational complexity results. All these theoretical results will greatly promote the use of extended expressions in practice.

扩展表达式在实际当中有着很多应用，然而相关的理论研究目前还远不能满足实际工作的需要。本项目将对其中迫切需要解决的问题进行深入、系统的研究。本项目研究扩展确定性表达式及其子类的语法表示的理论问题，希望彻底解决这类表达式没有语法定义这一严重制约其应用的问题。并研究它们在实际当中具有重要意义的若干应用问题，而以前由于没有语法定义，相关的应用无法进行。针对现有扩展表达式实用子类研究中存在的不足，采用新的方法与手段进行研究，希望提出新的子类及其推断算法。研究扩展表达式的确定性判定问题，希望得到基于原表达式的确定性判定算法。研究扩展表达式基本判定问题的实用算法与子类算法，并研究它们在实际问题当中的应用，希望得到对实际应用有价值的算法。对于扩展确定性语言研究中极为重要的若干判定问题，我们将进行相关的理论与算法研究，希望得到新的复杂度结论和算法。这些研究结果，将对扩展表达式的更好应用产生积极而深远的影响。

扩展表达式在实际当中有着很多应用，本项目对其中迫切需要解决的问题进行深入、系统的研究，包括语法表示和应用、推断问题、扩展确定性语言与扩展确定性表达式的判定算法、和扩展表达式及子类的基本判定问题与应用。本项目执行结果超额完成了研究计划，取得的主要进展和结果如下。.(1) 在语法表示研究方面，提出了扩展确定性表达式的第一个文法，给出了相关理论、算法、构造等问题的证明和结果。.(2) 在文法的应用研究方面，提出了文法的随机生成算法、扩展确定性表达式的辅助书写算法、首个抗正则表达式拒绝服务（ReDoS）攻击正则表达式合成与修复算法，构建了一个大规模的扩展确定性表达式库。.(3) 在推断算法研究方面，针对已有研究中存在的不足，开展网络数据的获取与实验，提出了多个扩展表达式新子类及其推断算法，在此基础上，提出若干基于正反例的推断算法，提出了高质量XML模式设计算法、多模态正则表达式自动合成框架。.(4) 在确定性语言的理论与判定算法研究方面，提出了支持计数、无序及无序连接操作符的多个自动机模型，给出相关的性质，对于所提出的支持无序的有限自动机（FAFs）与同时支持计数和无序的有限自动机（FACFs），证明了确定性FAFs识别支持无序的强确定性正则表达式类所表示的语言，确定性FACFs识别同时支持计数和无序的强确定性正则表达式类所表示的语言。.(5) 在扩展表达式的确定性判定算法研究方面，提出了无序正则表达式的基于原表达式的确定性判定算法，提出了基于原表达式的与基于标号表达式的带计数与无序的扩展表达式的确定性判定算法，提出了带计数与无序的扩展表达式的算法判定强确定性。.(6) 在基本判定问题的算法与应用研究方面，提出了扩展表达式的没有限制的通用成员判定算法，提出了确定性表达式的两种包含判定算法，证明支持无序的强确定性正则表达式与同时支持计数和无序的强确定性正则表达式的一致性的和非一致性的成员资格均可在多项式内判定，提出了字符单次出现带计数和无序操作符的确定性表达式子类的成员判定算法，提出动静态结合的正则表达式ReDoS攻击检测框架，与正则表达式ReDoS修复框架，提出一种基于语义相似性检查的机器翻译系统自动测试方法，对建模问题进行了研究并应用到字符串生成与填字游戏求解，对正则表达式质量保证手段进行了文献调研，对现有相关工作进行了归纳和总结。.(7) 已发表和录用23篇研究论文.