Editing Flex (lexical analyser generator)

{{Short description|UNIX program for lexical analysis}}
{{Infobox software
| name                   = flex
| logo                   =
| developer              = [[Vern Paxson]]
| released               = around {{Start date and age|1987}}<ref name=releasehistorypage9>{{cite book |last=Levine |first=John |author-link=John R. Levine |title=flex & bison |isbn=978-0-596-15597-1 |publisher=O'Reilly Media |date=August 2009 |page=9 |quote=In about 1987, Vern Paxson of the Lawrence Berkeley Lab took a version of lex written in ratfor (an extended Fortran popular at the time) and translated it into C, calling it flex, for {{'}}''F''ast ''Lex''ical Analyzer Generator.{{'}} |url=https://books.google.com/books?id=3Sr1V5J9_qMC&q=%22In+about+1987%2C+Vern+Paxson%22}}</ref>
| latest release version = 2.6.4
| latest release date    = {{Start date and age|2017|5|6}}
| operating system       = [[Unix-like]]
| genre                  = [[Lexical analysis|Lexical analyzer]] generator
| license                = [[BSD license]]
| website                = {{URL|https://github.com/westes/flex}}
}}
'''Flex''' (fast [[lexical analyzer]] generator) is a [[free and open-source software]] alternative to [[lex programming tool|lex]].<ref>{{cite book |last1=Levine |first1=John R. |authorlink1=John R. Levine |last2=Mason |first2=Tony |last3=Brown |first3=Doug |title=lex & yacc |publisher=[[O'Reilly Media|O'Reilly]] |year=1992 |edition=2nd |isbn=1-56592-000-7 |page=279 |quote=A freely available version of lex is ''flex''. |url=https://books.google.com/books?id=YrzpxNYegEkC&q=%22a+freely+available+version+of+lex+is+flex%22}}</ref> 
It is a [[computer program]] that generates [[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>
It is frequently used as the lex implementation together with [[Berkeley Yacc]] [[parser generator]] on [[Berkeley Software Distribution|BSD]]-derived operating systems (as both <code>lex</code> and <code>yacc</code> are part of [[POSIX]]),<ref>{{cite web |url=http://bxr.su/o/usr.bin/lex/ |title=src/usr.bin/lex/ |website=BSD Cross Reference |author=OpenBSD |author-link=OpenBSD |date=2015-12-11 |access-date=2015-12-26 |quote="This is flex, the fast lexical analyzer generator."}}</ref><ref>{{cite web |url=http://mdoc.su/-/flex.1 |title=<code>flex(1)</code> |website=*BSD [[man page]]s}}</ref><ref>{{cite web |url=http://mdoc.su/-/yacc.1 |title=<code>yacc(1)</code> |website=*BSD [[man page]]s}}</ref> or together with [[GNU bison]] (a version of [[yacc]]) in [[Ports collection|*BSD ports]]<ref>{{cite web |url=http://ports.su/devel/bison |title=bison-3.0.4 – GNU parser generator |work=[[OpenBSD ports]] |date=2015-11-15 |access-date=2015-12-26}}</ref> and in Linux distributions.  Unlike Bison, flex is not part of the [[GNU Project]] and is not released under the [[GNU General Public License]],<ref>[https://westes.github.io/flex/manual/Is-flex-GNU-or-not_003f.html#Is-flex-GNU-or-not_003f Is flex GNU or not?], flex FAQ</ref> although a manual for Flex was produced and published by the Free Software Foundation.<ref>{{Cite web|url=https://ftp.gnu.org/old-gnu/Manuals/flex-2.5.4/flex.html|title=Flex - a scanner generator - Table of Contents - GNU Project - Free Software Foundation (FSF)|website=ftp.gnu.org|access-date=2019-12-05}}</ref>

==History==
Flex was written in [[C (programming language)|C]] around 1987<ref name=releasehistorypage9 /> by [[Vern Paxson]], with the help of many ideas and much inspiration from [[Van Jacobson]]. Original version by [[Jef Poskanzer]]. The fast table representation is a partial implementation of a design done by Van Jacobson. The implementation was done by Kevin Gong and Vern Paxson.<ref name="flexman">{{cite web |title=Flex, version 2.5 A fast scanner generator Edition 2.5, March 1995 |url=https://www.cs.princeton.edu/~appel/modern/c/software/flex/flex_toc.html#TOC25 |access-date=20 April 2019}}</ref>

== Example lexical analyzer ==
This is an example of a Flex scanner for the instructional programming language [[PL/0]].

The tokens recognized are: '<code>+</code>', '<code>-</code>', '<code>*</code>', '<code>/</code>', '<code>=</code>', '<code>(</code>', '<code>)</code>', '<code>,</code>', '<code>;</code>', '<code>.</code>', '<code>:=</code>', '<code><</code>', '<code><=</code>', '<code><></code>', '<code>></code>', '<code>>=</code>';
numbers: <code>0-9 {0-9}</code>; identifiers: <code>a-zA-Z {a-zA-Z0-9}</code> and keywords: <code>begin</code>, <code>call</code>, <code>const</code>, <code>do</code>, <code>end</code>, <code>if</code>, <code>odd</code>, <code>procedure</code>, <code>then</code>, <code>var</code>, <code>while</code>.

<syntaxhighlight lang="c">
%{
#include "y.tab.h"
%}

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }
{letter}({letter}|{digit})* {
                       yylval.id = strdup(yytext);
                       return IDENT;      }
{digit}+             { yylval.num = atoi(yytext);
                       return NUMBER;     }
[ \t\n\r]            /* skip whitespace */
.                    { printf("Unknown character [%c]\n",yytext[0]);
                       return UNKNOWN;    }
%%

int yywrap(void){return 1;}
</syntaxhighlight>

==Internals==
{{main|Lexical analysis}}
These programs perform character parsing and tokenizing via the use of a [[deterministic finite automaton]] (DFA). A DFA is a theoretical machine accepting [[regular language]]s. These machines are a subset of the collection of [[Turing machine]]s. DFAs are equivalent to [[read-only right moving Turing machines]]. The syntax is based on the use of [[regular expressions]]. See also [[nondeterministic finite automaton]].

== Issues ==

=== Time complexity ===
A Flex lexical analyzer usually has time complexity <math>O(n)</math> in the length of the input. That is, it performs a constant number of operations for each input symbol. This constant is quite low: [[GNU Compiler Collection|GCC]] generates 12 instructions for the DFA match loop.{{citation needed|date=November 2015}} Note that the constant is independent of the length of the token, the length of the regular expression and the size of the DFA.

However, using the REJECT macro in a scanner with the potential to match extremely long tokens can cause Flex to generate a scanner with non-linear performance. This feature is optional. In this case, the programmer has explicitly told Flex to "go back and try again" after it has already matched some input. This will cause the DFA to backtrack to find other accept states. The REJECT feature is not enabled by default, and because of its performance implications its use is discouraged in the Flex manual.<ref name=performance>{{cite web |title=Performance - Lexical Analysis With Flex, for Flex 2.5.37 |publisher=Flex.sourceforge.net |date= |url=https://westes.github.io/flex/manual/Performance.html |access-date=2013-02-25}}</ref>

=== Reentrancy ===
By default the scanner generated by Flex is not [[Reentrant (subroutine)|reentrant]]. This can cause serious problems for programs that use the generated scanner from different threads. To overcome this issue there are options that Flex provides in order to achieve reentrancy. A detailed description of these options can be found in the Flex manual.<ref>{{cite web |url=https://westes.github.io/flex/manual/Reentrant.html |title=Reentrant - Lexical Analysis With Flex, for Flex 2.5.37 |publisher=Flex.sourceforge.net |date= |access-date=2013-02-25}}</ref>

=== Usage under non-Unix environments ===
Normally the generated scanner contains references to the ''unistd.h'' header file, which is [[Unix-like|Unix]] specific. To avoid generating code that includes ''[[unistd.h]]'', ''%option nounistd'' should be used. Another issue is the call to ''[[Not a typewriter|isatty]]'' (a Unix library function), which  can be found in the generated code. The ''%option never-interactive'' forces flex to generate code that does not use ''isatty''.<ref>{{cite web |title=Code-Level And API Options - Lexical Analysis With Flex, for Flex 2.5.37 |publisher=Flex.sourceforge.net |date= |url=https://westes.github.io/flex/manual/Code_002dLevel-And-API-Options.html |access-date=2013-02-25}}</ref>

===Using flex from other languages===
Flex can only generate code for [[C (programming language)|C]] and [[C++]]. To use the scanner code generated by flex from other languages a [[language binding]] tool such as [[SWIG]] can be used.

=== Unicode support ===
Flex is limited to matching 1-byte (8-bit) binary values and therefore does not support [[Unicode]].<ref>{{Cite web |last=Tomassetti |first=Gabriele |date=2020-03-04 |title=Why you should not use (f)lex, yacc and bison |url=https://tomassetti.me/why-you-should-not-use-flex-yacc-and-bison/ |access-date=2022-10-26 |website=Strumenta |language=en-US}}</ref> RE/flex and other alternatives do support Unicode matching.

==Flex++==

'''flex++''' is a similar lexical scanner for [[C++]] which is included as part of the flex package. The generated code does not depend on any [[Runtime library|runtime]] or external [[Library (computing)|library]] except for a memory allocator ([[malloc]] or a user-supplied alternative) unless the input also depends on it.  This can be useful in [[Embedded system|embedded]] and similar situations where traditional [[operating system]] or [[C standard library|C runtime]] facilities may not be available.

The flex++ generated C++ scanner includes the header file <code>FlexLexer.h</code>, which defines the interfaces of the two C++ generated classes.

==See also==
{{Portal|Free and open-source software}}
* [[Comparison of parser generators]]
*[[Lex programming tool|Lex]]
*[[yacc]]
*[[GNU Bison]]
*[[Berkeley Yacc]]

==References==
{{Reflist}}

==Further reading==
*{{cite book |last=Levine |first=John |author-link=John R. Levine |title=flex & bison |isbn=978-0-596-15597-1 |publisher=O'Reilly Media |date=August 2009 |url=http://oreilly.com/catalog/9780596155988}}
*M. E. Lesk and E. Schmidt, ''LEX - Lexical Analyzer Generator''
*Alfred Aho, Ravi Sethi and Jeffrey Ullman, ''Compilers: Principles, Techniques  and Tools'', Addison-Wesley (1986).  Describes the pattern-matching techniques used by flex (deterministic finite automata)

==External links==
* {{Official website|https://github.com/westes/flex}}
* [http://www.quut.com/c/ANSI-C-grammar-l-1998.html ANSI-C Lex Specification]
* [http://www.jflex.de/ JFlex: Fast Scanner Generator for Java]
* [http://dinosaur.compilertools.net/ Brief description of Lex, Flex, YACC, and Bison] {{Webarchive|url=https://web.archive.org/web/20050507124121/http://dinosaur.compilertools.net/ |date=2005-05-07 }}

{{DEFAULTSORT:Flex Lexical Analyser}}
[[Category:Compiling tools]]
[[Category:Free software programmed in C]]
[[Category:Finite-state machines]]
[[Category:Software using the BSD license]]
[[Category:Lexical analysis]]