Estoy trabajando en un analizador para un lenguaje de estilo C, y para ese analizador necesito la expresión regular que coincida con el estilo C / ** / comentarios. Ahora, he encontrado esta expresión en la web:
/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/
Sin embargo, como puede ver, esta es una expresión bastante desordenada, y no tengo idea de si realmente coincide exactamente con lo que quiero que coincida.
¿Existe una forma diferente de (rigurosamente) definir expresiones regulares que sean fáciles de verificar a mano que sean realmente correctas y que luego sean convertibles ('compilables') a la expresión regular anterior?
compilers
parsers
regular-languages
Alex ten Brink
fuente
fuente
(!\*)
pretendieron los fragmentos ? ¿Te refieres a la notación más común[^*]
? Y lo que es(!*|!/)
?Respuestas:
Puedo pensar en cuatro formas:
Defina un autómata para el idioma que le interesa. Convierta la expresión regular en un autómata (utilizando los derivados de Brzozowski). Verifique que ambos autómatas acepten el mismo lenguaje (determine y minimice o use un argumento de bisimulación).
Escriba un montón de casos de prueba y aplique su expresión regular a ellos.
Convierta el autómata definido en el punto 1 en una expresión regular, utilizando técnicas estándar.
Una combinación de lo anterior.
fuente
Si desea asegurarse de que está analizando los comentarios de C, debe confrontar su modelo con la especificación de C. C99 §6.4.9 define la sintaxis de los comentarios de la siguiente manera:
Esta es una prosa en inglés, no una definición formal, pero hay una interpretación razonablemente clara en términos de un autómata finito no determinista (NFA) que consume un comentario:
/
seguido de*
ingresa al estado de comentario en multilínea, y/
luego/
ingresa al estado de comentario en una sola línea.*
seguido de/
ingresa al estado posterior al comentario.Tenga en cuenta que para saber si se aplica el estado inicial, debe realizar un poco más de análisis para detectar cadenas y literales de caracteres.
Una vez que tenga un NFA, puede usar técnicas estándar para construir una expresión regular (no las veo en los artículos de Wikipedia, pero deberían discutirse en los libros de texto).
Si ya tiene una expresión regular y desea probarla, puede comparar su lenguaje generado con el del NFA deducido de la especificación del lenguaje: la igualdad de los idiomas regulares es decidible. Una forma de decidir la igualdad es construir un autómata determinista mínimo para cada uno; Si los idiomas son equivalentes, los DFA mínimos serán isomorfos.
fuente
Si está escribiendo un analizador, el analizador léxico maneja este tipo de cosas. Y allí puede expresar esto mediante expresiones regulares, o (como
flex
muestran los ejemplos que he visto) simplemente "escapar al lenguaje subyacente" y terminar el trabajo allí. Es decir, al ver/*
simplemente salte hacia adelante hasta que encuentre*/
(un DFA para esto es fácil de construir, y desde allí un fragmento C es fácil de escribir).fuente