Estándar Regex vs python regex discrepancia

Question

Estoy leyendo un libro y proporcionan un ejemplo de cómo hacer coincidir una cadena determinada con expresiones regulares. Aquí es su ejemplo:

b*(abb*)*(a|∊) - Strings of a's and b's with no consecutive a's. 

Ahora he intentado convertirlo a Python, así:

>> p = re.compile(r'b*(abb*)*(a|)') # OR 
>> p = re.compile(r'b*(abb*)*(a|\b)') 

# BUT it still doesn't work 
>>> p.match('aa') 
<_sre.SRE_Match object at 0x7fd9ad028c68> 

Mi pregunta es doble:

1. ¿Cuál es el equivalente de épsilon en python para hacer que el ejemplo anterior funcione?
2. ¿Puede alguien explicarme por qué la forma teórica o estándar de hacer expresiones regulares no funciona en Python? ¿Podría tener algo que ver con el emparejamiento más largo versus el más corto?

Aclaración: Para la gente preguntando qué expresiones regulares estándar es - es el estándar formal de la teoría del lenguaje: http://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory

Answer 1

Gracias por las respuestas. Siento que cada respuesta tiene parte de la respuesta. Esto es lo que estaba buscando.

1. ?El símbolo es solo una abreviatura de (algo | & epsilon;). Por lo tanto, (a | & epsilon;) se puede volver a escribir como a?. Así que el ejemplo se convierte en:

   b*(abb*)*a? 
   

   en Python que escribiríamos:

   p = re.compile(r'^b*(abb*)*a?$') 
   

2. La razón por la traducción directa de la sintaxis de expresiones regulares regulares en Python (es decir, copiar y pegar) que no funciona es porque partidos pitón la subcadena más corta (si los símbolos $ o^están ausentes) mientras que las expresiones regulares teóricas coinciden con la subcadena inicial más larga.
   Así por ejemplo, si tuviéramos una cadena:

   s = 'aa' 
   

   Nuestro libro de texto de expresiones regulares b * (ABB *) * a? no coincidiría porque tiene dos a. Sin embargo, si se copia directamente a Python:

   >> p = re.compile(r'b*(abb*)*a?') 
   >> bool(p.match(s)) 
   True 
   

   Esto se debe a que nuestra única expresión coincide con la subcadena 'a' de nuestra cadena 'AA'.
   Con el fin de decirle a Python que ver un partido en toda la cuerda que tenemos que le indiquen dónde el principio y el final de la cadena es, con los ^ y $ símbolos respectivamente:

   >> p = re.compile(r'^b*(abb*)*a?$') 
   >> bool(p.match(s)) 
   False 
   

   Tenga en cuenta que python regex coincide() coincide en el comenzando de la cadena, por lo que asume automáticamente el ^ al inicio. Sin embargo, la función de búsqueda () no funciona, y por lo tanto mantenemos el ^.
   Así, por ejemplo:

   >> s = 'aa' 
   >> p = re.compile(r'b*(abb*)*a?$') 
   >> bool(p.match(s)) 
   False     # Correct 
   >> bool(p.search(s)) 
   True     # Incorrect - search ignored the first 'a' 
   

Answer 2

• Uso bool(p.match('aa')) para comprobar si los partidos de expresiones regulares o no

• p = re.compile('b*(abb*)*a?$')

• \b coincide con el borde de la cadena; colocar entre \w y \W (caracteres de palabras y caracteres no palabra)

Regexp es bastante estándar en Python. Sin embargo, cada idioma tiene algún sabor de ellos, no son 100% portátiles. Existen pequeñas diferencias que se espera que busque antes de usar regexp en cualquier idioma específico.

adición

\epsilon no tiene símbolo especial en Python. Es un juego de caracteres vacío.

En su ejemplo a|\epsilon es equivalente a (a|) o simplemente a?. Después de lo cual $ es obligatorio para que coincida con el final de la cadena.

Answer 3

No estoy muy seguro de cómo funciona la coincidencia en Python, pero creo que es posible que necesite agregar^.... $ a su RE. La coincidencia de RegExp generalmente coincide con las subcadenas, y encuentra la coincidencia más grande, en el caso de p.match ('aa') que es "a" (probablemente el primero).^... $ asegura que estás haciendo coincidir la cadena ENTERA, que es lo que creo que quieres.

Los exps teóricos/estándar asumen que siempre está haciendo coincidir toda la cadena, porque la está usando para definir un lenguaje de cadenas que coinciden, no para encontrar una subcadena en una cadena de entrada.

Answer 4

Coincide porque su expresión regular coincide con cualquier segmento de ancho cero de cualquier texto de muestra. Necesita anclar su expresión regular.He aquí una manera de hacerlo, utilizando una búsqueda hacia delante afirmación de ancho cero:

re.compile(r'^(a(?!a)|b)*$') 

Answer 5

En realidad, funciona el ejemplo bien ... a unos pequeños detalles. Me gustaría escribir:

>>> p = re.compile('b*(abb*)*a?') 
>>> m = p.match('aa') 
>>> print m.group(0) 
'a' 
>>> m = p.match('abbabbabababbabbbbbaaaaa') 
>>> print m.group(0) 
abbabbabababbabbbbba 

Tenga en cuenta que el grupo 0 devuelve la parte de la cadena coincidente por la expresión regular.

Como puede ver, la expresión coincide con una sucesión de ayb sin repetición de a. Si, efectivamente, que desea comprobar toda la cadena, es necesario cambiado ligeramente:

>>> p = re.compile('^b*(abb*)*a?$') 
>>> m = p.match('aa') 
>>> print m 
None 

el reconocimiento fuerza ^ y $ del principio y del final de la cadena.

Por fin, se pueden combinar ambos métodos mediante el uso de la primera expresión regular, pero las pruebas al final:

>>> len(m.group(0)) == len('aa') 

Agregado: Para la segunda parte de la OT, me parece que hay no hay discrepancia entre la regex estándar y la implementación de python. Por supuesto, la notación es ligeramente diferente, y la implementación de python sugiere algunas extensiones (como la mayoría de los otros paquetes).

Answer 6

Tu segunda vez debería ser un reemplazo apropiado para epsilon, como mejor lo entiendo, aunque nunca he visto épsilon en una expresión regular antes.

Por lo que vale, su patrón coincide con 'a'. Es decir, que es coincidente:

• cero o más "b "s (la elección de cero)
• cero o más" (abb*) "s (la elección de cero)
• uno" a" o palabra que termina (eligiendo una a).

Como Jonathan Feinberg señalado, si se quiere garantizar el conjunto de partidos de cuerda, hay que anclar el principio ('^') y al final ('$') de su expresión regular. También debería usar una cadena sin formato al construir expresiones regex en python: r'my regex '. Eso evitará una excesiva barra invertida que escape a la confusión.

Answer 7

el problema con su expresión es que coincide con la cadena vacía, lo que significa que si lo hace:

>>> p = re.compile('b*(abb*)*(a|)') 
>>> p.match('c').group(0) 
'' 

y desde re.match intenta hacer coincidir el inicio de la cadena, lo que tiene que decirle que se hacer coincidir hasta el final de la cadena. sólo tiene que utilizar para que $

>>> p = re.compile(r'b*(abb*)*(a|)$') 
>>> print p.match('c') 
None 
>>> p.match('ababababab').group(0) 
'ababababab' 

ps usted puede haber notado que he usado r'pattern' en lugar de 'patrón' más en que here (primeros párrafos)