Как смоделировать обратные ссылки, прогнозирование и просмотр в конечных автоматах?

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

Из того, что я прочитал в книге о фиолетовом драконе, я понял, что для имитации предпросмотра где регулярное выражение r сопоставляется тогда и только тогда, когда за соответствием следует совпадение регулярного выражения s , вы создаете недетерминированный конечный результат. автомат состояний, в котором / заменяется на ε . Можно ли создать детерминированный конечный автомат, который делает то же самое?$r/s$$r$$s$$/$$\varepsilon$

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

([ab]^*)\1$\{ww \mid w \in \{a,b\}^*\}$

В мире конечных автоматов нет ничего особенного, потому что здесь мы сопоставляем только целые входные данные. Поэтому особая семантика «просто проверяй, но не потребляй» не имеет смысла; вы просто объединяете и / или пересекаете проверяющие и потребляющие выражения и используете полученные автоматы. Идея состоит в том, чтобы проверять прогнозные или прогнозные выражения, пока вы «потребляете» входные данные, и сохранять результат в состоянии.

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

/(?=c)[ab]+/$\{a,b,c\}$$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ источник ]}

и вам придется

• $i$$q_2$$q_2$
• $i$$-1$$q_2$

Обратите внимание, что левая часть автомата является параллельным автоматом канонических автоматов для [abc]*и c(итерированных) соответственно.

$i$$j$$i$$j$

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

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

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

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

Я полагаюсь на описание на http://www.regular-expressions.info/lookaround.html . Механизмы регулярных выражений, которые поддерживают эту функцию (Perl, TCL, Python, Ruby, ...), похоже, все основаны на возврате (т. Е. Они поддерживают гораздо больший набор языков, чем обычные языки). Похоже, они реализуют эту функцию как относительно «простое» расширение обратного отслеживания, вместо того, чтобы пытаться создать реальные конечные автоматы для выполнения задачи.

Позитивный Lookahead

Синтаксис для положительного взгляда - (?=регулярное выражение) . Так, например, q(?=u)совпадает qтолько в том случае, если за ним следует u, но не совпадает с u. Я предполагаю, что они реализуют это с изменением на откат назад. Создайте FSM для выражения перед положительным прогнозом. Когда это совпадение, запомните, где оно закончилось, и запустите новый FSM, представляющий выражение в положительном прогнозе. Если это соответствует, то у вас есть «совпадение», но совпадение «заканчивается» как раз перед позицией, где началось положительное совпадение.

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

Негативный Lookahead

Синтаксис для отрицательного просмотра - (?!регулярное выражение) . Так, например, q(?!u)совпадения, qтолько если за ним не следует u. Это может быть либо qдругой символ, либо символ «за» qв самом конце строки. Я полагаю, что это реализуется путем создания NFA для выражения lookahead, которое выполняется только в том случае, если NFA не соответствует следующей строке.

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

Позитивный взгляд сзади

(?<=)(?=q)uuqq$n$$n$$n$

Вы могли бы реализовать это без возврата назад, взяв пересечение «string, заканчивающегося регулярным выражением », с любой частью регулярного выражения, которая предшествует оператору lookbehind. Это будет сложно, потому что регулярное выражение lookbehind, возможно, должно оглянуться назад, чем текущее начало ввода.

Отрицательный взгляд сзади

Синтаксис для отрицательного взгляда сзади - (?<!регулярное выражение) . Так, например, (?<!q)uсовпадает u, но только если ему не предшествует q. Так что это будет соответствовать uin umbrellaи uin doubt, но не uin quick. Опять же, это, кажется, делается путем вычисления длины регулярного выражения , резервного копирования такого количества символов, проверки на соответствие регулярному выражению , но теперь провал всего совпадения, если совпадает просмотр назад.

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

По крайней мере, для обратных ссылок это невозможно. Например, регулярное выражение (.*)\1представляет язык, который не является регулярным. Это означает, что невозможно создать конечный автомат (детерминированный или нет), который распознал бы этот язык. Если вы хотите доказать это формально, вы можете использовать лемму прокачки .

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

Сзади фиксированная ширина должна быть идеально возможной без возврата. Пусть n будет шириной. Начиная с точки в вашей NFA, где начинался просмотр, вы разделяли состояния, оглядываясь назад, так что каждый путь к просмотру сзади заканчивался состоянием из n символов, которое входило только в просмотр сзади. Затем добавьте заглядывание в начало этих состояний (и сразу же при необходимости составьте подграф из AFA в NFA).

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