View source for RE/flex

{{Short description|Advanced lexical analyzer generator for C++}}
{{multiple issues|
{{primary sources|date=February 2024}}
}}
{{Infobox software
| name                   = RE/flex
| logo                   = 
| screenshot             =
| caption                =
| developer              = Dr. Robert van Engelen and others
| released               = {{Start date and age|2016|12|05}}
| latest release version = 5.3
| latest release date    = {{release date|2025|2|28}}
| operating system       = [[Cross-platform]]
| programming language   = [[C++]]
| genre                  = [[Lexical analysis]]
| license                = [[BSD license]]
| website                = https://github.com/Genivia/RE-flex
}}

'''RE/flex''' (regex-centric, fast lexical analyzer)<ref>{{cite web|url=https://www.codeproject.com/Articles/1180430/Constructing-Fast-Lexical-Analyzers-with-RE-flex-W|title=Constructing Fast Lexical Analyzers with RE/flex - Why Another Scanner Generator?|last=van Engelen|first=Robert|date=April 15, 2017|website=CodeProject}}</ref><ref>{{cite web|url=https://www.thefreecountry.com/programming/compilerconstruction.shtml|title=Free Compiler Construction Tools|last=Heng|first= Christopher|date=December 27, 2018}}</ref> is a free and open source [[computer program]] written in C++ that generates fast [[lexical analysis|lexical analyzer]]s (also known as "scanners" or "lexers")<ref>{{cite book |last1=Levine |first1=John R. | authorlink1=John R. Levine |last2=Mason |first2=Tony |last3=Brown |first3=Doug |title=lex & yacc |pages=1–2 |publisher=[[O'Reilly Media|O'Reilly]] |year=1992 |edition=2nd |isbn=1-56592-000-7 |url=https://books.google.com/books?id=YrzpxNYegEkC}}</ref><ref>{{cite book |last=Levine |first=John |author-link=John Levine |title=flex & bison |publisher=O'Reilly Media |date=August 2009 |isbn=978-0-596-15597-1 |page=304 |url=http://oreilly.com/catalog/9780596155988}}</ref> in C++.  RE/flex offers full [[Unicode]] support, indentation anchors, word boundaries, lazy quantifiers (non-greedy, lazy repeats), and performance tuning options.  RE/flex accepts [[Flex (lexical analyser generator)|Flex]] lexer specifications and offers options to generate scanners for Bison parsers.  RE/flex includes a fast C++ [[regular expression]] library.

== History ==

The RE/flex project was designed and implemented by professor Robert van Engelen in 2016 and released as free open source.  The software evolved with several contributions made by others.  The RE/flex tool generates lexical analyzers based on regular expression ("regex") libraries, instead of fixed [[Deterministic finite automata|DFA]] tables generated by traditional lexical analyzer generators.<ref>{{cite book|last1=Aho|first1=Alfred|last2=Sethi|first2=Ravi|last3=Ullman|first3=Jeffrey|title=Compilers: Principles, Techniques and Tools|url=https://archive.org/details/compilersprincip00ahoa|url-access=registration|publisher=Addison-Wesley|year=1986|isbn=9780201100884 }}</ref>

== Lexer specification ==

The RE/flex lexical analyzer generator accepts an extended syntax of [[Flex (lexical analyser generator)|Flex]] lexer specifications as input.  The RE/flex specification syntax is more expressive than the traditional [[Flex (lexical analyser generator)|Flex]] lexer specification syntax and may include indentation anchors, word boundaries, lazy quantifiers (non-greedy, lazy repeats), and new actions such as <code>wstr()</code> to retrieve Unicode wide-string matches.

A lexer specification is of the form:

<syntaxhighlight lang="text">
Definitions
%%
Rules
%%
User Code
</syntaxhighlight>

The Definitions section includes declarations and customization options, followed by name-pattern pairs to define names for regular expression patterns.  Named patterns may be referenced in other patterns by embracing them in <code>{</code> and <code>}</code>.  The following example defines two names for two patterns, where the second pattern <code>number</code> uses the previously named pattern <code>digit</code>:

<syntaxhighlight lang="cpp">
%top{
  #include <inttypes.h> // strtol()
}

%class{
  public:
    int value; // yyFlexLexer class public member
}

%init{
  value = 0; // yyFlexLexer initializations
}

%option flex

digit     [0-9]
number    {digit}+
</syntaxhighlight>

The Rules section defines pattern-action pairs.  The following example defines a rule to translate a number to the lexer class integer <code>value</code> member:

<syntaxhighlight lang="cpp">
{number}  value = strtol(yytext, NULL, 10);
\s        // skip white space
.         throw *yytext;
</syntaxhighlight>

The User Code section typically defines C/C++ functions, for example a <code>main</code> program:

<syntaxhighlight lang="cpp">
int main()
{
  yyFlexLexer lexer;
  try
  {
    while (lexer.yylex() != 0)
      std::cout << "number=" << lexer.value << std::endl;
  }
  catch (int ch)
  {
    std::cerr << "Error: unknown character code " << ch << std::endl;
  }
}
</syntaxhighlight>

The <code>yyFlexLexer</code> class is generated by RE/flex as instructed by the <code>%option flex</code> directive in the lexer specification.  The generated <code>lex.yy.cpp</code> source code contains the algorithm for lexical analysis, which is linked with the <code>libreflex</code> library.

== Source code output ==

The generated algorithm for lexical analysis is based on the concept that any regular expression engine can in principle be used to tokenize input into [[Lexical analysis#Token|token]]s: given a set of {{mvar|n}} regular expression patterns <math>p_i</math> for <math>i = 1,\ldots,n</math>, a regular expression of the form <code>"(<math>p_1</math>)|(<math>p_2</math>)|...|(<math>p_n</math>)"</code> with {{mvar|n}} alternations may be specified to match and tokenize the input.  In this way, the group capture index {{mvar|i}} of a matching pattern <math>p_i</math> that is returned by the regular expression matcher identifies the pattern <math>p_i</math> that matched the input text partially and continuously after the previous match.

This approach makes it possible for any regex library that supports group captures to be utilized as a matcher.  However, note that all groupings of the form <code>(X)</code> in patterns must be converted to non-capturing groups of the form <code>(?:X)</code> to avoid any unwanted group capturing within sub-expressions.

The following RE/flex-generated <code>yyFlexLexer</code> class <code>yylex</code> method repeatedly invokes the matcher's <code>scan</code> (continuous partial matching) operation to tokenize input:

<syntaxhighlight lang="cpp">
int yyFlexLexer::yylex()
{
  if (!has_matcher())
    matcher("(p1)|(p2)|...|(pn)"); // new matcher engine for regex pattern (p1)|(p2)|...|(pn)
  while (true)
  {
    switch (matcher().scan()) // scan and match next token, get capture index
    {
      case 0: // no match
        if (... EOF reached ...)
          return 0;
        output(matcher().input()); // echo the current input character
        break;
      case 1: // pattern p1 matched
        ... // Action for pattern p1
        break;
      case 2: // pattern p2 matched
        ... // Action for pattern p2
        break;
      ... // and so on for patterns up to pn
    }
  }
}
</syntaxhighlight>

If none of the {{mvar|n}} patterns match and the end-of-file (EOF) is not reached, the so-called "default rule" is invoked.  The default rule echo's the current input character and advances the scanner to the next character in the input.

The regular expression pattern <code>"(<math>p_1</math>)|(<math>p_2</math>)|...|(<math>p_n</math>)"</code> is produced by RE/flex from a lexer specification with {{mvar|n}} rules of pattern-action pairs:

<syntaxhighlight lang="text">
%%
p1    Action for pattern p1
p2    Action for pattern p2
...
pn    Action for pattern pn
%%
</syntaxhighlight>

From this specification, RE/flex generates the aforementioned <code>yyFlexLexer</code> class with the <code>yylex()</code> method that executes actions corresponding to the patterns matched in the input.  The generated <code>yyFlexLexer</code> class is used in a C++ application, such as a parser, to tokenize the input into the integer-valued tokens returned by the actions in the lexer specification.  For example:

<syntaxhighlight lang="cpp">
std::ifstream ifs(filename, std::ios::in);
yyFlexLexer lexer(ifs);
int token;
while ((token = lexer.yylex()) != 0)
  std::cout << "token = " << token << std::endl;
ifs.close();
</syntaxhighlight>

Note that <code>yylex()</code> returns an integer value when an action executes <code>return token_value;</code>.  Otherwise, <code>yylex()</code> does not return a value and continues scanning the input, which is often used by rules that ignore input such as comments.

This example tokenizes a file.  A lexical analyzer often serves as a tokenizer for a parser generated by a parser generator such as [[GNU Bison|Bison]].

== Compatibility ==

RE/flex is compatible with Flex specifications when <code>%option flex</code> is used.  This generates a <code>yyFlexLexer</code> class with <code>yylex()</code> method.  RE/flex is also compatible with Bison using a range of RE/flex options for complete coverage of Bison options and features.

By contrast to Flex, RE/flex scanners are [[Thread safety|thread-safe]] by default on work with reentrant Bison parsers.

== Unicode support ==

RE/flex supports [[Unicode]] regular expression patterns in lexer specifications and automatically tokenizes UTF-8, UTF-16, and UTF-32 input files.  Code pages may be specified to tokenize input files encoded in [[ISO/IEC 8859]] 1 to 16, [[Windows-1250]] to [[Windows-1258]], CP-437, CP-850, CP-858, MacRoman, [[KOI-8]], [[EBCDIC]], and so on.  Normalization to UTF-8 is automatically performed by internal incremental buffering for (partial) pattern matching with Unicode regular expression patterns.

== Indent, nodent, and dedent matching ==

RE/flex integrates indent and dedent matching directly in the regular expression syntax with new <code>\i</code> and <code>\j</code> anchors.  These indentation anchors detect changes of line [[Indentation (typesetting)|indentation]] in the input.  This allows many practical scenarios to be covered to tokenize programming languages with indented block structures.  For example, the following lexer specification detects and reports indentation changes:

<syntaxhighlight lang="cpp">
%%
^[ \t]+        std::cout << "| "; // nodent: text is aligned to current indent margin
^[ \t]*\i      std::cout << "> "; // indent: matched with \i
^[ \t]*\j      std::cout << "< "; // dedent: matched with \j
\j             std::cout << "< "; // dedent: for each extra level dedented
%%
</syntaxhighlight>

== Lazy quantifiers ==

Lazy quantifiers may be associated with repeats in RE/flex regular expression patterns to simplify the expressions using non-greedy repeats, when applicable.  Normally matching is "greedy", meaning that the longest pattern is matched.  For example, the pattern  <code>a.*b</code> with the greedy <code>*</code> repeat matches <code>aab</code>, but also matches <code>abab</code> because <code>.*</code> matches any characters except newline and <code>abab</code> is longer than <code>ab</code>.  Using a lazy quantifier <code>?</code> for the lazy repeat <code>*?</code>, pattern <code>a.*?b</code> matches <code>ab</code> but not <code>abab</code>.

As a practical application of lazy quantifiers, consider matching C/C++ multiline comments of the form <code>/*...*/</code>.  The lexer specification pattern <syntaxhighlight lang="ragel" inline>"/*"(.|\n)*?"*/"</syntaxhighlight> with lazy repeat <code>*?</code> matches multiline comments.  Without lazy repeats the pattern <syntaxhighlight lang="ragel" inline>"/*"([^*]|(\*+[^*/]))*\*+"/"</syntaxhighlight> should be used (note that quotation of the form <code>"..."</code> is allowed in lexer specifications only, this construct is comparable to the <code>\Q...\E</code> quotations supported by most regex libraries.)

== Other pattern matchers ==

Besides the built-in RE/flex POSIX regex pattern matcher, RE/flex also supports PCRE2, Boost.Regex and std::regex pattern matching libraries.  PCRE2 and Boost.Regex offer a richer regular expression pattern syntax with Perl pattern matching semantics, but are slower due to their intrinsic [[Nondeterministic finite automata|NFA]]-based matching algorithm.  

== Translation ==

Lex, Flex and RE/flex translate regular expressions to [[Deterministic finite automata|DFA]], which are implemented in tables for run-time scanning.  RE/flex differs from Lex and Flex in that the generated tables contain a list of opcode words executed by a [[Virtual_machine |virtual machine]] to perform pattern matching.  In addition, a [[Deterministic finite automata|DFA]] implemented in code instead of opcode tables is generated with the <code>--fast</code> option.

For example, the following direct-coded [[Deterministic finite automata|DFA]] for pattern <code>\w+</code> is generated with option <code>--fast</code>:

<syntaxhighlight lang="cpp">
void reflex_code_INITIAL(reflex::Matcher& m)
{
  int c0 = 0, c1 = 0;
  m.FSM_INIT(c1);
S0:
  m.FSM_FIND();
  c1 = m.FSM_CHAR();
  if ('a' <= c1 && c1 <= 'z') goto S5;
  if (c1 == '_') goto S5;
  if ('A' <= c1 && c1 <= 'Z') goto S5;
  if ('0' <= c1 && c1 <= '9') goto S5;
  return m.FSM_HALT(c1);
S5:
  m.FSM_TAKE(1);
  c1 = m.FSM_CHAR();
  if ('a' <= c1 && c1 <= 'z') goto S5;
  if (c1 == '_') goto S5;
  if ('A' <= c1 && c1 <= 'Z') goto S5;
  if ('0' <= c1 && c1 <= '9') goto S5;
  return m.FSM_HALT(c1);
}
</syntaxhighlight>

A list of virtual machine opcode words for pattern <code>\w+</code> is generated with option <code>--full</code>:

<syntaxhighlight lang="cpp">
REFLEX_CODE_DECL reflex_code_INITIAL[11] =
{
  0x617A0005, // 0: GOTO 5 ON 'a'-'z'
  0x5F5F0005, // 1: GOTO 5 ON '_'
  0x415A0005, // 2: GOTO 5 ON 'A'-'Z'
  0x30390005, // 3: GOTO 5 ON '0'-'9'
  0x00FFFFFF, // 4: HALT
  0xFE000001, // 5: TAKE 1
  0x617A0005, // 6: GOTO 5 ON 'a'-'z'
  0x5F5F0005, // 7: GOTO 5 ON '_'
  0x415A0005, // 8: GOTO 5 ON 'A'-'Z'
  0x30390005, // 9: GOTO 5 ON '0'-'9'
  0x00FFFFFF, // 10: HALT
};
</syntaxhighlight>

== Debugging and profiling ==

The RE/flex built-in profiler can be used to measure the performance of the generated scanner automatically.  The [[Profiling (computer_programming)|profiler]] [[Instrumentation (computer_programming)|instruments]] the scanner source code to collect run-time metrics.  At run-time when the instrumented scanner terminates, the profiler reports the number of times a rule is matched and the cumulative time consumed by the matching rule.  Profiling includes the time spent in the parser when the rule returns control to the parser.  This allows for fine-tuning the performance of the generated scanners and parsers.  Lexer rules that are [[Hot spot (computer programming)|hot spots]], i.e. computationally expensive, are detected and can be optimized by the user in the lexer source code.

Also debugging of the generated scanner is supported with Flex-compatible options.  Debugging outputs annotated lexer rules during scanning.

== See also ==

{{Portal|Free and open-source software}}
* [[Lexical analysis]]
* [[Comparison of parser generators]]

== References ==

{{Reflist}}

== External links ==

* [http://www.genivia.com/doc/reflex/html/index.html RE/flex manual]
* [https://github.com/Genivia/RE-flex GitHub project page]

[[Category:Compiling tools]]
[[Category:Finite automata]]
[[Category:Regular expressions]]
[[Category:Free software programmed in C++]]
[[Category:Software using the BSD license]]
[[Category:Lexical analysis]]