asv13
А можно посмотреть код DFA? Насколько он сложен? Пытался свой написать, упрощал структуру как мог, но очень быстро запутался в условиях и бросил. Что-то изменять, это полдня надо снова вникать в написанное.

Честно говоря, код уже куда-то потерялся, так как в проекте я от него отказался в конечном счете.
Но идеи черпал кажеться отсюда http://lacl.univ-paris12.fr//pommereau/tlf/index.html и отсюда http://pypi.python.org/pypi/dfa/20070511.

Ferroman
Может стоит либу на си взять какую, или саому накропать, раз уж скорость так критична…

Быстрее физически не будет - ‘re’ сишная либа. Если грубых ошибок в коде нет, т.е. - все регулярки компилируются до использования. Нет никаких шансов побить по быстродействию классический нисходящий рекурсивный разгребатор модуля ‘re’. Более того - сам использую эту либу из С++ программ - и не напрягает ради этого ембедить питон. Хотя звучит несколько забавно - включать питон в С++ приложение для увеличения скорости работы с регулярными выражениями :)