基于变异的正则表达式反例测试串生成算法

正则表达式在计算机科学的许多领域具有广泛应用. 然而, 由于正则表达式语法比较复杂, 并且允许使用大量元字符, 导致开发人员在定义和使用时容易出错. 测试是保证正则表达式语义正确性的实用和有效手段, 常用的方法是根据被测表达式生成一些字符串, 并检查它们是否符合预期. 现有的测试数据生成大多只关注正例串, 而研究表明, 实际开发中存在的错误大部分在于定义的语言比预期语言小, 这类错误只能通过反例串才能发现. 研究基于变异的正则表达式反例测试串生成. 首先通过变异向被测表达式中注入缺陷得到一组变异体, 然后在被测表达式所定义语言的补集中选取反例字符串揭示相应变异体所模拟的错误. 为了能够模拟复杂缺陷类型, 以及避免出现变异体特化而无法获得反例串的问题, 引入二阶变异机制. 同时采取冗余变异体消除、变异算子选择等优化技术对变异体进行约简, 从而控制最终生成的测试集规模. 实验结果表明, 与已有工具相比, 所提算法生成的反例测试串规模适中, 并且具有较强的揭示错误能力.     

One-Unambiguous Regular Languages

The ISO standard for the Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard, the right-hand sides of productions are based on regular expressions, although only regular expressions that denote words unambiguously, in the sense of the ISO standard, are allowed. In general, a word that is denoted by a regular expression is witnessed by a sequence of occurrences of symbols in the regular expression that match the word. In an unambiguous regular expression as defined by Booket al.(1971,IEEE Trans. Comput.C-20(2), 149–153), each word has at most one witness. But the SGML standard also requires that a witness be computed incrementally from the word with a one-symbol lookahead; we call such regular expressions 1-unambiguous. A regular language is a 1-unambiguouslanguage if it is denoted by some 1-unambiguous regular expression. We give a Kleene theorem for 1-unambiguous languages and characterize 1-unambiguous regular languages in terms of structural properties of the minimal deterministic automata that recognize them. As a result we are able to prove the decidability of whether a given regular expression denotes a 1-unambiguous language; if it does, then we can construct an equivalent 1-unambiguous regular expression in worst-case optimal time.     

State complexity of unique rational operations

For each basic language operation we define its “unique” counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity.     

Grail: A C++ Library for Automata and Expressions

Grail is a package for symbolic manipulation of finite-state automata and regular expressions. It provides most standard operations on automata and expressions, including minimization, subset construction, conversion between automata and regular expressions, and language enumeration and testing. Grail 's objects are parameterizable; users can provide their own classes to define the input alphabet of automata and expressions. Grail's operations are accessible either as individual programs or directly through a C++ class library.     

Extending regular expressions with context operators and parse extraction

Regular expressions are used in many applications to specify patterns because any regular expression can be compiled into a very efficient one-pass pattern matcher called a finite automaton. Finding matches is useful, but even more useful is parse extraction, which describes in detail how a pattern matches some input. After matching an address, for example, parse extraction makes it easy to find out the Zip code part of the address. We present an elegant, efficient algorithm for extracting a parse after matching with a finite automaton. In addition, we extend the regular expression language to include new operators for matching arbitrary left context and single character right context. The extended language can be matched as efficiently as the usual regular expression language, but is more expressive. Finally, we suggest how to apply the matching algorithms to match regular expressions containing arbitrary right context and single character left context. In effect, this allows one to specify patterns that seem to require an unlimited amount of look-ahead to match.     

From regular expressions to smaller NFAs

Several methods have been developed to construct λ-free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a λ-free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods.     

Result sequences

Expression evaluation in conventional programming languages may be viewed as a simplification of expression evaluation in the Icon programming language. The evaluation of an expression in Icon may yield a sequence of results. Goal-directed evaluation causes expressions to produce these results in an attempt to produce the successful evaluation of an enclosing expression. There are control operations that operate on result sequences. The study of expression evaluation in Icon therefore is more interesting than it is in most programming languages. This paper introduces a notation for result sequences and shows how it can be used to describe the static aspects of expression evaluation. Equivalences among control operations and expressions are demonstrated.     

A pattern matching macro processor

A general-purpose pattern matching macro processor is described. Macro patterns can be defined using regular expressions. Macro calls are treated by balancing pattern matching at the token unit level, allowing options, alternatives and repetition. Thus, text in a language with a nested structure can be dealt with. In a macro body, Algol-style macro-time operations are allowed, which improves writing and reading. Our macro processor can also be used as a tool for language conversion since it incorporates a feature to declare language-dependent constructs such as comments, string notations and parentheses pairs. Although our macro processor is not biased towards any particular language, it has successfully converted an Algol 68-style text into a Fortran text. Problems of language conversion using macros are briefly discussed based upon the experience obtained through this macro processor.     

Reactive automata

A reactive automaton has extra links whose role is to change the behaviour of the automaton. We show that these links do not increase the expressiveness of finite automata but that they can be used to reduce dramatically their state number both in the deterministic case and the non-deterministic case.Typical examples of regular expressions associated with deterministic automata of exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language.     

Decidability of operation problems for T0L languages and subclasses

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.     

State complexity of basic operations on suffix-free regular languages

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.     

路径表达式的并行算法研究

在面向对象数据库系统中,路径表达式是用于定位复杂对象的必要查询设施,因此,优化和并行化路径表达式的执行是实现高性能面向对象数据库系统的关键因素之一,由于ＯＱＬ语言的正交性,在ＳＥＬＥＣＴ,ＦＲＯＭ和（或）ＷＨＥＲＥ子句中均可嵌套路径表达式,而我们将着重讨论ＷＨＥＲＥ子句子路径表达式的并行计算,种路径表达式也称之为复杂谓词。本文分析了现有路径表达式的计算方法后,提出了两种新的路径表达式并行计算算法,     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

On the complexity of division and set joins in the relational algebra

We show that any expression of the relational division operator in the relational algebra with union, difference, projection, selection, constant-tagging, and joins, must produce intermediate results of quadratic size. To prove this result, we show a dichotomy theorem about intermediate sizes of relational algebra expressions (they are either all linear, or at least one is quadratic), and we link linear relational algebra expressions to expressions using only semijoins instead of joins.     

Regular Language Representations in the Constructive Type Theory of Coq

We explore the theory of regular language representations in the constructive type theory of Coq. We cover various forms of automata (deterministic, nondeterministic, one-way, two-way), regular expressions, and the logic WS1S. We give translations between all representations, show decidability results, and provide operations for various closure properties. Our results include a constructive decidability proof for the logic WS1S, a constructive refinement of the Myhill-Nerode characterization of regularity, and translations from two-way automata to one-way automata with verified upper bounds for the increase in size. All results are verified with an accompanying Coq development of about 3000 lines.     

正规语言闭包运算的Petri网构造方法

Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。     

On universality of concurrent expressions with synchronization primitives

Concurrent expressions are a class of extended regular expressions with a shuffle operator (6) and its closure (

). The class of concurrent expressions with synchronization primitives, called synchronized concurrent expressions, is introduced as an extended model of Shaw's flow expressions. This paper discusses some formal properties of synchronized concurrent expressions from a formal language theoretic point of view. It is shown that synchronized concurrent expressions with three signal/wait operations are universal in the sense that they can simulate any semaphore controlled concurrent expressions and they can describe the class of recursively enumerable sets. Some results on semaphore controlled regular expressions are also included to give a taste of more positive results.