Просмотр исходного текста страницы Простой сопоставитель регулярных выражений

{{Задача
|definition =
Даны регулярное выражение и текст. Нужно проверить допускает ли регулярное выражение данный текст.
}}

==Алгоритм==
Данный алгоритм работает быстрее [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], построенного по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], но только для регулярных выражений, состоящих из символов: 
:<tex>c</tex> {{---}} один любой буквенный символ,
:<tex>\ldotp</tex> {{---}} один любой символ,
:<tex>\wedge</tex> {{---}} символ начала текста,
:<tex>$</tex> {{---}} символ конца текста,
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.

Например, для <tex>\mathtt{http://\ldotp*wiki\ldotp*com}</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.

=== Псевдокод ===
 <font color=darkgreen>// поиск вхождения регулярного выражения в любом месте текста</font>
 '''function''' match(regexp: '''String''', text: '''String'''): '''boolean'''  
     '''if''' regexp[0] == '^'
         '''return''' matchHere(regexp[1:], text)  <font color=darkgreen>// regexp[n:] возвращает regexp без первых n элементов за O(1)</font>
     '''int''' i = 0
     '''while''' i <tex>\leqslant</tex> text.length
         '''if''' matchHere(regexp, text[i:])
             '''return''' ''true''
         i++
     '''return''' ''false''

Функция <tex>\mathrm{match(regexp, text)}</tex> проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое. 

Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. То есть если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.

В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. То есть если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.

 <font color=darkgreen>// поиск вхождения регулярного выражения в начале текста</font>
 '''function''' matchHere(regexp: '''String''', text: '''String'''): '''boolean''' 
     '''if''' regexp[0] == '\0'
         '''return''' ''true'' 
     '''if''' regexp[1] == '*'  <font color=darkgreen>// не будет выхода за пределы строки, так как в конце regexp и text всегда есть символ '\0'</font>
         '''return''' matchStar(regexp[0], regexp[2:], text)
     '''if''' regexp[0] == '$' '''and''' regexp[1] == '\0'
         '''return''' text == '\0'
     '''if''' text[0] != '\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == text[0])
         '''return''' matchHere(regexp[1:], text[1:])
     '''return''' ''false''

Основная часть работы сделана в <tex>\mathrm{matchHere(regexp, text)}</tex>, которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция <tex>\mathrm{matchHere}</tex> пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав <tex>\mathrm{matchHere}</tex> рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.

 <font color=darkgreen>// сопоставление с регулярным выражением вида: c*</font>
 '''function''' matchStar(c: '''char''', regexp: '''String''', text: '''String'''): '''boolean'''
     '''int''' i = 0
     '''while''' i <tex>\leqslant</tex> text.length '''and''' (text[i] == c '''or''' c == '.')
         '''if''' matchHere(regexp, text[i:])
             '''return''' ''true''
         i++
     '''return''' ''false''

Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)},\,</tex> то текст допускается этим регулярным выражением.
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция <tex>\mathrm{mathchStar},\,</tex> которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep Wikipedia {{---}} grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>$</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.

===Модификации===
Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>S</tex>. 
# Сопоставим часть текста без <tex>S</tex> с остатком регулярного выражения.
# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>S</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>S</tex> и повторяем шаг <tex>2</tex>.

=== Псевдокод ===
 '''function''' matchStar(c: '''char''', regexp: '''String''', text: '''String'''): '''boolean'''
     '''int''' i
     '''for''' (i = 0; text[i] != '\0' '''and''' (text[i] == c '''or''' c == '.'); i++)
     '''while''' i <tex>\geqslant</tex> 0
         '''if''' matchHere(regexp, text[i:])
             '''return''' ''true''
         i--
     '''return''' ''false''

==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]

==Примечания==
<references />

== Источники информации ==
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Регулярные языки и ДКА]]