Ужасы нашего городка

Как-то в стародавние времена, на одном всем известном форуме завелась нечистая сила, под именем Xenocephal. И до такой степени она (нечисть) всех затроллила, что сил уже никаких не было. В одном из своих эпичных постов, в недобрый час, помянуто было о C++ да метапрограммировании, да о том, что годиться все это, только чтобы было чем сосчитать факториал. Нечего мне было тогда ему ответить, но мысль в голову запала.

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

Вкратце напомню (а не вкратце в книге можно прочитать), что регулярное выражение может быть представлено НКА, который всем хорош, кроме квадратичного времени работы. НКА всегда может быть преобразован в ДКА (хотя само преобразование весьма нетривиально), обеспечивающий линейное время работы, но требующий, по серьезному, больше памяти.

Пример был взят из книги:

Как можно видеть, этот НКА (а недетерминирован он, поскольку из 0 узла выходят две дуги "а") соответствует регулярному выражению (a|b)*abb. После преобразования, должен получиться ДКА, описываемый следующим графом:

Дело было за малым - реализовать алгоритм в C++, да не абы как, а на шаблонах, и чтобы работал он во время компиляции. Поскольку был я в то время большим поклонником Александреску, в голове как-то само собой возникло следующее представление списков и графов (как списков связей между вершинами).

Common.h

// Вспомогательные шаблоны
struct NullType {static void Dump(void) {printf("\n");}};
template <int N> struct Int2Type {enum {Result = N};};
template <bool cond, class A, class B> struct If {typedef A Result;};
template <class A, class B> struct If<false,A,B> {typedef B Result;};

// Элемент множества
template <int N, class T>
struct Set
{ enum {Value = N};
  typedef T Next;
  static void Dump(void) {printf("%d ",N);T::Dump();}
};

// Узел графа
template <class T, int Src, int Dst, char Chr = 0>
struct Node
{ enum { Source  = Src,
         Dest    = Dst,
         Char    = Chr
       };
  typedef T Next;
  static void Dump(void) {printf("%3d -%c-> %3d\n",Src,Chr,Dst);T::Dump();}
};

// Элемент списка состояний
template <int N, class S, class T>
struct StateList
{ enum {Value = N};
  typedef S State;
  typedef T Next;
  static void Dump(void) {printf("%5d: ",N);S::Dump();T::Dump();}
};
template <int src, int dst, int a, class S, class T>
struct StateListEx: public StateList<dst,S,T>
{ enum {Src  = src,
        Dst  = dst,
        Move = a};
  static void Dump(void) {printf("%5d(%c): ",dst,a);S::Dump();T::Dump();}
};

// Проверка вхождения элемента в список
template <int N, class T> struct Exist;
template <int N> struct Exist<N,NullType> {enum {Result = false};};
template <int N, class T> struct Exist<N,Set<N,T> > {enum {Result = true};};
template <int N, int M, class T> struct Exist<N,Set<M,T> > 

   {enum {Result = Exist<N,T>::Result};};
template <int N, class S, class T> struct Exist<N, StateList<N,S,T> > 

   {enum {Result = true;};};
template <int N, int M, class S, class T> struct Exist<N, StateList<M,S,T> > 

   {enum {Result = Exist<N,T>::Result};};
template <int N, int Src, int a, class S, class T> 

struct Exist<N, StateListEx<Src,N,a,S,T> > {enum {Result = true;};};
template <int N, int Src, int Dst, int a, class S, class T> 

struct Exist<N, StateListEx<Src,Dst,a,S,T> > {enum {Result = Exist<N,T>::Result};};
template <int N, class T> struct NotExist {enum {Result = !Exist<N,T>::Result};};

// Проверка включения A в B
template <class A, class B> struct Include;
template <int N, class T, class B>
struct Include<Set<N,T>,B> 

   {enum {Result = Exist<N,B>::Result && Include<T,B>::Result};};
template <class B> struct Include<NullType,B> {enum {Result = true};};

