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 F {\displaystyle F} is a tuple
( Σ , T , S , S f , s 0 , R , R f , δ , φ ) {\displaystyle (\Sigma ,T,S,S_{f},s_{0},R,R_{f},\delta ,\varphi )} , where:
Σ {\displaystyle \Sigma } is a finite set of symbols (alphabet)
T {\displaystyle T} is a finite set of tags
S {\displaystyle S} is a finite set of states with initial state s 0 {\displaystyle s_{0}} and a subset of final states S f ⊆ S {\displaystyle S_{f}\subseteq S}
R {\displaystyle R} is a finite set of registers with a subset of final registers R f {\displaystyle R_{f}} (one per tag)
δ : S × Σ → S × O ∗ {\displaystyle \delta :S\times \Sigma \rightarrow S\times O^{*}} is a transition function
φ : S f → O ∗ {\displaystyle \varphi :S_{f}\rightarrow O^{*}} is a final function, where O {\displaystyle O} is a set of register operations of the following types: set register i {\displaystyle i} to nil or to the current position: i ← v {\displaystyle i\leftarrow v} , where v ∈ { n , p } {\displaystyle v\in \{\mathbf {n} ,\mathbf {p} \}}
copy register j {\displaystyle j} to register i {\displaystyle i} : i ← j {\displaystyle i\leftarrow j}
… excerpt ends here. Continue reading the full article.
