Software Impacts 6 (2020) 100027

Contents lists available at ScienceDirect

Software Impacts
journal homepage: www.journals.elsevier.com/software-impacts

Original software publication

RE2C: A lexer generator based on lookahead-TDFA
Ulya Trofimovich
Not affiliated to an organization

ARTICLEINFO

Keywords:
Lexical analysis
Regular expressions
Finite automata

ABSTRACTRE2C is a regular expression compiler: it transforms regular expressions into finite state machines and encodes
them as programs in the target language. At the core of RE2C is the lookahead-TDFA algorithm that allows
it to perform fast and lightweight submatch extraction. This article describes the algorithm used in RE2C andgives an example of TDFA construction.

Code metadata
Current code version
Permanent link to code/repository used for this code version
Permanent link to reproducible capsule
Legal Code License
Code versioning system used
Software code languages, tools, and services used
Compilation requirements, operating environments & dependencies
Link to developer documentation/manual
Support email for questions

2.0
https://github.com/SoftwareImpacts/SIMPAC-2020-29
https://codeocean.com/capsule/6014695/tree/v1
Public domain
Git
C++, Bison, RE2C (self-hosting)
OS: Linux, BSD, Nix/Guix, GNU Hurd, OS X, Windows, etc.
Dependencies: C++ compiler, Bash, CMake or Autotools. Optional Bison and Docutils.
https://re2c.org
re2c-general@lists.sourceforge.net

