¿Las expresiones regulares de Ruby 1.9 son igualmente potentes para una gramática libre de contexto?

Question

que tienen esta expresión regular:

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x 

Cuando la prueba en contra de varias cadenas, que parece ser tan potente como una gramática libre de contexto, ya que se encarga de la recursividad correctamente.

regex.match("aaacaaa") 
# => #<MatchData "aaacaaa" foo:"aaacaaa"> 
regex.match("aacaa") 
# => #<MatchData "aacaa" foo:"aacaa"> 
regex.match("aabcbaa") 
# => #<MatchData "aabcbaa" foo:"aabcbaa"> 
regex.match("aaacaa") 
# => nil 

"Fun with Ruby 1.9 Regular Expressions" tiene un ejemplo en el que en realidad organiza todas las partes de una expresión regular para que se vea como una gramática independiente del contexto de la siguiente manera:

sentence = %r{ 
    (?<subject> cat | dog | gerbil ){0} 
    (?<verb>  eats | drinks| generates){0} 
    (?<object> water | bones | PDFs  ){0} 
    (?<adjective> big | small | smelly ){0} 

    (?<opt_adj> (\g<adjective>\s)? ){0} 

    The\s\g<opt_adj>\g<subject>\s\g<verb>\s\g<opt_adj>\g<object> 
}x 

Entre su técnica para reorganizar las piezas de la expresión regular, y mi ejemplo de grupos recursivos de captura nombrada, ¿significa esto que las expresiones regulares de Ruby 1.9 tienen el poder equivalente a una gramática libre de contexto?

Answer 1

Esta es una de las cosas increíbles sobre el motor regexp Oniguruma utilizado en Ruby 1.9. Tiene la potencia de un analizador sintáctico y no está restringido al reconocimiento de idiomas regulares. Tiene lookahind/lookbehind positivo y negativo, que incluso se puede utilizar para reconocer algunos idiomas que son no ¡sin contexto! Tome el siguiente como un ejemplo:

regexp = /\A(?<AB>a\g<AB>b|){0}(?=\g<AB>c)a*(?<BC>b\g<BC>c|){1}\Z/ 

Esta expresión regular reconoce cadenas como “aaabbbccc” “abc”, “aabbcc”, y así sucesivamente - el número de “a”, “b”, y “c” debe ser igual o no coincidirá.

(Una limitación: no se puede utilizar grupos nombrados en la búsqueda hacia delante y de búsqueda hacia atrás.)

Aunque no he echado un vistazo bajo el capó, Oniguruma parece que tratar con grupos nombrados por simple descendente recursivo, la copia de seguridad cuando algo no concuerda He observado que no puede lidiar con la recursividad izquierda. Por ejemplo:

irb(main):013:0> regexp = /(?<A>\g<A>a|)/ 
SyntaxError: (irb):13: never ending recursion: /(?<A>\g<A>a|)/ 
    from C:/Ruby192/bin/irb:12:in `<main>' 

No me acuerdo de mi teoría de análisis muy claramente, pero yo creo que un programa de análisis no determinista de arriba hacia abajo como este debería ser capaz de analizar cualquier lenguaje libre de contexto. ("Idioma", no "gramática"; si su gramática ha dejado recursividad, deberá convertirla a recursividad correcta). Si eso no es correcto, edite esta publicación.