Flex (lexical analyser generator)

Last updated
flex
Developer(s) Vern Paxson
Initial releasearound 1987;35 years ago (1987) [1]
Stable release
2.6.4 / May 6, 2017;5 years ago (2017-05-06)
Repository
Operating system Unix-like
Type Lexical analyzer generator
License BSD license
Website github.com/westes/flex

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 Linux distributions. Unlike Bison, flex is not part of the GNU Project and is not released under the GNU General Public License, [9] although a manual for Flex was produced and published by the Free Software Foundation. [10]

Contents

History

Flex was written in C around 1987 [1] 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. [11]

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]%%"+"{returnPLUS;}"-"{returnMINUS;}"*"{returnTIMES;}"/"{returnSLASH;}"("{returnLPAREN;}")"{returnRPAREN;}";"{returnSEMICOLON;}","{returnCOMMA;}"."{returnPERIOD;}":="{returnBECOMES;}"="{returnEQL;}"<>"{returnNEQ;}"<"{returnLSS;}">"{returnGTR;}"<="{returnLEQ;}">="{returnGEQ;}"begin"{returnBEGINSYM;}"call"{returnCALLSYM;}"const"{returnCONSTSYM;}"do"{returnDOSYM;}"end"{returnENDSYM;}"if"{returnIFSYM;}"odd"{returnODDSYM;}"procedure"{returnPROCSYM;}"then"{returnTHENSYM;}"var"{returnVARSYM;}"while"{returnWHILESYM;}{letter}({letter}|{digit})*{yylval.id=strdup(yytext);returnIDENT;}{digit}+{yylval.num=atoi(yytext);returnNUMBER;}[\t\n\r]/* skip whitespace */.{printf("Unknown character [%c]\n",yytext[0]);returnUNKNOWN;}%%intyywrap(void){return1;}

Internals

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 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.[ citation needed ] 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. [12]

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. [13]

Usage under non-Unix environments

Normally the generated scanner contains references to the 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 does not use isatty. [14]

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.

Lack of Unicode support

Flex is limited to matching 1-byte (8-bit) binary values and therefore does not support Unicode. [15] 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 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.

See also

Related Research Articles

In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language.

Yacc is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser based on a formal grammar, written in a notation similar to Backus–Naur Form (BNF). Yacc is supplied as a standard utility on BSD and AT&T Unix. GNU-based Linux distributions include Bison, a forward-compatible Yacc replacement.

GNU Bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification in the BNF notation, warns about any parsing ambiguities, and generates a parser that reads sequences of tokens and decides whether the sequence conforms to the syntax specified by the grammar.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters into a sequence of lexical tokens. A program that performs lexical analysis may be termed a lexer, tokenizer, or scanner, although scanner is also a term for the first stage of a lexer. A lexer is generally combined with a parser, which together analyze the syntax of programming languages, web pages, and so forth.

Lex is a computer program that generates lexical analyzers.

Alfred Vaino Aho is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.

JavaCC is an open-source parser generator and lexical analyzer generator written in the Java programming language.

Doxygen is a documentation generator and static analysis tool for software source trees. When used as a documentation generator, Doxygen extracts information from specially-formatted comments within the code. When used for analysis, Doxygen uses its parse tree to generate diagrams and charts of the code structure. Doxygen can cross reference documentation and code, so that the reader of a document can easily refer to the actual code.

The Syntax/Semantic Language (S/SL) is an executable high level specification language for recursive descent parsers, semantic analyzers and code generators developed by James Cordy, Ric Holt and David Wortman at the University of Toronto in 1980.

The GNU toolchain is a broad collection of programming tools produced by the GNU Project. These tools form a toolchain used for developing software applications and operating systems.

Berkeley Yacc (byacc) is a Unix parser generator designed to be compatible with Yacc. It was originally written by Robert Corbett and released in 1989. Due to its liberal license and because it was faster than the AT&T Yacc, it quickly became the most popular version of Yacc. It has the advantages of being written in ANSI C89 and being public domain software.

