Flex (lexical analyser generator)

flex
Developer(s)	Vern Paxson
Initial release	around 1987 (1987)^[1]
Stable release	2.6.0 / November 17, 2015 (2015-11-17)
Operating system	Unix-like
Type	Lexical analyzer generator
License	BSD license
Website	flex.sourceforge.net

Flex (fast lexical analyzer generator) is a free and open-source software alternative to lex.^[2] It is a computer program that generates lexical analyzers (also known as "scanners" or "lexers").^[3]^[4] It is frequently used as the lex implementation together with Berkeley Yacc parser generator on BSD-derived operating systems (as both lex and yacc are part of POSIX),^[5]^[6]^[7] or together with GNU bison (a version of yacc) in *BSD ports^[8] and in GNU/Linux distributions. Unlike Bison, flex is not part of the GNU Project and is not released under the GNU Public License.^[9]

History

Flex was written in C by Vern Paxson around 1987.^[1] He was translating a Ratfor generator, which had been led by Jef Poskanzer.^[10]

Example lexical analyzer

This is an example of a Flex scanner for the instructional programming language PL/0.

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

%{
#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;}

Internals

Main article: 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 languages. These machines are a subset of the collection of Turing machines. 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 $O(n)$ in the length of the input. That is, it performs a constant number of operations for each input symbol. This constant is quite low: GCC generates 12 instructions for the DFA match loop. 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.^[11]

Reentrancy

By default the scanner generated by Flex is not 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.^[12]

Usage under non-Unix environments

Normally the generated scanner contains references to unistd.h header file which is Unix specific. To avoid generating code that includes unistd.h, %option nounistd should be used. Another issue is the call to isatty (a Unix library function), which can be found in the generated code. The %option never-interactive forces flex to generate code that doesn't use isatty.^[13]

Using flex from other languages

Flex can only generate code for C and C++. To use the scanner code generated by flex from other languages a language binding tool such as SWIG can be used.

Flex++

flex++ is similar lexical scanner for C++ which is included as part of the flex package. The generated code does not depend on any runtime or external 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 and similar situations where traditional operating system or C runtime facilities may not be available.

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

References

1 2 Levine, John (August 2009). flex & bison. O'Reilly Media. p. 9. ISBN 978-0-596-15597-1. 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 'Fast Lexical Analyzer Generator.'
↑ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex & yacc (2nd ed.). O'Reilly. p. 279. ISBN 1-56592-000-7. A freely available version of lex is flex.
↑ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex & yacc (2nd ed.). O'Reilly. pp. 1–2. ISBN 1-56592-000-7.
↑ Levine, John (August 2009). flex & bison. O'Reilly Media. p. 304. ISBN 978-0-596-15597-1.
↑ OpenBSD (2015-12-11). "src/usr.bin/lex/". BSD Cross Reference. Retrieved 2015-12-26. This is flex, the fast lexical analyzer generator.
↑ "flex(1)". *BSD man pages.
↑ "yacc(1)". *BSD man pages.
↑ "bison-3.0.4 – GNU parser generator". OpenBSD ports. 2015-11-15. Retrieved 2015-12-26.
↑ Is flex GNU or not?, flex FAQ
↑ When was flex born?, flex FAQ
↑ "Performance - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Retrieved 2013-02-25.
↑ "Reentrant - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Retrieved 2013-02-25.
↑ "Code-Level And API Options - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Retrieved 2013-02-25.

External links

This article is issued from Wikipedia - version of the Saturday, February 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.