Conversión de un patrón de expresión regular recursiva de PCRE a grupos de balanceo.NET

regex recursive-regex

Question

PCRE tiene una característica llamada patrón recursivo, que se puede usar para hacer coincidir subgrupos anidados. Por ejemplo, considere la "gramática"

Q -> /w | ''['' A '';'' Q* '',''? Q* '']'' | ''<'' A ''>''
A -> (Q | '','')*
// to match ^A$.

Se puede hacer en PCRE con el patrón.

^((?:,|(/w|/[(?1);(?2)*,?(?2)*/]|<(?1)>))*)$

(Ejemplo de caso de prueba: http://www.ideone.com/L4lHE )

Debe coincidir

abcdefg abc,def,ghi abc,,,def ,,,,,, [abc;] [a,bc;] sss[abc;d] as[abc;d,e] [abc;d,e][fgh;j,k] <abc> [<a>b;<c,d>,<e,f>] <a,b,c> <a,bb,c> <,,,> <> <><> <>,<> a<<<<>>><a>> <<<<<>>>><><<<>>>> <z>[a;b] <z[a;b]> [[;];] [,;,] [;[;]] [<[;]>;<[;][;,<[;,]>]>]

No debe coincidir:

<a bc> <abc<de> [a<b;c>;d,e] [a] <<<<<>>>><><<<>>>>> <<<<<>>>><><<<>>> [abc;def;] [[;],] [;,,] [abc;d,e,f] [<[;]>;<[;][;,<[;,]>]]> <z[a;b>]

No hay un patrón recursivo en .NET. En su lugar, proporciona grupos de equilibrio para la manipulación basada en la pila para hacer coincidir patrones anidados simples.

¿Es posible convertir el patrón PCRE anterior al estilo .NET Regex?

_{(Sí, sé que es mejor no usar expresiones regulares para esto. Es solo una pregunta teórica).}

Referencias

• pcre.org - Página del manual de PCRE - Patrones recursivos
• MSDN - Elementos del lenguaje de expresión regular - Equilibrio de definiciones de grupo

Answer 1

La alternativa de .Net al patrón recursivo es una pila. El desafío aquí es que necesitamos expresar la gramática en términos de pilas.
Aquí hay una forma de hacerlo:

Una notación ligeramente diferente para las gramáticas.

• Primero, necesitamos reglas gramaticales (como A y Q en la pregunta).
• Tenemos una pila. La pila solo puede contener reglas.
• En cada paso, sacamos el estado actual de la pila, coincidimos con lo que necesitamos para coincidir, e insertamos más reglas en la pila. Cuando terminamos con un estado, no presionamos nada y volvemos al estado anterior.

Esta notación se encuentra en algún lugar entre el autómata CFG y Pushdown , donde colocamos las reglas en la pila.

Ejemplo:

Comencemos con un ejemplo simple: a ⁿ b ⁿ . La gramática habitual para este idioma es:

S -> aSb | ε

Podemos reformular eso para que se ajuste a la notación:

# Start with <push S>
<pop S> -> "a" <push B> <push S> | ε
<pop B> -> "b"

En palabras:

• Comenzamos con S en la pila.
• Cuando sacamos S de la pila podemos:
  • No coinciden con nada, o ...
  • coincida con "a", pero luego tenemos que empujar el estado B a la pila. Esta es una promesa que haremos coincidir con "b". A continuación, también presionamos S para que podamos seguir haciendo coincidir "a" s si queremos.
• Cuando hayamos emparejado suficientes "a", comenzamos a sacar B s de la pila y hacemos coincidir una "b" para cada una.
• Cuando se hace esto, hemos igualado un número par de "a" y "b".

o, más libremente:

Cuando estamos en el caso S, coincida con "a" y presione B y luego S, o no coincida con nada.
Cuando estemos en el caso B, empareja "b".

En todos los casos, sacamos el estado actual de la pila.

Escribiendo el patrón en una expresión regular .Net

Necesitamos representar los diferentes estados de alguna manera. No podemos seleccionar ''1'' ''2'' ''3'' o ''a'' ''b'' ''c'' , ya que es posible que no estén disponibles en nuestra cadena de entrada; solo podemos hacer coincidir lo que está presente en la cadena.
Una opción es numerar nuestros estados (en el ejemplo anterior, S indicaría el número 0 y B es el estado 1).
Para el estado S _𝒊 podemos empujar 𝒊 caracteres a la pila. Para mayor comodidad, empujaremos los primeros 𝒊 caracteres desde el inicio de la cadena. Una vez más, no nos importa qué son estos personajes, solo cuántos hay.

Estado de empuje

En .Net, si queremos empujar los primeros 5 caracteres de una cadena a una pila, podemos escribir:

(?<=(?=(?<StateId>.{5}))/A.*)

Esto es un poco complicado:

• (?<=…/A.*) es un aspecto que va hasta el principio de la cadena.
• Cuando estamos en el inicio hay una mirada al futuro: (?=…) . Esto se hace para que podamos coincidir más allá de la posición actual; si estamos en la posición 2 , no tenemos 5 caracteres antes que nosotros. Así que estamos mirando hacia atrás y mirando hacia adelante.
• (?<StateId>.{5}) 5 caracteres en la pila, lo que indica que en algún momento debemos coincidir con el estado 5.

Estado pop

Según nuestra notación, siempre sacamos el estado superior de la pila. Eso es fácil: (?<-StateId>) .
Pero antes de hacerlo, queremos saber qué estado fue o cuántos caracteres capturó. Más específicamente, necesitamos verificar explícitamente cada estado, como un bloque de switch / case . Entonces, para verificar si la pila tiene actualmente el estado 5:

(?<=(?=.{5}(?<=/A/k<StateId>))/A.*)

• De nuevo, (?<=…/A.*) va hasta el principio.
• Ahora avanzamos (?=.{5}…) con cinco caracteres ...
• Y use otra mirada detrás de, (?<=/A/k<StateId>) para verificar que la pila realmente tenga 5 caracteres.

Esto tiene un inconveniente obvio: cuando la cadena es demasiado corta, no podemos representar el número de estados grandes. Este problema tiene soluciones:

• El número de palabras cortas en el idioma es final de todos modos, por lo que podemos agregarlas manualmente.
• Use algo más complicado que una sola pila: podemos usar varias pilas, cada una con cero o un personaje, efectivamente bits de nuestro estado (hay un ejemplo al final).

Resultado

Nuestro patrón para a ⁿ b ^{n se} ve así:

/A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            (?:
                # Push State B, Index = 1
                (?<=(?=(?<StateId>.{1}))/A.*)
                a
                # Push State A, Index = 0
                (?<StateId>)
                |

            )
        )
        |
        (?:
            # When In State B, Index = 1
            (?<=(?=.{1}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            b
        )
        |/Z
    ){2}
)+
/Z
# Assert state stack is empty
(?(StateId)(?!))