In computer science, scannerless parsing performs tokenization and parsing in a single step, rather than breaking it up into a pipeline of a lexer followed by a parser, executing concurrently. A language grammar is scannerless if it uses a single formalism to express both the lexical and phrase level structure of the language.

Lemon is a parser generator, maintained as part of the SQLite project, that generates a look-ahead LR parser in the programming language C from an input context-free grammar. The generator is quite simple, implemented in one C source file with another file used as a template for output. Lexical analysis is performed externally.

JetPAG is an open-source LL(k) parser and lexical analyzer generator, licensed under the GNU General Public License. It is a personal work of Tareq H. Sharafy, and is currently at final beta stages of development.

In computer science, SYNTAX is a system used to generate lexical and syntactic analyzers (parsers) for all kinds of context-free grammars (CFGs) as well as some classes of contextual grammars. It has been developed at INRIA in France for several decades, mostly by Pierre Boullier, but has become free software since 2007 only. SYNTAX is distributed under the CeCILL license.

<span class="mw-page-title-main">History of compiler construction</span>

In computing, a compiler is a computer program that transforms source code written in a programming language or computer language, into another computer language. The most common reason for transforming source code is to create an executable program.

A lookahead LR parser (LALR) generator is a software tool that reads a BNF grammar and creates an LALR parser which is capable of parsing files written in the computer language defined by the BNF grammar. LALR parsers are desirable because they are very fast and small in comparison to other types of parsers.

re2c is a free and open-source lexer generator for C, C++, Go, and Rust. It compiles declarative regular expression specifications to deterministic finite automata. Originally written by Peter Bumbulis and described in his paper, re2c was put in public domain and has been since maintained by volunteers. It is the lexer generator adopted by projects such as PHP, SpamAssassin, Ninja build system and others. Together with the Lemon parser generator, re2c is used in BRL-CAD. This combination is also used with STEPcode, an implementation of ISO 10303 standard.

RE/flex is a free and open source computer program written in C++ that generates fast lexical analyzers in C++. RE/flex offers full Unicode support, indentation anchors, word boundaries, lazy quantifiers, and performance tuning options. RE/flex accepts Flex lexer specifications and offers options to generate scanners for Bison parsers. RE/flex includes a fast C++ regular expression library.

References

  1. 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.'
  2. ↑ 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.
  3. ↑ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex & yacc (2nd ed.). O'Reilly. pp. 1–2. ISBN   1-56592-000-7.
  4. ↑ Levine, John (August 2009). flex & bison. O'Reilly Media. p. 304. ISBN   978-0-596-15597-1.
  5. ↑ OpenBSD (2015-12-11). "src/usr.bin/lex/". BSD Cross Reference. Retrieved 2015-12-26. This is flex, the fast lexical analyzer generator.
  6. ↑ "flex(1)". *BSD man pages .
  7. ↑ "yacc(1)". *BSD man pages .
  8. ↑ "bison-3.0.4 – GNU parser generator". OpenBSD ports . 2015-11-15. Retrieved 2015-12-26.
  9. ↑ Is flex GNU or not? Archived 2016-03-03 at the Wayback Machine , flex FAQ
  10. ↑ "Flex - a scanner generator - Table of Contents - GNU Project - Free Software Foundation (FSF)". ftp.gnu.org. Retrieved 2019-12-05.
  11. ↑ "Flex, version 2.5 A fast scanner generator Edition 2.5, March 1995" . Retrieved 20 April 2019.
  12. ↑ "Performance - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Archived from the original on 2014-01-27. Retrieved 2013-02-25.
  13. ↑ "Reentrant - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Archived from the original on 2010-11-17. Retrieved 2013-02-25.
  14. ↑ "Code-Level And API Options - Lexical Analysis With Flex, for Flex 2.5.37". Flex.sourceforge.net. Archived from the original on 2013-03-14. Retrieved 2013-02-25.
  15. ↑ Tomassetti, Gabriele (2020-03-04). "Why you should not use (f)lex, yacc and bison". Strumenta. Retrieved 2022-10-26.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.