Формальная языковая выразительность моделей Perl

Классические регулярные выражения эквивалентны конечным автоматам. Большинство современных реализаций "регулярных выражений" строго не являются регулярными выражениями, но являются более мощными. Некоторые люди начали использовать термин "шаблон", а не "регулярное выражение", чтобы быть более точным.

Какова формальная языковая классификация того, что можно описать с помощью современного "регулярного выражения", такого как шаблоны, поддерживаемые в Perl 5?

Обновление: под "Perl 5" я подразумеваю, что функции сопоставления шаблонов реализованы в Perl 5 и приняты многими другими языками (С#, JavaScript и т.д.) и не имеют ничего общего с Perl. Я не хочу рассматривать, например, трюки для встраивания кода Perl в шаблон.

Ответ 1

Недавно была обсуждена эта тема Perlmonks: полнота и регулярные выражения Тьюринга

Ответ 2

Perl regexps, как и слова любого языка шаблонов, где разрешены "обратные ссылки", на самом деле не являются "правильными".

Backreferences - это механизм сопоставления той же строки, которая ранее была сопоставлена подкатегорией. Например, /^(a*)\1$/ соответствует только строкам с четным числом a s, потому что после некоторого a должно следовать одно и то же число.

Легко доказать, что, например, pattern /^((a|b)*)\1$/ соответствует словам из нерегулярного языка (*), поэтому он более выразителен, чем ant конечный автомат. Регулярные выражения не могут "запомнить" строку произвольной длины, а затем снова совпадают (длина может быть очень длинной, а машина конечного состояния может имитировать конечное количество "памяти" ).

Формальное доказательство использовало бы лемму о перекачке. (Кстати, этот язык не может быть описан и без контекстной грамматики.)

Не говоря уже о трюках которые позволяют использовать perl-код в perl-регулярном выражении (нерегулярный язык с сбалансированными круглыми скобками).

(*) "Регулярные языки" - это множества слов, которые сопоставляются конечными автоматами. Я уже писал ответ об этом.

Ответ 3

Я всегда слышал реализацию regex perl, описанную как NFA с обратным отсчетом. У Википедии есть небольшой раздел:

Возможно, это немного слишком нечеткое, но информативное не менее:

Из Википедии:

Есть как минимум три разных алгоритмы, которые определяют, как и как данное регулярное выражение соответствует строка.

Самые старые и самые быстрые два человека полагаются на приводят к формальной теории языка, что допускает любые недетерминированные конечные конечный автомат (NFA), подлежащий преобразованию в детерминированное конечное состояние машина (DFA). DFA может быть построено явно, а затем выполняется результирующая строка ввода одного символа вовремя. Построение DFA для регулярное выражение размера m имеет времени и памяти O (2 м), но это может выполняться на строке размера n в время O (n). Альтернативный подход для имитации NFA непосредственно, по существу, построение каждого состояния DFA на и затем отбросить его на следующий шаг, возможно, с кешированием. Эта держит DFA неявным и избегает экспоненциальная стоимость строительства, но текущая стоимость возрастает до O (нм). явный подход называется DFA алгоритм и неявный подход алгоритм NFA. Как можно видеть как различные способы выполнения то же DFA, их также часто называют алгоритм DFA без различие. Эти алгоритмы быстро, но используя их для вызова сгруппированные подвыражения, ленивые количественная оценка и аналогичные функции является сложным. [12] [13]

Третий алгоритм должен соответствовать шаблон против входной строки на возвраты. Этот алгоритм обычно называемый NFA, но это терминология может ввести в заблуждение. это время работы может быть экспоненциальным, что простые реализации проявляются, когда сопоставление с выражениями типа (a | aa) * b, которые содержат как чередование и неограниченная количественная оценка и сила алгоритм для рассмотрения экспоненциально возрастающее число суб-дела. Более сложный реализации часто идентифицируют и ускорить или прервать общие случаи где они в противном случае будут работать медленно.

Хотя реализация обратного слежения только дают экспоненциальную гарантию в В худшем случае они обеспечивают большая гибкость и выразительность мощность. Например, любая реализация что позволяет использовать обратные ссылки или различные расширения, введенные Perl, должен использовать откат реализация.

Некоторые реализации пытаются обеспечить лучший из обоих алгоритмов выполняйте быстрое совпадение DFA, чтобы увидеть, строка соответствует регулярному выражению вообще, и только в этом случае выполняют потенциально более медленный откат матч.