Ответ 1
За исключением любого встроенного кода, такого как ?{ }, они, вероятно, не охватывают все контекстно-свободные, а тем более Turing Machines. Они могут, но, насколько мне известно, никто так и не доказал это так или иначе. Учитывая, что люди некоторое время пытались решить некоторые проблемы, связанные с контекстом, с регулярными выражениями Perl и еще не придумали решение, вероятно, что они не являются контекстно-зависимыми.
Существует интересная дискуссия о том, какие функции просто удобны, и которые на самом деле добавляют силу. Например, сопоставление 0 n * 1 * 0 n (это обозначение для "любого числа нулей, за которым следует один, за которым следует такое же количество нулей, как и раньше" ) не является чем-то, что можно сделать с чистыми регулярными выражениями. Вы можете доказать, что это не может быть сделано с помощью регулярных выражений с использованием леммы накачки, но простое, неформальное доказательство состоит в том, что регулярное выражение должно было бы подсчитать произвольное количество нулей, а регулярные выражения не могут подсчитывать.
Однако обратные ссылки могут соответствовать таковым:
/(0*) 1 \1/x;
Итак, это означает, что обратные ссылки дают вам больше энергии и не просто удобство. Что еще может дать нам больше силы, интересно?
Кроме того, Perl6 "шаблоны" (они даже не притворяются, что они уже представляют собой регулярные выражения) предназначены для того, чтобы выглядеть похожими на Perl5 regexes (так что вам не нужно много переучивать), но у них достаточно дополнительных функций полностью контекстно-свободный. Они на самом деле разработаны так, что вы можете использовать их, чтобы изменить способ анализа в лексической области.