// Проверка равенства списков
template <class A, class B> struct Equ 

   {enum {Result = Include<A,B>::Result && Include<B,A>::Result};};

// Слияние списков (A => B)
template <class A, class B> struct Append;
template <class T> struct Append<NullType,T> {typedef T Result;};
template <int N, class T, class B> 

struct Append<Set<N,T>,B> {typedef typename Append<T,Set<N,B> >::Result Result;};
template <int S, int D, int C, class T, class B> 

struct Append<Node<T,S,D,C>,B> 

   {typedef typename Append<T,Node<B,S,D,C> >::Result Result;};
template <int N, class S, class T, class B> 

struct Append<StateList<N,S,T>,B> 

   {typedef typename Append<T,StateList<N,S,B> >::Result Result;};
template <int Src, int Dst, int a, class S, class T, class B> 

struct Append<StateListEx<Src,Dst,a,S,T>,B> 

   {typedef typename Append<T,StateList<Dst,S,B> >::Result Result;};
template <class A, class B> struct AppendSafe;
template <class T> struct AppendSafe<NullType,T> {typedef T Result;};
template <int Src, int Dst, int a, class S, class T, class B> 

struct AppendSafe<StateListEx<Src,Dst,a,S,T>,B> 

   {typedef typename AppendSafe<T,StateListEx<Src,Dst,a,S,B> >::Result Result;};

// Включение в множество без повторов
template <int N, class T, class R> struct InsSet;
template <int N, class R> struct InsSet<N,NullType,R> 

   {typedef typename Set<N,R> Result;};
template <int N, class T, class R> struct InsSet<N,Set<N,T>,R> 

   {typedef typename InsSet<N,T,R>::Result Result;};
template <int N, int M, class T, class R> struct InsSet<N,Set<M,T>,R> 

   {typedef typename InsSet<N,T,Set<M,R> >::Result Result;};

// Включение в граф без повторов
template <int S, int D, int C, class T, class R> struct InsNode;
template <int S, int D, int C, class R> struct InsNode<S,D,C,NullType,R> 

   {typedef typename Node<R,S,D,C> Result;};
template <int S, int D, int C, class T, class R> 

struct InsNode<S,D,C,Node<T,S,D,C>,R> 

   {typedef typename InsNode<S,D,C,T,R>::Result Result;};
template <int S, int D, int C, int s, int d, int c, class T, class R> 

struct InsNode<S,D,C,Node<T,s,d,c>,R> 

   {typedef typename InsNode<S,D,C,T,Node<R,s,d,c> >::Result Result;};

// Включение в список состояний без повторов
template <int N, class S, class T, class R> struct InsState;
template <int N, class S, class R> struct InsState<N,S,NullType,R> 

   {typedef typename StateList<N,S,R> Result;};
template <int N, class S, class T, class R> 

struct InsState<N,S,StateList<N,S,T>,R> 

   {typedef typename InsState<N,S,T,R>::Result Result;};
template <int N, int n, class S, class s, class T, class R> 

struct InsState<N,S,StateList<n,s,T>,R> 

   {typedef typename InsState<N,S,T,StateList<n,s,R> >::Result Result;};

// Слияние списков без повторов (A => B)
template <class A, class B> struct Join;
template <class B> struct Join<NullType,B> {typedef B Result;};
template <int N, class T, class B> struct Join<Set<N,T>,B> 

  {typedef typename Join<T,typename InsSet<N,B,NullType>::Result>::Result Result;};
template <int S, int D, int C, class T, class B> 

struct Join<Node<T,S,D,C>,B> 

  {typedef typename Join<T,typename InsNode<S,D,C,B,NullType>::Result>::Result 

   Result;};
template <int N, class S, class T, class B> 

struct Join<StateList<N,S,T>,B> 

  {typedef typename Join<T,typename InsState<N,S,B,NullType>::Result>::Result 

   Result;};
template <int Src, int Dst, int a, class S, class T, class B> 

struct Join<StateListEx<Src,Dst,a,S,T>,B> 

  {typedef typename Join<T,typename InsState<Dst,S,B,NullType>::Result>::Result  

   Result;};

