¿Se pueden reescribir las expresiones regulares que contienen cuantificadores que no son de mala calidad (reacios) para no usarlas?

8

Considere un lenguaje de expresiones regulares con el cuantificador codicioso , el cuantificador no codicioso ? , alternancia ordenada y clases de caracteres. (Esto es esencialmente un sublenguaje de PCRE sin referencias posteriores, afirmaciones de búsqueda o algunos de los otros bits más elegantes).?

Un partido para una expresión regular para R en una cadena s = s 0 ... s n es un intervalo semiabierto sobre N de tal manera que es un 0 ... es un 1 - 1 es aceptada por R .[a0,a1)Rs=s0snNsa0sa11R

Damos una definición recursiva de lo que hace que una coincidencia sea mejor que otra. Una coincidencia para la expresión regular R en una cadena es mejor que otra coincidencia b = [ b 0 , b 1 ) si a 0 < b 0 o, si a 0 = b 0 y:a=[a0,a1)Rb=[b0,b1)a0<b0a0=b0

  • Si es una clase de personaje: las clases de personaje tienen coincidencias únicas, por lo que todas las coincidencias en la misma posición para R son iguales. Por lo tanto, este caso es imposible.RR

  • Si :R=ST

    • La parte inicial de es una mejor coincidencia para S que la parte inicial de b , oaSb
    • Las partes iniciales de y b son igualmente buenas coincidencias para S , y la parte posterior de a es una mejor coincidencia para T que la parte posterior de b .abSaTb
  • Si :R=S|T

    • es un partido para S y b no es, oaSb
    • y b son igualmente adecuadas para S y una es una mejor coincidencia para S que b es, oabSaSb
    • y b no son compatibles para S pero son partidos de T , y una es una mejor coincidencia para T que b es.abSTaTb

Todas las demás formas sintácticas se reducen a las tres anteriores para propósitos de prioridad de coincidencia:

  • : R S 0 | S 1 | ...R=SRS0|S1|
  • : R | S 1 | S 0R=S?R|S1|S0

Estos patrones infinitos se utilizan solo con fines de prioridad de coincidencia --- no son parte del lenguaje de coincidencia en consideración.

La relación "mejor" es un orden lineal débil sobre todas las coincidencias posibles para un patrón dado.

Llaman dos expresiones regulares partido equivalente si, para cada cadena de entrada finita, el conjunto de pares disjuntos mejores resultados para S es igual al conjunto de pares disjuntos mejores resultados para T .S,T ST

P: ¿Es el caso que por cada expresión regular contiene el cuantificador no arbóreo ? Hay una expresión regular equivalente T que no contiene cuantificadores no apetos?S?T

Editar: Esta es una reescritura completa de la pregunta para aclarar lo que se estaba preguntando.

uckelman
fuente
1
Traté de corregir LaTeX en la pregunta, pero compruebe que es lo que quería decir. (¡ \ttno evita que LaTeX interprete caracteres especiales y secuencias de control!)
Tsuyoshi Ito
2
Tienes que tener cuidado con lo que quieres decir con "poder expresivo" de una expresión regular. Si solo considera qué idioma reconoce la expresión regular, entonces es trivial que los cuantificadores reacios no agreguen ningún poder adicional porque no cambian el idioma que reconoce la expresión regular en primer lugar. Pero creo que está pensando en propiedades más finas de expresiones regulares, como qué subcadenas se capturan, etc.
Tsuyoshi Ito
1
No, L ( a+?) sigue siendo {a ^ n: n≥1}. Si realiza una coincidencia de expresión regular no anclado (como 'aaaa' =~ /a+?/en Perl), no obtendrá aaaacomo resultado, pero eso es solo porque las ramas se prueban en un orden diferente al a+. Si lo haces apropiadamente con los anclajes (como 'aaaa' =~ /^a+?\z/en Perl), obtienes aaaacomo resultado.
Tsuyoshi Ito
1
(1) Me alegra ver que mis comentarios y respuestas fueron útiles para que usted reformule la pregunta mejor (aunque no la haya admitido). (2) Espero que sepa que “los conjuntos de coincidencias no superpuestas que S y T tienen en t” no están bien definidas porque puede haber varios conjuntos de coincidencias no superpuestas. ¿Estás hablando de la lista que //gdevolvería una coincidencia global de expresiones regulares ( en Perl)?
Tsuyoshi Ito
2
Tu pregunta necesita aclararse; todavía estás hablando de "aceptar" un partido cuando codicioso versus no codicioso no cambia lo que se acepta; es solo un medio para especificar qué coincidencia localizar al buscar una coincidencia y encontrar muchas.
Eamon Nerbonne

Respuestas:

3

Esta respuesta se basa en el supuesto de que la equivalencia de dos expresiones regulares se define ya que reconocen el mismo lenguaje. No responde la pregunta actual.


Tiene un malentendido común de que los cuantificadores reacios cambian el conjunto de cadenas que coincide con una expresión regular. No lo hace, y solo cambia qué opciones se prueban primero.

Por ejemplo, si realiza una coincidencia de expresiones regulares 'aaaa' =~ /a+/en Perl, encuentra la primera coincidencia en la cadena aaaay recuerda qué subcadena coincide en una variable especial. Incluso si hay más de una subcadena aaaaque coincida con la expresión regular dada, se ignorarán las coincidencias que no sean la primera coincidencia.

Si los cuantificadores son codiciosos o reacios afecta a cuál es la primera coincidencia entre muchas coincidencias, pero el conjunto de coincidencias no cambia. En este sentido, el conjunto de cadenas que coincide con una expresión regular no cambia sin importar si utiliza cuantificadores codiciosos habituales o cuantificadores reacios.

Tsuyoshi Ito
fuente
No, estoy no hablar del conjunto de partidos que un patrón no anclada se consigue en una cadena dada. Estoy hablando del conjunto de cadenas para el que un patrón dado coincidirá con esas cadenas en su totalidad. En otras palabras, estoy interesado en reescribir patrones para mantener la equivalencia sobre el conjunto de cadenas para las cuales la primera coincidencia es la cadena completa . a+y a+?no son equivalentes en este sentido: aaaano es rival para este último.
uckelman
1
@uckelman: Según su definición, la cadena abbbno está en L ( a*(..)*) porque la primera coincidencia en la cadena abbbcon la expresión regular a*(..)*es abb. Esa no es la definición estándar del lenguaje reconocido por una expresión regular. Si eso es realmente lo que le interesa, debe nombrarlo de manera diferente.
Tsuyoshi Ito
Uckelman, estoy bastante seguro de los a+?partidos aaaa. Sé que Ruby regexpes sí.
Raphael
@Raphael: Supongo que estás hablando de "aaaa" =~ /a?/volver verdadero en Ruby, pero eso es porque el patrón coincide con una subcadena de aaaa , no porque coincida aaaa.
Tsuyoshi Ito
Me perdí un +(editado), y Ruby parece coincidir con la palabra completa (cf rubular.com).
Raphael