Рекурсивные регулярные выражения aka Контекстно-свободные грамматики

Я недавно уже упоминал, что то, что мы в Perl называем регулярными выражениями, следовало бы называть контекстно-свободно-грамматическими выражениями, но их так никто не называет, наверное, потому что это слишком гадко звучит. Об этом где-то как-то упоминается, но примеров кода, которые это демонстрировали бы, я не встречал. Придется самому исправить это упущение.

Пример грамматики взят из Parsing Techniques (A Practical Guide) by Dick Grune & Ceriel Jacobs, охренительно простой книжки про парсеры — насколько вообще простой может быть охренительно толковая книжка про парсеры. Очень рекомендую.

Итак, задача. Требуется составить регулярное выражение, которое будет совпадать со строкой, состоящей из одинакового количества символов a и b — в любом порядке. Эта задача не имеет решения, которое я и привожу ниже.

use Test::More tests => 31;

=pod

S -> aB | bA
A -> a | aB | bAA
B -> b | bA | aBB

=cut

my ($S, $A, $B);
$S = qr/ ( a (??{$B}) ) | ( b (??{$A}) ) /x;
$A = qr/ ( a ) | ( a (??{$S}) ) | ( b (??{$A}) (??{$A}) ) /x;
$B = qr/ ( b ) | ( b (??{$S}) ) | ( a (??{$B}) (??{$B}) ) /x;

ok('' !~ /^$S$/, 'EMPTY');

ok('a' !~ /^$S$/, 'a');
ok('b' !~ /^$S$/, 'b');

ok('aa' !~ /^$S$/, 'aa');
ok('ab' =~ /^$S$/, 'ab');
ok('ba' =~ /^$S$/, 'ba');
ok('bb' !~ /^$S$/, 'bb');

ok('aaa' !~ /^$S$/, 'aaa');
ok('aab' !~ /^$S$/, 'aab');
ok('aba' !~ /^$S$/, 'aba');
ok('abb' !~ /^$S$/, 'abb');
ok('baa' !~ /^$S$/, 'baa');
ok('bab' !~ /^$S$/, 'bab');
ok('bba' !~ /^$S$/, 'bba');
ok('bbb' !~ /^$S$/, 'bbb');

ok('aaaa' !~ /^$S$/, 'aaaa');
ok('aaab' !~ /^$S$/, 'aaab');
ok('aaba' !~ /^$S$/, 'aaba');
ok('aabb' =~ /^$S$/, 'aabb');
ok('abaa' !~ /^$S$/, 'abaa');
ok('abab' =~ /^$S$/, 'abab');
ok('abba' =~ /^$S$/, 'abba');
ok('abbb' !~ /^$S$/, 'abbb');
ok('baaa' !~ /^$S$/, 'baaa');
ok('baab' =~ /^$S$/, 'baab');
ok('baba' =~ /^$S$/, 'baba');
ok('babb' !~ /^$S$/, 'babb');
ok('bbaa' =~ /^$S$/, 'bbaa');
ok('bbab' !~ /^$S$/, 'bbab');
ok('bbba' !~ /^$S$/, 'bbba');
ok('bbbb' !~ /^$S$/, 'bbbb');

Вопросы есть?

Update: спасибо zloy-russkiy за ссылку на Regexp::Grammars для 5.10!
Update #2: спасибо Павлу Кудинову за его собственную реализацию парсера на рекурсивных регулярных выражениях для 5.8.8!