// Преобразование элементов списка
template <class T, int V, class R, template <int,int> class F> struct Map;
template <int V, class R, template <int,int> class F> 

struct Map<NullType,V,R,F> {typedef R Result;};
template <int N, class T, int V, class R, template <int,int> class F> 

struct Map<Set<N,T>,V,R,F>
{ typedef typename Map<T,V,Set<F<N,V>::Result,R>,F>::Result Result;
};
template <class T, int S, int D, int C, int V, class R, template <int,int> class F> struct Map<Node<T,S,D,C>,V,R,F>
{ typedef typename Map<T,V,Node<R,F<S,V>::Result,F<D,V>::Result,C>,F>::Result 

  Result;
};

Не буду объяснять подробно, что здесь да как, скажу только, что эти шаблоны, позволяют представлять произвольные графы в CompileTime и выполнять над их списками дуг некие базовые операции (вроде слияния списков). 

Итак, у нас на руках были графы. Но надо же было как-то представить и регулярные выражения. На помощь пришла все та-же книга. Достаточно было представить четыре элемента, чтобы из них можно было построить все остальное.

C - дуга:

template <char Chr>
struct C
{ typedef typename Node<NullType,0,1,Chr> Result;
  enum {Count = 2};
};
 

E - последовательность дуг:

template <int X, int N>
struct ConvA { enum { Result = (X==1) ? (X+N-1) : X }; };

template <int X, int N>
struct ConvB { enum { Result = (X==1) ? 1 : (X+N) }; };

template <class A, class B>
struct EImpl
{ private:
    typedef typename Map<typename A::Result, A::Count, NullType, ConvA>::Result A1;
    typedef typename Map<typename B::Result, A::Count, NullType, ConvB>::Result B1;
  public:
    typedef typename Append<A1,B1>::Result Result;
    enum {Count = A::Count+B::Count};
};
template <class T1, class T2, 

          class T3 = NullType, class T4 = NullType, class T5 = NullType>
struct E: public EImpl<T1, E<T2,T3,T4,T5> > {};
template <class T1, class T2>
struct E<T1,T2,NullType,NullType,NullType>: public EImpl<T1,T2> {};

Соответсвующая графу:

D - альтернатива:

template <int X, int N>
struct Add { enum { Result = X+N }; };

template <class A, class B>
struct DImpl
{ private:
    typedef typename Append<typename Map<typename A::Result, 2, 

                                         NullType, Add>::Result,
                            typename Map<typename B::Result, A::Count+2, 

                                         NullType, Add>::Result
                           >::Result N0;
    typedef typename   Node<N0,0,2> N1;
    typedef typename   Node<N1,0,A::Count+2> N2;
    typedef typename   Node<N2,3,1> N3;
  public:
    typedef typename   Node<N3,A::Count+3,1> Result;
    enum {Count = A::Count+B::Count+2};
};
template <class T1, class T2, 

          class T3 = NullType, class T4 = NullType, class T5 = NullType>
struct D: public DImpl<T1, D<T2,T3,T4,T5> > {};
template <class T1, class T2>
struct D<T1,T2,NullType,NullType,NullType>: public DImpl<T1,T2> {};

Реализующая граф:

Q - квантификатор:

template <class T, int Min = 0, int Max = 0> struct Q
{ Q() {STATIC_ASSERT(Min<=Max, Q_Spec);}
  private:
    typedef typename Map<typename T::Result, T::Count, NullType, ConvA>::Result A1;
    typedef typename Map<typename Q<T,Min,Max-1>::Result, T::Count, 

                         NullType, ConvB>::Result B1;
  public:
    typedef typename Node<typename Append<A1,B1>::Result,0,T::Count> Result;
    enum {Count = T::Count+Q<T,Min,Max-1>::Count};
};
template <class T, int N> struct Q<T,N,N>
{ private:
    typedef typename Map<typename T::Result, T::Count, NullType, ConvA>::Result A1;
    typedef typename Map<typename Q<T,N-1,N-1>::Result, T::Count, 

                         NullType, ConvB>::Result B1;
  public:
    typedef typename Append<A1,B1>::Result Result;
    enum {Count = T::Count+Q<T,N-1,N-1>::Count};
};
template <class T> struct Q<T,1,1>: public T {};
template <class T>
struct Q<T,0,0>
{ private:
    typedef typename Node<typename Map<typename T::Result, 2, 

