Derivando la expresión regular para C-style / ** / comments

8

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?

Alex ten Brink
fuente
2
Tenga en cuenta que este enfoque evitará comentarios anidados. Si de todos modos está creando un analizador completo, es posible que desee considerar analizar los comentarios de bloque "correctamente". no solo debe ser más claro, también puede leer metadatos estructurados de los comentarios si lo desea.
Raphael
¿Se (!\*)pretendieron los fragmentos ? ¿Te refieres a la notación más común [^*]? Y lo que es (!*|!/)?
Gilles 'SO- deja de ser malvado'
@Gilles: He actualizado la expresión. (! * |! /) está destinado a ser algo que no es ni * ni /.
Alex ten Brink
@Raphael, en C los comentarios no anidan .
vonbrand
@vonbrand: "C-style" no es muy específico, por lo que mencionar que una "mejora natural" no es posible es un punto válido.
frafl

Respuestas:

6

Puedo pensar en cuatro formas:

  1. 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).

  2. Escriba un montón de casos de prueba y aplique su expresión regular a ellos.

  3. Convierta el autómata definido en el punto 1 en una expresión regular, utilizando técnicas estándar.

  4. Una combinación de lo anterior.

Dave Clarke
fuente
5

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:

1. Excepto dentro de una constante de caracteres, un literal de cadena o un comentario, los caracteres /* introducen un comentario. El contenido de dicho comentario se examina solo para identificar caracteres multibyte y para encontrar los caracteres */que lo terminan.

2. Excepto dentro de una constante de caracteres, un literal de cadena o un comentario, los caracteres //introducen un comentario que incluye todos los caracteres multibyte hasta, pero no incluye, el siguiente carácter de nueva línea. El contenido de dicho comentario se examina solo para identificar caracteres multibyte y para encontrar el carácter de nueva línea que termina.

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:

  • Desde el estado inicial, /seguido de *ingresa al estado de comentario en multilínea, y /luego /ingresa al estado de comentario en una sola línea.
  • Desde el estado de comentario multilínea, *seguido de /ingresa al estado posterior al comentario.
  • Desde el estado de comentario en una sola línea, una nueva línea ingresa al estado posterior al comentario.
  • Cualquier otro personaje deja el estado sin cambios.

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.

Gilles 'SO- deja de ser malvado'
fuente
Una búsqueda en Google Books ofrece esta referencia para el algoritmo de Kleene: books.google.co.uk/…
rgrig
0

Si está escribiendo un analizador, el analizador léxico maneja este tipo de cosas. Y allí puede expresar esto mediante expresiones regulares, o (como flexmuestran 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).

vonbrand
fuente