Cinta adhesiva un Decididor de expresiones regulares

11

Su tarea es crear un programa que determine si una cadena dada es una expresión regular válida o no utiliza fragmentos de código provenientes de sitios en la red StackExchange.

A los efectos de este desafío, el dialecto expresión regular será un conjunto simplificada y en su mayoría mínima de meta-caracteres: ()*?|\. Como tal, no podrá utilizar analizadores de expresiones regulares incorporados.

  • \se usa para escapar de los metacaracteres. Debe ser seguido por un meta-personaje.
  • Los paréntesis sin escapes deben estar equilibrados
  • *y ?debe estar precedido por un no-meta-caracter, un grupo entre paréntesis o un meta-caracter escapado.
  • Todos los demás caracteres ASCII imprimibles más nueva línea, tabulación y espacio deben admitirse como caracteres no meta. Lo que sucede con una cadena que contiene otros caracteres no está definido.
  • El significado real de la expresión regular no es importante para este desafío.

Ejemplos

Truthy:
  abc
  a?
  (a|)*
  ()
  a|b*
  \*
  \\
  \\*
  a*b?(cd|e)
  +
  [
  }
  (123\))*
  \|
  (a(b(c|d)*e)*f)*
  (|\)*)
  (abc)+*
  (abc)+
  +abc

^ last test case is an actual newline

Falsy:
  ?abc
  *
  **
  \
  (
  a*?
  a?*
  ?
  a)
  (\)
  (|\)*
  \()
  |*
  (?:abc)
  \\**
  \n

Puntuación

Su puntaje general es la cantidad de fragmentos tomados de las preguntas y respuestas de StackExchange.

  • Los fragmentos repetidos cuentan tantas veces como se usan.
  • El espacio en blanco se puede agregar y eliminar libremente (debido a Python, Haskell y otros lenguajes sensibles al espacio en blanco) y no cuenta para el recuento de fragmentos.
    • La excepción sería si su código está realmente escrito en espacios en blanco .
  • Los fragmentos están permitidos en cualquier sitio de StackExchange siempre que provengan de preguntas, respuestas y comentarios que sean más antiguos (incluido el tiempo de edición; use revisiones más antiguas si es necesario) que este desafío. (24 de septiembre de 2019 a las 3:30 p.m. UTC)
  • Los fragmentos pueden provenir de cualquier parte de una pregunta, respuesta o cuerpo de comentario, ya sea en un bloque de código preformateado o no.
  • Empalmar un fragmento en el medio de otro hace que el fragmento externo cuente como dos fragmentos

¡La puntuación más baja gana!

Carne de res
fuente
1
@RobinRyder sí, cambiado
Beefster
¿Puede la publicación ser anterior o igual a este desafío, es decir, podemos usar fragmentos del cuerpo de este desafío?
Jo King
1
"Como tal, no podrá utilizar analizadores de expresiones regulares incorporados" ¿Es decir que está diseñado para frustrar el uso de eso por un simple sí / no, o que se nos prohíbe el uso de expresiones regulares en nuestras respuestas?
user0721090601
@guifa está diseñado para que no pueda simplemente tomar el motor de expresiones regulares de su idioma y ver si compila la expresión regular dada. Cada idioma que conozco admite un conjunto más grande de metacaracteres y grupos de captura especializados, por lo que no coincidirían con este conjunto de caracteres correctamente en todos los casos.
Beefster
1
@ JL2210 Eso lo convertiría en dos fragmentos: uno para el principio y otro para el final. Puede usar un solo fragmento siempre que pase todos los casos de prueba y provenga de una respuesta / pregunta / publicación que sea anterior a este desafío
Beefster

Respuestas:

6

Perl 6 , 20 fragmentos

{$_ eq m/[[<-[()*?|\\]>|\\<[()*?|\\]>|'(' <~~>* ')']<[*?]>?|\|]+/}

Pruébalo en línea!

Los fragmentos se toman de:

{$_ eq, m/[, <-[, ()*?, |\\, ]>, |\\, <[, ()*?, |\\, ]>, |, '(' <~~>* ')', <[, *?, ]>, ?|, \|, ]+/, }.

Este es principalmente el enfoque codicioso (hecho evidente por todos los fragmentos de uno o dos caracteres). Utilicé SymbolHound para buscar los caracteres individuales, y la única optimización real fue el '(' <~~>* ')'fragmento, que se toma de mi propia respuesta en expresiones regulares recursivas de Perl 6.

Explicación:

Básicamente, esto verifica si la entrada es igual a una coincidencia codiciosa de una expresión regular válida. La razón por la que no podemos usar la expresión regular en sí y agregarla ^$para marcar los extremos es porque estamos usando una expresión regular recursiva, que no funcionaría si hubiera ^$marcadores. La expresión regular en sí es:

m/[                             ]+/   # Match one or more times
   [              ]  # Any of 
    <-[()*?|\\]> |     # Not a metacharacter
    \\<[()*?|\\]>      # A metacharacter preceded by a \
    '(' <~~>* ')'      # Brackets surrounding a valid regex
                   <[*?]>?  # Optionally followed by a ? or *
                           | \|    # Or just the | metacharacter
Jo King
fuente
TIL ~~, gracias!
user0721090601
@ guifa Sí, lo aprendí a través de la especificación P6 , que tiene muchas cosas que aún no se han documentado correctamente. Sospecho ~~que no aparece porque aún no está completamente implementado (por ejemplo <~~0>), aunque hay otras gemas ocultas allí.
Jo King