Автоматы в современном мире — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлен алгоритм на С)
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
== Реализация регулярных выражений в современных языках ==
 
== Реализация регулярных выражений в современных языках ==
 
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:
 
В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:
# можно конвертировать его в детерминированный конечный автомат;
+
# Можно конвертировать его в детерминированный конечный автомат.
# можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой;
+
# Можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой.
# можно идти по автомату одновременно по всем возможным состояниям;
+
# Можно идти по автомату одновременно по всем возможным состояниям.
# можно конвертировать НКА в ДКА лениво (на лету).
+
# Можно конвертировать НКА в ДКА лениво (на лету).
 
Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.
 
Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.
 
{| cellpadding="1" style="margin-left: auto; margin-right: auto;"
 
{| 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>]]
 
|[[Файл: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'''. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения НКА по регулярному выражению написанная на C, занимающая чуть меньше, чем 400 строк и описанная в [https://swtch.com/~rsc/regexp/regexp1.html данной статье].
+
Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках 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''', представим НКА как связанный список структур состояний '''State'''
+
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Представим НКА как связанный список структур состояний <tex>\mathrm{state}</tex>
  '''struct''' State
+
  '''struct''' state:
{
+
    '''int''' c
    '''int''' c;
+
    '''state''' out
    '''State''' *out;
+
    '''state''' out1
    '''State''' *out1;
+
    '''int''' lastlist
    '''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''' представляет один из фрагментов НКА, зависящий от символа c.
+
    '''state''' start
Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция re2post, которая переписывает инфиксную форму регулярного выражения "a(bb)+a" в эквивалентную постфиксную вида "abb.+.a." (. используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
+
    '''ptrList''' out
  '''struct''' Frag
+
<tex>\mathrm{start}</tex> указывает на стартовое состояние фрагмента, а <tex>\mathrm{out}</tex> {{---}} лист указателей на <tex>\mathrm{state*}</tex> указатели, которые ещё не соединены.  
{
 
  '''State''' *start;
 
  '''Ptrlist''' *out;
 
};
 
'''Start''' указывает на стартовое состояние фрагмента, а '''out''' - лист указателей на '''State*''' указатели, которые ещё не соединены.  
 
 
Некоторые полезные функции для управления списком указателей:
 
Некоторые полезные функции для управления списком указателей:
  '''Ptrlist''' *list1('''State''' **outp);
+
  '''fun''' list1('''state''' outp): '''ptrList'''
  '''Ptrlist''' *append('''Ptrlist''' *l1, '''Ptrlist''' *l2);
+
  '''fun''' append('''ptrList''' l1, '''ptrList''' l2): '''ptrList'''
  '''void''' patch('''Ptrlist''' *l, '''State''' *s);
+
  '''fun''' patch('''ptrList''' l, '''state''' s)
'''List1''' создает новый список указателей состоящий из одного указателя '''outp'''. '''Append''' конкатенирует два списка указателей, возвращая результат. '''Patch''' связывает повисшую стрелку в списке '''l''' с состоянием '''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*''' post2nfa('''char''' *postfix)
+
  '''fun''' post2nfa('''string''' postfix): '''state'''
{
+
    '''frag''' stack[1000], e1, e2, e
    '''char''' *p;
+
    '''state''' s
    '''Frag''' stack[1000], *stackp, e1, e2, e;
+
    '''for''' i = 0 '''to''' postfix.length - 1
    '''State''' *s;
+
        '''switch'''(postfix[i])
    #define push(s) *stackp++ = s
+
            '''case''' '.': <span style="color:#008000">// конкатенация</span>
    #define pop()  *--stackp
+
                e2 = stack.pop()
    stackp = stack;
+
                e1 = stack.pop()
    '''for''' (p = postfix; *p; p++){
+
                patch(e1.out, e2.start)
      '''switch'''(*p){
+
                push(frag(e1.start, e2.out))
          '''defaul'''t: // символ
+
                '''break'''
            s = '''state'''(*p, NULL, NULL)
+
            '''case''' '|': <span style="color:#008000">// альтернатива</span>
            '''push'''('''frag'''(s, list1(&s->out));
+
                e2 = stack.pop()
            '''break''';
+
                e1 = stack.pop()
          '''case''' '.': // конкатенация
+
                s = state(Split, e1.start, e2.start)
            e2 = '''pop'''();
+
                push(frag(s, append(e1.out, e2.out)))
            e1 = '''pop'''();
+
                '''break'''
            '''patch'''(e1.out, e2.start);
+
            '''case''' '?': <span style="color:#008000">// ноль или один</span>
            '''push'''('''frag'''(e1.start, e2.out));
+
                e = stack.pop()
            '''break''';
+
                s = state(Split, e.start, NULL)
          '''case''' '|': // альтернатива
+
                push(frag(s, append(e.out, list1(s.out1))))
            e2 = '''pop'''();
+
                '''break'''
            e1 = '''pop'''();
+
            '''case''' '*': <span style="color:#008000">// ноль или больше</span>
            s = '''state'''(Split, e1.start, e2.start);
+
                e = stack.pop()
            '''push'''('''frag'''(s, append(e1.out, e2.out)));
+
                s = state(Split, e.start, NULL)
            '''break''';
+
                patch(e.out, s)
          '''case''' '?': // ноль или один
+
                push(frag(s, list1(s.out1)))
            e = '''pop'''();
+
                '''break'''
            s = '''state'''(Split, e.start, NULL);
+
            '''case''' '+': <span style="color:#008000">// один или больше</span>
            '''push'''('''frag'''(s, append(e.out, list1(&s->out1))));
+
                e = stack.pop()
            '''break''';
+
                s = state(Split, e.start, NULL)
          '''case''' '*': // ноль или больше
+
                patch(e.out, s)
            e = '''pop'''();
+
                stack.push(frag(e.start, list1(s.out1)))
            s = '''state'''(Split, e.start, NULL);
+
                '''break'''
            '''patch'''(e.out, s);
+
            '''defaul'''t: <span style="color:#008000">// символ</span>
            '''push'''(frag(s, list1(&s->out1)));
+
                s = state(postfix[i], NULL, NULL)
            break;
+
                push(frag(s, list1(s.out))
          '''case''' '+': // один или больше
+
                '''break'''
            e = '''pop'''();
+
    e = stack.pop()
            s = '''state'''(Split, e.start, NULL);
+
    patch(e.out, matchState)
            '''patch'''(e.out, s);
+
    '''return''' e.start
            '''push'''('''frag'''(e.start, list1(&s->out1)));
+
 
            break;
 
        }
 
    }
 
    e = '''pop'''();
 
    '''patch'''(e.out, matchstate);
 
    '''return''' e.start;
 
}
 
  
 
Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.
 
Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.
  '''struct''' List
+
  '''struct''' List:
{
+
    '''state''' s
  '''State''' **s;
+
    '''int''' n
  '''int''' n;
 
};
 
  
Обход будет использовать два списка: '''clist''' набор состояний, в которых уже находится, и '''nlist''' набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует '''clist''' стартовым состоянием и пошагово проходит.
+
Обход будет использовать два списка: <tex>\mathrm{cList}</tex> набор состояний, в которых уже находится, и <tex>\mathrm{nList}</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует <tex>\mathrm{cList}</tex> стартовым состоянием и пошагово проходит.
  '''int''' match('''State''' *start, '''char''' *s)
+
  '''fun''' match('''state''' start, '''string''' s): '''int'''
{
+
    '''List''' cList, nList, t
  '''List''' *clist, *nlist, *t;
+
    '''cList''' = startList(start, l1)
  '''clist''' = startlist(start, &l1);
+
    '''nList''' = l2
  '''nlist''' = &l2;
+
    '''for''' i = 0 '''to''' s.length - 1
  '''for''' ( ; *s, s++) {
+
        step(cList, s[i], nList)
    '''step'''(clist, *s, nlist);
+
        t = cList
    t = clist; clist = nlist; nlist = t;
+
        cList = nList
  }
+
        nList = t
  '''return''' ismatch(clist);
+
    '''return''' isMatch(cList)
}
+
Чтобы избежать преаллокаций на каждой итерации цикла, <tex>\mathrm{match}</tex> использует два преаллоцированных списка <tex>\mathrm{l1}</tex> и <tex>\mathrm{l2}</tex> как <tex>\mathrm{cList}</tex> и <tex>\mathrm{nList}</tex>, и меняет их на каждом шаге.  
Чтобы избежать преаллокаций на каждой итерации цикла, match использует два преаллоцированных списка '''l1''' и '''l2''' как '''clist''' и '''nlist''', и меняет их на каждом шаге.  
 
  
 
Если список последних вершин содержит терминальную вершину, то строка распознана.
 
Если список последних вершин содержит терминальную вершину, то строка распознана.
  
  '''int''' ismatch('''List''' *l)
+
  '''fun''' isMatch('''List''' l): '''int'''
{
+
    '''int''' i
  '''int''' i;
+
    '''for''' i = 0 '''to''' l.n - 1
  '''for''' ('''int''' i = 0; i < l->n; i++)
+
        '''if''' (l.s[i] == matchState)
    '''if''' (l->s[i] == matchstate)
+
        '''return''' 1
      '''return''' 1;
+
    '''return''' 0
  '''return''' 0;
 
}
 
  
'''Addstate''' добавляет состояние в список, но только если их ещё не было в нем.
 
  
'''void''' addstate('''Lis'''t *l, '''State''' *s)
+
<tex>\mathrm{addState}</tex> добавляет состояние в список, но только если их ещё не было в нем.
{
 
  '''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''' создает начальный список состояний и добавляет туда стартовое состояние.
+
'''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
  
'''List*''' startlist('''State''' *s, '''List''' *l)
+
<tex>\mathrm{startList}</tex> создает начальный список состояний и добавляет туда стартовое состояние.
{
 
  listid++;
 
  l->n = 0;
 
  '''addstate'''(l, s);
 
  '''return''' l;
 
}
 
  
'''Step''' вычисляет по символу, использую список текущих состояний '''clist''' следующий список '''nlist'''.
+
'''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)
  
'''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);
 
  }
 
}
 
 
=== Дополнительные возможности регулярных выражений ===
 
=== Дополнительные возможности регулярных выражений ===
  
 
==== Символьные классы ====  
 
==== Символьные классы ====  
Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны [0-9], [a-z], а также существуют дополнительные символьные классы <tex>[[:upper:]], [[:word:]]</tex>.  
+
Набор символов в квадратных скобках <tex>[ ]</tex> именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны <tex>\mathrm{[0-9]}, \mathrm{[a-z]}</tex>, а также существуют дополнительные символьные классы <tex>\mathtt{[[:upper:]]}, \mathtt{[[:word:]]}</tex>.  
  
 
==== Квантификация. ====
 
==== Квантификация. ====
Позволяет установить точное соответствие повторов равное числу n - {n}; {n,m} - не меньше чем n, и не больше чем m. {n,} - n и больше. Можно найти эквиваленты символам *, +, ?.  С помощью символов { }
+
Позволяет установить точное соответствие повторов равное числу <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>
 
{| class="wikitable"  
 
{| class="wikitable"  
 
|-
 
|-
| ?
+
| <tex>?</tex>
| {0,1}
+
| <tex>{0,1}</tex>
 
|-
 
|-
| +
+
|<tex>+</tex>
| {1,}
+
| <tex>{1,}</tex>
 
|-
 
|-
| *
+
| <tex>*</tex>
| {}
+
|<tex>\{ \}</tex>
 
|}
 
|}
  
Строка 180: Строка 157:
 
! Позиция
 
! Позиция
 
|-
 
|-
| ^
+
| <tex> \wedge </tex>
 
| Начало текста
 
| Начало текста
 
|-
 
|-
| $
+
| <tex>$</tex>
 
| Конец текста
 
| Конец текста
 
|-
 
|-
| \b
+
| <tex>\backslash b</tex>
 
| Граница слова
 
| Граница слова
 
|-
 
|-
| \G
+
| <tex>\backslash G</tex>
 
| Предыдущий успешный поиск
 
| Предыдущий успешный поиск
 
|}
 
|}
  
 
==== Жадная и ленивая квантификация ====
 
==== Жадная и ленивая квантификация ====
В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. greedy). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение (<.*>) найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.
+
В некоторых реализациях квантификаторам в регулярных выражениях соответствует максимально длинная строка из возможных (квантификаторы являются жадными, англ. ''greedy''). Это может оказаться значительной проблемой. Например, часто ожидают, что выражение <tex>(<.*>)</tex> найдёт в тексте теги HTML. Однако если в тексте есть более одного HTML-тега, то этому выражению соответствует целиком строка, содержащая множество тегов.
 
{| class="wikitable"
 
{| class="wikitable"
 
! Жадный
 
! Жадный
 
! Ленивый
 
! Ленивый
 
|-
 
|-
| *
+
| <tex>*</tex>
| *?
+
| <tex>*?</tex>
 
|-
 
|-
| +
+
| <tex>+</tex>
| +?
+
| <tex>+?</tex>
 
|-
 
|-
| {n,}
+
| <tex>\{n,\}</tex>
| {n,}?
+
| <tex>\{n,\}?</tex>
 
|}
 
|}
 
Эту проблему можно решить двумя способами.
 
Эту проблему можно решить двумя способами.
  
Учитывать символы, не соответствующие желаемому образцу (<[^>]*> для вышеописанного случая).
+
Учитывать символы, не соответствующие желаемому образцу ( <tex><[^>]*></tex> для вышеописанного случая).
Определить квантификатор как нежадный (ленивый, англ. lazy) большинство реализаций позволяют это сделать, добавив после него знак вопроса.
+
Определить квантификатор как нежадный (ленивый, англ. ''lazy'') {{---}} большинство реализаций позволяют это сделать, добавив после него знак вопроса.
  
 
==== Ревнивая квантификация (Сверхжадная) ====
 
==== Ревнивая квантификация (Сверхжадная) ====
В отличие от обычной (жадной) квантификации, ревнивая (possessive) квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.
+
В отличие от обычной (жадной) квантификации, ревнивая (англ. ''possessive'') квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.
  
 
Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.
 
Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.
Строка 221: Строка 198:
 
! Ревнивый
 
! Ревнивый
 
|-
 
|-
| *
+
| <tex>*</tex>
| *+
+
| <tex>*+</tex>
 
|-
 
|-
| ?
+
| <tex>?</tex>
| ?+
+
| <tex>?+</tex>
 
|-
 
|-
| +
+
| <tex>+</tex>
| ++
+
| <tex>++</tex>
 
|-
 
|-
| {n,}
+
| <tex>\{n,\}</tex>
| {n,}+
+
| <tex>\{n,\}+</tex>
 
|}
 
|}
  
 
== Несколько полезных оптимизаций на примере Haskell ==
 
== Несколько полезных оптимизаций на примере Haskell ==
[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
+
 
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
+
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 на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
* использовал Word вместо Integer, ещё в 8 раз быстрее
+
* вместо <tex>\mathrm{Set Int}</tex> использовал <tex>\mathrm{Integer}</tex>, а также использовал битовые операции, в результате производительность выросла в <tex>5</tex> раз
* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
+
* использовал <tex>\mathrm{Word}</tex> вместо <tex>\mathrm{Integer}</tex>, ещё в <tex>8</tex> раз быстрее
В итоге его реализация оказалась всего в 4 раза медленнее grep. Но это не предел, у него получилось реализовать [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автомат] и сделать свою реализацию в 1.5 раза быстрее, чем grep.
+
* а также использовал <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.
  
 
== ReDoS (regular expression denial of service) ==
 
== ReDoS (regular expression denial of service) ==
 
Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:
 
Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:
* использовать повторение ("+","*") для достаточно сложных подвыражений;
+
* использовать повторение <tex>(``+",``*")</tex> для достаточно сложных подвыражений;
 
* сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.
 
* сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.
 
Примеры вредоносных регулярных выражений:
 
Примеры вредоносных регулярных выражений:
* (a+)+
+
* <tex>(a+)+</tex>
* ([a-zA-Z]+)*
+
* <tex>([a-zA-Z]+)*</tex>
* (a|aa)+
+
* <tex>(a|aa)+</tex>
* (a|a?)+
+
* <tex>(a|a?)+</tex>
* (.*a){x} for x > 10
+
* <tex>(.*a)\{11,\}</tex>
Все эти выражения чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaaaa.
+
Все эти выражения чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaaaa</tex>.
 
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
 
Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
# [http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (email validation)] - '''выделенная''' часть является вредоносной<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>
+
# RegExLib, email validation <ref>[http://regexlib.com/REDetails.aspx?regexp_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>
# [http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository], Java Classname - '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</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>
Эти два примера также чувствительны к входной строке aaaaaaaaaaaaaaaaaaaaaaaa.
+
Эти два примера также чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaa</tex>.
  
 
== См. также ==
 
== См. также ==
Строка 262: Строка 240:
 
* [[ Детерминированные конечные автоматы ]]
 
* [[ Детерминированные конечные автоматы ]]
 
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
 
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
Строка 267: Строка 248:
 
* [https://swtch.com/~rsc/regexp/regexp1.html  Regular Expression Matching Can Be Simple And Fast]
 
* [https://swtch.com/~rsc/regexp/regexp1.html  Regular Expression Matching Can Be Simple And Fast]
 
* [https://en.wikipedia.org/wiki/ReDoS ReDos]
 
* [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 Machines]
+
* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-state Machines]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Контекстно-свободные грамматики]]

Текущая версия на 19:37, 4 сентября 2022

Реализация регулярных выражений в современных языках

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

  1. Можно конвертировать его в детерминированный конечный автомат.
  2. Можно идти по каждому из возможных путей, а в случае неудачи возвращаться назад и пробовать другой.
  3. Можно идти по автомату одновременно по всем возможным состояниям.
  4. Можно конвертировать НКА в ДКА лениво (на лету).

Следующее изображение наглядно показывает, что можно выделить более менее два основных подхода к реализации, давайте же разберемся почему так получилось.

regular expression and text size n [math]a?^na^n[/math] matching [math]a^n[/math]

Это произошло из-за того, что обычного функционала регулярных выражений зачастую недостаточно, не хватает выразительной мощности. В языках PCRE, Ruby, Python, Perl добавили поддержку обратных ссылок (англ. back reference). Она позволяет связывать ранее найденное сгруппированное выражение в скобках с числом от [math]1[/math] до [math]9[/math]. Например: [math]\mathtt{(cat|dog)\backslash1}[/math] найдет [math]\mathtt{catcat}[/math] или [math]\mathtt{dogdog}[/math], но никак не [math]\mathtt{catdog}[/math] или [math]\mathtt{dogcat}[/math]. Интересно, что с добавлением обратных ссылок регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения НКА по регулярному выражению написанная на C, занимающая чуть меньше, чем [math]400[/math] строк и описанная в данной статье[1].

Построение НКА

Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Представим НКА как связанный список структур состояний [math]\mathrm{state}[/math]

struct state:
    int c
    state out
    state out1
    int lastlist

Каждый [math]\mathrm{state}[/math] представляет один из фрагментов НКА, зависящий от символа [math]c[/math]. Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция [math]\mathrm{re2post}[/math], которая переписывает инфиксную форму регулярного выражения [math]``a(bb)+a"[/math] в эквивалентную постфиксную вида [math]``abb.+.a."[/math] ([math].[/math] используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:

struct frag:
    state start
    ptrList out

[math]\mathrm{start}[/math] указывает на стартовое состояние фрагмента, а [math]\mathrm{out}[/math] — лист указателей на [math]\mathrm{state*}[/math] указатели, которые ещё не соединены. Некоторые полезные функции для управления списком указателей:

fun list1(state outp): ptrList
fun append(ptrList l1, ptrList l2): ptrList
fun patch(ptrList l, state s)

[math]\mathrm{list1}[/math] создает новый список указателей состоящий из одного указателя [math]\mathrm{outp}[/math]. [math]\mathrm{append}[/math] конкатенирует два списка указателей, возвращая результат. [math]\mathrm{patch}[/math] связывает повисшую стрелку в списке [math]\mathrm{l}[/math] с состоянием [math]\mathrm{s}[/math]. Используя данные примитивы и стек фрагментов можно реализовать построение НКА.

fun post2nfa(string postfix): state
    frag stack[1000], e1, e2, e
    state s
    for i = 0 to postfix.length - 1
        switch(postfix[i])
            case '.': // конкатенация
                e2 = stack.pop()
                e1 = stack.pop()
                patch(e1.out, e2.start)
                push(frag(e1.start, e2.out))
                break
            case '|': // альтернатива
                e2 = stack.pop()
                e1 = stack.pop()
                s = state(Split, e1.start, e2.start)
                push(frag(s, append(e1.out, e2.out)))
                break
            case '?': // ноль или один
                e = stack.pop()
                s = state(Split, e.start, NULL)
                push(frag(s, append(e.out, list1(s.out1))))
                break
            case '*': // ноль или больше
                e = stack.pop()
                s = state(Split, e.start, NULL)
                patch(e.out, s)
                push(frag(s, list1(s.out1)))
                break
            case '+': // один или больше
                e = stack.pop()
                s = state(Split, e.start, NULL)
                patch(e.out, s)
                stack.push(frag(e.start, list1(s.out1)))
                break
            default: // символ
                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

Обход будет использовать два списка: [math]\mathrm{cList}[/math] набор состояний, в которых уже находится, и [math]\mathrm{nList}[/math] набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует [math]\mathrm{cList}[/math] стартовым состоянием и пошагово проходит.

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)

Чтобы избежать преаллокаций на каждой итерации цикла, [math]\mathrm{match}[/math] использует два преаллоцированных списка [math]\mathrm{l1}[/math] и [math]\mathrm{l2}[/math] как [math]\mathrm{cList}[/math] и [math]\mathrm{nList}[/math], и меняет их на каждом шаге.

Если список последних вершин содержит терминальную вершину, то строка распознана.

fun isMatch(List l): int
    int i
    for i = 0 to l.n - 1
        if (l.s[i] == matchState)
        return 1
    return 0


[math]\mathrm{addState}[/math] добавляет состояние в список, но только если их ещё не было в нем.

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

[math]\mathrm{startList}[/math] создает начальный список состояний и добавляет туда стартовое состояние.

fun startList(state s, List l): List
    listid++
    l.n = 0
    addState(l, s)
    return l

[math]\mathrm{step}[/math] вычисляет по символу, использую список текущих состояний [math]\mathrm{cList}[/math] следующий список [math]\mathrm{nList}[/math].

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)

Дополнительные возможности регулярных выражений

Символьные классы

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

Квантификация.

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

[math]?[/math] [math]{0,1}[/math]
[math]+[/math] [math]{1,}[/math]
[math]*[/math] [math]\{ \}[/math]

Позиция внутри строки

Следующие символы позволяют с позиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.

Представление Позиция
[math] \wedge [/math] Начало текста
[math]$[/math] Конец текста
[math]\backslash b[/math] Граница слова
[math]\backslash G[/math] Предыдущий успешный поиск

Жадная и ленивая квантификация

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

Жадный Ленивый
[math]*[/math] [math]*?[/math]
[math]+[/math] [math]+?[/math]
[math]\{n,\}[/math] [math]\{n,\}?[/math]

Эту проблему можно решить двумя способами.

Учитывать символы, не соответствующие желаемому образцу ( [math]\lt [^\gt ]*\gt [/math] для вышеописанного случая). Определить квантификатор как нежадный (ленивый, англ. lazy) — большинство реализаций позволяют это сделать, добавив после него знак вопроса.

Ревнивая квантификация (Сверхжадная)

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

Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.

Жадный Ревнивый
[math]*[/math] [math]*+[/math]
[math]?[/math] [math]?+[/math]
[math]+[/math] [math]++[/math]
[math]\{n,\}[/math] [math]\{n,\}+[/math]

Несколько полезных оптимизаций на примере Haskell

Gabriel Gonzalez [2] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в [math]480[/math] раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:

  • вместо [math]\mathrm{Set Int}[/math] использовал [math]\mathrm{Integer}[/math], а также использовал битовые операции, в результате производительность выросла в [math]5[/math] раз
  • использовал [math]\mathrm{Word}[/math] вместо [math]\mathrm{Integer}[/math], ещё в [math]8[/math] раз быстрее
  • а также использовал [math]\mathrm{ByteString}[/math] оптимизации, что увеличило производительность ещё [math]3[/math] раза.

В итоге его реализация оказалась всего в [math]4[/math] раза медленнее grep. Но это не предел, у него получилось реализовать параллельный конечный автомат[3] и сделать свою реализацию в [math]1.5[/math] раза быстрее, чем grep.

ReDoS (regular expression denial of service)

Интересно, что злоумышленники научились атаковать системы используя то, что некоторые алгоритмы имеют экспоненциальную сложность. В регулярных выражениях использующих обратную связь есть несколько вариантов:

  • использовать повторение [math](``+",``*")[/math] для достаточно сложных подвыражений;
  • сделать так, чтобы повторяющиеся подвыражения были суффиксами валидного совпадения.

Примеры вредоносных регулярных выражений:

  • [math](a+)+[/math]
  • [math]([a-zA-Z]+)*[/math]
  • [math](a|aa)+[/math]
  • [math](a|a?)+[/math]
  • [math](.*a)\{11,\}[/math]

Все эти выражения чувствительны к входной строке [math]aaaaaaaaaaaaaaaaaaaaaaaaaa[/math]. Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.

  1. RegExLib, email validation [4]выделенная часть является вредоносной
    ^([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}))$
  2. OWASP Validation Regex Repository [5], Java Classname — выделенная часть является вредоносной
    ^(([a-z])+.)+[A-Z]([a-z])+$

Эти два примера также чувствительны к входной строке [math]aaaaaaaaaaaaaaaaaaaaaaaa[/math].

См. также

Примечания

Источники информации