Как следует из названия, на прошлых выходных я потратил пару часов, пытаясь обдумать класс языков, сопоставляемых с Perl-совместимыми регулярными выражениями, за исключением любого оператора сопоставления, который позволяет выполнять произвольный код внутри шаблона .
Если вы не знаете, что такое PCRE, прочитайте это и это .
Проблема в том, что ресурсы, доступные в интернете, в основном останавливаются на языках без контекста, и PCRE могут соответствовать больше, чем те (см. Ниже); но я действительно не знаю, где найти больше теорем или статей о подобных вещах.
В частности: PCRE, очевидно, являются надмножеством обычных языков (поскольку синтаксис PCRE имеет все операторы регулярных языков).
Любой CFG может быть переведен в нормальную форму Грейбаха, что устраняет левую рекурсию. Я думаю, что это можно использовать с помощью (?(DEFINE)...)групп, чтобы «перевести» грамматику в соответствующие подпрограммы, избегая удушья левой рекурсии, переводя:
- нетерминал во главе каждого производства становится подпрограммой
(?<HEAD>...) - тело каждого производства помещается в подпрограмму; терминалы остаются как есть, нетерминалы становятся вызовами процедур (т.е.
(?&NONTERMINAL)); - все постановки с одним и тем же нетерминалом, как с головкой, объединяются с помощью
|оператора (плюс дополнительная группировка с(?:...), если необходимо) - шаблон затем становится
(?(DEFINE)...)группой, содержащей все «переведенные» произведения и вызов для процедуры начального символа, чтобы соответствовать всей строке, т.е.^(?(DEFINE)...)(?&START)$
Это должно иметь дело с любым CFG. Следовательно, PCRE должны соответствовать любому CFL.
Там еще: давайте возьмем простой язык т.е. язык строк повторяется дважды. Этот язык не является КЛЛ - лемма прокачки КЛЛ не работает. (Обратите особое внимание на то, что | v x w | ≤ p должно выполняться, поэтому вы не можете просто накачать начало или конец двух повторяющихся строк.)
Тем не менее, этот язык легко подкреплен PCRE: ^(.*)\1$. Поэтому мы строго выше КЛЛ.
Сколько выше? Ну, как я уже сказал, я понятия не имею. Я не мог найти никаких ресурсов о CSL или всех других классах между ними, чтобы принять решение. Любой эксперт готов обсудить это?
Приложение: меня попросили указать, какое именно подмножество синтаксиса PCRE должно быть разрешено. Как я писал в начале поста, я хотел исключить любой оператор, который позволяет выполнять произвольный код внутри шаблона, например ??{}.
Ради аргумента, я думаю, что мы можем придерживаться синтаксиса, определенного man-страницей pcresyntax (3) , которая является разумным подмножеством того, что предлагает Perl 5.10-5.12, за вычетом выносок (так как они не находятся внутри шаблона). Я не уверен, что добавление или удаление контрольных глаголов возврата изменяет язык, который мы можем распознать; если так, было бы неплохо выяснить, какие классы мы получаем с и без них.
Ответы:
Я также нашел этот пост очень интересным http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Это обеспечивает то же самое доказательство, которое я дал ранее о том, что регулярные выражения распознают CFL (переписывая грамматику через
DEFINEблоки) и даже некоторые CSL (например, язык повторяющихся строк); он основывается на этом и продолжает, давая доказательство того, что регулярные выражения с обратными ссылками являются NP-сложными (уменьшая 3-SAT до регулярного выражения).источник
Они выбирают в большинстве случаев контекстно-зависимые языки (которые, как вы указываете, являются надмножеством контекстно-свободных языков). Смотрите этот пост perl monks .
Основная идея заключается в том, что «память» машины - это число групп захвата, которое линейно ограничено.
источник