🎄This is the day 16 post for IPFactory Advent Calendar 2019 - Qiita.🎄

Hello, I'm 8ayac. I recently implemented a regular expression engine in Go as a learning exercise, and this post describes it.

What is a regular expression engine?

A regular expression engine is a system that performs regular expression matching. Regular expression engines can be divided into two types: DFA-based and VM-based. Their main characteristics are as follows.

  • DFA-based
    • Converts a regular expression into a DFA (deterministic finite automaton) and uses it for matching.
  • VM-based
    • Converts a regular expression into bytecode and uses it for matching.

I implemented both types, but this post covers the DFA-based engine.

What is a regular expression?

A regular expression is an expression that describes a pattern of characters. It originated as a mathematical concept with a precise definition, but that is somewhat outside the scope of this post, so I will leave it aside here. See 正規表現 - Wikipedia for details.

Under the formal definition, regular expressions support union (alternation), concatenation, and repetition. For example, these rules can be written as follows.

  • a|b
    • A pattern for either a or b.
  • ab
    • A pattern where b immediately follows a.
  • a*
    • A pattern where a is repeated zero or more times.

I implemented an engine that supports these basic rules.

A DFA-based regular expression engine

A DFA-based engine performs pattern matching through roughly the following steps.

  1. Convert the regular expression into an NFA.
  2. Convert the NFA into a DFA.
  3. Simulate the DFA.

I will briefly introduce finite automata, then look more closely at each step.

FA (finite automaton)

Roughly speaking, a finite automaton is a computational model for matching character strings against patterns. It maintains two things: a current state and a set of transition rules. As a string is read, it updates the current state from the initial state according to those rules. If the final state is an accepting state, it returns "accept." Otherwise, it returns "reject."

The following diagram shows a simple automaton that accepts the character a.

simple_fa

Its components are as follows. By convention, an accepting state is drawn with a double border.

  • Initial state
    • q0
  • Accepting state
    • q1
  • Transition rule
    • On receiving a in q0, change the state to q1.

For example, giving this automaton the input a changes its state from q0 to q1. The current state is then an accepting state, so the input a has been accepted.

Finite automata such as NFAs and DFAs are computational models that recognize regular expressions (or, more precisely, regular languages). It is also known that an equivalent automaton can be constructed from any regular expression. Using these properties, we can build an automaton from a regular expression and simulate it to perform matching. This is how a DFA-based regular expression engine works.

The difference between an NFA and a DFA

  • DFA (Deterministic Finite Automaton)
    • Has a unique destination state for a given input symbol.
  • NFA (Non-Deterministic Finite Automaton)
    • Has one or more destination states for a given input symbol, which need not be unique.

In other words, NFA is the general category of finite automata, and DFAs are included within it. Nondeterminism, the property of having no uniquely determined destination state, can be removed from an NFA. That is, any NFA can be converted into a DFA. The method for removing nondeterminism is described later.

Converting a regular expression into an NFA

A DFA-based regular expression engine first converts the regular expression into an NFA. This process has two main stages.

  1. Build an AST from the regular expression.
  2. Build an NFA from the AST.

In a little more detail, the steps are as follows.

  1. Obtain a sequence of tokens through lexical analysis.
  2. Parse the token sequence to obtain an AST.
  3. Obtain an NFA fragment from the AST.
  4. Convert the NFA fragment into an NFA.

Building an AST from a regular expression (compilation)

To build an NFA from a regular expression, we need to convert the regular expression string, such as a* or b|c, into a more convenient representation. That representation is an AST (abstract syntax tree). The process of building it is called compilation, and the program that does so is a compiler.

I used this article as a reference for the DFA-based compiler. Please refer to it for details.

Lexical analysis

First, we determine what kind of token each character in the regular expression string represents. The following tokens are currently implemented in both the DFA-based and VM-based engines (the VM-based engine also supports ? and .).

  • CHARACTER
    • An ordinary character.
  • UNION
    • Union (|).
  • STAR
    • Repetition (*).
  • PLUS
    • Repetition (+).
  • LPAREN
    • Left parenthesis (().
  • RPAREN
    • Right parenthesis ()).
  • EOF
    • End of the string.