1. Introduction
Regular expression engines can be divided in two categories: runtime libraries and lexer generators. Run-time libraries perform interpretation or just-in-time compilation of regular expressions. They use avariety of algorithms ranging from recursive backtracking to automata,string searching, or some combination of the above. Lexer generators, on the other hand, perform ahead-of-time compilation. They use
algorithms based on deterministic finite automata (DFA) and spend
considerable time on compilation and optimization in order to emit
better code. Consequently, lexer generators usually do not support features that cannot be implemented on vanilla DFA. One such feature issubmatch extraction — the ability to find the correspondence between
parts of the regular expression and parts of the input string. Submatch
extraction is a special case of the parsing problem: in addition to solving
the recognition problem it has to find the derivation of the input stringin the grammar defined by the regular expression. Unlike full parsing,submatch extraction needs only a partial derivation. Therefore it would
be wasteful to perform full parsing, and a more specialized algorithm
is needed that has overhead proportional to submatch detalization. For
an optimizing lexer generator like RE2C [1,2] it is important that thegenerated code is at least as fast and memory-efficient as hand-written
code, and there is zero overhead if submatch extraction is not used.
2. Tagged DFAThe above requirements place tight constraints on the submatch
extraction algorithm: it should be a one-pass DFA-based algorithm thatworks in constant memory independent of the input length. Such analgorithm was invented by Ville Laurikari [3]. It works as follows.
First, the regular expression is converted to a nondeterministic finite
automaton with tagged transitions (TNFA). Tags are submatch markers
that can be placed anywhere in the regular expression; for example, aThe code (and data) in this article has been certified as Reproducible by Code Ocean: (https://codeocean.com/). More information on the Reproducibility
Badge Initiative is available at https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals.
E-mail address: skvadrik@gmail.com.
https://doi.org/10.1016/j.simpa.2020.100027
Received 28 July 2020; Received in revised form 29 July 2020; Accepted 4 August 20202665-9638/© 2020 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license(http://creativecommons.org/licenses/by-nc-nd/4.0/).

U. Trofimovich

Software Impacts 6 (2020) 100027Fig. 1. Lookahead-TDFA construction for regular expression 𝑎∗ 𝑡1 (𝑡2 𝑏)∗ 𝑐 with tags 𝑡1 and 𝑡2 that matches strings 𝑎 … 𝑎𝑏 … 𝑏𝑐 (tag 𝑡1 marks the boundary between 𝑎s and 𝑏s, andtag 𝑡2 marks the last 𝑏). Top: TNFA (𝜖∕𝜖 labels are omitted, and negative tags indicate no-match). Middle: lookahead-TDFA under construction with state-sets, register matrices
and lookahead tags (𝑝 is the current position, and ∅ is no-match). Bottom left: lookahead-TDFA after construction. Bottom right: lookahead-TDFA after optimization (the numberof registers is minimized and some register operations are removed).

3. Lookahead TDFA

capturing group can be represented with a pair of tags for the openingand closing parentheses. TNFA is in essence a nondeterministic finite
state transducer that rewrites symbolic strings into tagged strings. The
most important part of Laurikari algorithm is TNFA determinization.
Its basic principle is the same as in the powerset construction thatconverts NFA to DFA: the NFA is simulated on all possible input strings,
maintaining a set of states at each step. If the current state-set is new,it becomes a new DFA state, otherwise it is mapped to an existing
DFA state. In the Laurikari algorithm state-sets are augmented with tag
information: each TNFA substate has an associated vector of registers
that store tag values, so that the whole state-set is a matrix indexed by
TNFA states and tags. Registers are needed because different substates
are reached by different TNFA paths, and the tags along one path may
disagree with tags along another path. If a tag is updated on a TNFApath, its value is stored into a new register. The augmented state-setscannot be mapped in the same way as ordinary DFA states, because apair of state-sets may have identical TNFA substates, but different registers. The key insight is that mapping of such state-sets is still possible if
there is a bijection between their registers: the bijective transformation
can be encoded in the form of register reordering operations on TDFAtransitions. After determinization all the information in TDFA state-sets
is erased, and the resulting TDFA is like ordinary DFA extended with afixed number of registers and operations on transitions that update andreorder tag values stored in registers. Algorithms like minimization are
applicable to TDFA, but they need to differentiate between transitions
with different register operations.

One improvement to Laurikari algorithm that allows to greatly
reduce the number of register operations is the use of the lookahead
symbol [4]. The idea is to delay the application of register operations
until the lookahead symbol is known, and attach the operations to
the outgoing transition on that symbol instead of the preceding incoming transition. The insight is that some of TNFA paths that havereached the current TDFA state are canceled after the application oflookahead symbol, and all register operations associated with thesepaths can be canceled as well. In other words, delaying for one step
allows one to split register operations on the lookahead symbol, andinstead of doing all of them, do only the relevant part. This requires amodification to the underlying TDFA state-sets: in addition to registers,
each substate needs to have an associated list of lookahead tags. The
additional information is erased after determinization, and the resulting
lookahead-TDFA is faster than ordinary TDFA and better suited forfurther transformations like minimization and register allocation. On
the whole, this idea is similar to the improvement of LALR parsers overLR parsers: the use of lookahead information in states greatly reduces
the number of conflicts (for TDFA a conflict is not an error, but it means
extra registers and register operations). An example of lookahead-TDFA
construction can be seen on Fig. 1.
4. Ambiguity resolution
One of the challenges that makes parsing harder than recognitionis ambiguity: there may be several ways to parse the input string.
Which way to prefer is usually defined by a disambiguation policy.
2

U. Trofimovich

Software Impacts 6 (2020) 100027

CRediT authorship contribution statement

TDFA algorithm can be parameterized over different policies; for example, RE2C supports both the Perl leftmost-greedy policy and thePOSIX longest-match policy [5]. Disambiguation happens at the timeof determinization (in 𝜖-closure construction), and the resulting TDFA
does not perform any disambiguation at run-time: ambiguity-resolving
decisions are embedded into its structure.

Ulya Trofimovich: Conceptualization, Software, Validation, Formalanalysis, Writing - original draft.
Declaration of competing interest

5. Impact

The authors declare that they have no known competing financial interests or personal relationships that could have appeared toinfluence the work reported in this paper.

RE2C is a lexer generator of choice for projects that need fast lexical
analyzers. It has a flexible user interface that allows one to customize
the generated code for a particular environment and input model. Fastand lightweight submatch extraction is yet another feature that makes
RE2C a good alternative to other lexer generators. Notable projects thatuse RE2C are the following:

Acknowledgments
I want to thank my parents Vladimir and Elina, my friend andfellow researcher Angelo Borsotti, my school math teachers Tatyana
Leonidovna and Demian Vladimirovich, and, most of all, Sergei.

• Ninja, a build system with a focus on speed. [6] Ninja is used
in a great number of open-source projects, and it is a necessarybuilding block in many operating systems and platforms.
• PHP, a popular general-purpose scripting language. [7]• BRL-CAD, a constructive solid geometry solid modeling computeraided design system. [8]• STEPCode, an implementation of ISO 10303 standard. [9]• Apache SpamAssassin, a program for e-mail spam filtering. [10]• Yasm, the Modular Assembler Project. [11]• Wake, the SiFive build tool. [12]References[1] RE2C, a lexer generator for C, C++ and Go. Website: https://re2c.org, source
code: https://github.com/skvadrik/re2c.
[2] Peter Bumbulis, Donald D. Cowan, RE2C: A more versatile scanner generator,ACM Lett. Programm. Lang. Syst. (LOPLAS) 2 (1-4) (1993) 70–84.
[3] Ville Laurikari, NFAs with tagged transitions, their conversion to deterministic
automata and application to regular expressions, in: Proceedings Seventh International Symposium on String Processing and Information Retrieval, 2000. SPIRE
2000, pp. 181–187, URL: http://laurikari.net/ville/spire2000-tnfa.pdf.
[4] Ulya Trofimovich, Tagged Deterministic Finite Automata with Lookahead, 2017,cs.FL.
[5] Angelo Borsotti, Ulya Trofimovich, Efficient POSIX submatch extraction on NFA,
preprint, 2019, URL: https://re2c.org/2019_borsotti_trofimovich_efficient_posix_
submatch_extraction_on_nfa.pdf.
[6] Ninja build system, URL: https://ninja-build.org, build files that use RE2C:
https://ninja-build.org/build.ninja.html.
[7] PHP Internals Book, chapter Building PHP, URL: http://www.phpinternalsbook.
com/php7/build_system/building_php.html.
[8] BRL-CAD: Tools, URL: http://sourceforge.net/p/brlcad/code/HEAD/tree/brlcad/
trunk/misc/tools/re2c.
[9] STEPCode: Build Process, URL: https://stepcode.github.io/docs/build_process.
[10] SpamAssassin (sa-compile), URL: https://spamassassin.apache.org/full/3.2.x/
doc/sa-compile.html.
[11] Yasm, URL: https://yasm.tortall.net.
[12] Wake, URL: https://github.com/sifive/wake.
[13] Repology: RE2C. URL: https://repology.org/project/re2c/information.
[14] Niels Bjørn Bugge Grathwohl, Parsing with Regular Expressions & Extensions toKleene Algebra, DIKU, University of Copenhagen, 2015.
[15] Mohammad Imran Chowdhury, StaDFA: An Efficient Subexpression Matching
Method (Master thesis), Florida State University, 2018.
[16] Michela Becchi, Data Structures, Algorithms and Architectures for Efficient
Regular Expression Evaluation, Washington University In St. Louis, School ofEngineering and Applied Science, 2009.

RE2C has a permissive license, which allows it to be used in proprietary software as well. The project has been ported to many operatingsystems; according to Repology [13], it is packaged in more than 60
distributions. Besides being a useful practical tool, RE2C is a researchplayground for the development of new algorithms in the field ofautomata and formal languages.
6. Conclusion and future work
Submatch extraction algorithm implemented in RE2C is both animportant theoretical development and a useful practical improvement.
It allows one to program lexical analyzers capable of submatch extraction without resorting to manual post-processing or the use ofstring-searching functions. The overhead on submatch extraction is
proportional to submatch detalization: there is zero overhead if nosubmatch information is needed, and even for large submatch-heavy
regular expressions like RFC-compliant URI and HTTP parsers theoverhead is modest (about 1.25x compared to simple recognition on
DFA [4]). Future work may relate TDFA to other parsing automata,such as DSST [14] and sta-DFA [15], and investigate the possibility ofusing tagged counter automata for counted repetition [16].

3