Регулярные выражения и PEG для поиска.
От: mefrill Россия  
Дата: 18.01.11 09:18
Оценка:
Привет,

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

Мне интересно, как парсер на основе рекурсивного спуска можно использовать для поиска подстрок в некотором тексте. Для регулярных выражений все очень просто:
1. Создаем по регулярке детерминированный конечный автомат.
2. Превращаем этот автомат в поисковый.
3. Идем по строке скармливаем его автомату. При переходе в допускающее состояние печатаем найденную подстроку.

Первый пункт -- это известное преобразование, корректно ввиду истинности теоремы Клини. Немного о втором пункте и о том, что такое поисковый автомат.

Предположим, у нас имеется регулярное выражени (a|b)c+, построим по нему ДКА:
             a       b     c
--> 0     1      2     --
       1     --     --     3
       2     --     --     3
   *  3     --      --    3


Этот ДКА не поисковый, чтобы найти по нему что-то в тексте abbccacc, надо запускать автомат с каждого символа текста сначала. Это затратная операция, надо поддерживать список состояний для каждого символа теста (до тех пор, пока в автомате есть переходы с этой позиции в тексте). Чтобы этого избежать добавляем в автомат переходы по следующему принципу:

Для каждого состояния q автомата, если из начального состояния имеется переход по символу X в состояние q', добавляем переход по этому символу в состояние q'.

Смысл такого добавления состоит в том, что при нахождении в каком-то состоянии автомат одновременно начинает считывать строку с начального состояния. В результате может получиться недетерминированный автомат. Построим поисковый автомат для автомата выше:
             a       b     c
--> 0     1      2     --
       1     1     2     3
       2     1     2     3
   *  3     1     2     3


Данный автомат даже остался детерминирвоанным, хотя добавились дополнительные шесть переходов. Этот автомат позволяет искать в тексте любую подстроку, удовлетворяющую регулярному выражению (a|b)c+. Это легко проверить, я этого делать здесь не буду.

В общем случае, поисковый автомат может стать НКА. Построить из такого НКА ДКА можно стандартным способом, хотя в некоторых случаях в результате может быть довольно много состояний. Рассмотрим, например, выражение (ax?){3,10}. Мы должны найти все подстроки от 3 до 10 символов a, необязательно разделенных символом x. При построении поискового автомата состояния вырастут экспоненциально правой границе интервала, в данном случае 10. Для больших выражений состояний может быть сотни тысяч. Поэтому, в некоторых случаях поисковый автомат построить трудно, можно вести поиск непосредственно по НКА.

Таким образом, кроме вырожденных случаев, легко построить поисковый ДКА, который будет находить все возможные подстроки за минимально возможное время. Как в этом случае с PEG.

PS: Ничего не имею против PEG, но считаю, что каждому инструменту -- своя область применения. PEG предназначен для синтаксического анализа, т.е. для построения из текста дерева разбора, но не для поиска. Регулярные выражения были введены конкретно для поиска и представляют собой удобный инструмент для описания отношения "быть рядом", которое естественно для поисковых шаблонов. Грамматика PEG -- косвенное описание отношения иерархии, через спецификацию алгоритма разбора, которую на самом деле представляет собой грамматика PEG. Алгроитм PEG описывает разбор конкретного текста, т.е. то, что называется match, но не поиск. Поэтому использовать его вместо РВ для поиска не хорошо. Использовать PEG для match по регуляркам мне кажется также не очень хорошо. В алгоритм PEG неявно встроено отношение иерархии, т.е. "быть частью". Пользователь же в абсолютном большинстве случаев использует отношение "быть рядом", которое выражается РВ очень удобно. Таким образом, здесь мы имеем нарушение принципа "не плоди сущности без нужды", заставляя пользователя использовать инструмент, семантика которого намного богаче того, что необходимо пользователю.

С уважением,
ВЛ.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.