Предположения
Основываясь на вашем вопросе и последующих комментариях, вы хотите использовать общий метод разбиения предложения на непересекающиеся, совпадающие подстроки с отбрасыванием несовпадающих частей предложения. Вы также, кажется, хотите оптимальную производительность во время выполнения. Также я предполагаю, что у вас уже есть алгоритм для преобразования регулярного выражения в форму DFA. Кроме того, я предполагаю, что вы делаете это обычным методом: сначала создать NFA и преобразовать его путем построения подмножества в DFA, поскольку я не знаю ни одного другого способа сделать это.
Прежде чем вы начнете гоняться за тенями, убедитесь, что вы пытаетесь применить правильный инструмент для работы. Любое обсуждение регулярных выражений почти всегда искажается тем фактом, что люди используют регулярные выражения для гораздо большего, чем они на самом деле оптимальны. Если вы хотите получить преимущества регулярных выражений, убедитесь, что вы используете регулярное выражение, а не что-то более широкое. Если то, что вы хотите сделать, не может быть несколько закодировано в самом регулярном выражении, то вы не сможете воспользоваться преимуществами алгоритмов регулярного выражения (полностью)
Очевидным примером является то, что никакая хитрость не позволит FSM или любому алгоритму предсказывать будущее. Например, выражение типа (a*b)|(a) при сопоставлении со строкой aaa ..., где многоточие является частью выражения, еще не отсканированного , поскольку пользователь еще не набрал их , не может дать Вы каждая возможная правильная подгруппа.
Для более подробного обсуждения реализаций регулярных выражений, и в частности NFA Томпсона, пожалуйста, проверьте эту ссылку , которая описывает простую реализацию C с некоторыми умными оптимизациями.
Ограничения обычных языков
O (n) и Space (O (1)) гарантии алгоритмов регулярных выражений - довольно узкое утверждение. В частности, обычный язык - это набор всех языков, которые могут быть распознаны в постоянном пространстве . Это различие важно. Любое усовершенствование алгоритма, которое делает что-то более сложное, чем принятие или отклонение предложения, вероятно, будет работать на большем наборе языков, чем на обычном. Вдобавок ко всему, если вы можете показать, что для реализации какого-либо усовершенствования требуется больше, чем постоянное пространство, то вы также находитесь вне гарантии производительности. При этом, мы все равно можем сделать очень многое, если будем очень осторожны, чтобы сохранить наш алгоритм в рамках этих узких ограничений.
Очевидно, что это исключает все, что мы могли бы сделать с рекурсивным возвратом. Стек не имеет постоянного пространства. Даже поддержание указателей в предложении было бы многословно, так как мы не знаем, как долго это предложение может быть. Достаточно длинное предложение переполняет любой целочисленный указатель. Мы не можем создавать новые состояния для автомата, поскольку мы идем, чтобы обойти это. Все возможные состояния (и несколько невозможных) должны быть предсказуемыми, прежде чем подвергать распознаватель любым входным данным, и эта величина должна быть ограничена некоторой константой, которая может варьироваться для конкретного языка, которому мы хотим соответствовать, но никакой другой переменной.
Это по-прежнему оставляет место для добавления дополнительного поведения. Обычный способ получить больше пробега - добавить несколько дополнительных аннотаций для случаев, когда происходят определенные события при обработке, например, когда подвыражение началось или прекратило сопоставление. Поскольку нам разрешена только постоянная обработка пространства, это ограничивает количество совпадений подвыражений, которые мы можем обработать. Обычно это означает последний экземпляр этого подвыражения. Вот почему, когда вы запрашиваете подгруппу, совпадающую с (a|)*, вы всегда получаете пустую строку, потому что за любой последовательностью a неявно следует бесконечное количество пустых строк.
Другое распространенное улучшение - делать какие-то умные вещи между состояниями. Например, в регулярном выражении Perl \b соответствует пустой строке, но только если предыдущий символ является символом слова, а следующий - нет, или наоборот. Для этого подходят многие простые утверждения, в том числе операторы привязки общей линии, ^ и $. Утверждения в прямом и обратном взглядах также возможны, но гораздо сложнее.
При обсуждении различий между различными распознавателями обычного языка, стоит уточнить, говорим ли мы о распознавании совпадений или распознавании поиска, причем первый вариант принимается, только если все предложение написано на языке, а последний принимает, если есть подстрока в предложении на языке. Они эквивалентны в том смысле, что если какое-либо выражение E принято методом поиска, то .*(E).* принимается в методе сопоставления.
Это важно, потому что мы могли бы прояснить, принимает ли выражение типа a*b|a aa или нет. В методе поиска это так. Любой токен будет соответствовать правой стороне дизъюнкции. Это не соответствует, тем не менее, потому что вы никогда не могли бы получить это предложение, шагая по выражению и генерируя токены из переходов, по крайней мере, за один проход. По этой причине я буду говорить только о семантике совпадений. Очевидно, что если вам нужна семантика поиска, вы можете изменить выражение с помощью .* 's
Примечание. Язык, определяемый выражением E|.*, на самом деле не очень управляемый язык, независимо от подъязыка E потому что он соответствует всем возможным предложениям. Это представляет собой реальную проблему для распознавателей регулярных выражений, потому что они действительно подходят только для распознавания языка или подтверждения того, что предложение не на том же языке, а не для выполнения какой-либо более конкретной работы.
Реализация средств распознавания обычного языка
Обычно существует три способа обработки регулярного выражения. Все три начинают то же самое, преобразовывая выражение в NFA. Этот процесс создает одно или два состояния для каждого производственного правила в исходном выражении. Правила очень просты. Вот несколько грубых ascii art: обратите внимание, что a - это любой отдельный буквенный символ в алфавите языка, а E1 и E2 - любое регулярное выражение. Epsilon (ε) - это состояние с входами и выходами, но оно игнорирует поток символов и не потребляет никаких входных данных.
a ::= > a ->
E1 E2 ::= >- E1 ->- E2 ->
/---->
E1* ::= > --ε <-\
\ /
E1
/-E1 ->
E1|E2 ::= > ε
\-E2 ->
И это все! Общие применения, такие как E +, E ?, [abc], эквивалентны EE *, (E |), (a | b | c) соответственно. Также обратите внимание, что мы добавляем для каждого правила производства очень небольшое количество новых состояний. Фактически каждое правило добавляет ноль или одно состояние (в этой презентации). символы, квантификаторы и дисфункция - все добавляют только одно состояние, а конкатенация не добавляет ни одного. Все остальное делается путем обновления указателей конца фрагментов для запуска указателей других состояний или фрагментов.
Эпсилон-переходные состояния важны, потому что они неоднозначны. При обнаружении, должен ли аппарат изменить состояние на один следующий за другим или другой? это должно изменить состояние вообще или остаться на месте? Вот почему эти автоматы называются недетерминированными. Решение состоит в том, чтобы автоматический переход в состояние right , в зависимости от того, что позволяет ему соответствовать наилучшему. Таким образом, сложная часть состоит в том, чтобы выяснить, как это сделать.
Есть два основных способа сделать это. Первый способ - попробовать каждый. Следуйте первому варианту, и если это не сработает, попробуйте следующий. Это рекурсивный возврат, появляется в нескольких (и заметных) реализациях. Для правильно созданных регулярных выражений эта реализация делает очень мало дополнительной работы. Если выражение немного более запутанное, рекурсивный возврат очень и очень плох, O (2 ^ n).
Другой способ сделать это - попробовать оба варианта параллельно. При каждом эпсилон-переходе добавляйте к набору текущих состояний оба состояния, которые предлагает эпсилон-переход. Поскольку вы используете набор, одно и то же состояние может появляться несколько раз, но вам нужно отслеживать его только один раз, независимо от того, находитесь вы в этом состоянии или нет. Если вы дойдете до того, что для определенного состояния нет возможности следовать, просто проигнорируйте его, этот путь не совпадает. Если больше нет состояний, тогда все выражение не совпадает. как только любое состояние достигает конечного состояния, все готово.
Именно из-за этого объяснения объем работы, которую мы должны сделать, немного вырос. Мы перешли от необходимости отслеживать одно состояние к нескольким. На каждой итерации нам, возможно, придется обновлять порядок m указателей состояния, включая такие вещи, как проверка на наличие дубликатов. Также увеличился объем необходимого хранилища, поскольку теперь это уже не один указатель на одно возможное состояние в NFA, а целый их набор.
Однако это не так близко, как кажется. Во-первых, число состояний ограничено количеством произведений в исходном регулярном выражении. Отныне мы будем называть это значение m , чтобы отличать его от количества символов на входе, которое будет n , Если два указателя состояния в конечном итоге переходят в одно и то же новое состояние, вы можете отказаться от одного из них, потому что независимо от того, что еще произойдет, они оба будут следовать по одному и тому же пути оттуда. Это означает, что количество указателей состояний, которое вам нужно, ограничено количеством состояний, поэтому оно равно m .
Это большая победа в худшем случае по сравнению с возвратом. После того, как каждый персонаж будет использован из ввода, вы будете создавать, переименовывать или уничтожать не более m указателей состояния. Нет никакого способа создать регулярное выражение, которое заставит вас выполнить больше, чем столько инструкций (иногда некоторый постоянный фактор в зависимости от вашей конкретной реализации), или заставит вас выделять больше места в стеке или куче.
Этот NFA, одновременно в некотором подмножестве его m состояний, можно рассматривать как некоторый другой конечный автомат, состояние которого представляет собой набор состояний, в которых он может моделировать NFA. Каждое состояние этого FSM представляет одно элемент из набора власти государств NFA. Это именно реализация DFA, используемая для сопоставления регулярных выражений.
Преимущество использования этого альтернативного представления состоит в том, что вместо обновления указателей состояний m вам нужно обновить только один. У него также есть недостаток, так как он моделирует блок питания из состояний m , фактически он имеет до 2 m состояний. Это верхний предел, потому что вы не моделируете состояния, которые не могут произойти, например, выражение a|b имеет два возможных состояния после чтения первого символа: либо для того, чтобы видеть a, либо для того, чтобы иметь видел b. Независимо от того, что вы вводите, он не может находиться в обоих этих состояниях одновременно, поэтому набор состояний не отображается в DFA. Фактически, поскольку вы устраняете избыточность эпсилон-переходов, многие простые DFA на самом деле становятся МЕНЬШЕ, чем NFA, которые они представляют, но просто нет способа гарантировать это.
Чтобы не допустить слишком большого роста состояний, решение, используемое в нескольких версиях этого алгоритма, состоит в том, чтобы генерировать только те состояния DFA, которые вам действительно нужны, и, если вы получаете слишком много, откажитесь от тех, которые вы недавно не использовали , Вы всегда можете создать их снова.
От теории к практике
Многие практические применения регулярных выражений включают отслеживание позиции ввода. Это технически обман, так как ввод может быть произвольно длинным. Даже если вы используете 64-битный указатель, ввод может быть длиной 2 64 + 1 символов, и вы потерпите неудачу. Ваши указатели позиции должны расти с длиной ввода, и теперь вашему алгоритму теперь требуется больше, чем постоянное пространство для выполнения. На практике это не имеет значения, потому что если ваше регулярное выражение в конечном итоге пробилось через такой большой объем ввода, вы, вероятно, не заметите, что оно потерпит неудачу, потому что вы прервете его задолго до этого.
Конечно, мы хотим сделать больше, чем просто принять или отклонить входные данные в целом. Наиболее полезный вариант этого заключается в извлечении подсовпадений, чтобы определить, какая часть ввода соответствует определенному разделу исходного выражения. Простой способ добиться этого - добавить эпсилон-переход для каждой из открывающих и закрывающих фигурных скобок в выражении. Когда симулятор FSM обнаруживает одно из этих состояний, он аннотирует указатель состояния информацией о том, где на входе он находился в момент, когда он столкнулся с этим конкретным переходом. Если тот же указатель возвращается к этому переходу во второй раз, старая аннотация отбрасывается и заменяется новой аннотацией для новой позиции ввода. Если указатели двух состояний с противоречивыми аннотациями сворачиваются в одно и то же состояние, аннотация более поздней позиции ввода снова побеждает.
Если вы придерживаетесь реализаций Thompson NFA или DFA, то в действительности не существует понятия жадного или не жадного сопоставления. Алгоритм обратного отслеживания должен дать подсказку о том, должен ли он начинаться с попытки сопоставления, насколько это возможно, и рекурсивной попытки с меньшими затратами, или с минимальными попытками, и с рекурсивной попыткой большего, когда он терпит неудачу с первой попытки. Метод Томпсона NFA пробует все возможные величины одновременно. С другой стороны, вы все еще можете использовать некоторые жадные / не жадные намеки. Эта информация будет использоваться для определения того, следует ли отдавать предпочтение новым или более старым аннотациям субсоответствия, чтобы захватить только правую часть ввода.
Другим практическим улучшением являются утверждения, производства, которые не потребляют ввод, но совпадают или отклоняются на основе некоторого аспекта позиции ввода. Например, в регулярном выражении perl, \b указывает, что ввод должен содержать границу слова в этой позиции, так что только что подобранный символ должен быть символом слова, но следующий символ не должен быть, или наоборот. Опять же, мы управляем этим, добавляя эпсилон-переход со специальными инструкциями к симулятору. Если утверждение проходит, указатель состояния продолжается, в противном случае он отбрасывается.
Утверждения с заглядыванием вперед и назад могут быть достигнуты с помощью немного больше работы. Типичное утверждение за кадром r0(?<=r1)r2 преобразуется в два отдельных выражения: .*r1 и r0εr2. Оба выражения применяются для ввода. Обратите внимание, что мы добавили .* к выражению утверждения, потому что на самом деле нам все равно, где оно начинается. Когда симулятор встречает эпсилон во втором сгенерированном фрагменте, он проверяет состояние первого фрагмента. Если этот фрагмент находится в состоянии, в котором он мог бы принять прямо здесь, утверждение проходит с указателем состояния, перетекающим в r2, но в противном случае он терпит неудачу, и оба фрагмента продолжаются, со вторым отбрасыванием указателя состояния при переходе в эпсилон.
Lookahead также работает с использованием дополнительного фрагмента регулярного выражения для утверждения, но это немного сложнее, потому что, когда мы достигаем точки на входе, где утверждение должно быть успешным, ни один из соответствующих символов не встречался (во взгляде сзади). бывает, все они встречались). Вместо этого, когда симулятор достигает утверждения, он запускает указатель в начальном состоянии подвыражения подтверждения и аннотирует указатель состояния в основной части моделирования, чтобы он знал, что он зависит от указателя подвыражения. На каждом шаге симуляция должна проверять, что указатель состояния, от которого она зависит, все еще совпадает. Если он не находит, он терпит неудачу, где бы он ни находился. Вам не нужно хранить больше копий указателей состояния подвыражений утверждения, чем вы делаете для основной части, если два указателя состояния в утверждении находятся в одном и том же состоянии, то указатели состояния, от которых зависит каждый из них, будут иметь одинаковые значения. судьба, и может быть повторно аннотирована, чтобы указать на единственный указатель, который вы держите.
Хотя мы добавляли специальные инструкции для переходов в эпсилон, неплохо было бы предложить инструкцию, заставляющую симулятор приостанавливать время от времени, чтобы пользователь мог видеть, что происходит. Всякий раз, когда симулятор сталкивается с таким переходом, он оборачивает свое текущее состояние в какой-то пакет, который можно вернуть вызывающему, осмотреть или изменить, а затем возобновить с того места, где он остановился. Это можно использовать для интерактивного сопоставления ввода, поэтому, если пользователь вводит только частичное совпадение, симулятор может запросить дополнительный ввод, но если пользователь вводит что-то недопустимое, симулятор пуст и может пожаловаться пользователю. Другая возможность состоит в том, чтобы выдавать каждый раз, когда сопоставляется подвыражение, что позволяет вам просматривать каждый подстрок во входных данных. Это не может быть использовано, чтобы исключить некоторые совпадения. Например, если вы попытались сопоставить ((a)*b) с aaa, вы могли бы увидеть три подспаривания для a, даже если все выражение в конечном итоге завершится ошибкой, потому что нет b и нет подспаривания для соответствующих b
Наконец, может быть способ изменить это для работы с обратными ссылками. Даже если он изящен, он наверняка будет неэффективным, в частности, регулярные выражения плюс обратные ссылки есть в NP-Complete, поэтому я даже не буду пытаться придумать способ сделать это, потому что нас интересует (здесь) (асимптотически) ) эффективные возможности.