Ejemplo de trabajo en Regex Storm

Notas:

• Tenga en cuenta que el cuantificador alrededor de los estados es (?:(?:…){2})+ - es decir, (recuento de estados) × (longitud de entrada). También agregué una alternancia para /Z No entremos en eso, pero es una solución para una optimización molesta en el motor .Net.
• Lo mismo se puede escribir como (?<A>a)+(?<-A>b)+(?(A)(?!)) - esto es solo un ejercicio.

Contestar la pregunta

La gramática de la pregunta se puede reescribir como:

# Start with <push A>
<pop A> -> <push A> ( @"," | <push Q> ) | ε
<pop Q> -> /w
           | "<" <push Q2Close> <push A>
           | "[" <push Q1Close> <push QStar> <push Q1Comma> <push QStar> <push Q1Semicolon> <push A>
<pop Q2Close> -> ">"
<pop QStar> -> <push QStar> <push Q> | ε 
<pop Q1Comma> -> ","?
<pop Q1Semicolon> -> ";"
<pop Q1Close> -> "]"

El patrón:

/A
# Push State A, Index = 0
(?<StateId>)
(?:
    (?:
        (?:
            # When In State A, Index = 0
            (?<=(?=.{0}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            (?:
                # Push State A, Index = 0
                (?<StateId>)
                (?:
                    ,
                    |
                    # Push State Q, Index = 1
                    (?<=(?=(?<StateId>.{1}))/A.*)
                )
                |

            )
        )
        |
        (?:
            # When In State Q, Index = 1
            (?<=(?=.{1}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            (?:
                /w
                |
                <
                # Push State Q2Close, Index = 2
                (?<=(?=(?<StateId>.{2}))/A.*)
                # Push State A, Index = 0
                (?<StateId>)
                |
                /[
                # Push State Q1Close, Index = 6
                (?<=(?=(?<StateId>.{6}))/A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))/A.*)
                # Push State Q1Comma, Index = 4
                (?<=(?=(?<StateId>.{4}))/A.*)
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))/A.*)
                # Push State Q1Semicolon, Index = 5
                (?<=(?=(?<StateId>.{5}))/A.*)
                # Push State A, Index = 0
                (?<StateId>)
            )
        )
        |
        (?:
            # When In State Q2Close, Index = 2
            (?<=(?=.{2}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            >
        )
        |
        (?:
            # When In State QStar, Index = 3
            (?<=(?=.{3}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            (?:
                # Push State QStar, Index = 3
                (?<=(?=(?<StateId>.{3}))/A.*)
                # Push State Q, Index = 1
                (?<=(?=(?<StateId>.{1}))/A.*)
                |

            )
        )
        |
        (?:
            # When In State Q1Comma, Index = 4
            (?<=(?=.{4}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            ,?
        )
        |
        (?:
            # When In State Q1Semicolon, Index = 5
            (?<=(?=.{5}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            ;
        )
        |
        (?:
            # When In State Q1Close, Index = 6
            (?<=(?=.{6}(?<=/A/k<StateId>))/A.*)
            (?<-StateId>)
            /]
        )
        |/Z
    ){7}
)+
/Z
# Assert state stack is empty
(?(StateId)(?!))

^{Lamentablemente, es demasiado largo para caber en una URL, por lo que no hay un ejemplo en línea.}

Si usamos pilas "binarias" con uno o cero caracteres, se vería así: https://gist.github.com/kobi/8012361

Aquí hay una captura de pantalla del patrón que pasa todas las pruebas: http://i.stack.imgur.com/IW2xr.png

Prima

El motor .Net puede hacer más que solo equilibrar, también puede capturar cada instancia de A o Q Esto requiere una ligera modificación del patrón: https://gist.github.com/kobi/8156968 .
Tenga en cuenta que hemos agregado los grupos Start , A y Q al patrón, pero no tienen ningún efecto en el flujo, se utilizan únicamente para la captura.

El resultado: por ejemplo, para la cadena "[<a>b;<c,d>,<e,f>]" , podemos obtener estas Capture s:

Group A
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-4) <a>b
    (2-2) a
    (7-9) c,d
    (13-15) e,f
Group Q
    (0-17) [<a>b;<c,d>,<e,f>]
    (1-3) <a>
    (2-2) a
    (4-4) b
    (6-10) <c,d>
    (7-7) c
    (9-9) d
    (12-16) <e,f>
    (13-13) e
    (15-15) f

Preguntas abiertas

• ¿Se puede convertir cada gramática a la notación de pila de estado?
• ¿Son (pasos del estado) × (longitud de entrada) suficientes pasos para unir todas las palabras? ¿Qué otra fórmula puede funcionar?

Código fuente

El código utilizado para generar estos patrones y todos los casos de prueba se pueden encontrar en https://github.com/kobi/RecreationalRegex

Answer 2

La respuesta es _{^{(probablemente)}} sí.

La técnica es mucho más compleja que la (?1) llamada recursiva, pero el resultado es casi 1 a 1 con las reglas de la gramática; trabajé de una manera tan metódica que puedo ver fácilmente en un script. Básicamente, combinas bloque por bloque y usas la pila para hacer un seguimiento de dónde estás. Esta es una solución casi funcional:

^(?:
    (/w(?<Q>)) # Q1
    |
    (<(?<Angle>))  #Q2 - start <
    |
    (/>(?<-Angle>)(?<-A>)?(?<Q>))  #Q2 - end >, match Q
    |
    (/[(?<Block>))  # Q3 start - [
    |
    (;(?<Semi-Block>)(?<-A>)?)  #Q3 - ; after [
    |
    (/](?<-Semi>)(?<-Q>)*(?<Q>))  #Q3 ] after ;, match Q
    |
    ((,|(?<-Q>))*(?<A>))   #Match an A group
)*$
# Post Conditions
(?(Angle)(?!))
(?(Block)(?!))
(?(Semi)(?!))

Falta la parte de permitir comas en Q->[A;Q*,?Q*] , y por alguna razón permite [A;A] , por lo que coincide con [;,,] y [abc;d,e,f] . El resto de las cadenas coinciden con los casos de prueba.
Otro punto menor es un problema con empujar a la pila con una captura vacía, no lo hace. A acepta Ø, así que tuve que usar (?<-A>)? para comprobar si capturó.

Todo el regex debería verse así , pero nuevamente, es inútil con el error allí.

¿Por qué no funciona?

No hay forma de sincronizar las pilas: si presiono (?<A>) y (?<B>) , puedo hacer que aparezcan en cualquier orden. Es por eso que este patrón no puede diferenciar <z[a;b>] de <z[a;b]> ... necesitamos una pila para todos.
Esto se puede resolver para casos simples, pero aquí tenemos algo mucho más complicado: una Q o A , no solo "<" o "[".