Изменения

В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить не НКА. Но после построения есть несколько вариантов:# можно Можно конвертировать его в детерминированный конечный автомат;.# можно Можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;.# можно Можно идти по автомату одновременно по всем возможным состояниям;.# можно Можно конвертировать НКА в ДКА лениво (на лету).

Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратной связиобратных ссылок (англ. ''back reference''). Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от <tex>1 </tex> до <tex>9</tex>. Например: <tex>\mathtt{(cat|dog)\1 backslash1}</tex> найдет <tex>\mathtt{catcat }</tex> или <tex>\mathtt{dogdog}</tex>, но никак не <tex>\mathtt{catdog }</tex> или <tex>\mathtt{dogcat}</tex>. Интересно, что с добавлением обратной связи обратных ссылок регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA НКА по регулярному выражению написанная на C, занимающая чуть меньше, чем <tex>400 </tex> строк и описанная в данной статье<ref>[https://swtch.com/~rsc/regexp/regexp1.html данной статьеArticle: Regular Expression Matching Can Be Simple And Fast]</ref>.

Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Представим НКА как связанный список структур состояний <tex>\mathrm{state}</tex> '''struct''' state: '''int''' c '''state''' out '''state''' out1 '''int''' lastlistКаждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа <tex>c</tex>.Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция <tex>\mathrm{re2post}</tex>, которая переписывает инфиксную форму регулярного выражения <tex>``a(bb)+a"</tex> в эквивалентную постфиксную вида <tex>``abb.+.a."</tex> (<tex>.</tex> используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой: '''struct''' frag: '''state''' start '''ptrList''' out<tex>\mathrm{start}</tex> указывает на стартовое состояние фрагмента, а <tex>\mathrm{out}</tex> {{---}} лист указателей на <tex>\mathrm{state*}</tex> указатели, которые ещё не соединены. Некоторые полезные функции для управления списком указателей: '''fun''' list1('''state''' outp): '''ptrList''' '''fun''' append('''ptrList''' l1, '''ptrList''' l2): '''ptrList''' '''fun''' patch('''ptrList''' l, '''state''' s)<tex>\mathrm{list1}</tex> создает новый список указателей состоящий из одного указателя <tex>\mathrm{outp}</tex>. <tex>\mathrm{append}</tex> конкатенирует два списка указателей, возвращая результат. <tex>\mathrm{patch}</tex> связывает повисшую стрелку в списке <tex>\mathrm{l}</tex> с состоянием <tex>\mathrm{s}</tex>.Используя данные примитивы и стек фрагментов можно реализовать построение НКА. '''fun''' post2nfa('''string''' postfix): '''state''' '''frag''' stack[1000], e1, e2, e '''state''' s '''for''' i = 0 '''to''' postfix.length - 1 '''switch'''(postfix[i]) '''case''' '.': <span style="color:#008000">// конкатенация</span> e2 = stack.pop() e1 = stack.pop() patch(e1.out, e2.start) push(frag(e1.start, e2.out)) '''break''' '''case''' '|': <span style="color:#008000">// альтернатива</span> e2 = stack.pop() e1 = stack.pop() s = state(Split, e1.start, e2.start) push(frag(s, append(e1.out, e2.out))) '''break''' '''case''' '?': <span style="color:#008000">// ноль или один</span> e = stack.pop() s = state(Split, e.start, NULL) push(frag(s, append(e.out, list1(s.out1)))) '''break''' '''case''' '*': <span style="color:#008000">// ноль или больше</span> e = stack.pop() s = state(Split, e.start, NULL) patch(e.out, s) push(frag(s, list1(s.out1))) '''break''' '''case''' '+': <span style="color:#008000">// один или больше</span> e = stack.pop() s = state(Split, e.start, NULL) patch(e.out, s) stack.push(frag(e.start, list1(s.out1))) '''break''' '''defaul'''t: <span style="color:#008000">// символ</span> s = state(postfix[i], NULL, NULL) push(frag(s, list1(s.out)) '''break''' e = stack.pop() patch(e.out, matchState) '''return''' e.start  Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве. '''struct''' List: '''state''' s '''int''' n Обход будет использовать два списка: <tex>\mathrm{cList}</tex> набор состояний, в которых уже находится, и <tex>\mathrm{nList}</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует <tex>\mathrm{cList}</tex> стартовым состоянием и пошагово проходит. '''fun''' match('''state''' start, '''string''' s): '''int''' '''List''' cList, nList, t '''cList''' = startList(start, l1) '''nList''' = l2 '''for''' i = 0 '''to''' s.length - 1 step(cList, s[i], nList) t = cList cList = nList nList = t '''return''' isMatch(cList)Чтобы избежать преаллокаций на каждой итерации цикла, <tex>\mathrm{match}</tex> использует два преаллоцированных списка <tex>\mathrm{l1}</tex> и <tex>\mathrm{l2}</tex> как <tex>\mathrm{cList}</tex> и <tex>\mathrm{nList}</tex>, и меняет их на каждом шаге.  Если список последних вершин содержит терминальную вершину, то строка распознана.  '''fun''' isMatch('''List''' l): '''int''' '''int''' i '''for''' i = 0 '''to''' l.n - 1 '''if''' (l.s[i] == matchState) '''return''' 1 '''return''' 0  <tex>\mathrm{addState}</tex> добавляет состояние в список, но только если их ещё не было в нем.  '''fun''' addState('''List''' l, '''state''' s): '''if''' (s == NULL || s.lastlist == listid) '''return''' s.lastlist = listid '''if'''(s.c == split) addState(l, s.out) addState(l, s.out1) '''return''' l.s[l.n++] = s <tex>\mathrm{startList}</tex> создает начальный список состояний и добавляет туда стартовое состояние.  '''fun''' startList('''state''' s, '''List''' l): '''List''' listid++ l.n = 0 addState(l, s) '''return''' l <tex>\mathrm{step}</tex> вычисляет по символу, использую список текущих состояний <tex>\mathrm{cList}</tex> следующий список <tex>\mathrm{nList}</tex>.  '''fun''' step('''List''' client, '''int''' c, '''List''' nList) '''int''' i '''state''' s listid++ nList.n = 0 '''for''' i = 0 '''to''' cList.n - 1 s = cList.s[i] '''if''' (s.c == c) addState(nList, s.out)

Набор символов в квадратных скобках <tex>[ ] </tex> именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны <tex>\mathrm{[0-9]}, \mathrm{[a-z]}</tex>, а также существуют дополнительные символьные классы <tex>\mathtt{[[:upper:]]}, \mathtt{[[:word:]]}</tex>.

Позволяет установить точное соотвествие соответствие повторов равное числу <tex>n </tex> {{- --}} <tex>{n}; </tex> <tex>{n,m} </tex> {{--- }} не меньше чем <tex>n</tex>, и не больше чем <tex>m</tex>. <tex>{n,} </tex> {{- --}} <tex>n </tex> и больше. Можно найти эквиваленты символам <tex>*, +, ?</tex>. С помощью символов <tex>\{ \}</tex>

| <tex>?</tex>| <tex>{0,1}</tex>

| <tex>+</tex>| <tex>{1,}</tex>

| <tex>*</tex>| <tex>\{\}</tex>

В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. ''greedy''). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение <tex>(<.*>) </tex> найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.

| <tex>*</tex>| <tex>*?</tex>

| <tex>+</tex>| <tex>+?</tex>

| <tex>\{n,\}</tex>| <tex>\{n,\}?</tex>|}Эту проблему можно решить двумя способами. Учитывать символы, не соответствующие желаемому образцу ( <tex><[^>]*></tex> для вышеописанного случая).Определить квантификатор как нежадный (ленивый, англ. ''lazy'') {{---}} большинство реализаций позволяют это сделать, добавив после него знак вопроса. ==== Ревнивая квантификация (Сверхжадная) ====В отличие от обычной (жадной) квантификации, ревнивая (англ. ''possessive'') квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения. Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.{| class="wikitable"! Жадный! Ревнивый|-| <tex>*</tex>| <tex>*+</tex>|-| <tex>?</tex>| <tex>?+</tex>|-| <tex>+</tex>| <tex>++</tex>|-| <tex>\{n,\}</tex>| <tex>\{n,\}+</tex>

[Gabriel Gonzalez <ref>[ https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez {{---}} Regex in Haskell]] </ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в <tex>480 </tex> раз медленеемедленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:* вместо <tex>\mathrm{Set Int }</tex> использовал <tex>\mathrm{Integer}</tex>, а также использовал битовые операции, в результате производительность выросла в <tex>5 </tex> раз* использовал <tex>\mathrm{Word }</tex> вместо <tex>\mathrm{Integer}</tex>, ещё в <tex>8 </tex> раз быстрее* а также использовал <tex>\mathrm{ByteString }</tex> оптимизации, что увеличило производительность ещё <tex>3 </tex> раза.В итоге его реализация оказалась всего в <tex>4 </tex> раза медленее медленнее grep. Но это не предел, у него получилось реализовать параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автоматData-Parallel Finite-State Machines] </ref> и сделать свою реализацию в <tex>1.5 </tex> раза быстрее, чем grep.

* использовать повторение <tex>("``+","``*") </tex> для достаточно сложных подвыражений;

* <tex>(a+)+</tex>* <tex>([a-zA-Z]+)*</tex>* <tex>(a|aa)+</tex>* <tex>(a|a?)+</tex>* <tex>(.*a)\{x11,\} for x </tex> 10Все эти выражения чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaaaa</tex>.

# RegExLib, email validation <ref>[http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (RegEx for email validation)] </ref> {{- --}} '''выделенная''' часть является вредоносной<br /><code>^([a-zA-Z0-9])'''(([\-.]|[_]+)?([a-zA-Z0-9]+))*'''(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$</code># OWASP Validation Regex Repository <ref>[http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository]</ref>, Java Classname {{- --}} '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>Эти два примера также чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaa</tex>.

* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State state Machines]