Let's look at the lexer code. Some code and comments have been omitted.

The tokens are defined in token/token.go.

package token

type Type int

const (
	CHARACTER Type = iota
	UNION
	STAR
	PLUS
	LPAREN
	RPAREN
	EOF
)

type Token struct {
	V  rune // token value
	Ty Type // token type
}

func NewToken(value rune, k Type) Token {
	return Token{
		V:  value,
		Ty: k,
	}
}

lexer/lexer.go performs the lexical analysis. The s slice in the Lexer struct stores the characters of the string to be analyzed. *Lexer.Scan() scans that string to the end, stores an appropriate token for each character in tokenList, and returns the list.

package lexer

import (
	"github.com/8ayac/dfa-regex-engine/token"
)

type Lexer struct {
	s []rune // string to be analyzed
}

func NewLexer(s string) *Lexer {
	return &Lexer{
		s: []rune(s),
	}
}

func (l *Lexer) Scan() (tokenList []token.Token) {
	for i := 0; i < len(l.s); i++ {
		switch l.s[i] {
		case '\x00':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.EOF))
		case '|':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.UNION))
		case '(':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.LPAREN))
		case ')':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.RPAREN))
		case '*':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.STAR))
		case '+':
			tokenList = append(tokenList, token.NewToken(l.s[i], token.PLUS))
		case '\\':
			tokenList = append(tokenList, token.NewToken(l.s[i+1], token.CHARACTER))
			i++
		default:
			tokenList = append(tokenList, token.NewToken(l.s[i], token.CHARACTER))
		}
	}
	return
}

The following part implements simple escape sequences. When it reads \, it treats the next character as an ordinary character and returns a CHARACTER token. This allows metacharacters such as * and + to be treated as ordinary characters.

case '\\':
			tokenList = append(tokenList, token.NewToken(l.s[i+1], token.CHARACTER))
			i++

Parsing

Parsing builds an AST from the token sequence obtained by the lexer. The program that performs this process is called a parser.

I implemented a recursive-descent parser (a predictive parser). The grammar rules are also based on the CodeZine article. I made a small change when implementing +, so the BNF is included below.

(A)
expression -> subexpr

(B) 
subexpr -> subexpr '|' seq | seq
(
    subexpr  -> seq _subexpr
    _subexpr -> '|' seq _subexpr | ε
)

(C) 
seq -> subseq | ε

(D)
subseq -> subseq sufope | sufope
(
    subseq  -> sufope _subseq
    _subseq -> sufope _subseq | ε
)

(E)
sufope -> factor ('*'|'+') | factor

(F)
factor -> '(' subexpr ')' | CHARACTER

In this implementation, we first create a function for each nonterminal symbol (here, a method on the Parser struct). Parsing proceeds by calling these functions recursively until a terminal symbol appears, meaning a symbol that does not occur on the left-hand side of any rule. The rules to apply are determined as tokens are read.

Here are excerpts of the methods corresponding to the rules. The full implementation is in parser/parser.go.

package parser

import (
	"fmt"

	"github.com/8ayac/dfa-regex-engine/lexer"
	"github.com/8ayac/dfa-regex-engine/node"
	"github.com/8ayac/dfa-regex-engine/token"
)

type Parser struct {
	tokens []token.Token
	look   token.Token  // 現在見ているトークン
}

func NewParser(s string) *Parser {
	p := &Parser{
		tokens: lexer.NewLexer(s).Scan(),
	}
	p.move()
	return p
}

func (psr *Parser) GetAST() node.Node {
	ast := psr.expression()
	return ast
}

func (psr *Parser) move() {
	if len(psr.tokens) == 0 {
		psr.look = token.NewToken('\x00', token.EOF)
	} else {
		psr.look = psr.tokens[0]
		psr.tokens = psr.tokens[1:]
	}
}

func (psr *Parser) moveWithValidation(expect token.Type) {
	if psr.look.Ty != expect {
		err := fmt.Sprintf("[syntax error] expect:\x1b[31m%s\x1b[0m actual:\x1b[31m%s\x1b[0m", expect, psr.look.Ty)
		panic(err)
	}
	psr.move()
}

