Как обратные ссылки в регулярных выражениях требуют возврата?

Ответ 1

Чтобы получить прямо на ваш вопрос, вы должны сделать короткое исследование Хомской иерархии. Это старый и красивый способ организации формальных языков в наборах возрастающей сложности. Самая низкая ступень иерархии - это обычные языки. Вы можете догадаться - и вы будете правы - что RL - это те, которые могут быть представлены "чистыми" регулярными выражениями: те, у кого только алфавит, пустая строка, конкатенация, чередование | и звезда Клейна * (смотрите Ма, нет обратных ссылок). Классическая теорема формальной теории языка - теорема Клейна - состоит в том, что DFA, NFA (как описано в цитируемой статье) и регулярные выражения имеют точно такую ​​же способность представлять и распознавать языки. Конструкция Томпсона, приведенная в статье, является частью доказательства теоремы.

Каждый RL также является CFL. Но существует бесконечно много CFL, которые не являются регулярными. Функция, которая может существовать в CFL, что делает их слишком сложными, чтобы быть регулярными, - это сбалансированные пары вещей: круглые скобки, начальные блоки и т.д. Почти все языки программирования - это CFL. CFL могут быть эффективно распознаны тем, что называется автоматом pushdown. Это, по существу, NFA с наложенным стеклом. Стек растет настолько, насколько это необходимо, поэтому он больше не является конечным автоматом. Парсеры реальных языков программирования - это почти все вариации на автоматах выталкивания.

Рассмотрим регулярное выражение с обратной регрессией

^(b*a)\1$

В словах это представляет строки длины 2n для некоторого n, где и n'th и 2n'th символы a, и все остальные символы b. Это прекрасный пример CFL, который не является регулярным. Вы можете строго доказать это с помощью другого крутого инструмента формального языка, называемого леммой о перекачке.

Именно поэтому обратные ссылки вызывают проблемы! Они позволяют "регулярные выражения", которые представляют языки, которые не являются регулярными. Поэтому нет NFA или DFA, которые могут их распознать.

Но подождите, это еще хуже, чем я догадывался. Рассмотрим

^(b*a)\1\1$

Теперь мы имеем строку длины 3n, где n'th, 2n'th и 3n'th элементы a, а все остальные b. Существует еще один вкус леммы о перекачке, который позволяет доказать, что этот язык слишком сложный, чтобы быть CFL! Никакой пускательный автомат не может распознать этот.

Обратные ссылки позволяют этим перегруженным регулярным выражениям представлять языки, которые являются тремя ступеньками вверх по иерархии Хомского: контекстно-зависимые языки. Грубо говоря, единственный способ распознать CSL - проверить все строки на языке равной длины (по крайней мере, если P!= NP, но это верно для всех практических целей и другой истории вообще). Число таких строк экспоненциально по длине той, которую вы сопоставляете.

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

Поэтому я согласен с автором статьи, которую вы цитировали. Можно написать совершенно невинно выглядящие регулярные выражения с no back refs, которые будут эффективно распознаны почти для всех входов, но там, где существует некоторый ввод, который вызывает сопряжение регулярных выражений Perl или Java или Python, потому что это поиск по возврату - потребовать миллионы лет для завершения матча. Это безумие. У вас может быть script, который исправит и прекрасно работает в течение многих лет, а затем блокируется в один прекрасный день только потому, что он наткнулся на один из плохих входов. Предположим, что регулярное выражение зарыто в анализаторе сообщений навигационной системы в самолете, на котором вы едете...

Edit

По запросу я опишу, как лемма Pumping может использоваться для доказательства языка a^k b a^k b не является регулярной. Здесь a^k является сокращением для a повторяющихся k раз. PL говорит, что должно существовать положительное целое число N такое, что каждая строка на регулярном языке длины по крайней мере N должна иметь вид R S T такой, что R S ^ k T также находится в языке для всех натуральных k. Здесь R, S, T являются строками, а S может быть пустым.

Доказательство PL зависит от того, что каждому регулярному языку соответствует некоторый DFA. Допустимый вход для этого DFA дольше, чем его количество (что соответствует L в лемме), должно привести к "loop:", чтобы повторить состояние. Вызовите это состояние X. Машина потребляет некоторую строку R, чтобы получить от начала до X, затем S, чтобы вернуться к X, затем T, чтобы перейти в принимающее состояние. Ну, добавление дополнительных копий S (или удаление S) на входе соответствует только другому числу "циклов" от X до X. Следовательно, будет также принята новая строка с дополнительными (или удаленными) копиями S.

Так как каждое RL должно удовлетворять PL, доказательство того, что язык не является регулярным, продолжается, показывая, что оно противоречит PL. Для нашего языка это не сложно. Предположим, вы пытаетесь убедить меня, что язык L = a^k b a^k b удовлетворяет PL. Поскольку он делает это, вы должны уметь дать мне некоторое значение N (см. Выше): количество состояний в гипотетическом DFA, которое распознает L. В этот момент я скажу: "Хорошо, г-н Регулярный парень, рассмотрите строка B = a^N b a^N b." Если L является регулярным, B должен привести к тому, что этот DFA (независимо от того, как он выглядит) должен быть петлей в пределах первых N символов, которые должны быть все a s! Таким образом, цикл (строка S выше) также состоит из всех a s. С этим я могу сразу показать, что ваше утверждение о регулярности L является ложным. Я просто решил обойти петлю во второй раз. Это заставит ваш гипотетический DFA принять новую строку a^M b a^N b, где M > N, потому что я добавил a в свою первую половину. Ой! Эта новая строка не находится в L, поэтому PL не является истиной в конце концов. Поскольку я могу делать этот трюк каждый раз, независимо от того, что вы предоставили N, PL не может удерживать L, и L не может быть регулярным в конце концов.

Поскольку это не является регулярным, теорема Клини говорит нам, что нет DFA или FA, а также не "чистое" регулярное выражение, которое описывает его.

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

NB: Оба из них не оправданы доказательством того, что back refs делает распознавание NP полным. Они просто говорят очень строгим образом, что обратные ссылки добавляют реальную сложность к чистым регулярным выражениям. Они позволяют использовать языки, которые не могут быть распознаны ни на одной машине с конечной памятью, ни с какой-либо бесконечно большой памятью LIFO. Я оставлю доказательство полноты NP для других.

Ответ 2

NFA и DFA Конечные автоматы, также называемые конечным автоматом, которые являются "абстрактной машиной, которая может находиться в одном из конечного числа состояний" [1]. Обратите внимание на конечное число состояний.

Быстрые алгоритмы NFA/DFA, обсуждаемые в связанной статье, Соответствие регулярного выражения может быть простым и быстрым, бывают быстрыми, потому что они могут работать с конечным числом состояний (независимо от длины ввода), как описано в статье.

Введение обратных ссылок делает число состояний (почти) "бесконечным" (в худшем случае около 256 ⁿ где n - длина ввода). Число состояний растет, потому что каждое возможное значение каждой обратной ссылки становится состоянием автоматов.

Таким образом, использование конечного автомата больше не подходит/возможно, и вместо этого должны использоваться алгоритмы обратного отслеживания.

Ответ 3

В этом уроке есть несколько отличных примеров:
http://www.regular-expressions.info/brackets.html

Частный случай, который вас заинтересует, показан в разделе "Откат в группы захвата" . Он объяснил, как весь матч можно отдать несколько раз до того, как будет найдено окончательное соответствует всему регулярному выражению. Кроме того, стоит отметить, что это может привести к неожиданным совпадениям.

Ответ 4

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