  This paper extends the work of Laurikari and Kuklewicz on tagged
deterministic finite automata (TDFA) in the context of submatch extraction in
regular expressions. The main goal of this work is application of TDFA to lexer
generators that optimize for speed of the generated code. I suggest a number of
practical improvements to Laurikari algorithm; notably, the use of one-symbol
lookahead, which results in significant reduction of tag variables and
operations on them. Experimental results confirm that lookahead-aware TDFA are
considerably faster and usually smaller than baseline TDFA; and they are
reasonably close in speed and size to ordinary DFA used for recognition of
regular languages. The proposed algorithm can handle repeated submatch and
therefore is applicable to full parsing. Furthermore, I examine the problem of
disambiguation in the case of leftmost greedy and POSIX policies. I formalize
POSIX disambiguation algorithm suggested by Kuklewicz and show that the
resulting TDFA are as efficient as Laurikari TDFA or TDFA that use leftmost
greedy disambiguation. All discussed algorithms are implemented in the open
source lexer generator RE2C.