// expression -> subexpr
func (psr *Parser) expression() node.Node {
	nd := psr.subexpr()
	psr.moveWithValidation(token.EOF)
	return nd
}

// subexpr -> subexpr '|' seq | seq
// (
//	subexpr  -> seq _subexpr
//	_subexpr -> '|' seq _subexpr | ε
// )
func (psr *Parser) subexpr() node.Node {
	nd := psr.seq()
	for {
		if psr.look.Ty == token.UNION {
			psr.moveWithValidation(token.UNION)
			nd2 := psr.seq()
			nd = node.NewUnion(nd, nd2)
		} else {
			break
		}
	}
	return nd
}

// seq -> subseq | ε
func (psr *Parser) seq() node.Node {
	if psr.look.Ty == token.LPAREN || psr.look.Ty == token.CHARACTER {
		return psr.subseq()
	}
	return node.NewCharacter('ε')
}

// subseq -> subseq sufope | sufope
// (
//	subseq  -> sufope _subseq
//	_subseq -> sufope _subseq | ε
// )
func (psr *Parser) subseq() node.Node {
	nd := psr.sufope()
	if psr.look.Ty == token.LPAREN || psr.look.Ty == token.CHARACTER {
		nd2 := psr.subseq()
		return node.NewConcat(nd, nd2)
	}
	return nd
}

// sufope -> factor ('*'|'+') | factor
func (psr *Parser) sufope() node.Node {
	nd := psr.factor()
	switch psr.look.Ty {
	case token.STAR:
		psr.move()
		return node.NewStar(nd)
	case token.PLUS:
		psr.move()
		return node.NewPlus(nd)
	}
	return nd
}

// factor -> '(' subexpr ')' | CHARACTER
func (psr *Parser) factor() node.Node {
	if psr.look.Ty == token.LPAREN {
		psr.moveWithValidation(token.LPAREN)
		nd := psr.subexpr()
		psr.moveWithValidation(token.RPAREN)
		return nd
	}
	nd := node.NewCharacter(psr.look.V)
	psr.moveWithValidation(token.CHARACTER)
	return nd
}

AST nodes

The functions corresponding to the rules return node.Node. This is an interface defined in node/node.go.

type Node interface {
	// そのノードを頂点にした木を文字列に変換して返す
	SubtreeString() string

	// ノードをNFA(の切れ端)にして返す
	Assemble(*utils.Context) *nfabuilder.Fragment
}

It represents a node in the AST. There are several node types, such as Character and Star, and each implements this interface. Each node has an Assemble method that returns the fragment of an NFA built from that node. Recursively traversing the AST from its root and calling Assemble therefore gives us the complete NFA.

The node types have the following meanings.

  • Character
    • A single character.
  • Union
    • Union (alternation).
  • Concat
    • Concatenation.
  • Star
    • Repetition (*).
  • Plus
    • Repetition (+).

The AST obtained from a regular expression

Let's look at the AST obtained from the regular expression (ab)|c*.

ast

The same AST can be drawn as the following graph.

ast_graph

NFA Fragment

AST nodes implement the following interface. Here, we will look at its Assemble method.

type Node interface {
	// そのノードを頂点にした木を文字列に変換して返す
	SubtreeString() string

	// ノードをNFA(の切れ端)にして返す
	Assemble(*utils.Context) *nfabuilder.Fragment
}

Assemble returns a *nfabuilder.Fragment struct representing a small part of an NFA. Although called a fragment, it is itself an NFA, but it is somewhat more flexible to rearrange than the NFA defined in nfa/nfa.go.

The Fragment struct

type Fragment struct {
	I     utils.State     // 初期状態
	F     mapset.Set      // 受理状態
	Rules nfarule.RuleMap // 遷移規則
}

The I field is the initial state. utils.State is a struct holding an integer. Using utils.Context ensures that this value is unique within an automaton.

The F field contains the accepting states. I wanted to store them as a set of states, so I used the external package https://github.com/deckarep/golang-set. I encountered a few inconveniences and made some small modifications before using it. You can think of it as something like Python's set type.

The Rules field contains the transition rules. nfarule.RuleMap is defined in nfa/nfarule/nfarule.go as follows. This map gives the set of destination states when a symbol (RuleArgs.C) is received in a state (RuleArgs.From).

