Здравствуйте, mefrill, Вы писали:

M>Привет,

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

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

Может быть будет полезно для дискуссий

Поиск сабматчей за линейное относительно длины строки время через НКА:
http://swtch.com/~rsc/regexp/regexp2.html

Оптимизация для солидного класса частных случаев: (искать фразу Use a one-pass NFA if possible)
http://swtch.com/~rsc/regexp/regexp3.html