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.     

NR‐grep: a fast and flexible pattern‐matching tool

We present nrgrep (‘non‐deterministic reverse grep’), a new pattern‐matching tool designed for efficient search of complex patterns. Unlike previous tools of the grep family, such as agrep and Gnu grep, nrgrep is based on a single and uniform concept: the bit‐parallel simulation of a non‐deterministic suffix automaton. As a result, nrgrep can find from simple patterns to regular expressions, exactly or allowing errors in the matches, with an efficiency that degrades smoothly as the complexity of the searched pattern increases. Another concept that is fully integrated into nrgrep and that contributes to this smoothness is the selection of adequate subpatterns for fast scanning, which is also absent in many current tools. We show that the efficiency of nrgrep is similar to that of the fastest existing string‐matching tools for the simplest patterns, and is by far unmatched for more complex patterns. Copyright © 2001 John Wiley & Sons, Ltd.     

NIDS中正则表达式数量限定符的电路设计与实现

针对网络入侵检测系统(NIDS)中复杂正则表达式匹配的数量限定符进行了硬件设计和实现。经过对这3种限定符匹配原理的分析,改变了以往的直接复制多个重复单元的实现方法,设计了一套完整的优化的数量限定符FPGA实现电路。实验测试结果表明,本设计每个非元字符平均大约需要0.92个逻辑单元,系统可以达到1.2 Gb/s的吞吐能力。     

Duration-constrained regular expressions

This paper investigates the logic-automata-connection for Duration Calculus. It has been frequently observed that Duration Calculus with linear duration terms comes close to being a logic of linear hybrid automata. We attempt to make this relation precise by constructing Kleene-connection between duration-constrained regular expressions and a subclass of linear hybrid automata called loop-reset automata in which any variable tested in a loop is reset in the same loop. The formalism of duration-constrained regular expressions is an extension of regular expressions with duration constraints, which are essentially formulas of Duration Calculus without negation, yet extended by a Kleene-star operator. In this paper, we show that this formalism is equivalent in expressive power to loop-reset automata by providing a translation procedure from expressions to automata and vice verse.Received June 1999Accepted in revised form September 2003 by M. R. Hansen and C. B. Jones     

基于正则表达式的DFA拆分算法研究

深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表：间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。     

Generating graphical applications from state-transition visual specifications

In graphical applications, visual representations are mostly used in an ad hoc fashion with little or no underlying formal support. Due to this, no common methodology for handling visual and diagrammatic representations has emerged and formal techniques for their support are underdeveloped. Usually, a programmer develops a graphical application by applying a general-purpose visual programming environment and ad hoc implementing the application requirements. Then, big efforts are often required when the application has to be successively modified or extended. In this paper, we present a finite-automaton-based formalism for the specification of rapid application development (RAD) visual applications, which provides a formal basis in the visual application generation. A prototype tool, based on this approach, has been developed and it is currently being experimented on a variety of case studies.     

Tlex

TLex is a pattern matching and parsing library for C++. In comparison to existing pattern matching tools, TLex sets a new standard for expressiveness when nearly optimal speed is required. It incorporates recent advances in regular expression technology that make it easier to write patterns and extract information from a successful match. An overview of TLex is presented, the pattern and parsing languages are described, and actual results of its use are discussed.     

First-order temporal pattern mining with regular expression constraints

Previous studies on mining sequential patterns have focused on temporal patterns specified by some form of propositional temporal logic. However, there are some interesting sequential patterns, such as the multi-sequential patterns, whose specification needs a more expressive formalism, the first-order temporal logic. Multi-sequential patterns appear in different application contexts, for instance in spatial census data mining, which is the target application of the study developed in this paper. We extend a well-known user-controlled tool, based on regular expressions constraints, to the multi-sequential pattern context. This specification tool enables the incorporation of user focus into the mining process. We present MSP-Miner, an Apriori-based algorithm to discover all frequent multi-sequential patterns satisfying a user-specified regular expression constraint.     

ANTLRWorks: an ANTLR grammar development environment

