Изменения

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

Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Для примера напишем программу на '''C''', представим Представим НКА как связанный список структур состояний <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};'''start''' </tex> указывает на стартовое состояние фрагмента, а '''<tex>\mathrm{out''' }</tex> {{--- }} лист указателей на '''<tex>\mathrm{state*''' }</tex> указатели, которые ещё не соединены.

'''ptrListfun''' *list1('''state''' **outp);: '''ptrList''' '''ptrListfun''' *append('''ptrList''' *l1, '''ptrList''' *l2);: '''ptrList''' '''voidfun''' 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>.

'''state*fun''' post2nfa('''charstring''' *postfix) { : '''charstate''' *p; '''frag''' stack[1000], *stackp, e1, e2, e; '''state''' *s; #define push(s) *stackp++ = s #define pop() *--stackp stackp = stack; '''for''' (p i = postfix; *p; p++){ 0 '''switchto'''(*p){postfix.length - 1 '''defaulswitch'''t: <span style="color:#008000">// символ</span> s = state(*p, NULL, NULLpostfix[i]) push(frag(s, list1(&s->out)); '''break'''; '''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> стартовым состоянием и пошагово проходит. '''intfun''' match('''state''' *start, '''charstring''' *s): '''int''' { '''List''' *cList, *nList, *t; '''cList''' = startList(start, &l1); '''nList''' = &l2; '''for''' ( ; *i = 0 '''to''' s, 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>, и меняет их на каждом шаге.

'''intfun''' isMatch('''List''' *l): '''int''' { '''int''' i; '''for''' (i = 0; i < '''to''' l.n ->n; i++)1 '''if''' (l->.s[i] == matchState) '''return''' 1; '''return''' 0; }

'''void''' addState('''Lis'''t *l, '''state''' *s) { '''if''' (s == NULL || s-<tex>lastlist == listid) '''return'''; s->lastlist = listid; '''if'''(s->c == split) \mathrm{ addState(l, s-}</tex>out); addState(lдобавляет состояние в список, s->out1); '''return'''; } l->s[l->n++] = s; }но только если их ещё не было в нем.

'''startListfun''' создает начальный список состояний и добавляет туда стартовое состояние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

'''List*''' <tex>\mathrm{startList('''state''' *s, '''List''' *l) { listid++; l-}</tex>n = 0; addState(l, s); '''return''' l; }создает начальный список состояний и добавляет туда стартовое состояние.

'''stepfun''' 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>.  '''cListfun''' 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>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>

| ^<tex> \wedge </tex>

| <tex>$</tex>

| <tex>\backslash b</tex>

| <tex>\backslash G</tex>

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

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

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

| <tex>\{n,\}</tex>| <tex>\{n,\}?</tex>

Учитывать символы, не соответствующие желаемому образцу ( <tex>(<[^>]*></tex> для вышеописанного случая).Определить квантификатор как нежадный (ленивый, англ. ''lazy'') {{---}} большинство реализаций позволяют это сделать, добавив после него знак вопроса.

В отличие от обычной (жадной) квантификации, ревнивая (англ. ''possessive'') квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.

| <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>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>.