lookaround влияет, какие языки могут быть подобраны регулярными выражениями?

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

Доказательство относительно простое, но алгоритм перевода регулярного выражения, содержащего lookarounds, в регулярное выражение без lookaround довольно запутанный.

Во-первых: обратите внимание, что регулярное выражение всегда можно отрицать (над конечным алфавитом). Имея конечный автомат состояний, который распознает язык, порождаемый выражением, вы можете просто поменять все принимающие состояния на непринимающие, чтобы получить FSA, который распознает именно отрицание этого языка, для которого существует семейство эквивалентных регулярных выражений.

Второе: поскольку регулярные языки (и, следовательно, регулярные выражения) замкнуты по отрицанию, они также замкнуты по пересечению, поскольку A intersect B = neg ( neg(A) union neg(B)) по законам де Моргана. Другими словами, если даны два регулярных выражения, то можно найти другое регулярное выражение, которое соответствует обоим.

Это позволяет моделировать поисковые выражения. Например, u(?=v)w соответствует только тем выражениям, которые будут соответствовать uv и uw.

Для отрицательного поиска нужен эквивалент регулярного выражения теоретико-множественного A\B, то есть просто A intersect (neg B) или эквивалентно neg (neg(A) union B). Таким образом, для любых регулярных выражений r и s можно найти регулярное выражение r-s, которое соответствует тем выражениям, которые соответствуют r, но не соответствуют s. В терминах отрицательной наглядности: u(?!v)w соответствует только тем выражениям, которые соответствуют uw - uv.

Есть две причины, по которым полезно использовать lookaround.

Во-первых, потому что отрицание регулярного выражения может привести к чему-то гораздо менее аккуратному. Например, q(?!u)=q($|[^u]).

Во-вторых, регулярные выражения делают больше, чем просто сопоставление выражений, они также потребляют символы из строки - или, по крайней мере, так нам нравится думать о них. Например, в python мне важны .start() и .end(), поэтому, конечно:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

В-третьих, и я думаю, это довольно важная причина, отрицание регулярных выражений не очень хорошо ложится на конкатенацию. neg(a)neg(b) - это не то же самое, что neg(ab), что означает, что вы не можете перевести поиск из контекста, в котором вы его нашли - вам придется обрабатывать всю строку. Полагаю, это делает его неприятным для работы и ломает интуицию людей о регулярных выражениях.

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

EDIT

Приношу свои извинения за то, что не выразился яснее: Я не верю, что можно доказать регулярность регулярных выражений + обходных путей с помощью структурной индукции, мой пример с u(?!v)w был просто примером, причем простым. Причина, по которой структурная индукция не сработает, заключается в том, что обходчики ведут себя некомпозиционно - то, что я пытался сказать об отрицаниях выше. Я подозреваю, что любое прямое формальное доказательство будет содержать много грязных деталей. Я пытался придумать простой способ показать это, но не могу придумать ни одного.

Для иллюстрации, используя первый пример Джоша ^([^a]|(?=..b))*$, это эквивалентно 7 состояниям DFSA со всеми состояниями, принимающими:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

Регулярное выражение только для состояния A выглядит так:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

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

Отвечая на комментарий Джоша - да, я действительно считаю, что наиболее прямой способ доказать эквивалентность - это FSA. Что делает это более сложным, так это то, что обычный способ построения FSA - это недетерминированный автомат - гораздо проще выразить u|v как просто автомат, построенный из автоматов для u и v с эпсилоновым переходом к ним обоим. Конечно, это эквивалентно детерминированной машине, но с риском экспоненциального раздувания состояний. В то время как отрицание гораздо проще сделать с помощью детерминированной машины.

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

Мои извинения за то, что не предоставил конструкцию.

