re2c

re2c es un generador de analizadores léxicos gratuito y de código abierto para C , C++ , D , Go , Haskell , Java , JavaScript , OCaml , Python , Rust , V y Zig . Compila especificaciones declarativas de expresiones regulares en autómatas finitos deterministas . Escrito originalmente por Peter Bumbulis y descrito en su artículo, ^{[ 1 ]} re2c se puso en dominio público y desde entonces ha sido mantenido por voluntarios. ^{[ 3 ]} Es el generador de analizadores léxicos adoptado por proyectos como PHP , ^{[ 4 ]} SpamAssassin , ^{[ 5 ]} el sistema de compilación Ninja ^{[ 6 ]} y otros. Junto con el generador de analizadores Lemon , re2c se utiliza en BRL-CAD . ^{[ 7 ]} Esta combinación también se utiliza con STEPcode, una implementación del estándar ISO 10303. ^{[ 8 ]}

El objetivo principal de re2c es generar analizadores léxicos rápidos : ^{[ 1 ]} al menos tan rápidos como los analizadores léxicos de C razonablemente optimizados codificados manualmente. En lugar de utilizar el enfoque tradicional basado en tablas, re2c codifica la máquina de estados finitos generada directamente en forma de saltos y comparaciones condicionales. El programa resultante es más rápido que su contraparte basada en tablas ^{[ 1 ]} y mucho más fácil de depurar y comprender. Además, este enfoque a menudo resulta en analizadores léxicos más pequeños, ^{[ 1 ]} ya que re2c aplica una serie de optimizaciones como la minimización de DFA y la construcción de autómatas de túnel. ^{[ 9 ]} Otra característica distintiva de re2c es su interfaz flexible: en lugar de asumir una plantilla de programa fija, re2c permite al programador escribir la mayor parte del código de la interfaz y adaptar el analizador léxico generado a cualquier entorno particular. La idea principal es que re2c debe ser una abstracción de costo cero para el programador: su uso nunca debería resultar en un programa más lento que la implementación correspondiente codificada manualmente.

• Extracción de subcoincidencias: ^{[ 10 ]} re2c admite grupos de captura compatibles con POSIX y etiquetas independientes ^{[ 11 ]} (con desambiguación voraz por la izquierda y manejo opcional de subcoincidencias repetidas). La implementación se basa en el algoritmo lookahead-TDFA. ^{[ 12 ] [ 13 ] [ 14 ]}

• Soporte de codificación: ^{[ 15 ]} re2c admite ASCII , UTF-8 , UTF-16 , UTF-32 , UCS-2 y EBCDIC .
• Interfaz de usuario flexible: ^{[ 16 ]} el código generado utiliza algunas operaciones primitivas para interactuar con el entorno (leer caracteres de entrada, avanzar a la siguiente posición de entrada, etc.); los usuarios pueden redefinir estas primitivas según sus necesidades.
• Estado almacenable: ^{[ 17 ]} re2c admite tanto analizadores léxicos de modelo pull (cuando el analizador léxico se ejecuta sin interrupciones y extrae más entrada según sea necesario) como analizadores léxicos de modelo push (cuando el analizador léxico se detiene y se reanuda periódicamente para analizar nuevos fragmentos de entrada).
• Condiciones de inicio: ^{[ 18 ]} re2c puede generar múltiples analizadores léxicos interrelacionados, donde cada analizador léxico se activa mediante una determinada condición en el programa.
• Autovalidación: ^{[ 19 ]} re2c tiene un modo especial en el que ignora todo el código de interfaz definido por el usuario y genera un programa esqueleto autocontenido . Además, re2c genera dos archivos: uno con las cadenas de entrada derivadas de la gramática regular y otro con resultados de coincidencia comprimidos que se utilizan para verificar el comportamiento del analizador léxico en todas las entradas. Las cadenas de entrada se generan de manera que cubran ampliamente las transiciones y rutas del autómata finito determinista (AFD). La generación de datos ocurre justo después de la construcción del AFD y antes de cualquier optimización, pero el analizador léxico en sí está completamente optimizado, por lo que los programas esqueleto son capaces de revelar cualquier error en las optimizaciones y la generación de código.
• Advertencias: ^{[ 20 ]} re2c realiza un análisis estático del programa y advierte a sus usuarios sobre posibles deficiencias o errores, como flujo de control indefinido, código inalcanzable, símbolos de escape mal formados y posible mal uso de las primitivas de la interfaz.
• Depuración. Además de generar analizadores léxicos legibles por humanos, re2c tiene varias opciones que generan diversas representaciones intermedias del analizador léxico generado, como NFA , múltiples etapas de DFA y el grafo del programa resultante en formato DOT . ^{[ 21 ]}

