# A closer look at TDFA

Angelo Borsotti
<EMAIL_ADDRESS>Ulya Trafimovich
<EMAIL_ADDRESS>
(2022)

###### Abstract

We present an algorithm for regular expression parsing and submatch extraction
based on tagged deterministic finite automata. The algorithm works with
different disambiguation policies. We give detailed pseudocode for the
algorithm, covering important practical optimizations. All transformations
from a regular expression to an optimized automaton are explained on a step-
by-step example. We consider both ahead-of-time and just-in-time
determinization and describe variants of the algorithm suited to each setting.
We provide benchmarks showing that the algorithm is very fast in practice. Our
research is based on two independent implementations: an open-source lexer
generator RE2C and an experimental Java library.

## Introduction

This paper describes tagged deterministic finite automata (TDFA). To the best
of our knowledge, it is the first _practical_ submatch extraction and parsing
algorithm based on deterministic finite automata that is capable of both POSIX
and leftmost greedy disambiguation. Most of the theory behind TDFA is not new,
but the previous papers are incomplete and lack important details. This paper
consolidates our previous research and provides a comprehensive description of
the algorithm. We hope that it will make TDFA easier to implement in practice.

Here is a brief history of TDFA development. In 2000 Laurikari published the
original paper [1]. In 2007 Kuklewicz implemented TDFA in a Haskell library
with POSIX longest-match disambiguation; he gave only an informal description
[2]. In 2016 Trafimovich presented TDFA with lookahead [3], implemented them
in the open-source lexer generator RE2C [4] and formalized Kuklewicz
disambiguation algorithm. In 2017 Borsotti implemented TDFA in an experimental
Java library [5]. In 2019 Borsotti and Trafimovich adapted Okui-Suzuki
disambiguation algorithm to TDFA and showed it to be faster than Kuklewicz
algorithm [6]. In 2020 Trafimovich published an article about TDFA
implementation in RE2C [7]. Finally, the present paper incorporates our past
research and adds novel findings on multi-pass TDFA that are better suited to
just-in-time determinization.

Before diving into details, we recall the key concepts discussed in the paper.

_Regular expressions_ (REs) are a notation for describing sets of strings
known as regular languages, or Type-3 languages in the Chomsky hierarchy. They
were first defined by Kleene [9] as sets of strings constructed from the
alphabet symbols and the empty word via the application of three basic
operations: concatenation, alternative and iteration. Later REs were
formalized via the notion of Kleene algebra [10]. In practice REs have many
extensions that vary in complexity and expressive power.

_Submatch extraction_ is an extension of REs that allows one to identify input
positions matching specific positions in a RE. Recall the difference between
_recognition_ and _parsing_ : to recognize a string means to determine its
membership in a language, but to parse a string means to also find its
derivation in a language grammar. Submatch extraction is in between: on one
extreme it approaches recognition (if there are no submatch markers in a RE),
but on the other extreme it is identical to parsing (if every position in a RE
is marked). In general it requires constructing a partial derivation, which
can be implemented more efficiently than full parsing.

_Finite state automata_ are a formalism equivalent to REs in the sense that
every RE can be converted to a deterministic finite automaton (DFA) or a
nondeterministic finite automaton (NFA), and vice versa. There are many
different kinds of NFA, but there is a unique minimal DFA for a given RE. Both
NFA and DFA solve the recognition problem for REs in linear time in the length
of input. In practice DFA are faster because they follow a single path, while
NFA have to track multiple paths simultaneously. NFA can be converted to DFA
using a _determinization_ procedure, but the resulting DFA may be
exponentially larger than the NFA.

_Tags_ are submatch markers: they mark positions in a RE that should be mapped
to offsets in the input string. When a RE is converted to an NFA, tags are
placed on the NFA transitions. This effectively turns NFA into a
nondeterministic finite-state _transducer_ that rewrites symbolic strings into
tagged strings (where tags are placed in-between symbols, marking submatch
boundaries). Conversion from a RE to a tagged NFA is natural if NFA mirrors
the structure of RE, as in the case of Thompson’s construction.

Determinization of a tagged NFA is problematic, because in a DFA multiple NFA
paths are collapsed into one, causing conflicts when the same tag has
different values on different NFA paths. To keep track of all possible tag
values, a DFA is augmented with _registers_ and _operations_ on transitions
that update register values. The number of registers and operations depends
only on the RE structure and tag density, but not on the input string,
therefore it adds only a constant overhead to the DFA execution. We describe
techniques that reduce redundant operations and minimize the overhead in
practice.

_Ambiguity_ is yet another problem for submatch extraction; it means the
existence of multiple different parse trees for the same input. Ambiguity
should not be confused with non-determinism, which means the existence of
multiple possibilities during matching that get canceled as more input is
consumed; ambiguity is a property of a RE. One way to resolve it is a
_disambiguation policy_ , the most notable examples being the leftmost-greedy
and the longest-match (POSIX) policies. TDFA can work with both policies, and
there is no runtime overhead on disambiguation — it is built into TDFA
structure. Some RE engines provide other ways to resolve ambiguity, such as
user-defined precedence rules, but these are ad-hoc, error-prone and often
difficult to reason about.

RE engines based on DFA can be divided in two groups: those using _ahead-of-
time_ (AOT) determinization (e.g. lexer generators) and those using _just-in-
time_ (JIT) determinization (e.g. runtime libraries). The former can spend
considerable amount of time on preprocessing, but the latter face a tradeoff
between the time spent on preprocessing and the time spent on matching.
Therefore it makes sense to use different variants of the algorithm in each
case. We describe _single-pass_ TDFA that are a natural fit for ahead-of-time
determinization, and _multi-pass_ TDFA that are better suited to just-in-time
determinization.

In practice performance of a matching algorithm depends on the representation
of results. The most generic representation is a parse tree; it precisely
reflects a derivation. A more lightweight representation is a list of offsets
or a single offset per submatch position in a RE (the latter is used in the
POSIX regexec function). Another representation, more suitable for
transducers, is a _tagged string_ — a sequence of input symbols interspersed
with tags. If a RE contains tags for every subexpression, then it is possible
to reconstruct a parse tree from offset lists or a tagged string (a procedure
is given in [6], section 6). TDFA can be used with all the above
representations, but it is more natural to use offsets with single-pass TDFA
and tagged strings with multi-pass TDFA.

The rest of the paper is structured as follows. Section 1 defines REs and
their conversion to nondeterministic automata. Section 2 defines TDFA and
determinization. Section 3 describes optimizations and practical
implementation details. Section 4 describes multi-pass TDFA and their
application to just-in-time determinization. Section 5 provides benchmarks and
comparison with other algorithms. Section 6 contains conclusions, and section
7 contains ideas for future work.

## Conventions

In this paper we use _pseudocode_ rather than formal mathematical notation to
describe algorithms. We focus on the practical side, because we want to
encourage TDFA implementation in real-world programs. The most theoretically
challenging part of the algorithm (POSIX disambiguation) is formalized in our
previous paper [6], and the core of the algorithm is based on the well-known
idea of determinization via powerset construction that does not need a formal
introduction.

In the pseudocode, we try to balance between formality and clarity. We omit
the definitions of basic operations on data structures, such as “append to a
list” or “push on stack”. We sometimes use set notation with predicates, and
sometimes prefer explicit loops that iterate over the elements of a set. To
reduce verbosity, we assume that function arguments are passed by reference
and modifications to them are visible in the calling function (although some
functions have explicit return values).

All algorithms presented here are implemented in the open-source lexer
generator RE2C and are known to work in practice.

##  1 TNFA

In this section we define regular expressions, their conversion to
nondeterministic automata and matching.

######  Definition 1.

Regular expressions (REs) over finite alphabet $\Sigma$ are:

  1. 1.

Empty RE $\epsilon$, unit RE $a\in\Sigma$ and tag $t\in\mathbb{N}$.

  2. 2.

Alternative $e_{1}|e_{2}$, concatenation $e_{1}e_{2}$ and repetition
$e_{1}^{n,m}$ $(0\\!\leq\\!n\\!\leq\\!m\\!\leq\\!\infty)$ where $e_{1}$ and
$e_{2}$ are REs over $\Sigma$.

Tags mark submatch positions in REs. Unlike capturing parentheses, tags are
not necessarily paired. Capturing groups can be represented with tags, but the
correspondence may be more complex than a pair of tags per group, e.g. POSIX
capturing groups require additional hierarchical tags [6].

Generalized repetition $e^{n,m}$ can be bounded ($m<\infty$) or unbounded
($m=\infty$). Unbounded repetition $e^{0,\infty}$ is the canonical Kleene
iteration, shortened as $e^{*}$. Bounded repetition is usually desugared via
concatenation, but we avoid desugaring as it may duplicate tags and change
submatch semantics in a RE.

######  Definition 2.

Tagged Nondeterministic Finite Automaton (TNFA) is a structure
$(\Sigma,T,Q,q_{0},q_{f},\Delta)$, where:

  * $\Sigma$ is a finite set of symbols (alphabet)

  * $T$ is a finite set of tags

  * $Q$ is a finite set of states with initial state $q_{0}$ and final state $q_{f}$

  * $\Delta$ is a transition relation that contains transitions of two kinds:

    * transitions on alphabet symbols $(q,a,p)$ where $q,p\in Q$ and $a\in\Sigma$

    * optionally tagged $\epsilon$-transitions with priority $(q,i,t,p)$ where $q,p\in Q$, $i\in\mathbb{N}$ and $t\in T\cup\overline{T}\cup\\{\epsilon\\}$

TNFA is in essence a non-deterministic finite state transducer with input
alphabet $\Sigma$ and output alphabet $\Sigma\cup T\cup\overline{T}$.
$\overline{T}=\\{-t\mid t\in T\\}$ is the set of all negative tags which
represent the absence of match: they appear whenever there is a way to bypass
a tagged subexpression in a RE, such as alternative or repetition with zero
lower bound. Negative tags serve a few purposes: they prevent propagation of
stale submatch values from one iteration to another, they spares the need to
initialize tags, and they are needed for POSIX disambiguation [6]. Priorities
are used for transition ordering during $\epsilon$-closure construction.

Algorithm 2 on page 2 shows TNFA construction: it performs top-down structural
recursion on a RE, passing the final state on recursive descent into
subexpressions and using it to connect subautomata. This is similar to
Thompson’s construction, except that non-essential $\epsilon$-transitions are
removed and tagged transitions are added. The resulting automaton mirrors the
structure of RE and preserves submatch information and ambiguity in it.

1

