17
правок
Изменения
fix some points
== Реализация регулярных выражений в современных языках ==
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:
# можно Можно конвертировать его в детерминированный конечный автомат;.# можно Можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;.# можно Можно идти по автомату одновременно по всем возможным состояниям;.# можно Можно конвертировать НКА в ДКА лениво (на лету).
Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.
{| cellpadding="1" style="margin-left: auto; margin-right: auto;"
|[[Файл:RegExp.png|779px|thumb|regular expression and text size n <tex>a?^na^n</tex> matching <tex>a^n</tex>]]
|}
Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках 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>. Интересно, что с добавлением обратной связи обратных ссылок регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения НКА по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в [https://swtch.com/~rsc/regexp/regexp1.html данной статье].
=== Построение НКА ===
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Для примера напишем программу на '''C''', представим НКА как связанный список структур состояний '''State'''<tex>\mathrm{state}</tex> '''struct''' Statestate
{
'''int''' c;
'''Statestate''' *out; '''Statestate''' *out1;
'''int''' lastlist;
};
Каждый '''Statestate''' представляет один из фрагментов НКА, зависящий от символа c.
Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция re2post, которая переписывает инфиксную форму регулярного выражения "a(bb)+a" в эквивалентную постфиксную вида "abb.+.a." (. используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
'''struct''' Fragfrag
{
'''Statestate''' *start; '''PtrlistptrList''' *out;
};
'''Startstart''' указывает на стартовое состояние фрагмента, а '''out''' - лист указателей на '''Statestate*''' указатели, которые ещё не соединены.
Некоторые полезные функции для управления списком указателей:
'''PtrlistptrList''' *list1('''Statestate''' **outp); '''PtrlistptrList''' *append('''PtrlistptrList''' *l1, '''PtrlistptrList''' *l2); '''void''' patch('''PtrlistptrList''' *l, '''Statestate''' *s);'''List1list1''' создает новый список указателей состоящий из одного указателя '''outp'''. '''Appendappend''' конкатенирует два списка указателей, возвращая результат. '''Patchpatch''' связывает повисшую стрелку в списке '''l''' с состоянием '''s'''.
Используя данные примитивы и стек фрагментов можно реализовать построение НКА.
'''Statestate*''' post2nfa('''char''' *postfix)
{
'''char''' *p;
'''Fragfrag''' stack[1000], *stackp, e1, e2, e; '''Statestate''' *s;
#define push(s) *stackp++ = s
#define pop() *--stackp
'''for''' (p = postfix; *p; p++){
'''switch'''(*p){
'''defaul'''t: <span style="color:#008000">// символ</span> s = '''state'''(*p, NULL, NULL) '''push'''('''frag'''(s, list1(&s->out));
'''break''';
'''case''' '.': <span style="color:#008000">// конкатенация</span> e2 = '''pop'''(); e1 = '''pop'''(); '''patch'''(e1.out, e2.start); '''push'''('''frag'''(e1.start, e2.out));
'''break''';
'''case''' '|': <span style="color:#008000">// альтернатива</span> e2 = '''pop'''(); e1 = '''pop'''(); s = '''state'''(Split, e1.start, e2.start); '''push'''('''frag'''(s, append(e1.out, e2.out)));
'''break''';
'''case''' '?': <span style="color:#008000">// ноль или один</span> e = '''pop'''(); s = '''state'''(Split, e.start, NULL); '''push'''('''frag'''(s, append(e.out, list1(&s->out1))));
'''break''';
'''case''' '*': <span style="color:#008000">// ноль или больше</span> e = '''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 = '''pop'''(); s = '''state'''(Split, e.start, NULL); '''patch'''(e.out, s); '''push'''('''frag'''(e.start, list1(&s->out1)));
break;
}
}
e = '''pop'''(); '''patch'''(e.out, matchstatematchState);
'''return''' e.start;
}
'''struct''' List
{
'''Statestate''' **s;
'''int''' n;
};
Обход будет использовать два списка: '''clistcList''' набор состояний, в которых уже находится, и '''nlistnList''' набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует '''clistcList''' стартовым состоянием и пошагово проходит. '''int''' match('''Statestate''' *start, '''char''' *s)
{
'''List''' *clistcList, *nlistnList, *t; '''clistcList''' = startliststartList(start, &l1); '''nlistnList''' = &l2;
'''for''' ( ; *s, s++) {
}
'''return''' ismatchisMatch(clistcList);
}
Чтобы избежать преаллокаций на каждой итерации цикла, match использует два преаллоцированных списка '''l1''' и '''l2''' как '''clistcList''' и '''nlistnList''', и меняет их на каждом шаге.
Если список последних вершин содержит терминальную вершину, то строка распознана.
'''int''' ismatchisMatch('''List''' *l)
{
'''int''' i;
'''for''' ('''int''' i = 0; i < l->n; i++) '''if''' (l->s[i] == matchstatematchState)
'''return''' 1;
'''return''' 0;
}
'''AddstateaddState''' добавляет состояние в список, но только если их ещё не было в нем.
'''void''' addstateaddState('''Lis'''t *l, '''Statestate''' *s)
{
'''if''' (s == NULL || s->lastlist == listid)
s->lastlist = listid;
'''if'''(s->c == split) {
'''return''';
}
}
'''StartliststartList''' создает начальный список состояний и добавляет туда стартовое состояние.
'''List*''' startliststartList('''Statestate''' *s, '''List''' *l)
{
listid++;
l->n = 0;
'''return''' l;
}
'''Stepstep''' вычисляет по символу, использую список текущих состояний '''clistcList''' следующий список '''nlistnList'''.
'''void''' step('''List''' *client, '''int''' c, '''List''' *nlistnList)
{
'''int''' i;
'''Statestate''' *s;
listid++;
'''if''' (s->c == c)
}
}
==== Символьные классы ====
Набор символов в квадратных скобках <tex>[ ] </tex> именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны <tex>\mathrm{[0-9]}, \mathrm{[a-z]}</tex>, а также существуют дополнительные символьные классы <tex>\mathtt{[[:upper:]]}, \mathtt{[[:word:]]}</tex>.
==== Квантификация. ====
Позволяет установить точное соответствие повторов равное числу <tex>n </tex> {{- --}} <tex>{n}</tex>; {n,m} {{--- }} не меньше чем n, и не больше чем m. {n,} {{- --}} n и больше. Можно найти эквиваленты символам <tex>*, +, ?</tex>. С помощью символов <tex>\{ \}</tex>
{| class="wikitable"
|-
==== Жадная и ленивая квантификация ====
В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение <tex>(<.*>) </tex> найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.
{| class="wikitable"
! Жадный
Эту проблему можно решить двумя способами.
Учитывать символы, не соответствующие желаемому образцу <tex>(<[^>]*></tex> для вышеописанного случая).Определить квантификатор как нежадный (ленивый, англ. lazy) — {{---}} большинство реализаций позволяют это сделать, добавив после него знак вопроса.
==== Ревнивая квантификация (Сверхжадная) ====
== ReDoS (regular expression denial of service) ==
Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:
* использовать повторение <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
Все эти выражения чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaaaa.
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
* [https://swtch.com/~rsc/regexp/regexp1.html Regular Expression Matching Can Be Simple And Fast]
* [https://en.wikipedia.org/wiki/ReDoS ReDos]
* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State state Machines]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