type RuleMap map[RuleArgs]mapset.Set

type RuleArgs struct {
	From utils.State // from state
	C    rune        // input symbol
}

Assembling a fragment

Calling Assemble on the root node of the AST ultimately produces an NFA equivalent to the original regular expression. When the root's Assemble method is called, it calls Assemble on any child nodes. The same process repeats if those nodes have children. By recursively traversing the AST in this way, we obtain a large NFA fragment.

The following Build method converts a fragment into an NFA.

func (frg *Fragment) Build() *nfa.NFA {
	return nfa.NewNFA(frg.I, frg.F, frg.Rules)
}

Representing each node as an NFA

Before looking at how each node is assembled, let's review the ε-transitions used in the process.

ε-transitions

An ε-transition can be represented by an automaton like the following.

char_frg_epsilon

ε represents the empty string. This automaton transitions to an accepting state without reading anything. Such an unconditional transition is called an ε-transition. The NFAs representing the nodes can be built using these transitions.

Character nodes

For a node such as Character('a'), we can build an NFA like the following that accepts the regular expression a.

char_frg_a

This NFA accepts when it receives the single symbol 'a' from the initial state (the circle on the left). It therefore appears to represent a regular expression matching the string a.

Let's look at the implementation.

type Character struct {
	Ty string
	V  rune	// Character('a')なら'a'
}

func (c *Character) Assemble(ctx *utils.Context) *nfabuilder.Fragment {
	// 新しいフラグメントを用意
	newFrg := nfabuilder.NewFragment()

	// 必要な状態を作成
	q1 := utils.NewState(ctx.Increment())
	q2 := utils.NewState(ctx.Increment())

	// 遷移規則を設定
	newFrg.AddRule(q1, c.V, q2)

	// 初期状態・受理状態を設定
	newFrg.I = q1
	newFrg.F.Add(q2)

	return newFrg
}

First, the V field of the Character struct specifies the single character to accept. It is used later when creating the transition rules.

Next, utils.NewState(), which creates a state, returns a State struct holding the integer passed as its argument. When creating a fragment, the integer held by the shared *utils.Context is used to give each new state a unique value. You can think of it as numbering the states. The implementation is as follows.

type Context struct {
	N int
}

func NewContext() *Context {
	return &Context{
		N: -1,
	}
}

func (ctx *Context) Increment() int {
	ctx.N++
	return ctx.N
}

Next is newFrg.AddRule(q1, c.V, q2). As its name suggests, this method adds a new transition rule to the fragment. If a rule with the same source state and transition condition already exists, it adds the new state to that rule's set of destinations.

func (frg *Fragment) AddRule(from utils.State, c rune, next utils.State) {
	r := frg.Rules
	_, ok := r[nfarule.NewRuleArgs(from, c)]
	if ok {
		r[nfarule.NewRuleArgs(from, c)].Add(next)
	} else {
		r[nfarule.NewRuleArgs(from, c)] = mapset.NewSet(next)
	}
}

Finally, we set the fragment's accepting and initial states and return it. The other nodes are implemented along similar lines. Some implementations are omitted below, but the full code is on GitHub.

Concat nodes

A Concat node represents concatenation, as in ab. I implemented it to produce a fragment like the following.

concat_frg

The colored boxes enclose fragments for the Concat node's children. For Concat(Character('a'), Character('b')), they are the fragments for Character('a') and Character('b'), respectively.

The regular expression ab means that b immediately follows a. This can be represented by an ε-transition from the accepting state of the fragment that comes first (the blue fragment) to the initial state of the other fragment. Finally, set the new fragment's initial state to the blue fragment's initial state and its accepting state to the green accepting state.

Union nodes

A Union node represents a regular expression such as a|b. I implemented it to produce a fragment like the following.

union_frg

As before, the colored boxes enclose fragments for the Union node's children. Create a new state with unconditional transitions to their initial states. Finally, make that new state the initial state of the new fragment.

Star nodes

A Star node represents repetition zero or more times, as in a*. It is implemented to produce a fragment like the following.

star_frg