_$\underline{simulation\big{(}(\Sigma,T,Q,q_{0},q_{f},\Delta),\;a_{1}\ldots
a_{n}\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

2 $m_{0}:$ vector of offsets of size $|T|$

3 $C=\\{(q_{0},m_{0})\\}$

4 for $k=\overline{1,n}$ do

5 $C=epsilon\rule{4.5pt}{0.5pt}closure(C,\Delta,q_{f},k)$

6 $C=step\rule{4.5pt}{0.5pt}on\rule{4.5pt}{0.5pt}symbol(C,\Delta,a_{k})$

7 if $C=\emptyset$ then return $\varnothing$

8

9 $C=epsilon\rule{4.5pt}{0.5pt}closure(C,\Delta,q_{f},n)$

10 if $\exists(q,m)$ in $C\mid q=q_{f}$ then return $m$

11 else return $\varnothing$

12

13

_$\underline{step\rule{4.5pt}{0.5pt}on\rule{4.5pt}{0.5pt}symbol\big{(}C,\Delta,a\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

14 return $\\{(p,m)\mid(q,m)$ in $C$ and $(q,a,p)\in\Delta\\}$

15

16

17

_$\underline{epsilon\rule{4.5pt}{0.5pt}closure\big{(}C,\Delta,q_{f},k\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

18 $C^{\prime}:$ empty sequence of configurations

19 for $(q,m)$ in $C$ in reverse order do

20 push $(q,m)$ on stack

21

22 while stack is not empty do

23 pop $(q,m)$ from stack

24 append $(q,m)$ to $C^{\prime}$

25 for each $(q,i,t,p)\in\Delta$ ordered by priority $i$ do

26 if $t>0$ then $m[t]=k$

27 else $m[-t]=\mathbf{n}$

28 if configuration with state $p$ is not in $C^{\prime}$ then

29 push $(p,m)$ on stack

30

31

32

33 return $\\{(q,m)$ in $C^{\prime}\mid q=q_{f}$ or

34 return $\\{(q,m)$ in $C^{\prime}\mid$
$\exists(q,a,\rule{4.5pt}{0.5pt})\in\Delta$ where $a\in\Sigma\\}$

35

36

37

Algorithm 1 TNFA simulation.

Algorithm 1 defines TNFA simulation on a string. It starts with a single
configuration $(q_{0},m_{0})$ consisting of the initial state $q_{0}$ and an
empty vector of tag values, and loops over the input symbols until all of them
are matched or the configuration set becomes empty, indicating match failure.
At each step the algorithm constructs $\epsilon$-closure of the current
configuration set, updating tag values along the way, and steps on transitions
labeled with the current input symbol. Finally, if all symbols have been
matched and there is a configuration with the final state $q_{f}$, the
algorithm terminates successfully and returns the final vector of tag values.
Otherwise it returns a failure. The algorithm uses leftmost greedy
disambiguation; POSIX disambiguation is more complex and requires a different
$\epsilon$-closure algorithm [6]. Figure 1 in section 2 shows an example of
TNFA simulation.

1

2

_$\underline{tn\\!f\\!a(e,q_{f})}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

3

4 if $e=\epsilon$ then

5 return $(\Sigma,\emptyset,\\{q_{f}\\},q_{f},q_{f},\emptyset)$

6

7 else if $e=a\in\Sigma$ then

8 return
$(\Sigma,\emptyset,\\{q_{0},q_{f}\\},q_{0},q_{f},\\{(q_{0},a,q_{f})\\})$

9

10 else if $e=t\in\mathbb{N}$ then

11 return
$(\Sigma,\\{t\\},\\{q_{0},q_{f}\\},q_{0},q_{f},\\{(q_{0},1,t,q_{f})\\})$

12

13 else if $e=e_{1}\cdot e_{2}$ then

14 $(\Sigma,T_{2},Q_{2},q_{2},q_{f},\Delta_{2})=tn\\!f\\!a(e_{2},q_{f})$

15 $(\Sigma,T_{1},Q_{1},q_{1},q_{2},\Delta_{1})=tn\\!f\\!a(e_{1},q_{2})$

16 return $(\Sigma,T_{1}\cup T_{2},Q_{1}\cup
Q_{2},q_{1},q_{f},\Delta_{1}\cup\Delta_{2})$

17

18 else if $e=e_{1}\mid e_{2}$ then

19 $(\Sigma,T_{2},Q_{2},q_{2},q_{f},\Delta_{2})=tn\\!f\\!a(e_{2},q_{f})$

20
$(\Sigma,T_{2},Q^{\prime}_{2},q^{\prime}_{2},q_{f},\Delta^{\prime}_{2})=ntags(T_{2},q_{f})$

21
$(\Sigma,T_{1},Q_{1},q_{1},q^{\prime}_{2},\Delta_{1})=tn\\!f\\!a(e_{2},q^{\prime}_{2})$

22
$(\Sigma,T_{1},Q^{\prime}_{1},q^{\prime}_{1},q_{2},\Delta^{\prime}_{1})=ntags(T_{1},q_{2})$

23 $Q=Q_{1}\cup Q^{\prime}_{1}\cup Q_{2}\cup Q^{\prime}_{2}\cup\\{q_{0}\\}$

24
$\Delta=\Delta_{1}\cup\Delta^{\prime}_{1}\cup\Delta_{2}\cup\Delta^{\prime}_{2}\cup\\{(q_{0},1,\epsilon,q_{1}),(q_{0},2,\epsilon,q^{\prime}_{1})\\}$

25 return $(\Sigma,T_{1}\cup T_{2},Q,q_{0},q_{f},\Delta)$

26

27 else if $e=e_{1}^{n,m}\mid_{1<n\leq m\leq\infty}$ then

28
$(\Sigma,T_{1},Q_{1},q_{2},q_{f},\Delta_{1})=tn\\!f\\!a(e_{1}^{n\\!-\\!1,m\\!-\\!1},q_{f})$

29 $(\Sigma,T_{2},Q_{2},q_{1},q_{2},\Delta_{2})=tn\\!f\\!a(e_{1},q_{2})$

30 return $(\Sigma,T_{1}\cup T_{2},Q_{1}\cup
Q_{2},q_{1},q_{f},\Delta_{1}\cup\Delta_{2})$

31

32 else if $e=e_{1}^{1,m}\mid_{1<m<\infty}$ then

33 if $m=1$ then return $tn\\!f\\!a(e_{1},q_{f})$

34
$(\Sigma,T_{1},Q_{1},q_{1},q_{f},\Delta_{1})=tn\\!f\\!a(e_{1}^{1,m\\!-\\!1},q_{f})$

35 $(\Sigma,T_{2},Q_{2},q_{0},q_{2},\Delta_{2})=tn\\!f\\!a(e_{1},q_{1})$

36
$\Delta=\Delta_{1}\cup\Delta_{2}\cup\\{(q_{1},1,\epsilon,q_{f}),(q_{1},2,\epsilon,q_{2})\\}$

37 return $(\Sigma,T_{1}\cup T_{2},Q_{1}\cup Q_{2},q_{0},q_{f},\Delta)$

38

39 else if $e=e_{1}^{0,m}$ then

40 $(\Sigma,T_{1},Q_{1},q_{1},q_{f},\Delta_{1})=tn\\!f\\!a(e_{1}^{1,m},q_{f})$

41
$(\Sigma,T_{1},Q^{\prime}_{1},q^{\prime}_{1},q_{f},\Delta^{\prime}_{1})=ntags(T_{1},q_{f})$

42 $Q=Q_{1}\cup Q^{\prime}_{1}\cup\\{q_{0}\\}$

43
$\Delta=\Delta_{1}\cup\Delta^{\prime}_{1}\cup\\{(q_{0},1,\epsilon,q_{1}),(q_{0},2,\epsilon,q^{\prime}_{1})\\}$

44 return $(\Sigma,T_{1},Q,q_{0},q_{f},\Delta)$

45

46 else if $e=e_{1}^{1,\infty}$ then

47 $(\Sigma,T_{1},Q_{1},q_{0},q_{1},\Delta_{1})=tn\\!f\\!a(e_{1},q_{1})$

48 $Q=Q_{1}\cup\\{q_{f}\\}$

49
$\Delta=\Delta_{1}\cup\\{(q_{1},1,\epsilon,q_{0}),(q_{1},2,\epsilon,q_{f})\\}$

50 return $(\Sigma,T_{1},Q,q_{0},q_{f},\Delta)$

51

52

 _$\underline{ntags(T,q_{f})}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

53 $\\{t_{i}\\}_{i=1}^{n}=T$

54 $Q=\\{q_{i}\\}_{i=0}^{n}$ where $q_{n}=q_{f}$

55 $\Delta=\\{(q_{i-1},1,-t_{i},q_{i})\\}_{i=1}^{n}$

56 return $(\Sigma,T,Q,q_{0},q_{f},\Delta)$

57

58

59

60

Algorithm 2 TNFA construction.

##  2 TDFA

In this section we define TDFA and show how to convert TNFA to TDFA.

######  Definition 3.

Tagged Deterministic Finite Automaton (TDFA) is a structure
$(\Sigma,T,S,S_{f},s_{0},R,R_{f},\delta,\varphi)$, where:

  * $\Sigma$ is a finite set of symbols (alphabet)

  * $T$ is a finite set of tags

  * $S$ is a finite set of states with initial state $s_{0}$ and a subset of final states $S_{f}\subseteq S$

  * $R$ is a finite set of registers with a subset of final registers $R_{f}$ (one per tag)

  * $\delta:S\times\Sigma\rightarrow S\times\mathbb{O}^{*}$ is a transition function

  * $\varphi:S_{f}\rightarrow\mathbb{O}^{*}$ is a final function

  * where $\mathbb{O}$ is a set of register operations of the following types:

    * set register $i$ to nil or to the current position: $i\leftarrow v$, where $v\in\\{\mathbf{n},\mathbf{p}\\}$

    * copy register $j$ to register $i$: $i\leftarrow j$

    * copy register $j$ to register $i$ and append history: $i\leftarrow j\cdot h$, where $h$ is a string over $\\{\mathbf{n},\mathbf{p}\\}$

Compared to an ordinary DFA, TDFA is extended with a set of tags $T$, a set of
registers $R$ with one final register per tag, and register operations that
are attributed to transitions and final states (the $\delta$ and $\varphi$
functions). $\mathbb{O}^{*}$ denotes the set of all sequences of operations
over $\mathbb{O}$. Operations can be of three types: set, copy, append. Set
operations are used for _single-valued_ tags (those represented with a single
offset), append operations are used for _multi-valued_ tags (those represented
with an offset list), and copy operations are used for all tags. The decision
which tags are single-valued and which ones are multi-valued is arbitrary and
individual for each tag (it may be, but does not have to be based on whether
the tag is under repetition). Register values are denoted by special symbols
$\mathbf{n}$ and $\mathbf{p}$, which mean _nil_ and the _current position_
(offset from the beginning of the input string).

Recall the canonical determinization algorithm that is based on powerset
construction: NFA is simulated on all possible strings, and the subset of NFA
states at each step of the simulation forms a new DFA state, which is either
mapped to an existing identical state or added to the growing set of DFA
states. Since the number of different subsets of NFA states is finite,
determinization eventually terminates. The presence of tags complicates
things: it is necessary to track tag values, which depend on the offset that
increases at every step. This makes the usual powerset construction
impossible: DFA states augmented with tag values are different and cannot be
mapped. As a result the set of states grows indefinitely and determinization
does not terminate. To address this problem, Laurikari used indirection:
instead of storing tag values in TDFA states, he stored value locations —
_registers_. As long as two TDFA states have the same registers, the actual
values in registers do not matter: they change dynamically at runtime (during
TDFA execution), but they do not affect TDFA structure. A similar approach was
used by Grathwohl [8], who described it as splitting the information contained
in a value into static and dynamic parts. The indirection is not free: it
comes at the cost of runtime operations that update register values. But it
solves the termination problem, as the required number of registers is finite,
unlike the number of possible register values.

From the standpoint of determinization, a TDFA state is a pair. The first
component is a set of configurations $(q,r,l)$ where $q$ is a TNFA state, $r$
is a vector of registers (one per tag) and $l$ is a sequence of tags. Unlike
TNFA simulation that updates tag values immediately when it encounters a
tagged transition, determinization delays the application of tags until the
next step. It records tag sequences along TNFA paths in the
$\epsilon$-closure, but instead of applying them to the current transition, it
stores them in configurations of the new TDFA state and later applies them to
the outgoing transitions. This allows filtering tags by the lookahead symbol:
configurations that have no TNFA transitions on the lookahead symbol do not
contribute any register operations to TDFA transition on that symbol. The use
of the lookahead symbol is what distinguishes TDFA(1) from TDFA(0) [3]; it
considerably reduces the number of operations and registers. During
$\epsilon$-closure construction configurations are extended to four components
$(q,r,h,l)$ where $h$ is the sequence of tags inherited from the origin TDFA
state and $l$ is the new sequence constructed by the $\epsilon$-closure.

1

_$\underline{determinization\big{(}\Sigma,T,Q,q_{0},q_{f},\Delta\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

2 $S,S_{f}:$ empty sets of states

3 $\delta:$ undefined transition function

4 $\varphi:$ undefined final function

5
$r_{0}=\\{1,...\,,|T|\\},\;R_{f}=\\{|T|\\!+\\!1,...\,,2|T|\\},\;R=\\{r_{0}\\}\cup
R_{f}$

6 $C=epsilon\rule{4.5pt}{0.5pt}closure(\\{(q_{0},r_{0},\epsilon,\epsilon)\\})$

7 $P=precedence(C)$

8 $s_{0}=add\rule{4.5pt}{0.5pt}state(S,S_{f},R_{f},\varphi,C,P,\epsilon)$

9 for each state $s\in S$ do

10 $V:$ map from tag and operation RHS to register

11 for each symbol $a\in\Sigma$ do

12 $B=step\rule{4.5pt}{0.5pt}on\rule{4.5pt}{0.5pt}symbol(s,a)$

13 $C=epsilon\rule{4.5pt}{0.5pt}closure(B)$

14 $O=transition\rule{4.5pt}{0.5pt}regops(C,R,V)$

15 $P=precedence(C)$

16 $s^{\prime}=add\rule{4.5pt}{0.5pt}state(S,S_{f},R_{f},\varphi,C,P,O)$

17 $\delta(s,a)=(s^{\prime},O)$

18

19

20 return TDFA $(\Sigma,T,S,S_{f},s_{0},R,R_{f},\delta,\varphi)$

21

22

_$\underline{add\rule{4.5pt}{0.5pt}state\big{(}S,S_{f},R_{f},\varphi,C,P,O\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

23 $X=\\{(q,r,l)\mid(q,r,\rule{4.5pt}{0.5pt},l)\in C\\}$

24 $s=(X,P)$

25 if $s\in S$ then

26 return $s$

27 else if $\exists s^{\prime}\in S$ such that $map(s,s^{\prime},O)$ then

28 return $s^{\prime}$

29

30 else

31 add $s$ to $S$

32 if $\exists(q,r,l)\in X$ such that $q=q_{f}$ then

33 add $s$ to $S_{f}$

34 $\varphi(s)=final\rule{4.5pt}{0.5pt}regops(R_{f},r,l)$

35

36 return $s$

37

38

39

 _$\underline{map\big{(}(X,P),(X^{\prime},P^{\prime}),O\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

40 if $X$ and $X^{\prime}$ have different subsets of TNFA states

41 if  or different lookahead tags for some TNFA state

42 if  or precedence is different: $P\neq P^{\prime}$ then

43 return $f\\!alse$

44

45 $M,M^{\prime}:$ empty maps from register to register

46 for each pair $(q,r,l)\in X$ and $(q,r^{\prime},l)\in X^{\prime}$ do

47 for each $t\in T$ do

48 if $history(l,t)=\epsilon$ or $t$ is a multi-tag then

49 $i=r[t],\;j=r^{\prime}[t]$

50 if both $M[i],M^{\prime}[j]$ are undefined then

51 $M[i]=j,\;M^{\prime}[j]=i$

52

53 else if $M[i]\neq j$ or $M^{\prime}[j]\neq i$ then

54 return $f\\!alse$

55

56

57

58

59 for each operation $i\leftarrow\rule{4.5pt}{0.5pt}$ in $O$ do

60 replace register $i$ with $M[i]$

61 remove pair $(i,M[i])$ from $M$

62

63 for each pair $(j,i)\in M$ where $j\neq i$ do

64 prepend copy operation $i\leftarrow j$ to $O$

65

66 return $topological\rule{4.5pt}{0.5pt}sort(O)$

67

68

 _$\underline{precedence\big{(}C\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

69 return vector
$\\{q\mid(q,\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt})$ in
$C\\}$

70

71

72

_$\underline{step\rule{4.5pt}{0.5pt}on\rule{4.5pt}{0.5pt}symbol\big{(}(X,P),a\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

73 $B:$ empty sequence of configurations

74 for $(q,r,l)\in X$ ordered by $q$ in the order of $P$ do

75 if $\exists(q,a,p)\in\Delta\mid a\in\Sigma$ then

76 append $(p,r,l,\epsilon)$ to $B$

77

78 return $B$

79

80

 _$\underline{epsilon\rule{4.5pt}{0.5pt}closure\big{(}B\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

81 $C:$ empty sequence of configurations

82 for $(q,r,h,\epsilon)$ in $B$ in reverse order do

83 push $(q,r,h,\epsilon)$ on stack

84

85 while stack is not empty do

86 pop $(q,r,h,l)$ from stack

87 append $(q,r,h,l)$ to $C$

88 for each $(q,i,t,p)\in\Delta$ ordered by priority $i$ do

89 if configuration with state $p$ is not in $C$ then

90 push $(p,r,h,lt)$ on stack

91

92

93

94 return $\\{(q,r,h,l)$ in $C\mid q=q_{f}$ or

95 return $\\{(q,r,h,l)$ in $C\mid$
$\exists(q,a,\rule{4.5pt}{0.5pt})\in\Delta$ where $a\in\Sigma\\}$

96

97

 _$\underline{transition\rule{4.5pt}{0.5pt}regops\big{(}C,R,V\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

98 $O:$ empty list of operations

99 for each $(q,r,h,l)\in C$ do

100 for each tag $t\in T$ do

101 if $h_{t}=history(h,t)\neq\epsilon$ then

102 $v=regop\rule{4.5pt}{0.5pt}rhs(r,h_{t},t)$

103 if $V[t][v]$ is undefined then

104 $i=max\\{R\\}+1$

105 $R=R\cup\\{i\\}$

106 $V[t][v]=i$

107 append operation $i\leftarrow v$ to $O$

108

109 $r[t]=V[t][v]$

110

111

112

113 return $O$

114

115

 _$\underline{final\rule{4.5pt}{0.5pt}regops\big{(}R_{f},r,l\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

116 $O:$ empty list of operations

117 for each tag $t\in T$ do

118 if $l_{t}=history(l,t)\neq\epsilon$ then

119 append $R_{f}[t]\leftarrow regop\rule{4.5pt}{0.5pt}rhs(r,l_{t},t)$ to $O$

120

121

122 return $O$

123

124

 _$\underline{regop\rule{4.5pt}{0.5pt}rhs\big{(}r,h_{t},t\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

125 if $t$ is a multi-valued tag then

126 return $r[t]\cdot h_{t}$

127 else

128 return the last element of $h_{t}$

129

130

 _$\underline{history\big{(}h,t\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

131 switch $h$ do

132 case $\epsilon$ do return $\epsilon$

133 case $\;\;\,t\cdot h^{\prime}$ do return $\mathbf{p}\cdot
history(h^{\prime})$

134 case $-t\cdot h^{\prime}$ do return $\mathbf{n}\cdot history(h^{\prime})$

135 case $\;\,\,\rule{4.5pt}{0.5pt}\cdot h^{\prime}$ do return
$history(h^{\prime})$

136

137

138

Algorithm 3 Determinization of TNFA $(\Sigma,T,Q,q_{0},q_{f},\Delta)$.

The second component of TDFA state is precedence information. It is needed for
ambiguity resolution: if some TNFA state in the $\epsilon$-closure can be
reached by different paths, one path must be preferred over the others. This
affects submatch extraction, as the paths may have different tags. The form of
precedence information depends on the disambiguation policy. We keep the
details scoped to functions $precedence$,
$step\rule{5.0pt}{0.5pt}on\rule{5.0pt}{0.5pt}symbol$ and
$epsilon\rule{5.0pt}{0.5pt}closure$, so that algorithm 3 can be adapted to
different policies without the need to change its structure. In the case of
leftmost greedy policy precedence information is an order on configurations,
represented by $precedence$ as a vector of TNFA states:
$step\rule{5.0pt}{0.5pt}on\rule{5.0pt}{0.5pt}symbol$ uses it to construct the
initial closure, and $epsilon\rule{5.0pt}{0.5pt}closure$ performs depth-first
search following transitions from left to right. POSIX policy is more complex;
we do not include pseudocode for it here, but it is extensively covered in
[6].

Algorithm 3 works as follows. The main function $determinization$ starts by
allocating initial registers $r_{0}$ from $1$ to $|T|$ and final registers
$R_{f}$ from $|T|+1$ to $2|T|$. It constructs initial TDFA state $s_{0}$ as
the $\epsilon$-closure of the initial configuration
$(q_{0},r_{0},\epsilon,\epsilon)$. The initial state $s_{0}$ is added to the
set of states $S$ and the algorithm loops over states in $S$, possibly adding
new states on each iteration. For each state $s$ the algorithm explores
outgoing transitions on all alphabet symbols. Function
$step\rule{5.0pt}{0.5pt}on\rule{5.0pt}{0.5pt}symbol$ follows transitions
marked with a given symbol, and function $epsilon\rule{5.0pt}{0.5pt}closure$
constructs $\epsilon$-closure $C$, recording tag sequences along each fragment
of TNFA path. The set of configurations in the $\epsilon$-closure forms a new
TDFA state $s^{\prime}$. Function $transition\rule{5.0pt}{0.5pt}regops$ uses
the $h$-components of configurations in $C$ to construct register operations
on transition from $s$ to $s^{\prime}$. The same register is allocated for all
outgoing transitions with identical operation right-hand-sides, but different
tags do not share registers, and vacant registers from other TDFA states are
not reused (these rules ensure that there are no artificial dependencies
between registers, which makes optimizations easier without the need to
construct SSA). The new state $s^{\prime}$ is inserted into the set of states
$S$: function $add\rule{5.0pt}{0.5pt}state$ first tries to find an identical
state in $S$; if that fails, it looks for a state that can be mapped to
$s^{\prime}$; if that also fails, $s^{\prime}$ is added to $S$. If the new
state contains the final TNFA state, it is added to $S_{f}$, and the
$final\rule{5.0pt}{0.5pt}regops$ function constructs register operations for
the final _quasi-transition_ which does not consume input characters and gets
executed only once at the end of match.

TDFA states are considered identical if both components (configuration set and
precedence) coincide. States that are not identical but differ only in
registers can be made identical (mapped), provided that there is a bijection
between registers. Function $map$ attempts to construct such a bijection $M$:
for every tag, and for each pair of configurations it adds the corresponding
pair of registers to $M$. If either of the two registers is already mapped to
some other register, bijection cannot be constructed. For single-valued tags
mapping ignores configurations that have the tag in the lookahead sequence —
every transition out of TDFA state overwrites tag value with a set operation,
making the current register values obsolete. For multi-valued tags this
optimization is not possible, because append operations do not overwrite
previous values. If the mapping has been constructed successfully, $map$
updates register operations: for each pair of registers in $M$ it adds a copy
operation, unless the left-hand-side is already updated by a set or append
operation, in which case it replaces left-hand-side with the register it is
mapped to. The operations are topologically sorted
($topological\rule{5.0pt}{0.5pt}sort$ is defined on page 6); in the presence
of copy and append operations this is necessary to ensure that old register
values are used before they are updated. Topological sort ignores trivial
cycles such as append operation $i\leftarrow i\cdot h$, but if there are
nontrivial cycles the mapping is rejected (handling such cycles requires a
temporary register, which makes control flow more complex and inhibits
optimizations).

After determinization is done, the information in TDFA states is erased — it
is no longer needed for TDFA execution. States are just atomic values with no
internal structure. Disambiguation decisions are embedded in TDFA; there is no
disambiguation at runtime. The only runtime overhead compared to an ordinary
DFA is the execution of register operations on transitions. A TDFA may have
more states than a DFA for the same RE with all tags removed, because states
that can be mapped in a DFA cannot always be mapped in a TDFA. Minimization
can reduce the number of states, especially if it is applied after register
optimizations that can get rid of many operations and make more states
compatible. We focus on optimizations in section 3.

Figure 1:  Example for a RE $(1a2)^{*}3(a|4b)5b^{*}$: TNFA, simulation on
string $aab$, determinization, TDFA.

Figure 1 shows an example of TDFA construction:

  * ➔

The RE is $(1a2)^{*}3(a|4b)5b^{*}$. It defines language $\\{a^{n}b^{m}\mid
n+m>0\\}$ and has five tags $t_{1},t_{2},t_{3},t_{4},t_{5}$.

  * ➔

TNFA has three kinds of transitions: bold transitions on alphabet symbols
(four of them for each symbol in the RE), thin $\epsilon$-transitions with
priority and dashed $\epsilon$-transitions with priority and tag. Tags
$t_{1}$, $t_{2}$ are under repetition, so the zero-repetition path
$0\\!\rightarrow\\!5\\!\rightarrow\\!6\\!\rightarrow\\!7$ contains transitions
with negative tags $-t_{1}$, $-t_{2}$. Likewise tag $t_{4}$ is in alternative,
so path $8\\!\rightarrow\\!9\\!\rightarrow\\!10\\!\rightarrow\\!13$ contains
transition with negative tag $-t_{4}$. Tags $t_{3}$, $t_{5}$ are in top-level
concatenation and do not need negative tags.

  * ➔

TNFA simulation on string $aab$ consists of four steps. The first step starts
with state $0$. Every other step starts with states from the previous step and
follows transitions labeled with the current symbol. Each step constructs
$\epsilon$-closure by following $\epsilon$-paths and collecting tag sequence
along the way. The value of positive tags in the corresponding row of the
closure matrix is set to the number of characters consumed so far. The value
of negative tags is set to nil $\mathbf{n}$. The value of tags not in the
sequence is inherited from the previous closure. Simulation ends when all
characters have been consumed. Since the last closure contains a row with the
final state $17$, it is a match and the final tag values are $1,2,2,2,3$.

  * ➔

The match is ambiguous: it is possible to match $aab$ by following path
$0\\!\rightsquigarrow\\!2\\!\rightsquigarrow\\!2\\!\rightsquigarrow\\!12\\!\rightsquigarrow\\!17$
(let the greedy repetition consume $aa$) but it is also possible to follow
path
$0\\!\rightsquigarrow\\!2\\!\rightsquigarrow\\!9\\!\rightsquigarrow\\!15\\!\rightsquigarrow\\!17$
(let the greedy repetition consume only the first $a$). The first match is
preferable by both POSIX and leftmost-greedy policies.

  * ➔

Determinization is similar to simulation, but TDFA states store registers
instead of offsets. This solves the problem of mapping states that differ only
in tag values: for example, closures $1$ and $2$ cannot be mapped, although
they have identical states and tag sequences, but TDFA state corresponding to
closure $2$ is mapped to state $1$. This is possible due to the register
operations on the dashed backward transition. Note that there is one copy
operation $r_{12}\leftarrow r_{11}$, but other copy operations for $r_{11}$,
$r_{13}$, $r_{14}$ are combined with set operations, e.g.
$r_{11}\leftarrow\mathbf{p}$ is the combination of
$r_{16}\leftarrow\mathbf{p}$ and $r_{11}\leftarrow r_{16}$ (see lines 43 – 45
of algorithm 3).

  * ➔

Unlike simulation, determinization does not immediately apply tag sequences to
registers. Instead, it stores them as part of TDFA state (in the _lookahead_
column, shortened as _la_). Compare tag sequences on transitions to closures
$0$, $1$, $2$ to that in states $0$, $1$, $2$ respectively — these are the
same tags. Lookahead tags form register operations on the outgoing
transitions: e.g. lookahead tag $t_{1}$ in the first row of TDFA state $0$
(corresponding to tagged TNFA transition $1\\!\rightarrow\\!2$) forms
operation $r_{11}\leftarrow\mathbf{p}$.

  * ➔

For every distinct set or append operation
$transition\rule{5.0pt}{0.5pt}regops$ allocates a new register and stores the
updated tag value in it. Note that it would be impossible to reuse the same
register (e.g. to have $r_{1}\leftarrow\mathbf{p}$ instead of
$r_{11}\leftarrow\mathbf{p}$ on transition from state $0$ to $1$) because
there may be conflicting operations (e.g. $r_{12}\leftarrow\mathbf{n}$ for
lookahead tag $-t_{1}$). Therefore tag $t_{1}$ in TDFA state $1$ is
represented with two registers $r_{11}$ and $r_{12}$, reflecting the fact that
state $1$ may be reached by different TNFA paths with conflicting submatch
values.

  * ➔

Final TDFA states are all states containing TNFA state $17$ (i.e. states $1$,
$2$ and $3$). In addition to normal transitions final TDFA states have quasi-
transitions that set final registers $r_{6}$ – $r_{10}$. These quasi-
transitions do not consume any symbol, and the operations on them are executed
once at the end of match.

  * ➔

In the resulting TDFA all internal structure in the states is erased, leaving
atomic states with transitions and register operations. Registers can be
renamed to occupy consecutive numbers, and the number of registers and
operations can be reduced (see section 3).

##  3 Implementation

In this section we describe optimizations and practical details that should be
taken into account when implementing TDFA. None of the optimizations is
particularly complex or vital for TDFA operation, but applied together and in
the correct order they can make TDFA considerably faster and smaller.

###  3.1 Multi-valued tags

The most straightforward representation of multi-valued tags is a vector of
offsets. It is very inefficient because copy and append operations need to
copy entire vectors (which could grow arbitrarily long). A more efficient
representation is a _prefix tree_. It is possible because tag sequences in the
operations map on the path tree constructed by the $\epsilon$-closure. The
tree can be stored as an array of nodes $(pred,o\\!f\\!\\!f\\!s)$ where $pred$
is the index of a predecessor node, and $o\\!f\\!\\!f\\!s$ is a positive or
negative tag value. Individual sequences in the tree are addressed by integer
indices of tree nodes (zero index corresponds to the empty sequence). This
representation is space efficient (common prefixes are shared), but most
importantly it makes copy operations as simple as copying scalar values (tree
indices). Append operations are more difficult, as they require a new slot (or
a couple of slots) in the prefix tree. However, if the backing array is
allocated in large chunks of memory, then the amortized complexity of each
operation is constant. This representation was used by multiple researches,
e.g. Karper describes it as the _flyweight pattern_ [12].

###  3.2 Fallback operations

In practice it is often necessary to match the longest possible prefix of a
string rather than the whole string. After matching a short prefix, TDFA may
attempt to match a longer prefix. If that fails, it must fallback to the
previous final state and restore the input position accordingly. A final state
is also a _fallback state_ if there are non-accepting paths out of it, and a
path is non-accepting if does not go through another final state (which may
happen either because the input characters do not match or due to a premature
end of input).

For an ordinary DFA the only information that should be saved in a fallback
state is the input position. For TDFA it is also necessary to backup registers
that may be clobbered on the non-accepting paths from the fallback state.
Backup operations should be added on transitions out of the fallback state,
and restore operations should be added on the fallback quasi-transition, which
replaces the final quasi-transition for fallback paths. Final registers can be
reused for backups, as by TDFA construction they are used only on the final
quasi-transitions. Backup registers are only needed for copy and append
operations (set operations do not depend on registers).

1

2

_$\underline{f\\!allback\rule{4.5pt}{0.5pt}regops\big{(}\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

3 $\psi:$ undefined fallback function

4 for each fallback state $s\in S$ do

5 $O:$ empty list of register operations

6 for each operation on quasi-transition $\varphi(s)$ do

7 if append $i\leftarrow j\cdot h$ and $j$ is clobbered then

8 $backup\rule{4.5pt}{0.5pt}regops(s,i,j)$

9 append operation $i\leftarrow i\cdot h$ to $O$

10 else if copy $i\leftarrow j$ and $j$ is clobbered then

11 $backup\rule{4.5pt}{0.5pt}regops(s,i,j)$

12 else

13 append a copy of this operation to $O$

14

15 $\psi(s)=O$

16 return $\psi$

17

18

19

 _$\underline{backup\rule{4.5pt}{0.5pt}regops\big{(}s,i,j\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

20 for each alphabet symbol $a\in\Sigma$ do

21 $(s^{\prime},O)=\delta(s,a)$

22 if exist non-accepting paths from $s^{\prime}$ then

23 append copy operation $i\leftarrow j$ to $O$

24

25

26

27

Algorithm 4 Adding fallback operations to TDFA
$(\Sigma,T,S,S_{f},s_{0},R,R_{f},\delta,\varphi)$.

Algorithm 4 shows how to add such operations. It assumes that fallback states
and clobbered registers for each fallback state have already been identified.
This can be done as follows. First, augment TDFA with a _default state_ that
makes transition function $\delta$ total (if a premature end of input is
possible, add a quasi-transition from non-final states to the default state).
Then compute reachability of the default state by doing backward propagation
from states that have transitions to it. If the default state is reachable
from a final state, then it is a fallback state. Clobbered registers can be
found by doing depth-first search from a fallback state, visiting states from
which the default state is reachable, and accumulating left-hand-sides of
register operations.

###  3.3 Register optimizations

TDFA induces a _control flow graph_ (CFG) with three kinds of nodes:

  * $\bullet$

_basic blocks_ for register operations on symbolic transitions

  * $\bullet$

_final blocks_ for final register operations

  * $\bullet$

_fallback blocks_ for fallback register operations

There is an arc between two blocks in CFG if one is reachable from another in
TDFA without passing through other register operations. Additionally, fallback
blocks have arcs to all blocks reachable by TDFA paths that may fall through
to these blocks. Figure 2 shows CFG for the example from section 2.

CFG represents a program on registers, so the usual compiler optimizations can
be applied to it, resulting in significant reduction of registers and
operations. RE2C uses the following optimization passes for the number of
repetitions $N=2$ (pseudocode is given by the algorithms 5 and 6):

  1. 1.

Compaction

  2. 2.

Repeat $N$ times:

    1. a.

Liveness analysis

    2. b.

Dead code elimination

    3. c.

Interference analysis

    4. d.

Register allocation with copy coalescing

    5. e.

Local normalization

1

2

_$\underline{optimizations\big{(}G\big{)}}\vskip 3.0pt plus 1.0pt minus
1.0pt$_

3 $V=compaction(G)$

4 $G=renaming(G,V)$

5 for $i=\overline{1,2}$ do

6 $L=liveness\rule{4.5pt}{0.5pt}analysis(G)$

7 $dead\rule{4.5pt}{0.5pt}code\rule{4.5pt}{0.5pt}elimination(G,L)$

8 $I=inter\\!f\\!erence\rule{4.5pt}{0.5pt}analysis(G,L)$

9 $V=register\rule{4.5pt}{0.5pt}allocation(G,I)$

10 $renaming(G,V)$

11 $normalization(G)$

12

13

14

 _$\underline{renaming\big{(}G,V\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

15 for each block $b$ in $G$ do

16 for each operation in $b$ do

17 if set operation $i\leftarrow v$ then

18 rename $i$ to $V[i]$

19

20 if copy or append operation $i\leftarrow j...$ then

21 rename $i$ to $V[i]$ and $j$ to $V[j]$

22

23

24

25

26

 _$\underline{liveness\rule{4.5pt}{0.5pt}analysis\big{(}G\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

27 $L:$ boolean matrix indexed by blocks and registers

28 for each block $b$ in $G$ do

29 for each register $i$ in $G$ do

30 $L[b][i]=f\\!alse$

31

32

33 for each final block $b$ in $G$ do

34 for each final register $i$ in $G$ do

35 $L[b][i]=true$

36

37

38 while $true$ do

39 $fix=true$

40 for each basic block $b$ in $G$ in post-order do

41 $L_{b}=$ copy of row $L[b]$

42 for each successor $s$ of block $b$ do

43 $L_{s}=$ copy of row $L[s]$

44 for each operation in $s$ in post-order do

45 if set operation $i\leftarrow v$ then

46 $L_{s}[i]=f\\!alse$

47

48 if copy operation $i\leftarrow j$ then

49 if $L_{s}[i]$ then

50 $L_{s}[i]=f\\!alse$

51 $L_{s}[j]=true$

52

53

54

55 for each register $i$ in $G$ do

56 $L_{b}[i]=L_{b}[i]\vee L_{s}[i]$

57

58 if $L[b]\neq L_{b}$ then

59 $L[b]=L_{b}$

60 $fix=f\\!alse$

61

62

63 if $fix$ then $break$

64

65 for each fallback block $b$ in $G$ do

66 for each final register $i$ in $G$ do

67 $L[b][i]=true$

68

69 $L_{b}=$ copy of row $L[b]$

70 for each operation $i\leftarrow\rule{4.5pt}{0.5pt}$ in $b$ do

71 $L_{b}[i]=f\\!alse$

72

73 for each copy or append operation $\rule{4.5pt}{0.5pt}\leftarrow j...$ in
$b$ do

74 $L_{b}[j]=true$

75

76 for each block $s$ in $G$ that may fall through to $b$ do

77 for each register $i$ in $G$ do

78 $L[s][i]=L[s][i]$ or $L_{b}[i]$

79

80

81

82 return $L$

83

84

85

86

87

 _$\underline{compaction\big{(}G\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

88 $U:$ boolean vector indexed by registers

89 $V:$ integer vector indexed by registers

90 for each register $i$ in $G$ do

91 $U[i]=f\\!alse$

92

93 for each block $b$ in $G$ do

94 for each operation in $b$ do

95 if set operation $i\leftarrow v$ then

96 $U[i]=true$

97

98 if copy or append operation $i\leftarrow j...$ then

99 $U[i]=U[j]=true$

100

101

102

103 $n=0$

104 for registers $i$ in $G$ such that $U[i]$ do

105 $n=n+1,\;V[i]=n$

106

107 return $V$

108

109

_$\underline{dead\rule{4.5pt}{0.5pt}code\rule{4.5pt}{0.5pt}elimination\big{(}G,L\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

110 for each basic block $b$ in $G$ do

111 $L_{b}=$ copy of row $L[b]$

112 for each operation $i\leftarrow\rule{4.5pt}{0.5pt}$ in $b$ in post-order
do

113 if $L_{b}[i]$ then

114 if set operation $i\leftarrow v$ then

115 $L_{b}[i]=f\\!alse$

116

117 if copy operation $i\leftarrow j$ then

118 $L_{b}[i]=f\\!alse$

119 $L_{b}[j]=true$

120

121

122 else remove dead operation

123

124

125

126

_$\underline{inter\\!f\\!erence\rule{4.5pt}{0.5pt}analysis\big{(}G,L\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

127 $I:$ boolean matrix indexed by registers

128 $V:$ vector of histories indexed by registers

129 for each register $i$ in $G$ do

130 for each register $j$ in $G$ do

131 $I[i][j]=I[j][i]=f\\!alse$

132

133

134 for each block $b$ in $G$ do

135 for each copy or append operation $i\leftarrow j...$ in $b$ do

136 $V[j]=j$

137

138 for each operation in $b$ do

139 $I_{b}=$ copy of row $L[b]$

140 if set operation $i\leftarrow v$ then

141 $V[i]=v$

142 $I_{b}[i]=f\\!alse$

143

144 else if copy operation $i\leftarrow j$ then

145 $V[i]=V[j]$

146 $I_{b}[i]=I_{b}[j]=f\\!alse$

147

148 else if append operation $i\leftarrow j\cdot h$ then

149 $V[i]=V[j]\cdot h$

150

151 for operations $k\leftarrow\rule{4.5pt}{0.5pt}$ in $b$ with $V[k]=V[i]$ do

152 $I_{b}[k]=f\\!alse$

153

154 for registers $k$ in $G$ such that $I_{b}[k]$ do

155 $I[i][k]=I[k][i]=true$

156

157

158

159 for registers $i$ in $G$ not used in append operations do

160 for registers $j$ in $G$ used in append operations do

161 $I[i][j]=I[j][i]=true$

162

163

164 return $I$

165

166

167

Algorithm 5 Register optimizations (part 1).

1

2

_$\underline{register\rule{4.5pt}{0.5pt}allocation\big{(}G,I\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

3 $V:$ vector of registers indexed by registers

4 $B:$ vector of registers indexed by registers

5 $S:$ vector of register sets indexed by registers

6 for each register $i$ in $G$ do

7 $B[i]=-1$

8 $S[i]=\emptyset$

9

10 for each block $b$ in $G$ do

11 for each operation in $b$ do

12 if copy or append $i\leftarrow j...$ and $i\neq j$ then

13 $x=B[i],\;y=B[j]$

14 if $x=-1$ and $y=-1$ then

15 $B[i]=B[j]=i$

16 $S[i]=\\{i,j\\}$

17

18 else if $x\neq-1$ and $y=-1$ then

19 if $\forall k\in S[x]:\neg I[k][j]$ then

20 $B[j]=x$

21 $S[x]=S[x]\cup\\{j\\}$

22

23

24 else if $x=-1$ and $y\neq-1$ then

25 if $\forall k\in S[y]:\neg I[k][i]$ then

26 $B[i]=y$

27 $S[y]=S[y]\cup\\{i\\}$

28

29

30

31

32

33 for registers $i$ in $G$ such that $B[i]=i$ do

34 for registers $j$ in $G$ such that $B[j]=j$ and $j>i$ do

35 if $\forall i\in S[x],j\in S[y]:\neg I[i][j]$ then

36 $B[y]=x$

37 $S[x]=S[x]\cup S[y]$

38 $S[y]=\emptyset$

39

40

41

42 for registers $i$ in $G$ such that $B[i]=-1$ do

43 if $\exists j$ in $G:B[j]=j$ and $\forall k\in S[j]:\neg I[i][k]$ then

44 $B[i]=j$

45 $S[j]=S[j]\cup\\{i\\}$

46

47

48 $n=0$

49 for registers $i$ in $G$ such that $B[i]=i$ do

50 $n=n+1$

51 for registers $j\in S[i]$ do

52 $V[j]=n$

53

54

55 return $V$

56

57

58

59

 _$\underline{normalization\big{(}G\big{)}}\vskip 3.0pt plus 1.0pt minus
1.0pt$_

60 for each block $b$ in $G$ do

61 for each contiguous set operation range $O$ do

62 $remove\rule{4.5pt}{0.5pt}duplicates(O)$

63 $sort(O)$

64

65 for each contiguous copy operation range $O$ do

66 $remove\rule{4.5pt}{0.5pt}duplicates(O)$

67 $topological\rule{4.5pt}{0.5pt}sort(O)$

68

69 for each contiguous append operation range $O$ do

70 $remove\rule{4.5pt}{0.5pt}duplicates(O)$

71

72

73

74

 _$\underline{topological\rule{4.5pt}{0.5pt}sort\big{(}O\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

75 $I:$ vector of in-degree indexed by registers

76 for each copy or append operation $i\leftarrow j...$ in $O$ do

77 $I[i]=I[j]=0$

78

79 for each copy or append operation $\rule{4.5pt}{0.5pt}\leftarrow j...$ in
$O$ do

80 $I[j]=I[j]+1$

81

82 $O^{\prime}:$ empty list of operations

83 $nontrivial\rule{4.5pt}{0.5pt}cycle=f\\!alse$

84 while $O$ is not empty do

85 for each operation $i\leftarrow\rule{4.5pt}{0.5pt}$ in $O$ do

86 if $I[i]=0$ then

87 remove operation from $O$, append to $O^{\prime}$

88 if this is a copy/append operation $i\leftarrow j...$ then

89 $I[j]=I[j]-1$

90

91

92

93 if nothing added to $O^{\prime}$ but $O$ is not empty then

94 if $\exists$ operation $i\leftarrow j...$ in $O$ with $i\neq j$ then

95 $nontrivial\rule{4.5pt}{0.5pt}cycle=true$

96 append $O$ to $O^{\prime}$

97 $break$ (only cycles left)

98

99 $O=O^{\prime}$

100 return $\not nontrivial\rule{4.5pt}{0.5pt}cycle$

101

102

 _$\underline{remove\rule{4.5pt}{0.5pt}duplicates\big{(}O\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

103 for each operation $o$ in $O$ do

104 for each subsequent operation $o^{\prime}=o$ in $O$ do

105 remove duplicate operation $o^{\prime}$

106

107

108

109

Algorithm 6 Register optimizations (part 2).

Compaction pass is applied only once immediately after determinization. It
renames registers so that they occupy contiguous range of numbers with no
“holes”. This is needed primarily to allow other optimization passes use
registers as indices in liveness and interference matrices.

Liveness analysis builds a boolean 2-dimensional matrix indexed by CFG blocks
and registers. A cell $L[b][i]$ is true iff register $i$ is alive in block $b$
(meaning that its value is used). Function
$liveness\rule{5.0pt}{0.5pt}analysis$ uses iterative data-flow approach.
Initially only the final registers in the final blocks are alive. The
algorithm iterates over CFG blocks in post-order, expanding the live set,
until it reaches a fix point. Lastly it marks backup registers as alive in all
blocks reachable from fallback blocks by non-accepting paths.

Dead code elimination removes operations whose left-hand-side register is not
alive.

Interference analysis builds a boolean square matrix indexed by registers. A
cell $I[i][j]$ is true iff registers $i$ and $j$ interfere with each other
(their lifetimes overlap, so they cannot be represented with one register).
Initially none of the registers interfere. Function
$inter\\!f\\!erence\rule{5.0pt}{0.5pt}analysis$ considers each CFG block $b$
and inspects each register $j$ used on the right-hand-side of an operation:
all registers alive in block $b$ interfere with $j$, except for registers that
have the same value (tracked by the vector $V$). Finally registers for multi-
valued and single-valued tags are marked as interfering with each other.

Register allocation partitions registers into equivalence classes. Registers
inside of one class do not interfere with each other, so they can all be
replaced with a single _representative_. Initially none of the registers
belongs to any class. Function $register\rule{5.0pt}{0.5pt}allocation$ loops
over copy operations and tries to put source and destination into one class
(so that the copy can be removed). Vector $B$ maps registers to their
representative, and vector $S$ maps representatives to their class. The
algorithm tries to merge non-interfering equivalence classes, and then puts
the remaining registers into an non-interfering class (allocating a new class
if necessary). Finally it maps representatives to consecutive numbers and
stores them in the $V$ vector. The constructed partitioning is not minimal,
but it’s a good approximation, since finding the minimal clique cover of a
graph is NP-complete.

Local normalization reconciles operations after previous passes. The
$normalization$ function removes duplicate operations that might appear after
different registers are collapsed into one. It also sorts operations, so that
operation sequences could be compared easily (which is used in further
optimizations like in minimization). Each continuous range of set, copy or
append operations is handled separately, because operations of different kinds
should not be reordered (that could change the end result).

Figure 2 is a continuation of example on figure 1:

  * ➔

The CFG contains $9$ blocks: basic blocks $0$ – $5$ (one for each tagged
transition on symbol in TDFA, plus the start block $0$) and final blocks $6$ –
$8$ (one per each final quasi-transition). There are no fallback blocks in
this example, because there are no fallback states in TDFA: every transition
out of a final state goes to another final state, so the attempt to match a
longer string will either fail immediately (before leaving the final state),
or it will succeed immediately.

  * ➔

The second CFG is after compaction and the first pass of liveness and
interference analysis. Compaction renames registers $r_{6}$ – $r_{15}$ and
$r_{20}$ to $r_{1}$ – $r_{11}$, reducing the size of the register range from
20 to 11 and the size of the liveness and interference matrices almost 2x and
4x respectively. Liveness information is shown at the top of each block.
Interference matrix uses asterisk for interfering register pairs and dot for
non-interfering ones. It can be seen that there are many dots in the table,
which means optimization opportunities. The interference matrix is
symmetrical, as the interference relation is commutative.

  * ➔

The third CFG is after the second pass of liveness and interference analysis.
The number of registers is reduced from $11$ to $5$. Many operations have been
eliminated, for example the copy operation $r_{1}\leftarrow r_{7}$ in the
final block $8$ of the second CFG was removed by copy coalescing, because
registers $1$ and $7$ did not interfere and register allocation put them in
one equivalence class (and likewise for the other copy operations in block
$8$). In basic blocks $1$ and $3$ set operations $r_{6}\leftarrow\mathbf{p}$
and $r_{9}\leftarrow\mathbf{p}$ were collapsed into
$r_{3}\leftarrow\mathbf{p}$ after non-interfering registers $r_{6}$ and
$r_{9}$ had been renamed to $r_{3}$. Interference matrix has dots only on the
main diagonal (a register does not interfere with itself), which leaves no
room for further optimization.

  * ➔

The resulting optimized TDFA is at the bottom of figure 2. The final registers
are now $r_{1}$ – $r_{5}$.

Figure 2:  Register optimizations for TDFA on figure 1.
Top to bottom: initial CFG, CFG after compaction with per-block liveness
information and interference table,
CFG on the second round of optimizations, optimized TDFA with final registers
$r_{1}$ to $r_{5}$.

###  3.4 Minimization

Minimization can be applied to TDFA in the same way as to an ordinary DFA
(e.g. the Moore’s algorithm), except that transitions on the same alphabet
symbol but with different register operations should be treated as different
transitions, so their destination states cannot be merged. To get optimal
performance minimization algorithm should be able to compare operations on
transitions in constant time. This is possible if operation sequences are
inserted into a hash map and represented with unique numeric identifiers. Such
a comparison may have false negatives, as non-identical operations lists may
be equivalent (e.g. $r_{1}\leftarrow\mathbf{p},r_{2}\leftarrow\mathbf{n}$ is
not identical, but equivalent to
$r_{2}\leftarrow\mathbf{n},r_{1}\leftarrow\mathbf{p}$). False negatives do not
affect minimization correctness, but the end result may be suboptimal. To
avoid that, minimization should be applied after register optimizations (which
may remove some register operations) and most importantly after normalization
(defined on page 6).

###  3.5 Fixed tags

_Fixed tags_ is a very important optimization that happens at the RE level. In
cases with high tag density (such as POSIX REs with nested submatch groups)
this optimization alone may be more effective than all register optimizations
combined. The key observation is, if a pair of tags is within fixed distance
from each other, there is no need to track both of them: the value of one tag
can be computed from the value of the other tag one by adding a fixed offset.
This optimization is fast (linear in the size of a RE) and has the potential
to reduce both TDFA construction time and matching time.

Algorithm 7 finds fixed tags by performing top-down structural recursion on a
RE. It has four parameters: $e$ is the current sub-RE, $t$ is the current base
tag, $d$ is the distance to base tag, and $k$ is the distance to the start of
the current level. Levels are parts of a RE where any two points either both
match or both do not match. A level increases on recursive descent into
alternative or repetition subexpressions, but not concatenation. Tags on
different levels should not be fixed on each other, even if they are within
fixed distance on any path that goes through both of them, because there are
paths that go through only one tag (so the other one is nil). Tag value $-1$
denotes the absence of base tag: when descending to the next level initially
there is no base tag, and the first tag on the current level becomes the base.
One exception is the top level, where the initial base tag should be a special
value denoting the rightmost position (which is always known at the end of the
match). The algorithm recursively returns the new base tag, the updated
distance to base tag, and the updated level distance. Special distance value
$N\\!a\\!N$ (not-a-number) is understood to be a fixed point in arithmetic
expressions: any expression involving $N\\!a\\!N$ amounts to $N\\!a\\!N$.

1

2

_$\underline{fixed\rule{4.5pt}{0.5pt}tags\big{(}e,t,d,k\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

3 if $e=\epsilon$ then

4 return $t,d,k$

5 else if $e=a\in\Sigma$ then

6 return $t,d+1,k+1$

7 else if $e=e_{1}|e_{2}$ then

8
$\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt},k_{1}=fixed\rule{4.5pt}{0.5pt}tags(e_{1},-1,N\\!a\\!N,0)$

9
$\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt},k_{2}=fixed\rule{4.5pt}{0.5pt}tags(e_{2},-1,N\\!a\\!N,0)$

10 if $k_{1}=k_{2}$ then

11 return $t,d+k_{1},k+k_{1}$

12 return $t,N\\!a\\!N,N\\!a\\!N$

13 else if $e=e_{1}e_{2}$ then

14 $t_{2},d_{2},k_{2}=fixed\rule{4.5pt}{0.5pt}tags(e_{2},t,d,k)$

15 $t_{1},d_{1},k_{1}=fixed\rule{4.5pt}{0.5pt}tags(e_{1},t_{2},d_{2},k_{2})$

16 return $t_{1},d_{1},k_{1}$

17 else if $e=e_{1}^{n,m}$ then

18
$\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt},k_{1}=fixed\rule{4.5pt}{0.5pt}tags(e_{1},-1,N\\!a\\!N,0)$

19 if $n=m$ then

20 return $t,d+n*k_{1},k+n*k_{1}$

21 return $t,N\\!a\\!N,N\\!a\\!N$

22 else if $e=t_{1}\in T$ then

23 if $t\neq-1$ and $d\neq N\\!a\\!N$ then

24 mark $t_{1}$ as fixed on $t$ with distance $d$

25 return $t,d,k$

26 return $t_{1},0,k$

27

28

Algorithm 7 Fixed tags optimization.

Figure 3:  Optimized TDFA with fixed tags $t_{1}\leftarrow(\mathbf{n}\text{ if
}t_{2}=\mathbf{n}\text{ else }t_{2}-1)$ and $t_{3}\leftarrow(t_{5}-1)$.
Tags $t_{2}$, $t_{4}$, $t_{5}$ correspond to final registers $r_{1}$, $r_{2}$,
$r_{3}$.

Figure 3 shows the effect of fixed tags in addition to other optimizations on
figure 2:

  * ➔

In the example RE $(1a2)^{*}3(a|4b)5b^{*}$ tags $t_{1}$ and $t_{2}$ are within
one symbol from each other, so the value of $t_{1}$ can be computed as nil if
$t_{2}$ is nil, or $t_{2}-1$ otherwise. Likewise $t_{3}$ can be computed as
$t_{5}-1$ (although there are multiple different paths through $(a|4b)$, they
all have the same length).

  * ➔

Fixed tags are identified at the RE level and excluded from TNFA construction
and determinization. There are no registers and register operations associated
with $t_{1}$ and $t_{3}$, except for computing their values from the base tags
$t_{2}$ and $t_{5}$ at the end of match.

##  4 Multi-pass TDFA

TDFA with registers described in section 2 are well suited for ahead-of-time
determinization (e.g. in lexer generators) when one can spend considerable
time on optimizations in order to emit a more efficient TDFA. However, in RE
libraries the overhead on determinization and optimizations is included in the
run time, therefore it is desirable to reduce TDFA construction time (although
the overhead may be amortized if a RE is compiled once and used to match many
strings).

Another concern is the density of submatch information in a RE. TDFA with
registers are perfect for _sparse_ submatch extraction, when the number of
tags is small compared to the size of RE and the runtime performance is
expected be close to an ordinary DFA. However, if a RE contains many tags (in
the extreme, if every subexpression is tagged) then transitions get cluttered
with operations, making TDFA execution very slow. Moreover, the optimizations
described in section 3 become problematic due to the size of liveness and
interference tables.

Multi-pass TDFA address these issues: they reduce TDFA construction time and
they are better suited to dense submatch extraction. The main difference with
canonical TDFA is that multi-pass TDFA have no register operations. Instead,
as the name suggests, they have multiple passes: a _forward_ pass that matches
the input string and records a sequence of TDFA states, and one or more
_backward_ passes that iterate through the recorded states and collect
submatch information (one backward pass is sufficient, but an extra pass may
be used e.g. to estimate and preallocate memory for the results). The
representation of submatch results may vary and affects only the backward
pass(es); forward pass is the same for all representations.

1

2

_$\underline{unique\rule{4.5pt}{0.5pt}origins\big{(}C\big{)}}\vskip 3.0pt plus
1.0pt minus 1.0pt$_

3 $U:$ mapping from TNFA states in $C$ to integers

4 $i=0$

5 for each unique origin $o$ in $C$ do

6 for each
$(q,o^{\prime},\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt},\rule{4.5pt}{0.5pt})$
in $C$ such that $o^{\prime}=o$ do

7 $U[q]=i$

8

9 $i=i+1$

10

11 return $U$

12

13

14

 _$\underline{match\big{(}\mathcal{F},\;a_{1}\ldots a_{n}\big{)}}\vskip 3.0pt
plus 1.0pt minus 1.0pt$_

15 $V=\\{s_{0}\\}$

16 for $k=\overline{1,n}$ do

17 if $s=\delta(s,a_{k})$ is defined then

18 append $s$ to $V$

19

20 else return $\varnothing$

21

22 return $V$

23

24

25

_$\underline{extract\rule{4.5pt}{0.5pt}o\\!f\\!\\!f\\!sets\big{(}\mathcal{F},\;a_{1}\ldots
a_{n},\;s_{0}\ldots s_{n}\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

26 $E=\\{\varnothing\\}_{i=1}^{|T|}$ (no value for each tag)

27 $(i,h)=\varphi(s_{n})$

28 $k=n$

29 while $true$ do

30 for tag $t$ in $h$ in reverse order do

31 if $t>0$ and $E[t]=\varnothing$ then

32 $E[t]=k$

33 else if $E[-t]=\varnothing$ then

34 $E[-t]=-1$

35

36 if $k=0$ then break

37 $(\rule{4.5pt}{0.5pt},B)=\delta(s_{k-1},a_{k})$

38 $(i,h)=B[i]$

39 $k=k-1$

40

41 return $E$

42

43

44

45

_$\underline{construct\rule{4.5pt}{0.5pt}backlinks\big{(}C,U,U^{\prime}\big{)}}\vskip
3.0pt plus 1.0pt minus 1.0pt$_

46 $B:$ backlink array of size $|range(U^{\prime})|$

47 for each $(q,o,\rule{4.5pt}{0.5pt},h,\rule{4.5pt}{0.5pt})$ in $C$ do

48 $i=U^{\prime}[q]$

49 if $B[i]$ is undefined then

50 $B[i]=(U[o],h)$

51

52

53 return $B$

54

55

56

_$\underline{extract\rule{4.5pt}{0.5pt}tstring\big{(}\mathcal{F},\;a_{1}\ldots
a_{n},\;s_{0}\ldots s_{n}\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

57 $(i,h)=\varphi(s_{n})$

58 $x=h$

59 for $k=\overline{n,1}$ do

60 $(\rule{4.5pt}{0.5pt},B)=\delta(s_{k-1},a_{k})$

61 $(i,h)=B[i]$

62 $x=h\cdot a_{k}\cdot x$

63

64 return $x$

65

66

67

_$\underline{extract\rule{4.5pt}{0.5pt}o\\!f\\!\\!f\\!set\rule{4.5pt}{0.5pt}lists\big{(}\mathcal{F},\;a_{1}\ldots
a_{n},\;s_{0}\ldots s_{n}\big{)}}\vskip 3.0pt plus 1.0pt minus 1.0pt$_

68 $E=\\{\\{\\}\\}_{i=1}^{|T|}$ (empty list for each tag)

69 $(i,h)=\varphi(s_{n})$

70 $k=n$

71 while $true$ do

72 for tag $t$ in $h$ in reverse order do

73 if $t>0$ then

74 prepend $k$ to $E[t]$

75 else

76 prepend $-1$ to $E[-t]$

77

78 if $k=0$ then break

79 $(\rule{4.5pt}{0.5pt},B)=\delta(s_{k-1},a_{k})$

80 $(i,h)=B[i]$

81 $k=k-1$

82

83 return $E$

84

85

86

Algorithm 8 Backlink construction and matching with multi-pass TDFA
$\mathcal{F}=(\Sigma,T,S,S_{f},s_{0},\delta,\varphi)$.

Multi-pass TDFA construction differs from algorithm 3 in section 2 in a few
ways. Recall that a closure $C$ corresponds to a TDFA transition between
states $s$ and $s^{\prime}$. For multi-pass TDFA closure configurations are
extended to five components $(q,o,r,h,l)$ where the new component $o$ is the
_origin_ TNFA state in $s$ that leads to state $q$ in $s^{\prime}$, and the
remaining components are as in algorithm 3. Origins are needed to trace back
the matching TNFA path from a sequence of TDFA states. Path fragments
corresponding to closure configurations are represented with _backlinks_ , and
every TDFA transition is associated with a backlink array. A backlink is a
pair $(i,h)$ where $i$ is an index in backlink arrays on preceding
transitions, and $h$ is a tag sequence corresponding to the $h$-component of a
configuration. Backlinks on transitions do not map one-to-one to
configurations, because in TDFA(1) contrary to TDFA(0) configurations with
identical origins have identical $h$-components (inherited from the lookahead
tags), resulting in identical backlinks. To deduplicate such backlinks,
$unique\rule{5.0pt}{0.5pt}origins$ in algorithm 8 creates a per-state mapping
from origin state to a unique origin index. Transition function is defined as
$\delta(s,a)=(s^{\prime},B)$ where
$B=construct\rule{5.0pt}{0.5pt}backlinks(C,U,U^{\prime})$ and $U$,
$U^{\prime}$ are the unique origin mappings for $s$ and $s^{\prime}$
respectively. Final TDFA states are associated with a single backlink, and the
final function is defined as $\varphi(s)=(i,l)$ where $i$ is the unique origin
index of the final state $q_{f}$ in $C$ and $l$ is the lookahead tag sequence
($l$-component of the final configuration). The resulting TDFA has no
registers or register operations; the $R$ and $R_{f}$ components are removed
from TDFA, and functions $transition\rule{5.0pt}{0.5pt}regops$,
$final\rule{5.0pt}{0.5pt}regops$ and their dependencies in algorithm 3 are not
needed.

Algorithm 8 shows matching with a multi-pass TDFA. The forward pass is defined
by the function $match$, which executes TDFA on a string $a_{1}\ldots a_{n}$
and returns the matching sequence of TDFA states $s_{0}\ldots s_{n}$ (or
$\varnothing$ on failure). Backward pass depends on the representation of
submatch results; we provide three variants for offsets, offset lists and
tagged strings. In each case the backward pass follows a sequence of backlinks
from the final state to the initial state. Function
$extract\rule{5.0pt}{0.5pt}o\\!f\\!\\!f\\!sets$ extracts the last offset for
each tag and avoids overwriting it by initializing all offsets to
$\varnothing$ and checking each offset before writing. Function
$extract\rule{5.0pt}{0.5pt}o\\!f\\!\\!f\\!set\rule{5.0pt}{0.5pt}lists$ is
similar, but it collects offsets into lists. Function
$extract\rule{5.0pt}{0.5pt}tstring$ concatenates the $h$-components of
backlinks interleaved with input symbols (this representation can be used to
reconstruct a full parse tree, see [6] section 6).

In practice we found that the following details affect performance of
algorithm 8. The $h$-components of backlinks should be stored as arrays which
allow fast access to individual tags, rather than linked lists packed in a
prefix tree (the latter representation was used for multi-valued tags in
section 3). The forward pass should record references to backlink arrays
instead of TDFA states in order to reduce the number of indirections and
lookups. For tagged strings a separate backward pass may be used to estimate
the amount of space for the resulting string and preallocate it. If tags in a
RE have _nested_ structure (e.g. in the case of POSIX capturing groups) then
negative transition should be added only for the topmost tag of a
subexpression (as described in [6] section 9) rather than for all nested tags
(as described in algorithm 2). The mapping from a tag to its nested tags
should be stored separately and used during matching (as in [6] section 6).

Figure 4:  Multi-pass TDFA for RE $(1a2)^{*}3(a|4b)5b^{*}$ matching string
$aab$.

Figure 4 shows multi-pass TDFA for the running example (compare it with figure
1):

  * ➔

TDFA transition $0\\!\rightarrow\\!1$ has two backlinks because the five
configurations in state $1$ originate in two TNFA states $2$ and $9$. Likewise
transition $1\\!\rightarrow\\!1$ has two backlinks corresponding to origins
$2$ and $9$, transitions $0\\!\rightarrow\\!2$ and $1\\!\rightarrow\\!2$ have
one backlink corresponding to origin $12$, and transitions
$2\\!\rightarrow\\!3$ and $3\\!\rightarrow\\!3$ have one backlink
corresponding to origin $15$.

  * ➔

Final states $1$, $2$ and $3$ have a backlink corresponding to the final
configuration with TNFA state $17$.

  * ➔

The $i$-component of each backlink equals to the unique origin index of the
configuration $o$-component. For example, both backlinks on transition
$1\\!\rightarrow\\!1$ have $i=0$ because their configurations (in the shadow
TDFA state mapped to state $1$ on figure 1) have origins $2$ and $9$ in TDFA
state $1$, which have the same unique origin index $0$ (because they both have
origin $2$ in TDFA state $0$). Consequently, both backlinks on transition
$1\\!\rightarrow\\!1$ connect to the first backlink on transitions
$0\\!\rightarrow\\!1$ and $1\\!\rightarrow\\!1$. On the other hand, the final
backlink in state $1$ connects to the second one.

  * ➔

The sequence of TDFA states matching $aab$ is
$0\\!\rightarrow\\!1\\!\rightarrow\\!1\\!\rightarrow\\!2$, and backlinks can
be traced back from the final backlink in state $2$ using $i$-component as
index in backlink arrays.

  * ➔

Submatch results for string $aab$ are as follows. Single offsets:
$t_{1}\\!=\\!1$, $t_{2}\\!=\\!2$, $t_{3}\\!=\\!2$, $t_{4}\\!=\\!2$,
$t_{5}\\!=\\!3$. Offset lists: $t_{1}\\!=\\!\\{0,1\\}$,
$t_{2}\\!=\\!\\{1,2\\}$, $t_{3}\\!=\\!\\{2\\}$, $t_{4}\\!=\\!\\{2\\}$,
$t_{5}\\!=\\!\\{3\\}$. Tagged string: $1\,a\,2\,1\,a\,2\,3\,4\,b\,5$.

##  5 Evaluation

In this section we evaluate TDFA performance in practice and compare it to
other algorithms. We present three groups of benchmarks that cover different
settings and show different aspects of the algorithm:

  1. 1.

AOT determinization (figures 5, 6, 7, 8). We compare three lexer generators:
RE2C [4], Ragel [14] and Kleenex [13] that are based on different types of
deterministic automata. All of them generate optimized C code, which is
further compiled to binary by GCC and Clang. The generated programs do string
rewriting: they read 100MB of input text and insert markers at submatch
extraction points. These benchmarks use leftmost-greedy disambiguation. The
following automata are compared:

     * $\bullet$

TDFA(1), the algorithm described by Trafimovich in [3] and presented in this
paper. It is implemented in RE2C with the optimizations described in section
3.

     * $\bullet$

TDFA(0), the original algorithm described by Laurikari in [1]. Contrary to
TDFA(1) that use one-symbol lookahead, TDFA(0) do not use lookahead: the two
types of automata are called so by analogy with LR(1) and LR(0). TDFA(0) apply
register operations to the incoming transition, while TDFA(1) split them on
the lookahead symbol and apply them to the outgoing transitions, which reduces
the number of tag conflicts. As a consequence, TDFA(0) typically require more
registers and copy operations, which makes them slower than TDFA(1); see [3]
for a detailed comparison. TDFA(0) algorithm is also implemented in RE2C and
benefits from the same optimizations as TDFA(1).

     * $\bullet$

StaDFA, the algorithm described by Chowdhury in [11], with a few modifications
of our own that were necessary for correctness. It is very similar to TDFA,
but the automata have register operations in states rather than on transitions
(which implies that staDFA do not use lookahead). The algorithm is implemented
in RE2C and uses the same optimizations as TDFA(1) and TDFA(0).

     * $\bullet$

DSSTs, the algorithm described by Grathwohl in [8]. DSSTs stands for
Deterministic Streaming String Transducers; these are more distant relatives
to TDFA, better suited to string rewriting and full parsing. DSST states
contain path trees constructed by the $\epsilon$-closure, while TDFA states
contain similar information decomposed into register tables and lookahead
tags. DSST registers contain fragments of strings over the output alphabet
(the analogue of our tagged strings). Register operations on transitions
concatenate and move string fragments. DSSTs are implemented in Kleenex.

     * $\bullet$

Ordinary DFA with ad-hoc user-defined actions and manual conflict resolution
via precedence operators, implemented in Ragel. This approach is fast, but it
has correctness issues: in some cases it is impossible to resolve the
conflicts between actions by preferring one action over the other; instead, it
is necessary to keep both actions until more input is consumed and non-
determinism is resolved. But this is also impossible, as the actions modify
the same shared state (e.g. set the same local variables). An action may
conflict with itself on different transitions due to non-determinism.

  2. 2.

JIT determinization, C++ (figure 9). These benchmarks compare TDFA(1) and
multi-pass TDFA(1) presented in section 4 in the case of single offsets and
offset lists. Both algorithms are implemented in a C++ library based on RE2C.
These benchmarks use POSIX disambiguation.

  3. 3.

JIT determinization, Java (figures 10, 11). We compare two independent
implementations: one in pure Java (by Borsotti), and one in C++ via JNI, based
on RE2C (by Trafimovich), both published as part of the RE2C repository [5].
These benchmarks compare TDFA(1) and multi-pass TDFA(1) in the case of single
offsets, offset lists and tagged strings, and with different submatch density:
sparse tags and full parsing (where every subexpression in a RE is tagged).
They use POSIX disambiguation.

Hardware specifications: Intel Core i7-8750H CPU with 32 KiB L1 data cache, 32
KiB L1 instruction cache, 256 KiB L2 cache, 9216 KiB L3 cache, 32 GiB RAM.
Software versions: RE2C 3.0, Ragel 7.0.4, Kleenex built from Git at commit
d474c60, GCC 11.2.0, Clang 13.0.0, OpenJDK 17.0.1.

Figure 5:  Benchmarks for AOT determinization, real-world REs.

Figure 5 shows benchmark results for AOT determinization in the case of real-
world REs that are likely to be used in practice: HTTP message headers, URI,
Apache logs, date, email addresses and IP addresses. REs vary from very large
and complex to small and simple; the number of tags in REs varies accordingly.

The main conclusions are:

  * $\bullet$

TDFA(1) and ordinary DFA are close in size and speed (the result often depends
on GCC/Clang).

  * $\bullet$

In simple cases staDFA and TDFA(0) are on par with TDFA(1), but in complex
cases they are considerably slower and larger, and staDFA can get extremely
large.

  * $\bullet$

DSSTs are generally slower and larger in most of the cases.

Figure 6:  Benchmarks for AOT determinization, artificial REs with
alternative.

Figure 6 shows benchmark results for AOT determinization in the case of
artificial REs with emphasis on alternative, in series of increasing size,
complexity and the number of tags. Ordinary DFA are excluded because Ragel’s
ad-hoc disambiguation operators do not allow to implement all cases correctly.
Conclusions:

  * $\bullet$

TDFA(1) perform better than other algorithms.

  * $\bullet$

TDFA(0) are generally slower than TDFA(1); the difference grows with RE size.

  * $\bullet$

StaDFA are close to TDFA(1) on small REs, but they degrade on large REs in
both size and speed.

  * $\bullet$

DSSTs are generally slower and almost always larger than TDFA(1).

Figure 7:  Benchmarks for AOT determinization, artificial REs with
concatenation.

Figure 7 shows benchmark results for AOT determinization in the case of
artificial REs with emphasis on concatenation, in series of increasing size,
complexity and the number of tags. Ordinary DFA are excluded because Ragel’s
ad-hoc disambiguation operators do not allow to implement all cases correctly.
Conclusions:

  * $\bullet$

TDFA(1) perform better than other algorithms.

  * $\bullet$

TDFA(0) are slower than TDFA(1), but the difference is not radical.

  * $\bullet$

StaDFA are slower than TDFA(1) on small REs, and the difference gets radical
with RE size.

  * $\bullet$

DSSTs are generally slower and almost always larger than TDFA(1).

Figure 8:  Benchmarks for AOT determinization, artificial REs with repetition.

Figure 8 shows benchmark results for AOT determinization in the case of
artificial REs with emphasis on repetition, in series of increasing size,
complexity and the number of tags. Ordinary DFA are excluded because Ragel’s
ad-hoc disambiguation operators do not allow to implement all cases correctly,
and DSSTs are excluded in cases where they get too large to be compiled.
Conclusions:

  * $\bullet$

TDFA(1) perform better than other algorithms.

  * $\bullet$

TDFA(0) are slower than TDFA(1), but the difference is not radical.

  * $\bullet$

StaDFA are slower and larger than TDFA(1) on small REs, and the difference
gets radical with RE size.

  * $\bullet$

DSSTs are generally larger than TDFA(1), and the difference gets extreme with
RE size.

Figure 9:  Benchmarks for JIT determinization, C++ (regcomp/regexec time,
relative).

Figure 10:  Benchmarks for JIT determinization, Java, sparse tags (regexec
speed).

Figure 11:  Benchmarks for JIT determinization, Java, full parsing (regexec
speed).

Figure 9 shows benchmark results for JIT determinization, C++. Time is shown
relative to the first row. There are two groups of benchmarks: real-world REs
and artificial REs $(a)^{*}a^{10^{k}}$ for $k\in\\{1,2,3\\}$. Conclusions:

  * $\bullet$

Compilation is predictably slower for TDFA than for multi-pass TDFA for both
groups, as multi-pass TDFA do not need register actions and subsequent
register optimizations.

  * $\bullet$

Execution time differs for the two groups: for real-world benchmarks TDFA are
generally faster than multi-pass TDFA, while for artificial benchmarks TDFA
are much slower than multi-pass TDFA, and the difference grows with the size
of RE. In fact artificial REs demonstrate a pathological case for TDFA with
register actions: increasing $k$ results in increased degree of
nondeterminism, which requires more registers and copy operations in order to
track all nondeterministic values. High degree of nondeterminism is specific
to some REs with counted repetition, as demonstrated in [3] (page 21).

  * $\bullet$

The results are similar for single-offset and offset-list cases, although the
latter is predictably slower.

Figures 10 and 11 show benchmark results for JIT determinization, Java, in the
case of sparse tags and full parsing respectively. The plots show the
dependence of matching speed on RE size. Conclusions:

  * $\bullet$

Remarkably, the case of tagged strings with multi-pass TDFA is the only one
that shows almost no degradation with RE size (the lines are almost
horizontal). This holds for both implementations.

  * $\bullet$

TDFA with register actions (the RE2C implementation) is clearly the fastest
algorithm in the case of sparse tags. However, in the case of full parsing it
either degrades faster than multi-pass TDFA (in the last-offset case), or it
is generally slower (in the offset-list case). For pure-Java implementation
multi-pass TDFA is almost always faster than TDFA with register actions.

##  6 Conclusions

TDFA(1) are generally faster and smaller than other automata capable of
submatch extraction.

Optimizations play a very important part in any performance-sensitive TDFA
implementation (compare the unoptimized TDFA on figure 1 with the final
optimized TDFA on figure 3).

The overhead on submatch extraction depends on tag density and degree of
nondeterminism in a RE. In the case of sparse tags with low nondeterminism
TDFA with register actions are by far the fastest and have negligible
difference compared to ordinary DFA. In the case of high tag density (in the
extreme, full parsing) or in the case of highly nondeterministic REs multi-
pass TDFA are more efficient.

The overhead on submatch extraction depends on the representation of submatch
results. Tagged string extraction with multi-pass TDFA is the only algorithm
that shows almost no degradation with RE size. Extracting only the last offset
is predictably faster than extracting all offsets (fortunately, the choice is
individual for each tag, so all offsets can be extracted only for a selected
subset of tags).

Multi-pass TDFA are better suited to JIT determinization than TDFA with
register actions.

##  7 Future work

One very useful direction of future work is to find _deterministic points_ in
a RE. Often shifting a tag by a fixed number of characters in a concatenation
subexpression can reduce its degree of nondeterminism (the maximum number of
registers in a single TDFA state needed to track all parallel versions of the
same tag). As a consequence, this means fewer registers and register
operations. For example, tag $t_{1}$ in $a^{*}1a^{k}a^{*}$ has nondeterminism
degree $k$ and requires $2*k$ register operations, while tag $t_{2}$ in
$a^{*}a^{k}2a^{*}$ has degree is $1$ and only $1$ operation. But tags $t_{1}$
and $t_{2}$ are within fixed distance of $k$ characters, so $t_{1}$ can be the
computed as $t_{2}-k$. In other words, $t_{2}$ is a deterministic point for
$t_{1}$. Identifying such points in a RE would be a useful optimization.

## Acknowledgments

I want to thank my parents Vladimir and Elina, my dearest friend and open
source programmer Sergei, my teachers Tatyana Leonidovna and Demian
Vladimirovich and the whole open source community. And, of course, my coauthor
Angelo who was the greatest inspiration and help in this work!  Ulya
Trafimovich

## References

  * [1] Ville Laurikari, NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions, Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pp. 181-187, http://laurikari.net/ville/spire2000-tnfa.pdf, 2000\.
  * [2] Chris Kuklewicz, Regular expressions/bounded space proposal, http://wiki.haskell.org/index.php?title=Regular_expressions/Bounded_space_proposal&oldid=11475, 2007\.
  * [3] Ulya Trafimovich, Tagged Deterministic Finite Automata with Lookahead, arXiv:1907.08837 [cs.FL], 2017\.
  * [4] RE2C, a lexer generator for C, C++, Go and Rust. Source code: https://github.com/skvadrik/re2c. Official website: https://re2c.org.
  * [5] Experimental Java library for TDFA. Source code: https://github.com/skvadrik/re2c/tree/master/benchmarks/submatch_java.
  * [6] Angelo Borsotti, Ulya Trafimovich, Efficient POSIX submatch extraction on nondeterministic finite automata, Software: Practice and Experience 51, no. 2, pp. 159–192, DOI: https://doi.org/10.1002/spe.2881, preprint: https://www.researchgate.net/publication/344781678_Efficient_POSIX_submatch_extraction_on_nondeterministic_finite_automata, 2019\.
  * [7] Ulya Trafimovich, RE2C: A lexer generator based on lookahead-TDFA, Software Impacts, 6, 100027, DOI: https://doi.org/10.1016/j.simpa.2020.100027, 2020\.
  * [8] Niels Bjørn Bugge Grathwohl, Parsing with Regular Expressions & Extensions to Kleene Algebra, DIKU, University of Copenhagen, 2015\.
  * [9] Stephen Cole Kleene, Representation of events in nerve nets and finite automata, RAND Project US Air Force, 1951\.
  * [10] Dexter Kozen, A completeness theorem for Kleene algebras and the algebra of regular events, Elsevier, Information and computation, vol. 110 (2) pp. 366–390, 1994\.
  * [11] Mohammad Imran Chowdhury, staDFA: An Efficient Subexpression Matching Method, Master thesis, Florida State University, 2018\.
  * [12] Aaron Karper, Efficient regular expressions that produce parse trees (thesis), University of Bern, 2014\.
  * [13] Kleenex language, DIKU, University of Copenhagen. Official website: https://kleenexlang.org. Source code: https://github.com/diku-kmc/kleenexlang,
  * [14] Ragel State Machine Compiler. Official website: https://www.colm.net/open-source/ragel.