php - regulares - regex preg_match

Coincide con ^ nb ^ nc ^ n(por ejemplo, "aaabbbccc") utilizando expresiones regulares(PCRE)

Question

Es un hecho bien conocido que las implementaciones de expresiones regulares modernas (más notablemente PCRE) tienen poco en común con la noción original de gramáticas regulares . Por ejemplo, puede analizar el ejemplo clásico de una gramática sin contexto {a ⁿ b ⁿ ; n> 0} (ej. aaabbb ) usando esta expresión regular ( demo ):

~^(a(?1)?b)$~

Mi pregunta es: ¿hasta dónde puedes llegar? ¿También es posible analizar la gramática sensible al contexto {a ⁿ b ⁿ c ⁿ ; n> 0} (por ejemplo, aaabbbccc ) utilizando PCRE?

Answer 1

Mi pregunta es: ¿hasta dónde puedes llegar?

En aras de no crear código que sea un pantano ilegible de puntuación, voy a arriesgar los votos a la baja y responder a una pregunta diferente, aunque muy relacionada: ¿hasta dónde debes llegar?

Los analizadores de expresiones regulares son algo genial de tener en su kit de herramientas, pero no son la parte final de la programación. La capacidad de escribir analizadores sintácticamente de forma legible también es algo genial de tener en su kit de herramientas.

Las expresiones regulares deben usarse hasta el punto en que comiencen a hacer que su código sea difícil de entender. Más allá de eso, su valor es dudoso en el mejor de los casos, perjudicial en el peor. Para este caso específico, en lugar de usar algo como lo horrible:

~^(?=(a(?-1)?b)c)a+(b(?-1)?c)$~x

(con disculpas a NikiC), que la gran mayoría de las personas que intentan mantener tendrá que reemplazar totalmente o pasar mucho tiempo leyendo y entendiendo, es posible que desee considerar algo así como un solución de analizador (pseudo-código):

# Match "aa...abb...bcc...c" where:
# - same character count for each letter; and
# - character count is one or more.

def matchABC (string str):
    # Init string index and character counts.
    index = 0
    dim count[''a''..''c''] = 0

    # Process each character in turn.
    for ch in ''a''..''c'':
        # Count each character in the subsequence.
        while index < len(str) and str[index] == ch:
            count[ch]++
            index++

    # Failure conditions.
    if index != len(str):        return false # did not finish string.
    if count[''a''] < 1:           return false # too few a characters.
    if count[''a''] != count[''b'']: return false # inequality a and b count.
    if count[''a''] != count[''c'']: return false # inequality a and c count.

    # Otherwise, it was okay.
    return true

Esto será mucho más fácil de mantener en el futuro. Siempre me gusta sugerirles a las personas que deben suponer que los que vienen detrás de ellos (que tienen que mantener el código que escriben) son psicópatas que saben dónde vives; en mi caso, eso puede ser cierto, no tengo idea de dónde vives. :-)

A menos que tenga una necesidad real de expresiones regulares de este tipo (y a veces hay buenas razones, como el rendimiento en los idiomas interpretados), primero debe optimizar para la legibilidad .

Answer 2

Truco Qtax

Una solución que no fue mencionada:

^(?:a(?=a*(/1?+b)b*(/2?+c)))+/1/2$

Vea lo que coincide y falla en la demostración de expresiones regulares .

Esto utiliza grupos de autorreferencia (una idea @Qtax utilizada en su expresión regular vertical ).

Answer 3

Aquí hay una solución alternativa que usa grupos de equilibrio con .NET regex:

^(?''a''a)+(?''b-a''b)+(?(a)(?!))(?''c-b''c)+(?(b)(?!))$

No PCRE, pero puede ser de interés.

Ejemplo en: http://ideone.com/szhuE

Editar : se agregó el control de equilibrio faltante para el grupo a, y un ejemplo en línea.

Answer 4

Inspirado por la respuesta de NullUserExceptions (que ya eliminó porque falló en un caso), creo que he encontrado una solución:

$regex = ''~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x'';

var_dump(preg_match($regex, ''aabbcc''));    // 1
var_dump(preg_match($regex, ''aaabbbccc'')); // 1
var_dump(preg_match($regex, ''aaabbbcc''));  // 0
var_dump(preg_match($regex, ''aaaccc''));    // 0
var_dump(preg_match($regex, ''aabcc''));     // 0
var_dump(preg_match($regex, ''abbcc''));     // 0

Pruébelo usted mismo: http://codepad.viper-7.com/1erq9v

Explicación

Si considera la expresión regular sin la aserción positiva de búsqueda anticipada (la parte (?=...) ), tiene esto:

~^a+(b(?-1)?c)$~

Esto no hace más que verificar que haya un número arbitrario de a , seguido de un número igual de b s y c s.

Esto todavía no satisface nuestra gramática, porque el número de a debe ser el mismo también. Podemos asegurarlo comprobando que el número de a es igual a la cantidad de b s. Y esto es lo que hace la expresión en la afirmación de anticipación: (a(?-1)?b)c . La c es necesaria, por lo que no solo coincidimos con una parte de la b s.

Conclusión

Creo que esto muestra de manera impresionante que la expresión regular moderna no solo es capaz de analizar gramáticas no regulares, sino que incluso puede analizar gramáticas sin contexto. Con suerte, esto servirá para descansar el interminable loro de "no se puede hacer X con expresiones regulares porque X no es regular"