Flex ( generador de analizador léxico rápido ) es una alternativa de software libre y de código abierto a lex . [2]
Es un programa informático que genera analizadores léxicos (también conocidos como "escáneres" o "lexers"). [3] [4]
Se utiliza con frecuencia como la implementación de lex junto con el generador de analizador sintáctico Berkeley Yacc en sistemas operativos derivados de BSD (ya que tanto y son parte de POSIX ), [5] [6] [7] o junto con GNU bison (una versión de yacc ) en puertos *BSD [8] y en distribuciones Linux. A diferencia de Bison, flex no es parte del Proyecto GNU y no se publica bajo la Licencia Pública General de GNU , [9] aunque la Free Software Foundation produjo y publicó un manual para Flex. [10]lex
yacc
Flex fue escrito en C alrededor de 1987 [1] por Vern Paxson , con la ayuda de muchas ideas y mucha inspiración de Van Jacobson . Versión original de Jef Poskanzer . La representación rápida de la tabla es una implementación parcial de un diseño realizado por Van Jacobson. La implementación fue realizada por Kevin Gong y Vern Paxson. [11]
Este es un ejemplo de un escáner Flex para el lenguaje de programación instruccional PL/0 .
Los tokens reconocidos son: ' +
', ' -
', ' *
' /
, ' ' =
, ' (
', ' ', )
' ,
', ' ;
', ' .
', ' :=
', ' <
', ' <=
', ' ' <>
, ' ' >
, ' ' >=
; números: 0-9 {0-9}
; identificadores: a-zA-Z {a-zA-Z0-9}
y palabras clave: begin
, call
, const
, do
, end
, if
, , , , .odd
procedure
then
var
while
% { #include "y.tab.h" % } dígito [ 0-9 ] letra [ a - zA - Z ] %% "+" { devolver MÁS ; } "-" { devolver MENOS ; } "*" { devolver VECES ; } "/" { devolver BARRA LARGA ; } "(" { devolver LPAREN ; } ")" { devolver RPAREN ; } ";" { devolver PUNTO Y COMA ; } "," { devolver COMA ; } "." { devolver PUNTO ; } ":=" { devolver CONVIERTE EN ; } "=" { devolver EQL ; } "<>" { devolver NEQ ; } "<" { devolver LSS ; } ">" { devolver GTR ; } "<=" { devolver LEQ ; } ">=" { devolver GEQ ; } "comienzo" { devolver BEGINSYM ; } "llamada" { devolver CALLSYM ; } "const" { devolver CONSTSYM ; } "hacer" { devolver DOSYM ; } "fin" { devolver ENDSYM ; } "si" { devolver IFSYM ; } "impar" { devolver ODDSYM ; } "procedimiento" { devolver PROCSYM ; } "entonces" { devolver THENSYM ; } "var" { devolver VARSYM ; } "mientras" { devolver WHILESYM ; } { letra }({ letra } | { dígito }) * { yylval . id = strdup ( yytext ); devolver IDENT ; } { dígito } + { yylval . num = atoi ( yytext ); return NÚMERO ; } [ \ t \ n \ r ] /* omitir espacios en blanco */ . { printf ( "Carácter desconocido [%c] \n " , yytext [ 0 ]); return DESCONOCIDO ; } %% int yywrap ( void ){ devolver 1 ;}
Estos programas realizan el análisis de caracteres y la tokenización mediante el uso de un autómata finito determinista (DFA). Un DFA es una máquina teórica que acepta lenguajes regulares . Estas máquinas son un subconjunto de la colección de máquinas de Turing . Los DFA son equivalentes a las máquinas de Turing de solo lectura con movimiento a la derecha . La sintaxis se basa en el uso de expresiones regulares . Véase también autómata finito no determinista .
Un analizador léxico Flex suele tener una complejidad temporal en la longitud de la entrada. Es decir, realiza un número constante de operaciones para cada símbolo de entrada. Esta constante es bastante baja: GCC genera 12 instrucciones para el bucle de coincidencia de DFA. [ cita requerida ] Tenga en cuenta que la constante es independiente de la longitud del token, la longitud de la expresión regular y el tamaño del DFA.
Sin embargo, el uso de la macro REJECT en un escáner con el potencial de hacer coincidir tokens extremadamente largos puede hacer que Flex genere un escáner con un rendimiento no lineal. Esta característica es opcional. En este caso, el programador le ha dicho explícitamente a Flex que "regrese y vuelva a intentarlo" después de que ya haya hecho coincidir alguna entrada. Esto hará que el DFA retroceda para encontrar otros estados de aceptación. La característica REJECT no está habilitada de forma predeterminada y, debido a sus implicaciones de rendimiento, su uso no se recomienda en el manual de Flex. [12]
De forma predeterminada, el escáner generado por Flex no es reentrante . Esto puede causar serios problemas para los programas que utilizan el escáner generado desde diferentes subprocesos. Para superar este problema, Flex ofrece opciones para lograr la reentrada. Se puede encontrar una descripción detallada de estas opciones en el manual de Flex. [13]
Normalmente, el escáner generado contiene referencias al archivo de encabezado unistd.h , que es específico de Unix . Para evitar generar código que incluya unistd.h , se debe utilizar %option nounistd . Otro problema es la llamada a isatty (una función de la biblioteca de Unix), que se puede encontrar en el código generado. La %option never-interactive obliga a flex a generar código que no utiliza isatty . [14]
Flex solo puede generar código para C y C++ . Para utilizar el código generado por Flex a partir de otros lenguajes, se puede utilizar una herramienta de vinculación de lenguajes como SWIG .
Flex está limitado a la coincidencia de valores binarios de 1 byte (8 bits) y, por lo tanto, no admite Unicode . [15] RE/flex y otras alternativas sí admiten la coincidencia Unicode.
flex++ es un escáner léxico similar para C++ que se incluye como parte del paquete flex. El código generado no depende de ningún entorno de ejecución ni de ninguna biblioteca externa , excepto de un asignador de memoria ( malloc o una alternativa proporcionada por el usuario), a menos que la entrada también dependa de él. Esto puede resultar útil en aplicaciones integradas y situaciones similares en las que los sistemas operativos tradicionales o las funciones de entorno de ejecución de C pueden no estar disponibles.
El escáner C++ generado por flex++ incluye el archivo de encabezado FlexLexer.h
, que define las interfaces de las dos clases generadas por C++.
1987, Vern Paxson del Laboratorio Lawrence Berkeley tomó una versión de lex escrita en ratfor (un Fortran extendido popular en ese momento) y la tradujo a C, llamándola flex, para ' F ast Lexical Analyzer Generator ' .
versión disponible gratuitamente de lex es flex .
Este es flex, el generador rápido de analizadores léxicos.