The colored fragment is the Star node's child. For Star(Character('a')), it corresponds to Character('a').

Two new states are added. For convenience, call them q and s.

Add ε-transitions in the following directions.

  • q → The green fragment's original initial state
  • q → s
  • The green fragment's original accepting state → s
  • The green fragment's original accepting state → The green fragment's original initial state

Finally, set the initial and accepting states of the new fragment as follows.

  • Initial state
    • q
  • Accepting states
    • s and the green fragment's original initial state

Note that the green fragment's original accepting state becomes an ordinary state, neither an accepting nor an initial state.

Plus nodes

A Plus node represents repetition one or more times, as in a+. The regular expression a+ can be written as aa* using the * operator. I therefore built a fragment equivalent to Concat(Character('a'), Star('a')).

Converting an NFA into a DFA

After building an NFA, we convert it into a DFA. This is because simulating a DFA is simpler and more efficient than simulating an NFA. I mentioned earlier that nondeterminism can be removed from an NFA. Here, I will describe the method and its implementation.

Removing ε-transitions from an NFA

First, we remove the ε-transitions to build an equivalent NFA. An NFA containing ε-transitions is called an ε-NFA.

To remove ε-transitions, we calculate the states reachable from each state of the ε-NFA for the input ε*→some symbol→ε*, where ε* means one or more εs. That is, we first find the states reachable through ε-transitions alone, then the states reachable by reading a symbol, and finally the states reachable through ε-transitions alone from there. This gives the destinations for any symbol from each state, allowing us to remove the ε-transitions.

Let's try this with the following ε-NFA.

eNFAtoNFA

First, we calculate which states can be reached from each state without consuming any input. Perhaps this could also be described as finding where each state can go when given one or more empty strings as input. Examining the automaton gives the following table.

Source state a b c ε*
q0 {q0} - - {q0,q1,q2}
q1 - {q1} - {q1,q2}
q2 - - {q2} {q2}

I implemented the following methods to find the destination states for an input of ε*.

func (nfa *NFA) epsilonClosure(state utils.State) (reachable mapset.Set) {
	reachable = mapset.NewSet(state)

	modified := true
	for modified {
		modified = false
		for q := range reachable.Iter() {
			dst, ok := nfa.CalcDst(q.(utils.State), 'ε')
			if !ok || reachable.IsSuperset(dst) {
				continue
			}
			reachable = reachable.Union(dst)
			modified = true
		}
	}
	return
}

func (nfa *NFA) CalcDst(q utils.State, c rune) (mapset.Set, bool) {
	s, ok := nfa.Rules[nfarule.NewRuleArgs(q, c)]
	if ok {
		return s, true
	}
	return nil, false
}

Using this table, we can find the destination states for an input of ε*→some symbol→ε*. For example, consider the input ε*→a→ε* at q0. It can be calculated as follows.

  1. Find the destinations for ε*. → {q0,q1,q2}
  2. Find the destinations for a from each state in {q0,q1,q2}.
    1. q0: {q0}
    2. q1: None
    3. q2: None
  3. Find the destinations for ε* from every state that appeared in step 2.
    1. q0: {q0,q1,q2}
  4. We now know that an input of a at q0 may lead to {q0,q1,q2}.

Repeat this calculation for every state and every symbol in the ε-NFA. This gives the following table.

Source state a b c
q0 {q0,q1,q2} {q1,q2} {q2}
q1 - {q1,q2} {q2}
q2 - - {q2}

This table is itself a set of NFA transition rules, so we have derived an NFA from the ε-NFA. The following diagram presents the same table visually.

removeEpsilon_result

The full implementation for removing ε-transitions is in the code on GitHub.

The following method on *NFA runs this process.

func (nfa *NFA) ToWithoutEpsilon() {
	if nfa.F.IsSubset(nfa.epsilonClosure(nfa.I)) {
		nfa.F.Add(nfa.I)
	}
	nfa.Rules = nfa.removeEpsilonRule()
}

Subset construction

After building an equivalent NFA from the ε-NFA, we convert it into a DFA. The method used to remove nondeterminism is called subset construction. It treats each set of NFA destination states as a single state. This makes the destination from each state unique, removing nondeterminism.