                          NullType, Add>::Result,0,2> N0;
    typedef typename Node<N0,3,1> N1;
    typedef typename Node<N1,3,2> N2;
  public:
    typedef typename Node<N2,0,1> Result;
    enum {Count = T::Count+2};
};
template <class T>
struct Q<T,1,0>
{ public:
    typedef typename Node<typename T::Result,1,0> Result;
    enum {Count = T::Count};
};
template <class T>
struct Q<T,0,1>
{ public:
    typedef typename Node<typename T::Result,0,1> Result;
    enum {Count = T::Count};
};

который соответствует графу:

Теперь можно записать наше регулярное выражение:

typedef E< Q< D< C<'a'>, C<'b'> > >, C<'a'>, C<'b'>, C<'b'> >::Result G;

Выглядит ужасно, но нам ведь главное принцип? 

Когда основная часть пути была пройдена, грех было не реализовать собственно само преобразование:

enum CONSTS {
   MAX_FIN_STATE = 9
};

// Реализация DFA
template <class Graph> class DFAImpl;
template <class T, int Src, int Dst, char Chr>
class DFAImpl<Node<T,Src,Dst,Chr> >: public DFAImpl<typename T>
{ public:
    typedef typename    DFAImpl<typename T>::ResultType ResultType;
    ResultType          Parse(char C)
    {
      if ((State==Src)&&(C==Chr)) {
           State = Dst;
           if (State<MAX_FIN_STATE) {
               State = 0;
               return rtSucceed;
           }
           return rtNotCompleted;
      }
      return DFAImpl<typename T>::Parse(C);
    }
    void Dump(void) {T::Dump();}
};
template <>
class DFAImpl<NullType>
{ public:
    DFAImpl():          State(0) {}
    enum ResultType {
       rtNotCompleted = 0,
       rtSucceed      = 1,
       rtFailed       = 2
    };
    ResultType          Parse(char C)
    {  State = 0;
       return rtFailed;
    }
  protected:
    int                 State;
};

// Вычисление хода (списка состояний) из вершины
// N - Узел
// T - Граф
// R - Результирующее состояние
// a - Символ алфавита
template <int N, class T, class R, int a = 0> struct Move;
template <int N, class R, int a> struct Move<N,NullType,R,a> {typedef R Result;};
template <int N, class T, int D, class R, int a> struct Move<N,Node<T,N,D,a>,R,a>
{ typedef typename Move<N,T,typename InsSet<D,R,NullType>::Result,a>::Result 

  Result;
};
template <int N, int M, class T, int D, class R, int a, int b> 

struct Move<N,Node<T,M,D,b>,R,a>
{ typedef typename Move<N,T,R,a>::Result Result;
};

// Фильтрация списка по условию F
// T - Исходный список (Set, StateListEx)
// С - Значение параметра предиката F
// R - Результирующий список (Set, StateListEx)
// F - Предикат (Exist, NotExist, Important)
template <class T, class C, class R, template <int,class> class F> struct Filter;
template <class C, class R, template <int,class> class F> 

struct Filter<NullType,C,R,F> {typedef R Result;};
template <int N, class T, class C, class R, template <int,class> class F> 

struct Filter<Set<N,T>,C,R,F>
{ typedef typename If<F<N,C>::Result,
                      typename Filter<T,C,typename Set<N,R>,F>::Result,
                      typename Filter<T,C,R,F>::Result
                     >::Result Result;
};
template <int Src, int Dst, int a, class S, class T, class C, class R, 

          template <int,class> class F>
