In the automata theory, a tagged deterministic finite automaton (TDFA) is an extension of deterministic finite automaton (DFA). In addition to solving the recognition problem for regular languages, TDFA is also capable of submatch extraction and parsing. While canonical DFA can find out if a string belongs to the language defined by a regular expression, TDFA can also extract substrings that match specific subexpressions. More generally, TDFA can identify positions in the input string that match tagged positions in a regular expression (tags are meta-symbols similar to capturing parentheses, but without the pairing requirement).
History
TDFA were first described by Ville Laurikari in 2000.
Prior to that it was unknown whether it is possible to perform submatch extraction in one pass on a deterministic finite-state automaton, so this paper was an important advancement. Laurikari described TDFA construction and gave a proof that the determinization process terminates, however the algorithm did not handle disambiguation correctly.
In 2007 Chris Kuklewicz implemented TDFA in a Haskell library Regex-TDFA with POSIX longest-match semantics.
Kuklewicz gave an informal description of the algorithm
and answered the principal question whether TDFA are capable of POSIX longest-match disambiguation, which was doubted by other researchers.
In 2017 Ulya Trafimovich described TDFA with one-symbol lookahead.
The use of a lookahead symbol reduces the number of registers and register operations in a TDFA, which makes it faster and often smaller than Laurikari TDFA. Trafimovich called TDFA variants with and without lookahead TDFA(1) and TDFA(0) by analogy with LR parsers LR(1) and LR(0). The algorithm was implemented in the open-source lexer generator RE2C.
Trafimovich formalized Kuklewicz disambiguation algorithm.
In 2018 Angelo Borsotti worked on an experimental Java implementation of TDFA; it was published later in 2021.
In 2019 Borsotti and Trafimovich adapted POSIX disambiguation algorithm by Okui and Suzuki to TDFA. They gave a formal proof of correctness of the new algorithm and showed that it is faster than Kuklewicz algorithm in practice.
In 2020 Trafimovich published an article about TDFA implementation in RE2C.
In 2022 Borsotti and Trafimovich published a paper with a detailed description of TDFA construction.
The paper incorporated their past research and presented multi-pass TDFA that are better suited to just-in-time determinization. They also compared TDFA against other algorithms and provided benchmarks.
Formal definition
TDFA have the same basic structure as ordinary DFA: a finite set of states linked by transitions. In addition to that, TDFA have a fixed set of registers that hold tag values, and register operations on transitions that set or copy register values. The values may be scalar offsets, or offset lists for tags that match repeatedly (the latter can be represented efficiently using a trie structure). There is no one-to-one mapping between tags in a regular expression and registers in a TDFA: a single tag may need many registers, and the same register may hold values of different tags.
The following definition is according to Trafimovich and Borsotti. The original definition by Laurikari is slightly different.
A tagged deterministic finite automaton is a tuple , where:
is a finite set of symbols (alphabet) is a finite set of tags is a finite set of states with initial state and a subset of final states is a finite set of registers with a subset of final registers (one per tag) is a transition function is a final function, where is a set of register operations of the following types: set register to nil or to the current position: , where copy register to register : copy register to register and append history: , where is a string over
Example
Figure 0 shows an example TDFA for regular expression with alphabet and a set of tags that matches strings of the form with at least one symbol. TDFA has four states three of which are final . The set of registers is with a subset of final registers where register corresponds to -th tag. Transitions have operations defined by the function, and final states have operations defined by the function (marked with wide-tipped arrow). For example, to match string , one starts in state 0, matches the first and moves to state 1 (setting registers to undefined and to the current position 0), matches the second and loops to state 1 (register values are now ), matches and moves to state 2 (register values are now ), executes the final operations in state 2 (register values are now ) and finally exits TDFA.
Complexity
Canonical DFA solve the recognition problem in linear time. The same holds for TDFA, since the number of registers and register operations is fixed and depends only on the regular expression, but not on the length of input. The overhead on submatch extraction depends on tag density in a regular expression and nondeterminism degree of each tag (the maximum number of registers needed to track all possible values of the tag in a single TDFA state). On one extreme, if there are no tags, a TDFA is identical to a canonical DFA. On the other extreme, if every subexpression is tagged, a TDFA effectively performs full parsing and has many operations on every transition. In practice for real-world regular expressions with a few submatch groups the overhead is negligible compared to matching with canonical DFA.
TDFA construction
TDFA construction is performed in a few steps. First, a regular expression is converted to a tagged nondeterministic finite automaton (TNFA). Second, a TNFA is converted to a TDFA using a determinization procedure; this step also includes disambiguation that resolves conflicts between ambiguous TNFA paths. After that, a TDFA can optionally go through a number of optimizations that reduce the number of registers and operations, including minimization that reduces the number of states. Algorithms for all steps of TDFA construction with pseudocode are given in the paper by Borsotti and Trafimovich.
This section explains TDFA construction on the example of a regular expression , where is a tag and are alphabet symbols.
Tagged NFA
TNFA is a nondeterministic finite automaton with tagged ε-transitions. It was first described by Laurikari, although similar constructions were known much earlier as Mealy machines and nondeterministic finite-state transducers. TNFA construction is very similar to Thompson's construction: it mirrors the structure of a regular expression. Importantly, TNFA preserves ambiguity in a regular expression: if it is possible to match a string in two different ways, then TNFA for this regular expression has two different accepting paths for this string. TNFA definition by Borsotti and Trafimovich differs from the original one by Laurikari in that TNFA can have negative tags on transitions: they are needed to make the absence of match explicit in cases when there is a bypass for a tagged transition.
Figure 1 shows TNFA for the example regular expression . It has three kinds of transitions: transitions on alphabet symbols (dark blue), tagged ε-transitions (the one from state 4 to state 12 with tag and the one from state 10 to state 11 with negative tag , bright green), and untagged ε-transitions (light blue). TNFA has a single start state 0 and a single final state 11.
In order to understand TNFA determinization, it helps to understand TNFA simulation first. Recall the canonical ε-NFA simulation: it constructs a subset of active states as an ε-closure of the start state, and then in a loop repeatedly steps on the next input symbol and constructs ε-closure of the active state set. Eventually the loop terminates: either the active set becomes empty (which means a failure), or all input symbols get consumed (which means a success if the active set contains a final state, otherwise a failure). TNFA simulation is similar, but it additionally tracks tag values. Every time simulation encounters a tagged transition, it updates tag value to the current offset. Since the simulation tracks multiple nondeterministic paths simultaneously, tag values along these paths may differ and should be tracked separately. Another difficulty is the need for disambiguation: unlike canonical NFA simulation, TNFA simulation needs to distinguish ambiguous paths, as they may have different tag values.
Figure 2 shows an example of TNFA simulation on a string :
Disambiguation
Ambiguity means the existence of multiple different parse trees for the same input. It is a property of a regular expression; ambiguity is preserved by TNFA construction and gets resolved during TNFA simulation or determinization. One way to resolve ambiguity is use a disambiguation policy, the most notable examples being the leftmost-greedy and the longest-match (POSIX) policies. The leftmost-greedy policy is defined in terms of regular expression structure; it admits a simple and efficient implementation. The POSIX policy, on the other hand, is defined in terms of the structure of parse results; it is more difficult to implement and computationally more complex than the leftmost-greedy policy. TDFA can work with both policies, and there is no runtime overhead on disambiguation, since it happens during determinization and gets built into TDFA structure. For TNFA simulation, on the other hand, the time spent on disambiguation is included in the runtime.
The example regular expression is deliberately ambiguous, as it allows one to parse in two different ways: either as the left alternative , or the right one . Depending on which alternative is preferred, tag should either have value (the offset at the position between symbols and ), or (undefined). Both POSIX and leftmost greedy disambiguation policies agree that the first alternative is preferable in this case.
Determinization
TNFA determinization is based on the canonical powerset construction algorithm that converts an NFA to a DFA. The algorithm simulates NFA on all possible strings. At each step of the simulation, the active set of NFA states forms a new DFA state. If the new state is identical to an existing DFA state, it is discarded and replaced with the existing one, and the current branch of simulation terminates. Otherwise the new state is added to the growing set of DFA states and simulation from this state continues. Eventually determinization terminates: although the set of all possible strings is infinite, the set of different DFA states is finite, and at some point all new states become identical to existing ones.
In the case of TDFA naive powerset construction faces a problem: TDFA states contain tag information, which changes at every step of the simulation (as the offsets increase). This prevents TDFA states from mapping: a pair of states that contain identical TNFA states but different tag offsets are not identical and cannot be mapped. As a result, simulation continues indefinitely, the set of TDFA states grows, and determinization does not terminate. To solve this problem, Laurikari applied the idea of indirection: instead of storing immediate tag values in TDFA states, he suggested storing them indirectly in registers. Tag values in registers may be different, but it doesn't matter as long as the registers are identical. This solves the termination problem: even if TDFA states have different registers, they can be made identical (mapped to each other) by adding operations that copy the corresponding register values. Indirection is not free: it requires adding runtime register operations on transitions that update register values. To reduce the runtime overhead, Trafimovich used the lookahead optimization. The idea is to move register operations from the incoming transition into a TDFA state to the outgoing transitions from this state. This way the operations get split on the lookahead symbol,