Le espressioni regolari di Ruby 1.9 sono ugualmente potenti per una grammatica senza contesto?

Question

Ho questa espressione regolare:

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

quando i test contro diverse stringhe, sembra essere potente come una grammatica libera dal contesto perché gestisce la ricorsione in modo corretto.

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" ha un esempio in cui ha effettivamente organizza tutte le parti di una regex in modo che appaia come una grammatica context-free come segue:

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 

Tra la sua tecnica per riorganizzare le parti della regex, e il mio esempio di gruppi di cattura denominati ricorsivi, significa che le espressioni regolari di Ruby 1.9 hanno il potere equivalente a una grammatica senza contesto?

Answer 1

Questa è una delle cose meravigliose del motore di regexp di Oniguruma usato in Ruby 1.9: ha la potenza di un parser e non si limita a riconoscere le lingue regolari. Ha un lookahead positivo e negativo/lookbehind, che può essere utilizzato anche per riconoscere alcune lingue che sono non context-free! Prendiamo il seguente come esempio:

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

Questa espressione regolare riconosce stringhe come “abc”, “aabbcc”, “aaabbbccc”, e così via - il numero di “a”, “b” e “c” deve essere uguale o non corrisponderà.

(Una limitazione: non è possibile utilizzare i gruppi citati nella lookahead e lookbehind.)

Anche se non ho sbirciato sotto il cofano, Oniguruma sembra a che fare con i gruppi nominati dal semplice discesa ricorsiva, il backup quando qualcosa non corrisponde Ho osservato che non può gestire la ricorsione a sinistra. Per esempio:

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>' 

Non ricordo la mia teoria di analisi in modo molto chiaro, ma penso che un non-deterministico parser top-down come questo dovrebbe essere in grado di analizzare qualsiasi linguaggio context-free. ("Lingua", non "grammatica"; se la tua grammatica ha lasciato la ricorsione, dovrai convertirla in ricorsione corretta.) Se ciò non è corretto, ti preghiamo di modificare questo post.