struct Filter<StateListEx<Src,Dst,a,S,T>,C,R,F>
{ typedef typename If<F<Dst,C>::Result,
          typename Filter<T,C,typename StateListEx<Src,Dst,a,S,R>,F>::Result,
          typename Filter<T,C,R,F>::Result
  >::Result Result;
};

// Вычисление e-замыкания
// T - Начальный список узлов
// G - Граф
// R - Результирующий список узлов
template <class T, class G, class R> struct EClos;
template <class G, class R> struct EClos<NullType,G,R> {typedef R Result;};
template <int N, class T, class G, class R> struct EClos<Set<N,T>,G,R>
{ private:
  typedef typename Move<N,G,NullType>::Result L;
  typedef typename 

  Filter<L,typename Append<T,R>::Result,NullType,NotExist>::Result F;
  public:
    typedef typename EClos<typename Append<T,F>::Result,G,
                           typename Set<N,R>
                          >::Result Result;
};

// Вычисление хода из множества вершин
// T - Состояние
// G - Граф
// R - Результирующее состояние
// a - Символ алфавита
template <class T, class G, class R, int a> struct MoveSet;
template <class G, class R, int a> struct MoveSet<NullType,G,R,a> 

{typedef R Result;};
template <int N, class T, class G, class R, int a> 

struct MoveSet<Set<N,T>,G,R,a>
{ typedef typename MoveSet<T,G,typename 

    Join<R,typename Move<N,G,NullType,a>::Result>::Result,a>::Result Result;
};

// Вычисление списка состояний, полученных всеми ходами из вершины
// N - Генератор номеров узлов
// K - Генератор номеров финальных узлов
// T - Алфавит
// n - Текущий узел
// S - Текущее состояние (Set)
// G - Граф
// R - Результирующий список расширенных состояний
template <int N, int K, class T, int n, class S, class G, class R> struct MoveList;
template <int N, int K, int n, class S, class G, class R> struct MoveList<N,K,NullType,n,S,G,R> {typedef R Result;};
template <int N, int K, int a, class T, int n, class S, class G, class R> struct MoveList<N,K,Set<a,T>,n,S,G,R>
{ private:
    typedef typename MoveSet<S,G,NullType,a>::Result S0;
    typedef typename EClos<S0,G,NullType>::Result S1;
    enum { N1 = (NotExist<1,S1>::Result)?K:N };
  public:
    typedef typename MoveList<(N==N1)?(N+1):N,
                              (K==N1)?(K+1):K,
                              T,n,S,G,
                              StateListEx<n,N1,a,S1,R> >::Result Result;
};

// Построение алфавита языка по графу NFA
// T - Граф
// R - Результирующий алфавит
template <class T, class R> struct Alf;
template <class R> struct Alf<NullType,R> {typedef R Result;};
template <class T, int S, int D, class R> struct Alf<Node<T,S,D,0>,R> {typedef typename Alf<T,R>::Result Result;};
template <class T, int S, int D, int a, class R> struct Alf<Node<T,S,D,a>,R>
{ typedef typename Alf<T, typename InsSet<a,R,NullType>::Result>::Result Result;
};

// Инкремент генератора узлов
// T - Список состояний (StateListEx)
// R - Результирующее значение генератора
// F - Предикат (Exist, NotExist)
template <class T, int R, template <int,class> class F> struct Incr;
template <int R, template <int,class> class F> 

struct Incr<NullType,R,F> {enum {Result = R};};
template <int Src, int N, int a, class S, class T, int R, template <int,class> class F> struct Incr<StateListEx<Src,N,a,S,T>,R,F>
{ enum { Result = Incr<T, (F<1,S>::Result)?((N>=R)?(N+1):R):R, F>::Result};
};

// Определение значимого узла
// N - Узел
// G - Граф
template <int N, class G> struct Important;
template <int N> struct Important<N,NullType> {enum {Result = (N==1)};};
template <int N, class T, int D> struct Important<N,Node<T,N,D,0> > 