ДАЛЬНЕЙШЕЕ РЕДАКТИРОВАНИЕ: Я нашел сообщение в блоге, в котором описывается алгоритм генерации DFA из регулярного выражения, дополненного обходными путями. Он интересен тем, что автор расширяет идею NFA-e с "помеченными эпсилоном переходами" очевидным способом, а затем объясняет, как преобразовать такой автомат в DFA.

Я думал, что нечто подобное можно было бы сделать, но я рад, что кто-то это написал. Это было выше моих сил - придумать что-то настолько изящное.

У меня такое ощущение, что здесь задаются два разных вопроса:

• Являются ли движки Regex, которые включают в себя "поиск вокруг" больше мощнее, чем движки Regex, которые этого не делают?
• Осматривается ли предоставить движку Regex возможность анализировать языки, сложнее, чем те, которые сгенерированы из Хомского Тип 3 - Регулярная грамматика ?

Практически ответ на первый вопрос положительный. Lookaround даст движку Regex, который использует эту функцию принципиально больше, чем та, которая не использует. Это потому что он предоставляет более богатый набор «якорей» для процесса сопоставления. Lookaround позволяет вам определить все Regex как возможную точку привязки (утверждение нулевой ширины). Вы можете получить довольно хороший обзор возможностей этой функции здесь .

Lookaround, хотя и мощный, не поднимает движок Regex за пределы теоретических ограничения, налагаемые на него Грамматикой Типа 3. Например, вы никогда не сможете надежно анализировать язык на основе Context Free - Type 2 Grammar с использованием механизма Regex оснащен обзорным. Механизмы регулярных выражений ограничены мощностью конечной автоматики и это в корне ограничивает выразительность любого языка, который они могут анализировать, до уровня грамматики типа 3. Независимо от того сколько «трюков» добавлено в ваш движок Regex, языков, созданных с помощью Context Free Grammar всегда останется за пределами его возможностей. Синтаксический анализ без контекста - грамматика типа 2 требует автоматизации, чтобы «запомнить», где она находится. рекурсивная языковая конструкция.Все, что требует рекурсивной оценки правил грамматики, не может быть проанализировано с помощью Двигатели регулярных выражений.

Подводя итог: Lookaround предоставляет некоторые практические преимущества движкам Regex, но не «изменяет игру» на теоретический уровень.

РЕДАКТИРОВАТЬ

Есть ли грамматика со сложностью где-то между Типом 3 (Обычный) и Типом 2 (Без контекста)?

Я считаю, что ответ отрицательный. Причина в том, что нет теоретического предела размещается на размере NFA / DFA, необходимом для описания обычного языка. Он может стать сколь угодно большим и поэтому нецелесообразно использовать (или указывать). Вот где полезны уловки, такие как "взгляд вокруг". Они предоставить сокращенный механизм, чтобы указать, что в противном случае привело бы к очень большим / сложным NFA / DFA технические характеристики. Они не увеличивают выразительности Обычные языки, они просто делают их более практичными. Как только вы поймете эту точку, она станет ясно, что есть много "функций", которые можно добавить в движки Regex, чтобы сделать их более полезны в практическом смысле - но ничто не сделает их способными выйти за рамки пределы обычного языка.

Основное различие между обычным и контекстно-свободным языком заключается в том, что обычный язык не содержит рекурсивных элементов. Чтобы оценить рекурсивный язык, вам понадобится Push Down Автоматизация чтобы «запомнить», где вы находитесь в рекурсии. NFA / DFA не суммирует информацию о состоянии, поэтому не может обрабатывать рекурсию. Таким образом, с учетом нерекурсивного определения языка будет некоторое количество NFA / DFA (но не обязательно практическое выражение Regex), чтобы описать его.

Я согласен с другими сообщениями, что lookaround является регулярным (это означает, что он не добавляет никаких фундаментальных возможностей к регулярным выражениям), но у меня есть аргумент в его пользу, который, IMO, проще, чем другие, которые я видел.

