Flex (generador de analizador léxico)

Flex (generador rápido de analizador léxico) es una alternativa de software gratuita y de código abierto a lex. Es un programa informático que genera analizadores léxicos (también conocidos como "escáneres" o "lexers"). Se utiliza frecuentemente como implementación de lex junto con el generador de analizador Berkeley Yacc en sistemas operativos derivados de BSD (ya que tanto lex como yacc son parte de POSIX), o junto con GNU. bison (una versión de yacc) en puertos *BSD y en distribuciones de Linux. A diferencia de Bison, flex no forma parte del Proyecto GNU y no se publica bajo la Licencia Pública General GNU, aunque la Free Software Foundation produjo y publicó un manual para Flex.

Historia

Flex fue escrito en C alrededor de 1987 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 estuvo a cargo de Kevin Gong y Vern Paxson.

Ejemplo de analizador léxico

Este es un ejemplo de un escáner Flex para el lenguaje de programación instructivo PL/0.

Los tokens reconocidos son: '+', '-', '* ', '/', '=', ' (', ')', ',', ';', '.', ':=', ' <', '<=', '<>&# 39;, '>', '>='; números: 0-9 {0-9}; identificadores: a-zA-Z {a-zA-Z0-9} y palabras clave: begin, call, const, hacer, fin, si, impar, procedimiento, entonces, var, mientras.

%{}#include "y.tab.h"%}dígito [0-9]carta [a-zA-Z]%%"+" {} retorno PLUS; }"- {} retorno MINUS; }"* {} retorno TIEMPOS; }"/" {} retorno SLASH; }"( {} retorno LPAREN; }")" {} retorno RPAREN; }"; {} retorno SEMICOLON; }" {} retorno COMMA; }". {} retorno PERIOD; }":=" {} retorno BECOMES; }"=" {} retorno EQL; }"Seguido" {} retorno NEQ; }"Seguido" {} retorno LSS; }"No" {} retorno GTR; }"Seguido" {} retorno LEQ; }"No" {} retorno GEQ; }"Principio" {} retorno BEGINSYM; }"llamar" {} retorno CALLSYM; }"Contesta" {} retorno CONSTSYM; }"do" {} retorno DOSYM; }"final" {} retorno ENDSYM; }"si" {} retorno IFSYM; }"odd" {} retorno ODDSYM; }"procedimiento" {} retorno PROCSYM; }"entonces" {} retorno THENSYM; }"var" {} retorno VARSYM; }"mientras" {} retorno WHILESYM; }{}carta♪♪carta}Silencio{}dígito})* {} yylval.id = strdup()Yytext); retorno IDENT; }{}dígito}+ {} yylval.num = atoi()Yytext); retorno NUMBER; }[ tnr] /* skip whitespace */. {} printf()"Unknown character [%c]n",Yytext[0]); retorno UNKNOWN; }%%int Yywrap()vacío){retorno 1;

Internos

Estos programas realizan análisis y tokenización de caracteres 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 máquinas de Turing de movimiento derecho de solo lectura. La sintaxis se basa en el uso de expresiones regulares. Véase también autómata finito no determinista.

Problemas

Complejidad del tiempo

Un analizador lexical flexible generalmente tiene complejidad de tiempo O()n){displaystyle O(n)} 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 del partido DFA. 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 e intente nuevamente" después de que ya haya coincidido con alguna entrada. Esto hará que el DFA retroceda para encontrar otros estados aceptados. La función REJECT no está habilitada de forma predeterminada y, debido a sus implicaciones en el rendimiento, no se recomienda su uso en el manual de Flex.

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.

Uso en entornos que no son Unix

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 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 utiliza isatty.

Usando 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 enlace de idiomas como SWIG.

Soporte Unicode

Flex se limita a hacer coincidir valores binarios de 1 byte (8 bits) y, por lo tanto, no admite Unicode. RE/flex y otras alternativas admiten la coincidencia Unicode.

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 de C++ generado por flex++ incluye el archivo de encabezado FlexLexer.h, que define las interfaces de las dos clases generadas por C++.