Programmers tend to avoid using language tools, resorting to ad hoc methods, because tools can be hard to use, their parsing strategies can be difficult to understand and debug, and their generated parsers can be opaque black‐boxes. In particular, there are two very common difficulties encountered by grammar developers: understanding why a grammar fragment results in a parser non‐determinism and determining why a generated parser incorrectly interprets an input sentence. This paper describes ANTLRWorks, a complete development environment for ANTLR grammars that attempts to resolve these difficulties and, in general, make grammar development more accessible to the average programmer. The main components are a grammar editor with refactoring and navigation features, a grammar interpreter, and a domain‐specific grammar debugger. ANTLRWorks' primary contributions are a parser non‐determinism visualizer based on syntax diagrams and a time‐traveling debugger that pays special attention to parser decision‐making by visualizing lookahead usage and speculative parsing during backtracking. Copyright © 2008 John Wiley & Sons, Ltd.     

Exact formulations for the minimum interference problem in k‐connected ad hoc wireless networks

Energy consumption is one of the most critical issues in wireless ad hoc and sensor networks. A considerable amount of energy is dissipated due to radio transmission power and interference (message collisions). A typical topology control technique aims at reducing energy consumption while ensuring specific desired properties to the established wireless network (such as biconnectivity). Energy minimization can be achieved by reducing the transmission power and selecting edges that suffer or cause less interference. We propose four integer programming formulations for the k‐connected minimum wireless ad hoc interference problem, which consists in a topology control technique to find a power assignment to the nodes of an ad hoc wireless network such that the resulting network topology is k‐vertex connected and the radio interference is minimum. Interference is measured by three different models: Boolean, protocol, and physical. We report computational experiments comparing the formulations and interference models. Optimal solutions for moderately sized networks are obtained using a commercial solver.     

A framework for source code search using program patterns

For maintainers involved in understanding and reengineering large software, locating source code fragments that match certain patterns is a critical task. Existing solutions to the problem are few, and they either involve manual, painstaking scans of the source code using tools based on regular expressions, or the use of large, integrated software engineering environments that include simple pattern-based query processors in their toolkits. We present a framework in which pattern languages are used to specify interesting code features. The pattern languages are derived by extending the source programming language with pattern-matching symbols. We describe SCRUPLE, a finite state machine-based source code search tool, that efficiently implements this framework. We also present experimental performance results obtained from a SCRUPLE prototype, and the user interface of a source code browser built on top of SCRUPLE     

A framework for traversing dense annotation lattices

Pattern matching, or querying, over annotations is a general purpose paradigm for inspecting, navigating, mining, and transforming annotation repositories—the common representation basis for modern pipelined text processing architectures. The open-ended nature of these architectures and expressiveness of feature structure-based annotation schemes account for the natural tendency of such annotation repositories to become very dense, as multiple levels of analysis get encoded as layered annotations. This particular characteristic presents challenges for the design of a pattern matching framework capable of interpreting ‘flat’ patterns over arbitrarily dense annotation lattices. We present an approach where a finite state device applies (compiled) pattern grammars over what is, in effect, a linearized ‘projection’ of a particular route through the lattice. The route is derived by a mix of static grammar analysis and runtime interpretation of navigational directives within an extended grammar formalism; it selects just the annotations sequence appropriate for the patterns at hand. For expressive and efficient pattern matching in dense annotations stores, our implemented approach achieves a mix of lattice traversal and finite state scanning by exposing a language which, to its user, provides constructs for specifying sequential, structural, and configurational constraints among annotations.     

Development and evaluation of a system enhancing Second Life to support synchronous role‐based collaborative learning

Research and commercial interest toward 3D virtual worlds are recently growing because they probably represent the new direction for the next generation of web applications. Although these environments present several features that are useful for informal collaboration, structured collaboration is required to effectively use them in a working or in a didactical setting. This paper presents a system supporting synchronous collaborative learning by naturally enriching Learning Management System services with meeting management and multimedia features. Monitoring and moderation of discussions are also managed at a single group and at the teaching level. The Second Life (SL) environment has been integrated with two ad hoc developed Moodle plug‐ins and SL objects have been designed, modeled, and programmed to support synchronous role‐based collaborative activities. We also enriched SL with tools to support the capturing and displaying of textual information during collaborative sessions for successive retrieval. In addition, the multimedia support has been enhanced with functionalities for navigating multimedia contents. We also report on an empirical study aiming at evaluating the use of the proposed SL collaborative learning as compared with face‐to‐face group collaboration. Results show that the two approaches are statistically undistinguishable in terms of performance, comfort with communication, and overall satisfaction. Copyright © 2009 John Wiley & Sons, Ltd.     

