Выразительность формального языка шаблонов Perl

Регулярные выражения Perl, как и регулярные выражения любого языка шаблонов, где разрешены "обратные ссылки", на самом деле не являются "обычными".

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

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

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

Не говоря уже о уловках, позволяющих использовать код Perl в регулярных выражениях Perl (нерегулярный язык сбалансированного круглые скобки)

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

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

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

Я всегда слышал, как реализация регулярного выражения Perl описывается как NFA с возвратом. В Википедии, кажется, есть небольшой раздел по этому поводу:

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

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

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

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

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

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

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