Let's look at the following NFA as an example.

example_NFA

The destinations from each state are as follows.

Set of source states a b
{q0} {q0,q2} {q1}
{q1} {q2} {q1,q2}
{q2} - -

Next, examine the destination sets that have appeared and find their destinations if they are not yet known. The destinations from {q1} and {q2} are already known, so they do not need to be examined again.

Set of source states a b
{q0} {q0,q2} {q1}
{q1} {q2} {q1,q2}
{q2} - -
{q0,q2} {q0,q2} {q1}
{q1,q2} {q2} {q1,q2}

Continue examining any destination sets whose destinations remain unknown. In this example, all of them have been examined, so we are done.

Once the table is complete, treat each set as a new state to construct the DFA. If an original set contains even one accepting state, the corresponding DFA state is also accepting. The correspondence is as follows.

Set of source states DFA state Accepting?
{q0} q0 -
{q1} q1 -
{q2} q2 o
{q0,q2} q3 o
{q1,q2} q4 o

I defined this mapping as follows.

type DFAStatesMap map[mapset.Set]utils.State

Using the information so far, we can build the following DFA transition table.

Source state a b
q0 q3 q1
q1 q2 q4
q2 - -
q3 q3 q1
q4 q2 q4

The following diagram presents the table visually.

result_dfa

We have now removed the nondeterminism.

Implementing subset construction

The procedure is essentially the same as the one described above. The implementation uses loops rather than building a table. Some code has been omitted, and explanatory comments have been added. The full implementation is in the code on GitHub.

func (nfa *NFA) SubsetConstruction() (dI utils.State, dF mapset.Set, dRules dfarule.RuleMap) {
	I := nfa.I         // NFAの初期状態
	F := nfa.F         // NFAの受理状態
	Rules := nfa.Rules // NFAの遷移規則

	dI = utils.NewState(0)     // DFAの初期状態
	dF = mapset.NewSet()       // DFAの受理状態
	dRules = dfarule.RuleMap{} // DFAの遷移規則

	dStates := DFAStatesMap{} // NFAの状態集合をキーにDFAの状態集合を導くマップ
	dStates[mapset.NewSet(I)] = utils.NewState(0)

	queue := mapset.NewSet(mapset.NewSet(I)) // 次に部分集合構成法を適用すべき状態集合のキュー
	for queue.N() != 0 {
		dstate := queue.Pop().(mapset.Set) // 処理する状態集合を取得(Pop)する

		// もとの状態集合に集合状態が含まれていればDFAの受理状態として登録
		if F.Intersect(dstate).N() > 0 {
			dF.Add(dStates.getState(dstate))
		}

		Sigma := nfa.AllSymbol() // nfaの遷移規則に出現するすべてのシンボル(文字)
		for c := range Sigma.Iter() {
			dnext := mapset.NewSet() // 処理中の状態集合から遷移し得る状態の集合
			for q := range dstate.Iter() {
				d, ok := Rules[nfarule.NewRuleArgs(q.(utils.State), c.(rune))]
				if ok {
					dnext = dnext.Union(d)
				}
			}

			// 遷移先がなければ、次のループへ。
			if dnext.N() == 0 {
				continue
			}

			// 遷移先を未検証な状態集合は検証する必要があるため、キューに追加する。
			if !dStates.haveKey(dnext) {
				queue.Add(dnext)
				dStates[dnext] = utils.NewState(len(dStates)) // 状態の番号が一意になるように
			}

			for k := range dStates {
				if k.Equal(dnext) {
					dnext = k // Swap to avoid problems with pointers
				}
			}
			dRules[dfarule.NewRuleArgs(dStates[dstate], c.(rune))] = dStates[dnext] // DFAの遷移規則を追加
		}
	}

	return
}

The SubsetConstruction() method returns the initial state, accepting states, and transition rules needed to create a DFA. These values are passed to the constructor for the DFA struct defined in dfa/dfa.go.

The entire process can be run through the ToDFA function defined in nfa2dfa/nfa2dfa.go.

func ToDFA(nfa *nfa.NFA) *dfa.DFA {
	nfa.ToWithoutEpsilon()
	I, F, Delta := nfa.SubsetConstruction()
	return dfa.NewDFA(I, F, Delta)
}

