59
правок
Изменения
Новая страница: «{{Задача |definition = Даны регулярное выражение и текст. Нужно проверить допускает ли регуляр...»
{{Задача
|definition =
Даны регулярное выражение и текст. Нужно проверить допускает ли регулярное выражение данный текст.
}}
==Алгоритм==
Введем обозначения:
:<tex>c</tex> {{---}} один любой буквенный символ
:<tex>\ldotp</tex> {{---}} один любой символ
:<tex>\wedge</tex> {{---}} символ начала текста
:<tex>\mathdollar</tex> {{---}} символ конца текста
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз
=== Псевдокод ===
'''function''' match(regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ поиск вхождения регулярного выражения в любом месте текста</font>
'''if''' (regexp[0] == '^')
'''return''' matchHere(regexp + 1, text)
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text++ != '\0')
'''return''' ''false''
'''function''' matchHere(regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ поиск вхождения регулярного выражения в начале текста</font>
'''if''' (regexp[0] == '\0')
'''return''' ''true''
'''if''' (regexp[1] == '*')
'''return''' matchStar(regexp[0], regexp + 2, text)
'''if''' (regexp[0] == '$' '''and''' regexp[1] == '\0')
'''return''' *text == '\0';
'''if''' (*text!='\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == *text))
'''return''' matchHere(regexp + 1, text + 1)
'''return''' ''false''
'''function''' matchStar(c : '''char''', regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ сопоставление с регулярным выражением вида: c*</font>
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text != '\0' '''and''' (*text++ == c '''or''' c == '.')) <font color=darkgreen>/Цикл '''do-while''' используется вместо '''while''', так как * допускает пустую строку</font>
'''return''' ''false''
Данный псевдокод использует указатели и арифметические операции над ними из языка C.
Функция <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> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
Основная часть работы сделана в <tex>\mathrm{matchHere(regexp, text)}</tex>, которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция <tex>\mathrm{matchHere}</tex> пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав <tex>\mathrm{matchHere}</tex> рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.
Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>(regexp[0] == \backslash0)</tex>, то текст допускается этим регулярным выражением.
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в [https://ru.wikipedia.org/wiki/Grep '''grep'''], где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.
Данный алгоритм прост и лаконичен, но у него есть недостаток. Для регулярного выражения содержащего несколько <tex>.*</tex> подряд этот алгоритм может работать очень медленно. Рассмотрим время работы '''grep'а''' (наш алгоритм схож со стандартным '''grep'ом'''). Например команда: "<tex>grep</tex> <tex>a.*a.*a.*a.a</tex>" потребует 20 секунд, чтобы обработать текстовой файл размером 4MB на обычной машине. В то же время алгоритм, который конвертирует [[Недетерминированные конечные автоматы|недетерминированный конечный автомат]] в [[Детерминированные конечные автоматы|детерминированный конечный автомат]] (например, [https://ru.wikipedia.org/wiki/Grep '''egrep''']), потребует менее одной десятой доли секунды на обработку тех же данных.
===Модификации===
Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>s</tex>.
# Сопоставим часть текста без <tex>s</tex> с остатком регулярного выражения.
# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>s</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>s</tex> и повторяем шаг 2.
=== Псевдокод ===
'''function''' matchStar(c : '''char''', regexp: '''char'''*, text: '''char'''*): '''boolean'''
'''char''' *t
'''for''' (t = text; *t != '\0' '''and''' (*t == c '''or''' c == '.'); t++)
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text != '\0' '''and''' (*text++ == c '''or''' c == '.'))
'''return''' ''false''
Увеличить количество символов из которых может состоять регулярное выражение можно, задавая регулярное выражение последовательностью структур, описывающих каждый ее элемент.
=== Псевдокод ===
'''struct''' Token
type: '''int''' <font color=darkgreen>/ тип элемента: STAR, QUESTION, PLUS, SYMBOL, ...</font>
c: '''char''' <font color=darkgreen>/ сам символ</font>
cs: '''char'''* <font color=darkgreen>/ для случая [...]</font>
ncs: '''bool''' <font color=darkgreen>/ для случая отрицания cs: [^...]</font>
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
== Источники информации ==
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
|definition =
Даны регулярное выражение и текст. Нужно проверить допускает ли регулярное выражение данный текст.
}}
==Алгоритм==
Введем обозначения:
:<tex>c</tex> {{---}} один любой буквенный символ
:<tex>\ldotp</tex> {{---}} один любой символ
:<tex>\wedge</tex> {{---}} символ начала текста
:<tex>\mathdollar</tex> {{---}} символ конца текста
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз
=== Псевдокод ===
'''function''' match(regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ поиск вхождения регулярного выражения в любом месте текста</font>
'''if''' (regexp[0] == '^')
'''return''' matchHere(regexp + 1, text)
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text++ != '\0')
'''return''' ''false''
'''function''' matchHere(regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ поиск вхождения регулярного выражения в начале текста</font>
'''if''' (regexp[0] == '\0')
'''return''' ''true''
'''if''' (regexp[1] == '*')
'''return''' matchStar(regexp[0], regexp + 2, text)
'''if''' (regexp[0] == '$' '''and''' regexp[1] == '\0')
'''return''' *text == '\0';
'''if''' (*text!='\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == *text))
'''return''' matchHere(regexp + 1, text + 1)
'''return''' ''false''
'''function''' matchStar(c : '''char''', regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>/ сопоставление с регулярным выражением вида: c*</font>
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text != '\0' '''and''' (*text++ == c '''or''' c == '.')) <font color=darkgreen>/Цикл '''do-while''' используется вместо '''while''', так как * допускает пустую строку</font>
'''return''' ''false''
Данный псевдокод использует указатели и арифметические операции над ними из языка C.
Функция <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> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
Основная часть работы сделана в <tex>\mathrm{matchHere(regexp, text)}</tex>, которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция <tex>\mathrm{matchHere}</tex> пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав <tex>\mathrm{matchHere}</tex> рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.
Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>(regexp[0] == \backslash0)</tex>, то текст допускается этим регулярным выражением.
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в [https://ru.wikipedia.org/wiki/Grep '''grep'''], где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.
Данный алгоритм прост и лаконичен, но у него есть недостаток. Для регулярного выражения содержащего несколько <tex>.*</tex> подряд этот алгоритм может работать очень медленно. Рассмотрим время работы '''grep'а''' (наш алгоритм схож со стандартным '''grep'ом'''). Например команда: "<tex>grep</tex> <tex>a.*a.*a.*a.a</tex>" потребует 20 секунд, чтобы обработать текстовой файл размером 4MB на обычной машине. В то же время алгоритм, который конвертирует [[Недетерминированные конечные автоматы|недетерминированный конечный автомат]] в [[Детерминированные конечные автоматы|детерминированный конечный автомат]] (например, [https://ru.wikipedia.org/wiki/Grep '''egrep''']), потребует менее одной десятой доли секунды на обработку тех же данных.
===Модификации===
Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>s</tex>.
# Сопоставим часть текста без <tex>s</tex> с остатком регулярного выражения.
# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>s</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>s</tex> и повторяем шаг 2.
=== Псевдокод ===
'''function''' matchStar(c : '''char''', regexp: '''char'''*, text: '''char'''*): '''boolean'''
'''char''' *t
'''for''' (t = text; *t != '\0' '''and''' (*t == c '''or''' c == '.'); t++)
'''do'''
'''if''' (matchHere(regexp, text))
'''return''' ''true''
'''while''' (*text != '\0' '''and''' (*text++ == c '''or''' c == '.'))
'''return''' ''false''
Увеличить количество символов из которых может состоять регулярное выражение можно, задавая регулярное выражение последовательностью структур, описывающих каждый ее элемент.
=== Псевдокод ===
'''struct''' Token
type: '''int''' <font color=darkgreen>/ тип элемента: STAR, QUESTION, PLUS, SYMBOL, ...</font>
c: '''char''' <font color=darkgreen>/ сам символ</font>
cs: '''char'''* <font color=darkgreen>/ для случая [...]</font>
ncs: '''bool''' <font color=darkgreen>/ для случая отрицания cs: [^...]</font>
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
== Источники информации ==
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
