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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (fix)
м (rollbackEdits.php mass rollback)
 
(не показана 51 промежуточная версия 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. Интересно, что с добавлением обратной связи регулярные выражения перестаю относиться к классу регулярных языков. К сожалению, лучшая реализация требует экспоненциального времени работы. Приведенная на графике синяя кривая является реализацией построения NFA по регулярному выражению написанная на 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>.
 
=== Построение НКА ===
 
=== Построение НКА ===
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе.  
+
Для построения автомата нам нужно построить отдельно части НКА для каждой части выражения, финальным шагом будет соединение всего автомата вместе. Представим НКА как связанный список структур состояний <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)
  
 
=== Дополнительные возможности регулярных выражений ===
 
=== Дополнительные возможности регулярных выражений ===
  
 
==== Символьные классы ====  
 
==== Символьные классы ====  
Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. Можно указывать диапазоны [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>
 
|}
 
|}
  
 
==== Позиция внутри строки ====
 
==== Позиция внутри строки ====
Следующие символы позволяют спозиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.
+
Следующие символы позволяют с позиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.
 
{| class="wikitable"
 
{| class="wikitable"
 
! Представление
 
! Представление
 
! Позиция
 
! Позиция
 
|-
 
|-
| ^
+
| <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'') квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.
  
 
Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.
 
Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.
Строка 79: Строка 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>.
  
 
== См. также ==
 
== См. также ==
Строка 120: Строка 240:
 
* [[ Детерминированные конечные автоматы ]]
 
* [[ Детерминированные конечные автоматы ]]
 
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
 
* [[ Построение по НКА эквивалентного ДКА, алгоритм Томпсона ]]
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
Строка 125: Строка 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].

См. также

Примечания

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