Detecting False Matches in String-Matching Algorithms

Consider a text string of length n, a pattern string of length m, and a match vector of length n which declares each location in the text to be either a mismatch (the pattern does not occur beginning at that location in the text) or a potential match (the pattern may occur beginning at that location in the text). Some of the potential matches could be false, i.e., the pattern may not occur beginning at some location in the text declared to be a potential match. We investigate the complexity of two problems in this context, namely, checking if there is any false match, and identifying all the false matches in the match vector. We present an algorithm on the CRCW PRAM that checks if there exists a false match in O(1) time using O(n) processors. This algorithm does not require preprocessing the pattern. Therefore, checking for false matches is provably simpler than string matching since string matching takes time on the CRCW PRAM. We use this simple algorithm to convert the Karp—Rabin Monte Carlo type string-matching algorithm into a Las Vegas type algorithm without asymptotic loss in complexity. We also present an efficient algorithm for identifying all the false matches and, as a consequence, show that string-matching algorithms take time even given the flexibility to output a few false matches. Received January 28, 1995; revised January 17, 1996.     

Mediating the expression of emotion in educational collaborative virtual environments: an experimental study

The use of avatars with emotionally expressive faces is potentially highly beneficial to communication in collaborative virtual environments (CVEs), especially when used in a distance learning context. However, little is known about how, or indeed whether, emotions can effectively be transmitted through the medium of a CVE. Given this, an avatar head model with limited but human-like expressive abilities was built, designed to enrich CVE communication. Based on the facial action coding system (FACS), the head was designed to express, in a readily recognisable manner, the six universal emotions. An experiment was conducted to investigate the efficacy of the model. Results indicate that the approach of applying the FACS model to virtual face representations is not guaranteed to work for all expressions of a particular emotion category. However, given appropriate use of the model, emotions can effectively be visualised with a limited number of facial features. A set of exemplar facial expressions is presented.     

S4W: a problem‐solving environment for wireless system design

This work describes the Site‐Specific System Simulator for Wireless System Design (S⁴W), a problem‐solving environment (PSE) that integrates visualization and computational tools with a high‐level graphical user interface. S⁴W improves the ability of wireless system engineers to design an indoor wireless system by encouraging them to think in terms of designing the system for optimal performance. Issues of computation management, data management, and location of resources are hidden from the user. The complex nature of data sets in the domain of wireless simulations calls for a customized set of visualization tools. Therefore, a number of ad hoc visualizations were developed for S⁴W. A study comparing the integrated system with an earlier, unintegrated version is presented. This helps to demonstrate the productivity gains that a PSE provides. Copyright © 2007 John Wiley & Sons, Ltd.     

Integrated implementation of dynamic untyped object‐based operator overloading

Operator overloading, a popular mechanism in the C++ language, is a form of ad hoc polymorphism on operator functions, allowing alternative implementations for different argument types. Classless languages with untyped objects are languages that lack classes and treat all objects as compliant to a common Object type. Languages in this category are flexible, dynamic, and easy‐to‐use, with popular examples being JavaScript, Lua, and ActionScript (the latter being hybrid by also offering classes). This paper presents an integrated implementation of untyped operator overloading which enable users to handle dynamically the full range of operators on objects. The focus is on features not supported by other languages, such as (i) arithmetic and relational operators allowing to separately handle caller lhs and rhs positions; (ii) an assignment operator with an untyped analogy of type casting; (iii) a slot access operator allowing user‐defined policies for editing object slots; and (iv) a function‐call operator to support functors. Operators are treated as first‐class object slots, distinguished by reserved indices that match the respective operator lexemes. All reported techniques have been applied in implementing the operator overloading features of the Delta language. Copyright © 2010 John Wiley & Sons, Ltd.