{enum { Result = Important<N,T>::Result };};
template <int N, class T, int D, int C> struct Important<N,Node<T,N,D,C> > 

{enum {Result = true};};
template <int N, class T, int S, int D, int C> struct Important<N,Node<T,S,D,C> > {enum { Result = Important<N,T>::Result };};

// Оптимизированное построение списка значимых узлов
// T - Граф
// R - Результирующий список
template <class T, class R> struct ImportantOpt;
template <class R> struct ImportantOpt<NullType,R> 

{typedef typename InsSet<1,R,NullType>::Result Result;};
template <class T, int S, int D, class R> struct ImportantOpt<Node<T,S,D,0>,R>
{ typedef typename ImportantOpt<T,R>::Result Result;
};
template <class T, int S, int D, int C, class R> 

struct ImportantOpt<Node<T,S,D,C>,R>
{ typedef typename ImportantOpt<T,typename InsSet<S,R,NullType>::Result>::Result 

  Result;
};

// Сравнение состояний по совокупности значимых узлов
// A - Список узлов (Set)
// B - Список узлов (Set)
// G - Граф
// I - Список значимых узлов (вычислять однократно на верхнем уровне)
template <class A, class B, class G> struct EquEx
{ private:
    typedef typename Filter<A,G,NullType,Important>::Result A1;
    typedef typename Filter<B,G,NullType,Important>::Result B1;
  public:
    enum { Result = Equ<A1,B1>::Result };
};
template <class A, class B, class I> struct EquExOpt
{ private:
    typedef typename Filter<A,I,NullType,Exist>::Result A1;
    typedef typename Filter<B,I,NullType,Exist>::Result B1;
  public:
    enum { Result = Equ<A1,B1>::Result };
};

// Получение списка узлов
// G - Граф
// R - Результирующий список
template <class T, class R> struct NodeList;
template <class R> struct NodeList<NullType,R> {typedef R Result;};
template <class T, int S, int D, int C, class R> struct NodeList<Node<T,S,D,C>,R>
{ private:
    typedef typename InsSet<S,R, NullType>::Result R0;
    typedef typename InsSet<D,R0,NullType>::Result R1;
  public:
    typedef typename NodeList<T,R1>::Result Result;
};

// Проверка вхождения (по равенству состояний)
// T - Контрольный список (StateList)
// S - Искомое состояние (Set)
// I - Список значимых узлов
template <class T, class S, class I> struct ExistS;
template <class S, class I> struct ExistS<NullType,S,I> {enum {Result = false};};
template <int N, class s, class T, class S, class I> struct ExistS<StateList<N,s,T>,S,I>
{ enum { Result = (Equ<s,S>::Result) ? // EquExOpt<s,S,I>::Result
                  true :
                  ExistS<T,S,I>::Result
       };
};

// Отброс ранее найденных узлов
// T - Исходный список (StateListEx)
// С - Контрольный список (StateList)
// I - Список значимых узлов (Set)
// R - Результирующий список (StateListEx)
template <class T, class C, class I, class R> struct FilterT;
template <class C, class I, class R> struct FilterT<NullType,C,I,R> 

{typedef R Result;};
template <int Src, int Dst, int a, class S, class T, class C, class I, class R> struct FilterT<StateListEx<Src,Dst,a,S,T>,C,I,R>
{ typedef typename If<ExistS<C,S,I>::Result,
                      typename FilterT<T,C,I,R>::Result,
                      typename FilterT<T,C,I,StateListEx<Src,Dst,a,S,R> >::Result
                     >::Result Result;
};

// Формирование результирующего графа
// T - Множество ранее сформированных вершин (StateList)
// a - Символ перехода к искомой вершине
// S - Исходное состояние (Set)
// I - Список значимых узлов
// R - Формируемый граф
template <class T, int Src, int Dst, int a, class S, class I, class R> struct GenImpl;
template <int Src, int Dst, int a, class S, class I, class R> struct GenImpl<NullType,Src,Dst,a,S,I,R> {typedef R Result;};
template <int n, class s, class T, int Src, int Dst, int a, class S, class I, class R> struct GenImpl<StateList<n,s,T>,Src,Dst,a,S,I,R>
{ typedef typename If<Equ<s,S>::Result, // EquExOpt<s,S,I>
                      Node<R,Src,n,a>,
                      typename GenImpl<T,Src,Dst,a,S,I,R>::Result
                     >::Result Result;
};