El programa re2c puede contener cualquier número de /*!re2c ... */bloques. Cada bloque consta de una secuencia de reglas , definiciones y configuraciones (pueden mezclarse, pero generalmente es mejor colocar primero las configuraciones, luego las definiciones y finalmente las reglas). Las reglas tienen la forma REGEXP { CODE }o donde es una expresión regular y es un bloque de código C. Cuando coincide con la cadena de entrada, el flujo de control se transfiere al asociado . Hay una regla especial: la regla predeterminada con en lugar de ; se activa si ninguna otra regla coincide. re2c tiene una semántica de coincidencia codiciosa : si varias reglas coinciden, se prefiere la regla que coincide con el prefijo más largo; si las reglas en conflicto coinciden con el mismo prefijo, la regla anterior tiene prioridad. Las definiciones tienen la forma (y también en modo de compatibilidad Flex ). Las configuraciones tienen la forma donde es el nombre de la configuración particular y es un número o una cadena. Para un uso más avanzado, consulte el manual oficial de re2c. ^{[ 22 ]}REGEXP := CODE;REGEXPCODEREGEXPCODE*REGEXPNAME = REGEXP;NAME { REGEXP }re2c:CONFIG = VALUE;CONFIGVALUE

re2c utiliza la siguiente sintaxis para expresiones regulares:

• "foo"literal de cadena sensible a mayúsculas y minúsculas
• 'foo'literal de cadena que no distingue entre mayúsculas y minúsculas
• [a-xyz], [^a-xyz]clase de personaje (posiblemente negada)
• .cualquier carácter excepto salto de línea
• R \ Sdiferencia de clases de personajes
• R*cero o más ocurrencias deR
• R+una o más ocurrencias deR
• R?cero o una ocurrencia deR
• R{n}repetición Rexactamente nveces
• R{n,}repetición de Ral menos nveces
• R{n,m}repetición de Rde na mveces
• (R)Los paréntesis Rse utilizan para anular la precedencia o para la coincidencia de subconjuntos al estilo POSIX.
• R Sconcatenación: Rseguida deS
• R | Salternativa: RoS
• R / Santicipación: Rseguido de S, pero Sno se consume
• namela expresión regular definida como name(excepto en el modo de compatibilidad Flex )
• @staguna etiqueta s : guarda la última posición de entrada en la que @stagcoincide en una variable llamadastag
• #mtaguna m-tag : guarda todas las posiciones de entrada en las que #mtagcoinciden en una variable llamadamtag

Las clases de caracteres y los literales de cadena pueden contener las siguientes secuencias de escape: \a, \b, \f, \n, \r, \t, \v, \\, escapes octales \oooy escapes hexadecimales \xhh, \uhhhhy \Uhhhhhhhh.

Aquí hay un programa muy simple en re2c ( example.re ). Comprueba que todos los argumentos de entrada sean números hexadecimales. El código para re2c está entre comentarios /*!re2c ... */; el resto es código C puro . Consulte el sitio web oficial de re2c para ver ejemplos más complejos. ^{[ 23 ]}

#include <stdio.h>static int lex ( const char YYCURSOR []) { const char * YYMARKER ; /*!re2c  re2c:define:YYCTYPE = char;  re2c:yyfill:enable = 0; fin = "\x00";  hexadecimal = "0x" [0-9a-fA-F]+; * { printf("err\n"); return 1; }  hex end { printf("hex\n"); return 0; }  */ }int main ( int argc , char * argv []) { for ( int i = 1 ; i < argc ; ++ i ) { lex ( argv [ i ]); } return 0 ; }

Dado esto, re2c -is -o example.c example.rese genera el código siguiente (example.c). El contenido del comentario /*!re2c ... */se sustituye por un autómata finito determinista codificado en forma de saltos y comparaciones condicionales; el resto del programa se copia textualmente en el archivo de salida. Existen varias opciones de generación de código; normalmente, re2c utiliza switchsentencias condicionales, pero puede usar ifsentencias anidadas (como en este ejemplo con -sla opción ), o generar mapas de bits y tablas de saltos. La mejor opción depende del compilador de C; se recomienda a los usuarios de re2c que experimenten.

/* Generado por re2c 1.2.1 el viernes 23 de agosto de 2019 a las 21:59:00 */ #include <stdio.h>static int lex ( const char * YYCURSOR ) { const char * YYMARKER ; { char yych ; yych = * YYCURSOR ; if ( yych == '0' ) goto yy4 ; ++ YYCURSOR ; yy3 : { printf ( "err \n " ); return 1 ; } yy4 : yych = * ( YYMARKER = ++ YYCURSOR ); if ( yych != 'x' ) goto yy3 ; yych = *++ YYCURSOR ; if ( yych >= 0x01 ) goto yy8 ; yy6 : YYCURSOR = YYMARKER ; goto yy3 ; yy7 : yych = *++ YYCURSOR ; yy8 : if ( yych <= '@' ) { if ( yych <= 0x00 ) goto yy9 ; if ( yych <= '/' ) goto yy6 ; if ( yych <= '9' ) goto yy7 ; goto yy6 ; } else { if ( yych <= 'F' ) goto yy7 ; if ( yych <= ' `' ) goto yy6 ; if ( yych <= 'f' ) goto yy7 ; goto yy6 ; } yy9 : ++ YYCURSOR ; { printf ( "hex \n " ); return 0 ; } }}int main ( int argc , char ** argv ) { for ( int i = 1 ; i < argc ; ++ i ) { lex ( argv [ i ]); } return 0 ; }

• Ragel
• Lex
• Comparación de generadores de analizadores sintácticos

• Sitio web oficial