Towards an Effective Syntax and a Generator for Deterministic Standard Regular Expressions. (8th November 2018)

• Record Type: Journal Article
• Authors: Xu, Zhiwu; Lu, Ping; Chen, Haiming
• Is Part Of: Computer journal. Volume 62:Number 9(2019)
• Page Start: 1322
• Page End: 1341
• Publication Date: 2018-11-08
• Subjects: deterministic regular expressions -- grammars -- properties -- optimizations -- generation; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy110
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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.