Ruby 1.9.1 supporta il seguente espressione regolare:
regex = %r{ (?<foo> a\g<foo>a | b\g<foo>b | c) }x
p regex.match("aaacbbb")
# the result is #<MatchData "c" foo:"c">
"Fun with Ruby 1.9 Regular Expressions" ha un esempio in cui egli in realtà 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
Penso che questo significhi che almeno il motore regex di Ruby 1.9.1, che è il motore regex di Oniguruma, è in realtà equivalente a una grammatica context-free, sebbene i gruppi di cattura non siano utili come un generatore di parser.
Ciò significa che "Pumping lemma for context-free languages" deve descrivere la classe di lingue riconoscibile dal motore regex di Ruby 1.9.1.
MODIFICA: Whoops! Ho incasinato, e non ho fatto un test importante che in realtà rende la mia risposta sopra totalmente sbagliata. Non cancellerò la risposta, perché è comunque un'informazione utile.
regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x
#I added anchors for the beginning and end of the string
regex.match("aaacbbb")
#returns nil, indicating that no match is possible with recursive capturing groups.
EDIT: Tornando a questo molti mesi dopo, ho appena scoperto che la mia prova in ultima modifica non era corretta. non dovrebbe corrispondere allo regex anche se regex funziona come una grammatica senza contesto.
Il test corretta dovrebbe essere su una stringa come "aabcbaa", e che non corrisponda alla espressione regolare:
regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x
regex.match("aaacaaa")
# => #<MatchData "aaacaaa" foo:"aaacaaa">
regex.match("aacaa")
# => #<MatchData "aacaa" foo:"aacaa">
regex.match("aabcbaa")
# => #<MatchData "aabcbaa" foo:"aabcbaa">
fonte
2010-04-18 04:51:45
Sì, le espressioni "regolari" sono state estese per riconoscere le lingue che le macchine a stati finiti non riconoscono. – WhirlWind
questo non risponde alla domanda. vuole una dichiarazione di un teorema (simile al lemma del pompaggio) che può usare per dimostrare quali espressioni regolari possono supportare quando supportano le retroconti. –
@ken: credo che abbia cambiato la domanda dopo aver risposto .... – zsong