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

Question

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

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

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

Answer 1

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

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

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

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

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

---

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

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