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 "scanners" o "lexers"). [3] [4] Se utiliza con frecuencia como implementación lex junto con el generador de analizador sintáctico Berkeley Yacc en sistemas operativos derivados de BSD (ya que ambos lex
y yacc
son parte de POSIX ), [5] [6] [7] o junto con GNU bison (una versión de yacc) en puertos * BSD [8] y en distribuciones de Linux. A diferencia de Bison, flex no es parte del Proyecto GNU y no se publica bajo la Licencia Pública General GNU , [9] aunque la Free Software Foundation produjo y publicó un manual para Flex. [10]
Desarrollador (es) | Vern Paxson |
---|---|
Versión inicial | alrededor de 1987 [1] |
Lanzamiento estable | 2.6.4 / 6 de mayo de 2017 |
Repositorio | |
Sistema operativo | Tipo Unix |
Tipo | Generador de analizador léxico |
Licencia | Licencia BSD |
Sitio web | github |
Historia
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 de tabla rápida 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]
Analizador léxico de ejemplo
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 ]%% "+" { return MÁS ; } "-" { return MENOS ; } "*" { return TIEMPOS ; } "/" { return SLASH ; } "(" { return LPAREN ; } ")" { return RPAREN ; } ";" { return SEMICOLON ; } "," { return COMMA ; } "." { Volver PERIODO ; } ": =" { return SE CONVIERTE ; } "=" { return EQL ; } "<>" { return NEQ ; } "<" { return LSS ; } ">" { return GTR ; } "<=" { return LEQ ; } "> =" { return GEQ ; } "comenzar" { return BEGINSYM ; } "llamar" { return CALLSYM ; } "const" { return CONSTSYM ; } "hacer" { return DOSYM ; } "fin" { return ENDSYM ; } "si" { return IFSYM ; } "impar" { return ODDSYM ; } "procedimiento" { return PROCSYM ; } "luego" { return THENSYM ; } "var" { return VARSYM ; } "mientras" { return WHILESYM ; } { letra } ({ letra } | { dígito }) * { yylval . id = strdup ( yytext ); return IDENT ; } { dígito } + { yylval . num = atoi ( yytext ); return NUMBER ; } [ \ t \ n \ r ] / * omitir espacios en blanco * / . { printf ( "Carácter desconocido [% c] \ n " , yytext [ 0 ]); volver DESCONOCIDO ; } %%int yywrap ( void ) { return 1 ;}
Internos
Estos programas realizan análisis de caracteres y tokenización mediante el uso de un autómata finito determinista (DFA). Un DFA es una máquina teórica que acepta idiomas 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 en movimiento a la derecha de solo lectura . La sintaxis se basa en el uso de expresiones regulares . Véase también autómata finito no determinista .
Asuntos
Complejidad del tiempo
Un analizador léxico Flex generalmente tiene complejidad de tiempo 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 ciclo 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 coincidido con alguna entrada. Esto hará que DFA retroceda para buscar otros estados de aceptación. La función RECHAZAR no está habilitada de forma predeterminada y, debido a sus implicaciones en el rendimiento, se desaconseja su uso en el manual de Flex. [12]
Reentrada
De forma predeterminada, el escáner generado por Flex no es reentrante . Esto puede causar serios problemas a los programas que utilizan el escáner generado desde diferentes subprocesos. Para superar este problema, Flex ofrece opciones para lograr la reentrada. Puede encontrar una descripción detallada de estas opciones en el manual de Flex. [13]
Uso en entornos que no son Unix
Normalmente, el analizador 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 usar % 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 opción% nunca interactiva obliga a flex a generar código que no usa isatty . [14]
Usar flex de otros idiomas
Flex solo puede generar código para C y C ++ . Para utilizar el código del escáner generado por flex desde otros idiomas , se puede utilizar una herramienta de vinculación de idiomas como SWIG .
Flex ++
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 tiempo de ejecución o 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 situaciones integradas y similares en las que el sistema operativo tradicional o las funciones de tiempo 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 en C ++.
Ver también
- Comparación de generadores de analizadores sintácticos
- Lex
- yacc
- GNU Bison
- Berkeley Yacc
Referencias
- ↑ a b Levine, John (agosto de 2009). flex & bison . O'Reilly Media. pag. 9. ISBN 978-0-596-15597-1.
En alrededor de 1987, Vern Paxson del Laboratorio Lawrence Berkeley tomó una versión de la lex escrito en Ratfor (una extendida Fortran popular en ese momento) y lo tradujo al C, que calificó de flexión, por ' F ast Lex ical Analizador generador. '
- ^ Levine, John R .; Mason, Tony; Brown, Doug (1992). lex y yacc (2ª ed.). O'Reilly . pag. 279. ISBN 1-56592-000-7.
Una versión de lex disponible gratuitamente es flex .
- ^ Levine, John R .; Mason, Tony; Brown, Doug (1992). lex y yacc (2ª ed.). O'Reilly . págs. 1-2. ISBN 1-56592-000-7.
- ^ Levine, John (agosto de 2009). flex & bison . O'Reilly Media. pag. 304. ISBN 978-0-596-15597-1.
- ^ OpenBSD (11 de diciembre de 2015). "src / usr.bin / lex /" . Referencia cruzada BSD . Consultado el 26 de diciembre de 2015 .
Esto es flex, el generador de analizador léxico rápido.
- ^ " flex(1)" . * Páginas de manual de BSD .
- ^ " yacc(1)" . * Páginas de manual de BSD .
- ^ "bison-3.0.4 - Generador de analizador de GNU" . Puertos OpenBSD . 2015-11-15 . Consultado el 26 de diciembre de 2015 .
- ^ ¿Flex GNU es o no? Archivado el 3 de marzo de 2016 en Wayback Machine , preguntas frecuentes sobre flex
- ^ "Flex - un generador de escáner - Tabla de contenido - Proyecto GNU - Free Software Foundation (FSF)" . ftp.gnu.org . Consultado el 5 de diciembre de 2019 .
- ^ "Flex, versión 2.5 Un generador de escáner rápido Edición 2.5, marzo de 1995" . Consultado el 20 de abril de 2019 .
- ^ "Rendimiento: análisis léxico con Flex, para Flex 2.5.37" . Flex.sourceforge.net. Archivado desde el original el 27 de enero de 2014 . Consultado el 25 de febrero de 2013 .
- ^ "Reentrante - Análisis léxico con Flex, para Flex 2.5.37" . Flex.sourceforge.net. Archivado desde el original el 17 de noviembre de 2010 . Consultado el 25 de febrero de 2013 .
- ^ "Opciones de API y de nivel de código: análisis léxico con Flex, para Flex 2.5.37" . Flex.sourceforge.net. Archivado desde el original el 14 de marzo de 2013 . Consultado el 25 de febrero de 2013 .
Otras lecturas
- Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.
- ME Lesk y E. Schmidt, LEX - Generador de analizador léxico
- Alfred Aho, Ravi Sethi y Jeffrey Ullman, Compiladores: Principios, técnicas y herramientas , Addison-Wesley (1986). Describe las técnicas de coincidencia de patrones utilizadas por flex (autómatas finitos deterministas)
enlaces externos
- Página web oficial
- Especificación ANSI-C Lex
- JFlex: Generador de escáner rápido para Java
- Breve descripción de Lex, Flex, YACC y Bison