re2c es un generador de lexer gratuito y de código abierto para C , C ++ y Go . Compila especificaciones declarativas de expresiones regulares a autómatas finitos deterministas . Originalmente escrito por Peter Bumbulis y descrito en su artículo, [1] re2c fue puesto en el dominio público y desde entonces ha sido mantenido por voluntarios. [2] Es el generador de lexer adoptado por proyectos como PHP , [3] SpamAssassin , [4] Ninja build system [5] y otros. Junto con el Limón generador de analizador sintáctico, re2c se utiliza en BRL-CAD . [6] Esta combinación también se utiliza con STEPcode, una implementación del estándar ISO 10303 . [7]
Autor (es) original (es) | Peter Bumbulis |
---|---|
Versión inicial | alrededor de 1994 [1] |
Lanzamiento estable | 2.1.1 / 27 de marzo de 2021 |
Repositorio | github |
Tipo | Generador de analizador léxico |
Licencia | Dominio publico |
Sitio web | re2c |
Filosofía
El objetivo principal de re2c es generar lexers rápidos : [1] al menos tan rápido como los lexers C razonablemente optimizados codificados a mano. En lugar de utilizar el enfoque tradicional basado en tablas, re2c codifica la máquina de estados finitos generada directamente en forma de saltos condicionales y comparaciones. 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 da como resultado lexers más pequeños, [1] ya que re2c aplica una serie de optimizaciones como la minimización de DFA y la construcción de un túnel automático. [8] 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 lexer generado a cualquier entorno particular. La idea principal es que re2c debería ser una abstracción de coste cero para el programador: su uso nunca debería resultar en un programa más lento que la implementación codificada a mano correspondiente.
Características
- Extracción de subcoincidencia : [9] re2c admite tanto grupos de captura compatibles con POSIX como etiquetas independientes [10] (con desambiguación codiciosa más a la izquierda y manejo opcional de subcoincidencia repetida). La implementación se basa en el algoritmo lookahead-TDFA. [11] [12] [13]
- Soporte de codificación: [14] re2c admite ASCII, UTF-8, UTF-16, UTF-32, UCS-2 y EBCDIC.
- Interfaz de usuario flexible: [15] 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 para lo que necesiten.
- Estado almacenable : [16] re2c soporta tanto lexers de modelo de extracción (cuando lexer se ejecuta sin interrupciones y extrae más entrada según sea necesario) y lexers de modelo push (cuando lexer se detiene periódicamente y se reanuda para analizar nuevos fragmentos de entrada).
- Condiciones de inicio: [17] re2c puede generar múltiples léxers interrelacionados, donde cada léxico es activado por una determinada condición en el programa.
- Autovalidación : [18] re2c tiene un modo especial en el que ignora todo el código de interfaz definido por el usuario y genera un programa esqueleto autónomo . 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 lexer en todas las entradas. Las cadenas de entrada se generan para que cubran ampliamente las transiciones y rutas de DFA. La generación de datos ocurre inmediatamente después de la construcción de DFA y antes de cualquier optimización, pero el lexer en sí está completamente optimizado, por lo que los programas de esqueleto son capaces de revelar cualquier error en las optimizaciones y la generación de código.
- Advertencias: [19] 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 lexers legibles por humanos, re2c tiene una serie de opciones que descargan varias representaciones intermedias del lexer generado, como NFA , múltiples etapas de DFA y el gráfico de programa resultante en formato DOT . [20]
Sintaxis
El programa re2c puede contener cualquier número de /*!re2c ... */
bloques. Cada bloque consta de una secuencia de reglas , definiciones y configuraciones (se pueden mezclar, pero generalmente es mejor poner las configuraciones primero, luego las definiciones y luego las reglas). Las reglas tienen la forma REGEXP { CODE }
o REGEXP := CODE;
donde REGEXP
es una expresión regular y CODE
es un bloque de código C. Cuando REGEXP
coincide con la cadena de entrada, el flujo de control se transfiere al asociado CODE
. Hay una regla especial: la regla predeterminada con en *
lugar de REGEXP
; se activa si no coincide ninguna otra regla. re2c tiene una semántica de coincidencia codiciosa : si coinciden varias reglas, se prefiere la regla que coincida 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 NAME = REGEXP;
(y también NAME { REGEXP }
en el modo de compatibilidad Flex ). Las configuraciones tienen la forma re2c:CONFIG = VALUE;
donde CONFIG
es el nombre de la configuración particular y VALUE
es un número o una cadena. Para un uso más avanzado, consulte el manual oficial de re2c. [21]
Expresiones regulares
re2c usa 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 carácter (posiblemente negado).
cualquier carácter excepto nueva líneaR \ S
diferencia de clases de caracteresR*
cero o más ocurrencias deR
R+
una o más ocurrencias deR
R?
OpcionalR
R{n}
repetición de tiemposR
exactosn
R{n,}
repetición deR
al menosn
vecesR{n,m}
repetición deR
desden
am
veces(R)
soloR
; los paréntesis se utilizan para anular la precedencia o para la subcoincidencia de estilo POSIXR S
concatenación:R
seguido deS
R | S
alternativa:R
oS
R / S
lookahead:R
seguido deS
, peroS
no se consumename
la expresión regular definida comoname
(excepto en el modo de compatibilidad Flex )@stag
una etiqueta S : guarda la última posición de entrada en la que@stag
coincide con una variable denominadastag
#mtag
una etiqueta m : guarda todas las posiciones de entrada en las que#mtag
coincide con una variable denominadamtag
Las clases de caracteres y literales de cadena pueden contener las siguientes secuencias de escape: \a
, \b
, \f
, \n
, \r
, \t
, \v
, \\
, octal escapes \ooo
y fugas hexadecimal \xhh
, \uhhhh
y \Uhhhhhhhh
.
Ejemplo
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á incluido en los comentarios /*!re2c ... */
, todo el resto es código C simple . Consulte el sitio web oficial de re2c para ver ejemplos más complejos. [22]
#include static int lex ( const char * YYCURSOR ) { const char * YYMARKER ; / *! re2c re2c: define: YYCTYPE = char; re2c: yyfill: enable = 0; end = "\ x00"; hex = "0x" [0-9a-fA-F] +; * {printf ("err \ n"); return 1; } extremo hexadecimal {printf ("hexadecimal \ n"); return 0; } * / }int main ( int argc , char ** argv ) { for ( int i = 1 ; i < argc ; ++ i ) { lex ( argv [ i ]); } return 0 ; }
Dado eso, re2c -is -o example.c example.re
genera el siguiente código (ejemplo.c). El contenido del comentario /*!re2c ... */
se sustituye por un autómata finito determinista codificado en forma de saltos condicionales y comparaciones; el resto del programa se copia literalmente en el archivo de salida. Hay varias opciones de generación de código; normalmente re2c usa switch
declaraciones, pero puede usar if
declaraciones anidadas (como en este ejemplo con -s
opción), o generar mapas de bits y tablas de salto. La mejor opción depende del compilador de C; Se anima a los usuarios de re2c a experimentar.
/ * Generado por re2c 1.2.1 el viernes 23 de agosto 21:59:00 2019 * / #include 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 ; }
Ver también
- Comparación de generadores de analizadores sintácticos
Referencias
- ^ a b c d e Bumbulis, Peter; Donald D., Cowan (marzo-diciembre de 1993). "RE2C: un generador de escáner más versátil" . Cartas ACM sobre lenguajes y sistemas de programación . 2 (1–4): 70–84. doi : 10.1145 / 176454.176487 . S2CID 14814637 .
- ^ "Autores, documentación re2c" .
- ^ "Construyendo PHP" . Libro de aspectos internos de PHP . Consultado el 20 de julio de 2020 .
- ^ "SpamAssassin (compilación sa)" .
- ^ "Ninja: build.ninja" . Ninja . Consultado el 20 de julio de 2020 .
- ^ "BRL-CAD (herramientas: re2c)" .
- ^ http://stepcode.github.io/docs/build_process/
- ^ Joseph, Grosch (1989). "Generación eficiente de escáneres controlados por tablas". Práctica y experiencia de software 19 : 1089–1103.
- ^ "Extracción de subcoincidencias, documentación re2c" .
- ^ Ville, Laurikari (2000). "NFA con transiciones etiquetadas, su conversión a autómatas deterministas y aplicación a expresiones regulares" (PDF) . Séptimo Simposio Internacional sobre Procesamiento de Cadenas y Recuperación de Información, 2000. SPIRE 2000. Actas .
- ^ Ulya, Trofimovich (2017). "Autómatas finitos deterministas etiquetados con Lookahead". arXiv : 1907.08837 [ cs.FL ].
- ^ Ulya, Trofimovich (2020). "RE2C - un generador de lexer basado en TDFA anticipado" . Impactos del software . 6 : 100027. doi : 10.1016 / j.simpa.2020.100027 .
- ^ Ulya, Trofimovich (2021). "Lookahead TDFA en imágenes (diapositivas)" (PDF) .
- ^ "Codificaciones, documentación re2c" .
- ^ "Interfaz de programa, documentación re2c" .
- ^ "Estado almacenable, documentación re2c" .
- ^ "Condiciones de inicio, documentación re2c" .
- ^ "Esqueleto, documentación re2c" .
- ^ "Advertencias, documentación re2c" .
- ^ "Visualización, documentación re2c" .
- ^ "Manual de usuario (C), documentación re2c" .
- ^ "Webcite oficial" .
enlaces externos
- Página web oficial