// Формирование результирующего графа
// T - Множество новых узлов
// С - Ранее сформированные узлы
// I - Множество значимых узлов
// R - Результирующий граф
template <class T, class C, class I, class R> struct Gen;
template <class C, class I, class R> struct Gen<NullType,C,I,R> 

{typedef R Result;};
template <int Src, int Dst, int a,class S, class T, class C, class I, class R> struct Gen<StateListEx<Src,Dst,a,S,T>,C,I,R>
{ typedef typename Gen<T,C,I,typename GenImpl<C,Src,Dst,a,S,I,R>::Result>::Result 

  Result;
};

// Шаг преобразования
// N - Генератор номеров результирующих узлов
// K - Генератор номеров финальных узлов
// G - Граф (NFA)
// A - Алфавит (Set)
// I - Список значимых узлов (Set)
// R - Результирующий граф (DFA)
// M - Список помеченных состояний (StateList)
// D - Список непомеченных состояний (StateListEx)
template <int N, int K, class G, class A, class I, class R, class M, class D> struct ConvertImpl;
template <int N, int K, class G, class A, class I, class R, class M> struct ConvertImpl<N,K,G,A,I,R,M,NullType> {typedef R Result;};
template <int N, int K, class G, class A, class I, class R, class M, int Src, int Dst, int a, class S, class D>
struct ConvertImpl<N,K,G,A,I,R,M,StateListEx<Src,Dst,a,S,D> >
{ private:
    typedef typename MoveList<N,K,A,Dst,S,G,NullType>::Result T;
    typedef typename StateList<Dst,S,M> M1;
    typedef typename Append<D,M1>::Result MD;
    typedef typename FilterT<T,MD,I,NullType>::Result T1;
    typedef typename AppendSafe<T1,D>::Result D1;
    typedef typename Gen<T,typename Append<T1,MD>::Result,I,R>::Result R1;
    enum { N1 = Incr<T1,N,Exist>::Result,
           K1 = Incr<T1,K,NotExist>::Result
         };
  public:
    typedef typename ConvertImpl<N1,K1,G,A,I,R1,M1,D1>::Result Result;
};

// Преобразование NFA -> DFA
// G - Граф
// R - Результирующий граф
template <class G, class R> struct Convert
{ private:
    typedef typename Alf<G,NullType>::Result A;
    typedef typename ImportantOpt<G,NullType>::Result I;
  public:
    typedef typename ConvertImpl<1,MAX_FIN_STATE+1,G,A,I,NullType,NullType,
                                 StateListEx<0,0,0,typename EClos<Set<0,NullType>,G,NullType>::Result,NullType> >::Result Result;
};

template <class T>
class DFA: public DFAImpl<typename Convert<typename T::Result,NullType>::Result> {};

Я умолчу о том, сколько раз мне понадобилось расшифровывать километровые сообщения об ошибках в шаблонах, о том, как зависал компилятор, и как мне пришлось оптимизировать алгоритм, результатом, стало то, что следующий код стал работать:

typedef Convert<G,NullType>::Result R;
R::Dump();

На выходе он выдавал список дуг:

  1 -a->  10
  1 -b->  11
 13 -a->  10
 13 -b->   1
 10 -a->  10
 10 -b->  13
 11 -a->  10
 11 -b->  11
  0 -a->  10
  0 -b->  11

0 узел соответсвовал начальному состоянию ДКА, 1 - конечному. Можно легко убедиться, что это именно тот самый граф, который мы рассчитывали получить. Делать на его основе интерпретатор регулярных выражений я не стал, поскольку меня уже отпустило. Чего и Вам желаю :)

Весь проект можно взять здесь.