Towards an Effective Syntax and a Generator for Deterministic Standard Regular Expressions
Towards an Effective Syntax and a Generator for Deterministic Standard Regular Expressions
复制标题
走向有效的语法和确定性标准正则表达式的生成器
DOI：
10.1093/comjnl/bxy110
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Haiming Chen
中科院分区：
文献类型：
--
作者：
Zhiwu Xu;Ping Lu;Haiming Chen
确定性正则表达式是XML模式的核心部分，并在其他应用程序中使用。但与正则表达式不同，确定性正则表达式没有简单的语法，而是以语义的方式定义的。此外，不是每个正则表达式都可以重写为等效的确定性正则表达式。确定性正则表达式的这些属性给用户开发XML模式定义和使用确定性正则表达式带来了负担。本文提出了一种确定性标准正则表达式（DREG）的语法，并证明了DREG的语法是上下文无关的。在上下文无关DREG文法的基础上，设计了一个DREG生成器，该生成器可以随机生成DREG，并可用于DREG相关的应用，如DTD或XML Schema的基准测试验证器，DTD和XML Schema的包含性检查等。实验结果证明了该发生器的有效性和实用性。
Deterministic regular expressions are a core part of XML Schema and used in other applications. But unlike regular expressions, deterministic regular expressions do not have a simple syntax, instead they are defined in a semantic manner. Moreover, not every regular expression can be rewritten to an equivalent deterministic regular expression. These properties of deterministic regular expressions put a burden on the user to develop XML Schema Definitions and to use deterministic regular expressions. In this paper, we propose a syntax for deterministic standard regular expressions (DREGs), and prove that the syntax of DREGs is context-free. Based on the context-free grammars for DREGs, we further design a generator for DREGs, which can generate DREGs randomly, and be used in applications associated with DREGs, e.g. benchmarking a validator for DTD or XML Schema, and inclusion checking of DTD and XML Schema. Experimental results demonstrate the efficiency and usefulness of the generator.