Having explained the theory behind Regular Expressions (see here), let’s implement a Regular Expression engine in Scala.
The code can be found on Github in repo .
Of all the programming languages I have tried, I think Scala is my favourite. It favours immutable objects, supports functional styles of programming, and has an expressive type system which reduces the difference between the set of compilable programs and the set of working programs.
Scala has several features which will be useful when writing the Regular Expression engine, which will be pointed out as we go.
Building an NFA
We begin by writing a class to represent an NFA.
Recall that an NFA consists of a set of states, and a set of transitions between them. An obvious implementation might represent a state as a
Map[Character, Set[State]], with a flag to mark final states.
The problem with this approach is that it incompatible with immutable objects. Once a state has been created, it cannot be modified - we can only create a new state. This means that when a transition is added to a state, we must recursively modify all the states which point to said state. If the NFA contains cycles, this process repeats forever. The solution to this is to have the NFA itself own the transitions.
Thus an NFA will consist of a start State, a set of final states, and a map of State -> Character -> Set[State]. There’s a slight complication: we also need to be able to match the empty string, 𝜀.
In Scala, this can be represented succinctly.
Constructing an NFA
This is a good start, but constructing NFAs like this would be tedious, illegible, and error prone. To mitigate this we can use a companion object with some static factories for the five base NFAs (a companion object is a singleton object with the same name as a class).
We start by writing a factory method for the single character case.
This describes the single character NFA as an NFA with a start state, a single final state, and a transition from one to the other. As a small optimisation, since
Epsilon is a singleton, we can cache a reference to the empty Nfa. This is one of the benefits of immutable state.
This leaves the three compound cases: concatenation, union, and the Kleene star.
These work pretty much as you’d expect. We create the required additional states, and add the required 𝜀 transitions to the transitions of the existing NFAs. Irritatingly we need typecasts to stop the compiler inferring that the transition maps only use
Epsilon as a key, which prevents the combination of the maps.
This gives us all the tools we need to construct an NFA that is equivalent to any Regular Expression.
While functionally this is all we need, it’s still pretty clunky. We can use a Scala feature to help with this.
Scala doesn’t have operators. It has types that have methods with names like
::. We can add methods with these sorts of names to our own types.
While operators can be overused (the Dispatch library was a classic example of this), in cases where we are trying to code externally defined operators with Scala code they can be quite helpful.
In this case, the union and Kleene star have standard notation (
* respectively). We can add methods with these names to the Nfa class.
(Yes, I’m aware concatenation is missing. I’m getting to that.)
One approach to concatenation is to allow instances of the Nfa type to be constructed from Strings. A String is a sequence of characters, which we can take to be the Nfa that matches the sequence. This also generalises nicely to the empty string, which can be taken as the Nfa matching 𝜀.
This also allows us to demonstrate another Scala feature: implicits. If we have an instance of a type
A, we required a type
B, and we have an implicit method
a2B of type
A => B, the compiler will allow us to use instances of type
A as if they were instances of type
Used improperly, implicits can make code confusing by making it difficult to see where a conversion is happening. Determining if this is one of those cases is left as an exercise for the reader.
We can now write code like this:
There’s just one more trick we need.
It turns out Scala has a trick we can use to implement concatenation as an instance method.
Scala allows any type that implements an
apply method to be called as a function.
Which means the following is working Scala code:
It may have a few more parentheses than one would use to write it in the standard library, but it’s otherwise a pretty natural way of writing it.
We’ve implemented the beginning of a regular expression engine, by creating an NFA class and a concise way of instantiating it. In Part 2, we’ll look at implementing compilation into a DFA.