■

前回考えた擬似コーディングを元にNtrans表の作成までをコーディング。

nfa.h

#ifndef _NFA_INCLUDE_CHECK
#define _NFA_INCLUDE_CHECK

#include <iostream>
#include "regex.h"

const int NTRANS_MAX = 128;
const char EMPTY = -1;

struct Ntrans {
  char ch;
  int to;
  int from;
};

struct Nnode {
  char ch;
  int to;
  Nnode* next;
};


class NfaClass {
  Ntrans* ntrans[NTRANS_MAX];
  int nodeNum;
  int ntransNum;
  void nfaIter(Stree& st, Leaf* leaf, int start, int last);
  void createTrans(int from, int to, char ch);
  int getNewNode() { return ++nodeNum; }

public:
  NfaClass(Stree& st) {

        nodeNum = 1;
        ntransNum = 0;

        Leaf* leaf = st.getRoot();
        nfaIter(st, leaf, 0, 1);
  }
  ~NfaClass();
  void showAll();
};

#endif

nfa.cpp

#include "nfa.h"

void NfaClass::nfaIter(Stree& st, Leaf* leaf, int start, int last)
{
  switch (leaf->op) {
  case e_union:
        {
          int newNodeA, newNodeB, newNodeC, newNodeD;
          newNodeA = getNewNode();
          newNodeB = getNewNode();
          newNodeC = getNewNode();
          newNodeD = getNewNode();

          createTrans(start, newNodeA, EMPTY);
          createTrans(newNodeB, last, EMPTY);
          createTrans(start, newNodeC, EMPTY);
          createTrans(newNodeD, last, EMPTY);

          nfaIter(st, leaf->eleft, newNodeA, newNodeB);
          nfaIter(st, leaf->eright, newNodeC, newNodeD);
        }
        break;

  case e_concat:
        {
          int newNode = getNewNode();
          nfaIter(st, leaf->eleft, start, newNode);
          nfaIter(st, leaf->eright, newNode, last);
        }
        break;

  case e_closure:
        {
          int newNodeA, newNodeB;
          newNodeA = getNewNode();
          newNodeB = getNewNode();

          createTrans(start, newNodeA, EMPTY);
          createTrans(newNodeB, newNodeA, EMPTY);
          createTrans(newNodeA, last, EMPTY);

          nfaIter(st, leaf->eleft, newNodeA, newNodeB);
        }
        break;

  case e_pclosure:
        {
          int newNodeA, newNodeB;
          newNodeA = getNewNode();
          newNodeB = getNewNode();

          createTrans(start, newNodeA, EMPTY);
          createTrans(newNodeB, newNodeA, EMPTY);
          createTrans(newNodeB, last, EMPTY);

          nfaIter(st, leaf->eleft, newNodeA, newNodeB);
        }
        break;

  case e_char:
        createTrans(start, last, leaf->ech);
        break;

  case e_empty:
        createTrans(start, last, EMPTY);
        break;
  }
}

void NfaClass::createTrans(int from, int to, char ch)
{
  Ntrans* nt = new Ntrans();
  nt->ch = ch;
  nt->to = to;
  nt->from = from;
  ntrans[ntransNum++] = nt;
}

NfaClass::~NfaClass()
{
}

void NfaClass::showAll() {
  for (int i=0; i<ntransNum; i++) {
        Ntrans* nt = ntrans[i];
        cout << "from:" << nt->from << " "
                 << "to:" << nt->to << " "
                 << "char: " << nt->ch << endl;
  }
}

後はこれを元にNnodeを作って、DFAを作る。