17
правок
Изменения
Добавлен алгоритм на С
== Реализация регулярных выражений в современных языках ==
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить не НКА. Но после построения есть несколько вариантов:
# можно конвертировать его в детерминированный конечный автомат;
# можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;
|[[Файл:RegExp.png|779px|thumb|regular expression and text size n <tex>a?^na^n</tex> matching <tex>a^n</tex>]]
|}
Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратной связи. Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от 1 до 9. Например: '''(cat|dog)\1 ''' найдет '''catcat ''' или '''dogdog''', но никак не '''catdog ''' или '''dogcat'''. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA НКА по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в [https://swtch.com/~rsc/regexp/regexp1.html данной статье].
=== Построение НКА ===
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Для примера напишем программу на '''C''', представим НКА как связанный список структур состояний '''State''' '''struct''' State { '''int''' c; '''State''' *out; '''State''' *out1; '''int''' lastlist; }; Каждый '''State''' представляет один из фрагментов НКА, зависящий от символа c.Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция re2post, которая переписывает инфиксную форму регулярного выражения "a(bb)+a" в эквивалентную постфиксную вида "abb.+.a." (. используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой: '''struct''' Frag { '''State''' *start; '''Ptrlist''' *out; };'''Start''' указывает на стартовое состояние фрагмента, а '''out''' - лист указателей на '''State*''' указатели, которые ещё не соединены. Некоторые полезные функции для управления списком указателей: '''Ptrlist''' *list1('''State''' **outp); '''Ptrlist''' *append('''Ptrlist''' *l1, '''Ptrlist''' *l2); '''void''' patch('''Ptrlist''' *l, '''State''' *s);'''List1''' создает новый список указателей состоящий из одного указателя '''outp'''. '''Append''' конкатенирует два списка указателей, возвращая результат. '''Patch''' связывает повисшую стрелку в списке '''l''' с состоянием '''s'''.Используя данные примитивы и стек фрагментов можно реализовать построение НКА. '''State*''' post2nfa('''char''' *postfix) { '''char''' *p; '''Frag''' stack[1000], *stackp, e1, e2, e; '''State''' *s; #define push(s) *stackp++ = s #define pop() *--stackp stackp = stack; '''for''' (p = postfix; *p; p++){ '''switch'''(*p){ '''defaul'''t: // символ s = '''state'''(*p, NULL, NULL) '''push'''('''frag'''(s, list1(&s->out)); '''break'''; '''case''' '.': // конкатенация e2 = '''pop'''(); e1 = '''pop'''(); '''patch'''(e1.out, e2.start); '''push'''('''frag'''(e1.start, e2.out)); '''break'''; '''case''' '|': // альтернатива e2 = '''pop'''(); e1 = '''pop'''(); s = '''state'''(Split, e1.start, e2.start); '''push'''('''frag'''(s, append(e1.out, e2.out))); '''break'''; '''case''' '?': // ноль или один e = '''pop'''(); s = '''state'''(Split, e.start, NULL); '''push'''('''frag'''(s, append(e.out, list1(&s->out1)))); '''break'''; '''case''' '*': // ноль или больше e = '''pop'''(); s = '''state'''(Split, e.start, NULL); '''patch'''(e.out, s); '''push'''(frag(s, list1(&s->out1))); break; '''case''' '+': // один или больше 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, matchstate); '''return''' e.start; }
Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.
'''struct''' List
{
'''State''' **s;
'''int''' n;
};
Обход будет использовать два списка: '''clist''' набор состояний, в которых уже находится, и '''nlist''' набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует '''clist''' стартовым состоянием и пошагово проходит.
'''int''' match('''State''' *start, '''char''' *s)
{
'''List''' *clist, *nlist, *t;
'''clist''' = startlist(start, &l1);
'''nlist''' = &l2;
'''for''' ( ; *s, s++) {
'''step'''(clist, *s, nlist);
t = clist; clist = nlist; nlist = t;
}
'''return''' ismatch(clist);
}
Чтобы избежать преаллокаций на каждой итерации цикла, match использует два преаллоцированных списка '''l1''' и '''l2''' как '''clist''' и '''nlist''', и меняет их на каждом шаге.
Если список последних вершин содержит терминальную вершину, то строка распознана.
'''int''' ismatch('''List''' *l)
{
'''int''' i;
'''for''' ('''int''' i = 0; i < l->n; i++)
'''if''' (l->s[i] == matchstate)
'''return''' 1;
'''return''' 0;
}
'''Addstate''' добавляет состояние в список, но только если их ещё не было в нем.
'''void''' addstate('''Lis'''t *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;
}
'''Startlist''' создает начальный список состояний и добавляет туда стартовое состояние.
'''List*''' startlist('''State''' *s, '''List''' *l)
{
listid++;
l->n = 0;
'''addstate'''(l, s);
'''return''' l;
}
'''Step''' вычисляет по символу, использую список текущих состояний '''clist''' следующий список '''nlist'''.
'''void''' step('''List''' *client, '''int''' c, '''List''' *nlist)
{
'''int''' i;
'''State''' *s;
listid++;
nlist->n = 0;
'''for''' (i = 0; i < clist->n; i++) {
s = clist->s[i];
'''if''' (s->c == c)
'''addstate'''(nlist, s->out);
}
}
=== Дополнительные возможности регулярных выражений ===
==== Квантификация. ====
Позволяет установить точное соотвествие соответствие повторов равное числу n - {n}; {n,m} - не меньше чем n, и не больше чем m. {n,} - n и больше. Можно найти эквиваленты символам *, +, ?. С помощью символов { }
{| class="wikitable"
|-
==== Позиция внутри строки ====
Следующие символы позволяют спозиционировать с позиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.
{| class="wikitable"
! Представление
== Несколько полезных оптимизаций на примере Haskell ==
[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленеемедленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
* использовал Word вместо Integer, ещё в 8 раз быстрее
* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
В итоге его реализация оказалась всего в 4 раза медленее медленнее grep. Но это не предел, у него получилось реализовать [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автомат] и сделать свою реализацию в 1.5 раза быстрее, чем grep.
== ReDoS (regular expression denial of service) ==
