Context-Free Grammars for Deterministic Regular Expressions with Interleaving

In this paper, we study deterministic regular expressions with interleaving (IDREs). Regular expressions extended with interleaving are good at describing sequential and parallel data patterns. The interleaving makes these expressions exponentially more succinct than standard regular expressions. And when they obey the determinism constraint, they are more efficient for matching and parsing processes than general ones. However, the interleaving also makes the structure of expressions more complex, and the semantic definition of determinism is hard to follow, which prevent users from writing and developing IDREs. We address this problem by proposing a determinism checking method and a syntactic description for IDREs. Our checking method can locate the source of nondeterminism more efficiently and accurately than the existing method when the nondeterminism is caused by unary operators. We prove that the grammars of IDREs are context-free and suggest effective optimization rules to simplify the grammars.