Alexandre holds a bachelor degree in systems analysis and has extensive experience in embedded systems, C/C++, and Java. He currently works as a contractor and can be contacted at calsavara@ hotmail.com.
Regular expressions let you look for sequences of characters that match a given pattern. It is a useful and powerful capability, usually found only in advanced editors for programmers, but many other applications could benefit from it.
In this article, I present a relatively small class that uses regular expressions to add powerful string search capabilities to Java. In addition to implementing regular expression search, I also present a utility similar to the UNIX grep tool to exemplify its use. I chose to use an object-oriented implementation instead of the traditional state table. The result is not as fast as the traditional implementation, but it is easier to understand and maintain and (more importantly) easy to extend or customize.
Regular expressions are a way to specify patterns to search. The patterns are specified as human readable strings, obeying a given syntax. A pattern can be anything from a simple string (although in this case it would be easier and faster to use the language built-in string search) to a pattern of arbitrary complexity.
The pattern string is a sequence of tokens, each with a special meaning that says what to match. There are tokens to match any character, a set of characters, a character class (predefined character set), or one character of a set of alternatives. A simple character is represented by itself and there are tokens (escape codes) to represent nonprintable characters.
Tokens always match just one character, but special operators allow a token to be matched several times (repeated) and tokens can be grouped and nested to be repeated or used as alternatives to match. Table 1 provides a complete list of tokens and Table 2 provides the pattern syntax. Table 3 lists some examples of valid patterns.
My implementation is totally contained in the class jlib.util.RegExp (available electronically; see "Resource Center," page 5). There are a number of auxiliary classes, but they are all private and internal classes. I also use an exception class, jlib.util.SyntaxError (also available electronically) to sign errors in the pattern string.
The key idea behind my implementation is to represent the pattern string as a graph of nodes. Each node represents what to match and the links between nodes represent the possible alternatives. Once the graph is constructed, finding a match is just a matter of traversing the graph from the starting node until the end node is reached.
The nodes are instances of the jlib.strucs.RegExp.Node private internal class or one of its subclasses. Table 4 lists all subclasses, what they match, and the corresponding tokens.
Each class stores internally all information it needs in order to know what to match. For example, the class jlib.strucs .RegExp.Literal stores the character to match in the field pattern, and the class jlib.strucs.RegExp.Set stores the set of the characters to match as an array of character ranges in the field set. It also stores whether the set is negated in the field invert.
The class jlib.strucs.RegExp.Node has just one method, match(), which should be overriden by its subclasses. This method is called by the class jlib.strucs.RegExp when it is traversing the graph in order to match the input string with the pattern. The subclasses can, and should, use the fields of the outer class jlib.strucs.RegExp to get the input string in order to match it with the pattern they represent. Table 5 lists the fields of the outer class jlib.strucs.RegExp, interesting for the subclasses and what they contain when the match() method is called.
If the input string matches the pattern at the position specified by the index field, the subclass must return true, and update the index field if necessary. Table 6 explains the implementation of each subclass. Notice that the tokens *, +, ?, |, and () do not have corresponding subclasses. This is because these tokens do not match anything by themselves, but they affect the operation of other tokens. They can be implemented by the way the nodes that represent the tokens they operate on are linked. In other words, these tokens are represented by paths (links) in the graph, not by nodes. Figure 1 shows how these tokens are represented.
The pattern graph is built by the pattern parser. The parser builds the graph and checks the pattern syntax at the same time, while it parses the pattern string. If an error is found, an instance of the jlib.util.SyntaxError class is thrown with an appropriate error message. The parser is composed of several methods that resemble the productions presented in Table 2. Table 7 lists all methods that compose the parser.
When the parser methods are called, the field expression contains the pattern string and the field index points to the character being parsed. Each method parses the pattern string, updates the field index as needed, and returns a graph representation of what it parsed as an array of two nodes, the graph start, and end nodes. Figure 2 shows some pattern string examples and the graph that the parser creates.
The test for a match is done by the private internal method visit(). When it is called, the fields input and index should contain the input string and the position to match, respectively. The visit() method receives as input the node to match with the input string's current position. If a match is found, the field found is set to True.
The method visit() first calls the match() method of the node it received as input. If the method returns False, visit() returns; otherwise, it calls itself recursively with each one of the possible paths. If the node does not link to any other node, that means that it is an ending node of the pattern graph, so visit() sets the field found to True and returns.
The public method next() searches for a pattern. Starting at the position given by the field index, it calls the visit() method with the pattern graph starting node. If a match is not found, it calls visit() again to try a match at the next position, until a match is found or the end of the input is reached.
Using the Class
Using the jlib.util.RegExp class is straightforward. First, construct an instance of the jlib.util.RegExp with the pattern string and, optionally, whether you want to take case into account. Once the object is constructed, you can get the pattern string through the getExpression() method and query/set the case sensitiveness of the object using the getCase()/setCase() methods.
To search for a pattern, call the search() method with an input string and, optionally, an initial position to start searching. The method looks for a match starting at the given position and returns whether a match was found or not. After that, you can call the method next() to search for more matches. Each time next() is called, it looks for a new match starting at the last match found.
You can also use the method startSearch() to just initialize the object to search. In this case, you must call the next() method later to actually perform the search. After a search is performed, the method found() returns whether a match was found on the last search and the method getInput() returns the input string.
After a successful search, the method match() returns the substring found and the methods matchBegin() and matchEnd() return the start and end position of the match found in the input string.
To illustrate the class jlib.util.RegExp, I present a simple utility, JGrep (available electronically), that looks for text inside text files. It is similar to the popular grep tool, hence its name. Execute the class without any option to get a help screen. Notice that the messages and help screen are localized for English and Portuguese through property files. Available electronically are property files for English (the default) and Portuguese.
The choice of an appropriate solution can be the difference between success and failure. Frequently, complex topics can be turned into straightforward implementations by employing original and simple algorithms and data structures. By using a graph, I made regular expression implementation easier to understand and maintain.
My implementation also shows the power of object orientation. By using an object-oriented approach, I made regular expressions easy to extend. To create a new token, just change the appropriate parser methods to recognize it and, if needed, subclass jlib.util.RegExp.Node or one of its subclasses.