Я покажу, что lookaround является регулярным, предоставив конструкцию DFA. Язык является регулярным тогда и только тогда, когда у него есть DFA, который его распознает. Обратите внимание, что Perl на самом деле не использует DFA внутри языка (подробнее см. в этой статье: http://swtch.com/~rsc/regexp/regexp1.html), но мы построим DFA для целей доказательства.

Традиционный способ построения DFA для регулярного выражения заключается в том, чтобы сначала построить NFA с помощью алгоритма Томпсона. Если даны два фрагмента регулярных выражений r1 и r2, алгоритм Томпсона предоставляет конструкции для конкатенации (r1r2), чередования (r1|r2) и повторения (r1*) регулярных выражений. Это позволяет построить НФА бит за битом, который распознает исходное регулярное выражение. Более подробную информацию см. в статье выше.

Чтобы показать, что положительный и отрицательный lookahead являются регулярными, я приведу конструкцию для конкатенации регулярного выражения u с положительным или отрицательным lookahead: (?=v) или (?!v). Только конкатенация требует особого подхода; обычные конструкции чередования и повторения работают нормально.

Конструкция как для u(?=v), так и для u(?!v) такова:

Другими словами, соедините каждое конечное состояние существующего НФА для u с состоянием принятия и с НФА для v, но модифицированным следующим образом. Функция f(v) определяется так:

• Пусть aa(v) - функция на НФА v, которая изменяет каждое состояние акцепта на "состояние антиакцепта". Состояние антиприема определяется как состояние, которое приводит к неудачному совпадению, если любой путь через NFA заканчивается в этом состоянии для данной строки s, даже если другой путь через v для s заканчивается в состоянии принятия.
• Пусть loop(v) - функция на НФА v, которая добавляет самопереход в любом состоянии принятия. Другими словами, как только путь приводит к состоянию принятия, этот путь может оставаться в состоянии принятия вечно, независимо от того, какой вход следует за ним.
• Для отрицательного lookahead, f(v) = aa(loop(v)).
• Для положительного lookahead, f(v) = aa(neg(v)).

Для интуитивного примера того, почему это работает, я использую регекс (b|a(?:.b))+, который является немного упрощенной версией регекса, предложенного мной в комментариях к доказательству Фрэнсиса. Если мы используем мою конструкцию вместе с традиционными конструкциями Томпсона, то получим:

Переходы es - это эпсилон-переходы (переходы, которые могут быть сделаны без потребления входных данных), а состояния антиприема помечены символом X. В левой половине графа вы видите представление (a|b)+: любой a или b переводит граф в состояние принятия, но также позволяет перейти обратно в состояние начала, чтобы мы могли сделать это снова. Но обратите внимание, что каждый раз, когда мы встречаем a, мы также попадаем в правую половину графа, где мы находимся в состоянии антипринятия, пока не встретим "any", за которым следует b.

Это не традиционный НФА, потому что традиционные НФА не имеют состояний анти-принятия. Однако мы можем использовать традиционный алгоритм NFA->DFA, чтобы преобразовать его в традиционный DFA. Алгоритм работает как обычно, когда мы моделируем несколько запусков NFA, заставляя наши состояния DFA соответствовать подмножествам состояний NFA, в которых мы могли бы находиться. Единственная изюминка заключается в том, что мы немного изменили правило для решения вопроса о том, является ли состояние DFA состоянием принятия (финальным) или нет. В традиционном алгоритме состояние DFA является состоянием принятия, если любое из состояний NFA было состоянием принятия. Мы модифицируем это, чтобы сказать, что состояние DFA является состоянием принятия тогда и только тогда, когда:

• = 1 состояние NFA является состоянием принятия, и

• 0 состояний НФА являются состояниями антиприема.

Этот алгоритм даст нам DFA, который распознает регулярное выражение с заблаговременным просмотром. Следовательно, lookahead является регулярным. Заметим, что lookbehind требует отдельного доказательства.