| Re2c | |
|---|---|
| Tipo de | software libre y de código abierto y generador de analizador léxico [d] |
| Escrito en | C y C++ |
| Sistema operativo | multiplataforma |
| Primera edición | 1994 [1] |
| ultima versión |
|
| Estado | activo |
| Sitio web | re2c.org _ |
| Archivos multimedia en Wikimedia Commons | |
re2c ( r egular e xpression to c , r egular e xpression to c ode ) es una utilidad generadora gratuita de código abierto que genera lexers rápidos y fácilmente integrables , orientada a trabajar con lenguajes: C , C++ , Go , Rust .
La utilidad fue creada originalmente por Peter Bumbulis y descrita en su artículo [3] , luego re2c se lanzó al dominio público y desde entonces ha sido mantenida por voluntarios [4] .
La utilidad se diferencia de sus análogos más conocidos (como lex y flex ) en que tiene una interfaz de interacción flexible (el código generado interactúa con un programa externo usando primitivas), genera lexers optimizados que no son de tabla, admite capturas (extracción de subcoincidencia ) basado en autómatas finitos deterministas con etiquetas (TDFA).
La utilidad se usa principalmente en proyectos donde se requiere un análisis sintáctico de alta velocidad , como Ninja [5] y PHP [6] .
El objetivo principal de re2c es generar lexers rápidos [3] que sean al menos tan rápidos como los lexers escritos a mano razonablemente optimizados . En lugar de utilizar el enfoque de hoja de cálculo tradicional, re2c codifica la máquina de estado generada directamente en forma de condicionales y comparaciones. Como resultado, el programa es más rápido que su contraparte basada en tablas [3] y mucho más fácil de depurar y comprender. Además, este enfoque a menudo conduce a lexers más pequeños [3] porque re2c aplica una serie de optimizaciones, como la minimización de DFA y la construcción de autómatas de túneles [7] . Otra gran característica de re2c es su interfaz flexible. En lugar de utilizar 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 en particular. La idea principal es que re2c debe ser una abstracción de costo cero para el programador, el uso de la utilidad nunca debe hacer que el programa se ejecute más lento que la implementación codificada a mano correspondiente.
La implementación se basa en el algoritmo "lookahead-TDFA" [10] [11] [12] ;
El programa re2c puede contener cualquier número /*!re2c ... */de bloques. Cada bloque consta de una secuencia de reglas, definiciones y configuraciones (se pueden mezclar, pero generalmente es mejor colocar primero las configuraciones, luego las definiciones y luego las reglas). Las reglas son de la forma - REGEXP { CODE }o REGEXP := CODE;, donde REGEXPes una expresión regular y CODE- es un bloque de código C. Cuando REGEXPcoincide con la cadena de entrada, el flujo de control se transfiere al bloque correspondiente CODE. Hay una regla especial: la regla predeterminada con *en lugar de REGEXP, se activa si ninguna otra regla coincide. re2c tiene una semántica de coincidencia codiciosa : si coinciden varias reglas, se prefiere la regla que coincide con el prefijo más largo, si las reglas en conflicto coinciden con el mismo prefijo, entonces la regla anterior tiene prioridad. Las definiciones tienen la forma NAME = REGEXP;(y en consecuencia NAME { REGEXP }en el modo compatible con Flex). Las configuraciones tienen el formato re2c:CONFIG = VALUE;, donde CONFIGes el nombre de una configuración específica y VALUEes un número o una cadena. Para un uso más avanzado, consulte el manual oficial de re2c [20] .
re2c usa la siguiente sintaxis para expresiones regulares:
Las clases de caracteres y los literales de cadena pueden contener las siguientes secuencias de escape: \a, \b, \f, \n, \r, \t, \v, \\, octal \oooy hexadecimal \xhh, \uhhhh, \Uhhhhhhhh.
El siguiente es un ejemplo de un programa re2c simple en el archivo example.re . Comprueba que todos los argumentos de entrada sean números decimales. El código para re2c está enmarcado en los comentarios /*!re2c ... */[21] .
c :
// re2c $ENTRADA -o $SALIDA -i --case-ranges #incluir <afirmar.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; /*!re2c re2c:yyfill:habilitar = 0; re2c:define:YYCTYPE = char; número = [1-9][0-9]*; número { devuelve verdadero; } * { falso retorno; } */ } int principal () { afirmar ( lex ( "1234" )); devolver 0 ; }Dado que el comando $ re2c -is -o example.c example.regenera el siguiente código ( ejemplo.c ). El contenido del comentario /*!re2c ... */se reemplaza por un autómata finito determinista codificado como saltos y comparaciones condicionales, el resto del programa se copia textualmente en el archivo de salida. Hay varias opciones para generar código, generalmente re2c usa el operador switch, pero puede usar operadores anidados if(como en este ejemplo con la opción -s) o generar mapas de bits y tablas de salto . Qué opción es mejor depende del compilador de C , se anima a los usuarios de re2c a experimentar.
/* Generado por re2c */ // re2c $ENTRADA -o $SALIDA -i --case-ranges #incluir <afirmar.h> bool lex ( const char * s ) { const char * YYCURSOR = s ; { char yych ; yych = * YYCURSOR ; cambiar ( yych ) { caso '1' ... '9' : goto yy2 ; predeterminado : ir a yy1 ; } yy1 : ++ YYCURSOR ; { devuelve falso ; } yy2 : yych = *++ YYCURSOR ; cambiar ( yych ) { caso '0' ... '9' : goto yy2 ; predeterminado : ir a yy3 ; } yy3 : { devuelve verdadero ; } } } int principal () { afirmar ( lex ( "1234" )); devolver 0 ; }ir :
//ir:generar re2go $ENTRADA -o $SALIDA -i paquete principal func lex ( cadena de cadena ) { var cursor int /*!re2c re2c:define:YYCTYPE = byte; re2c:define:YYPEEK = "str[cursor]"; re2c:define:YYSKIP = "cursor += 1"; re2c:yyfill:habilitar = 0; número = [1-9][0-9]*; número {volver} * { pánico("¡error!") } */ } función principal () { lex ( "1234\x00" ) } // Código generado por re2c, NO EDITAR. //ir:generar re2go $ENTRADA -o $SALIDA -i paquete principal func lex ( cadena de cadena ) { var cursor int { var yych byte yych = cadena [ cursor ] cambiar ( yych ) { caso '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : ir a yy2 predeterminado : ir a yy1 } yy1 : cursor += 1 { pánico ( "¡error!" ) } yy2 : cursor += 1 yych = cadena [ cursor ] cambiar ( yych ) { caso '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' : ir a yy2 predeterminado : ir a yy3 } yy3 : { volver } } } función principal () { lex ( "1234\x00" ) }óxido :
// re2rust $ENTRADA -o $SALIDA fn lex ( s : & [ u8 ]) -> bool { dejar mut cursor = 0 ; /*!re2c re2c:define:YYCTYPE = u8; re2c:define:YYPEEK = "*s.get_unchecked(cursor)"; re2c:define:YYSKIP = "cursor += 1;"; re2c:yyfill:habilitar = 0; número = [1-9][0-9]*; número { devuelve verdadero; } * { falso retorno; } */ } fn principal () { ¡afirmar! ( lex ( b"1234 \0 " )); } /* Generado por re2c */ // re2rust $ENTRADA -o $SALIDA fn lex ( s : & [ u8 ]) -> bool { dejar mut cursor = 0 ; { #[permitir(asignaciones_no_usadas)] sea mut yych : u8 = 0 ; let mut yystate : usize = 0 ; ' yyl : bucle { estado de coincidencia { 0 => { yych = inseguro { * s . get_unchecked ( cursor )}; cursor += 1 ; partido yych { 0x31 ..= 0x39 => { yestado = 2 ; continuar 'yyl ; } _ => { yestado = 1 ; continuar 'yyl ; } } } 1 => { devuelve falso ; } 2 => { yych = inseguro { * s . get_unchecked ( cursor )}; partido yych { 0x30 .. = 0x39 _ cursor += 1 ; yestado = 2 ; continuar 'yyl ; } _ => { yestado = 3 ; continuar 'yyl ; } } } 3 => { devuelve verdadero ; } _ => { ¡pánico! ( "error interno del lexer" ) } } } } } fn principal () { ¡afirmar! ( lex ( b"1234 \0 " )); }