Minimizing a DFA

We can now obtain a DFA equivalent to an NFA. However, the DFA produced by these steps still contains redundancy. Every DFA has equivalent DFAs with different structures. I will describe how to find the minimal one, with the fewest states. From here on, finding the minimal form of a DFA is called DFA minimization.

The minimization algorithm

A DFA can be minimized by finding equivalent states and combining them. Two states can be considered equivalent when they satisfy the following conditions.

  • Both are non-accepting, or both are accepting.
  • They have the same number of destinations.
  • The same symbols lead to the same states (their destinations cannot be distinguished).

Let's use the following example.

minimize_dfa_example

First, write the transition rules as a table.

Source state a Accepting?
q0 q1 -
q1 q2 o
q2 q2 o

Checking the table against the conditions above shows that q1 and q2 are equivalent. Once we know that, we can merge q2 into q1 to create the following DFA.

minimize_dfa_result

Implementing minimization

I implemented minimization as a method on *DFA in dfa/dfa.go. The method is excerpted below. It may differ a little from the algorithm described above, but it essentially does the same thing.

func (dfa *DFA) Minimize() {
	states := mapset.NewSet(dfa.I) // DFA内の状態集合
	for _, v := range dfa.Rules {
		states.Add(v)
	}
	n := states.N()

	eqMap := map[utils.State]utils.State{} // 等価な状態を関連付けたマップ
	for i := 0; i < n; i++ {
		q1 := utils.NewState(i)
		for j := i + 1; j < n; j++ {
			q2 := utils.NewState(j)
			if !dfa.isEquivalent(q1, q2) {
				continue // q1とq2が等価な状態でなければ、次の状態を調べる。
			}
			if _, ok := eqMap[q2]; ok {
				continue
			}
			eqMap[q2] = q1         // 等価な状態を関連付ける。
			dfa.mergeState(q1, q2) // 状態をマージする
		}
	}
}

The following part tripped me up during implementation.

if _, ok := eqMap[q2]; ok {
	continue
}

This part is useful when, for example, q0, q1, and q2 are all equivalent. In that case, the transition rules of q1 and q2 need to be merged into q0. However, simply merging one of each pair of compared states into the other causes a problem. The loop here merges states in the following order.

  1. q0 and q1 are equivalent → Merge q1 into q0.
  2. q0 and q2 are equivalent → Merge q2 into q0.
  3. q1 and q2 are equivalent → Merge q2 into q1.

The third step is the problem. q2 has already been merged into q0, but it is then also merged into q1. To avoid this, the merge is skipped if the source state is already registered in eqMap.

Simulating the DFA (matching)

So far, I have explained how to obtain a DFA equivalent to a regular expression. Next is the implementation that simulates the DFA to perform pattern matching.

The DFA struct

It is defined in dfa/dfa.go as follows.

type DFA struct {
	I     utils.State     // 初期状態
	F     mapset.Set      // 受理状態
	Rules dfarule.RuleMap // 遷移規則
}

The initial and accepting states are the same as in the NFA. The transition rules differ slightly. Because each destination is unique, the map value is utils.State rather than mapset.Set. It is defined in dfa/dfarule/dfarule.go as follows.

type RuleMap map[RuleArgs]utils.State

type RuleArgs struct {
	From utils.State // from state
	C    rune        // input symbol
}

The Runtime struct

The Runtime struct represents the DFA runtime. Its fields hold the DFA struct and the current state (cur). It is defined in dfa/dfa.go as follows. The constructor sets the current state to the initial state of the DFA passed as its argument.

type Runtime struct {
	d   *DFA
	cur utils.State	// 現在の状態
}

func NewRuntime(d *DFA) (r *Runtime) {
	r = &Runtime{
		d: d,
	}
	r.cur = d.I
	return
}

Methods on this Runtime struct perform the actual DFA simulation.

The transit method

The transit method takes a character (symbol) and changes the state according to the transition rules. Its return value indicates whether a transition was possible.

