Регулярные выражения

Очередные наброски, которые надеюсь доделать. На этот раз регулярные выражения. Начнём с простого разбор выражения. Доступны такие элементы как множества с интервалами [] без отрицания, групирующие скобки (), |+*? . Парсер имеет две основные процедуры:

BuildTree которая разбирает строку с выражением и генерирует дерево обычное дерево.
BuildGraph генерирует граф из дерева (по скорости линейна).

Все результаты выводятся ввиде .dot файлов. Граф или дерево состоит в основном из элементов следующих типов:

Sym - символный отрезок
Con - последовательность двух участков
Or - два паралельных участка. Никаких лямбда переходов в графе не возникает.

Примеры:

Дерево для выражения: ab(c|de)[zx]

Граф для выражения: ab(c|de)[zx]

Дерево для выражения: x*y+z?

Граф для выражения: x*y+z?

Парсер 1

Вариант работающий на lalr автомате. Грамматику можно описать приблизительно так:

all:   list
all:   all '|' list
list:  item
list:  item list
item:  atom
item:  atom +
item:  atom *
item:  atom ?
atom:  char
atom:  set
atom:  ( all )
set:   [ set- ]
set-: set-atom
set-: set- set-atom
set-atom: char
set-atom: char - char

Вообще я думал что этот вариант будет самым простым, но сам автомат получился не такой маленький как мне этого хотелось бы.

[reg_parse1.cpp]

Парсер 2

Парсер на основе простейшего стека. Выражение разбирается как самая обычная примитивная формула. Нет даже приоритетов операций.

[reg_parse2.cpp]

Поиск по регулярному выражению

Немного неуклюжее нагромождение классов, которое обесапечивает работу регулярного выражения. Сначала строится граФ выражения, который по сути является недетерминорованным автоматом. Далее начинается работа детерминированного автомата, точнее делаются шаги вдоль недетерминорованного графа, а полученные при этом состояния кешируются. При желании можно вызвать процедуру, которая полностью закеширует все возможные состояния автомата, построив тем самым полный детерминированный автомат. Исходник не затачивался ни на скорость ни на простоту, а нужен был всего лишь для эксперементов с циклами внутри выражений. Коментариев к принципам его работы, к сожалени, тоже не слишком много. Возможно в будушем сделаю из него что-нибудь хорошее.

[regexp1.cpp]