func (r *Runtime) transit(c rune) bool {
	key := dfarule.NewRuleArgs(r.cur, c)
	_, ok := r.d.Rules[key]
	if ok {
		r.cur = r.d.Rules[key]
		return true
	}
	return false
}

The isAccept method

The isAccept method checks whether the current state is accepting. It returns true for an accepting state and false otherwise.

func (r *Runtime) isAccept() bool {
	accepts := r.d.F
	if accepts.Contains(r.cur) {
		return true
	}
	return false
}

The Matching method

The Matching method reads the supplied string one character at a time through to the end, performing transitions according to the transition function. It ultimately returns whether the DFA accepted the string.

Whether a DFA obtained from a regular expression accepts a string is equivalent to whether the regular expression matches that string. To perform regular expression matching, we can therefore convert the expression into a DFA and call this method.

func (r *Runtime) Matching(str string) bool {
	r.cur = r.d.I
	for _, c := range []rune(str) {
		if !r.transit(c) {
			return false
		}
	}
	return r.isAccept()
}

Trying it out

Create a file like the following and run it with go run main.go.

package main

import (
	"fmt"
	"github.com/8ayac/dfa-regex-engine/nfa2dfa"
	"github.com/8ayac/dfa-regex-engine/parser"
	"github.com/8ayac/dfa-regex-engine/utils"
)

func main() {
	// 正規表現のパターン
	pattern := "bana(na)*"

	psr := parser.NewParser(pattern)        // パーサの構造体を作る
	ast := psr.GetAST()                     // ASTを取得
	frg := ast.Assemble(utils.NewContext()) // ASTのルートノードのAssembleメソッドを実行
	nfa := frg.Build()                      // Fragment構造体をNFA構造体に変換
	nfa.ToWithoutEpsilon()					// ε-NFAをNFAに変換
	d := nfa2dfa.ToDFA(nfa)                 // NFAをDFAに変換
	d.Minimize()							// DFAを最小化
	r := d.GetRuntime()                     // ランタイムを取得

	// マッチングを実行
	for _, s := range []string{"bana", "banana", "banana", "banaNa", "apple"} {
		MATCHED := r.Matching(s)
		if MATCHED {
			fmt.Printf("%s\t=> Matched!\n", s)
		} else {
			fmt.Printf("%s\t=> NOT Matched...\n", s)
		}
	}
}

The output is as follows.

$ go run main.go
bana	=> Matched!
banana	=> Matched!
banana	=> Matched!
banaNa	=> NOT Matched...
apple	=> NOT Matched...

The dfaregex package

It works, but writing out "build the AST, call Assemble, take the fragment…" every time is tedious. I therefore created a Regexp struct in the dfaregex package whose constructor runs the required steps together.

package dfaregex

(snip)

type Regexp struct {
	regexp string
	d      *dfa.DFA
}

func NewRegexp(re string) *Regexp {
	psr := parser.NewParser(re)
	ast := psr.GetAST()
	frg := ast.Assemble(utils.NewContext())
	nfa := frg.Build()
	d := nfa2dfa.ToDFA(nfa)
	d.Minimize()

	return &Regexp{
		regexp: re,
		d:      d,
	}
}

func Compile(re string) *Regexp {
	return NewRegexp(re)
}

func (re *Regexp) Match(s string) bool {
	rt := re.d.GetRuntime()
	return rt.Matching(s)
}

The Compile method is simply a wrapper around the constructor. The Match method creates a runtime each time and performs the string matching.

With this wrapper, the earlier main.go becomes the following shorter version.

package main

import (
	"fmt"
	"github.com/8ayac/dfa-regex-engine/dfaregex"
)

func main() {
	pattern := "bana(na)*"
	re := dfaregex.Compile(pattern)
	
	for _, s := range []string{"bana", "banana", "banana", "banaNa", "apple"} {
		MATCHED := re.Match(s)
		if MATCHED {
			fmt.Printf("%s\t=> Matched!\n", s)
		} else {
			fmt.Printf("%s\t=> NOT Matched...\n", s)
		}
	}
}

Thoughts and closing remarks

I became interested in regular expression engines after learning about ReDoS (Regular Expression DoS) while bug hunting as a hobby. Implementing an engine seems to have made me even more interested in ReDoS.

References