■

正規表現コーディング完了。 ./RegeX '(a*|b+)de(f|c)' adef こんなんとかちゃんと認識してくれた。（adefは左記の正規表現を満たす）いやーちゃんと動くと楽しいねやっぱ。 NFAからDFAへの変換メイン部は以下の感じ void DfaClass::nfaToDfa(NfaClass& nf…

2007-03-16

■

general regex general regex

DFAのコーディング完了 ε遷移をDFAの状態に追加する部分がちょっとおかしいのでデバッグ中。

2007-03-15

■

general regex general regex

NFAからDFAへの変換アルゴリズムを以下のように変更 ※「状態」と単体で書いた場合はDFAの状態とする Dtrans ... nnodeの状態番号のリストを保持させる Dnode .... 二つの状態を表しそれをe_node, e_transitionとし、それぞれ、「DFAの状態」と「その状態から…

2007-03-14

■

general regex general regex

昨日の続き。 NFAのdtransからdnodeへの変換は以下のようにした void NfaClass::setTransToNode() { for (int i=0; i<ntransNum; i++) { int from = ntrans[i]->from; if (nnode[from] != NULL) { // create new Nnode, and set to next link of nnode[i]. Nnode* newNode = new Nnode(); newNode->ch </ntransnum;>…

2007-03-13

■

general regex general regex

前回のコーディングでntransというNFA用のデータ構築まで出来、次はnnodeという状態番号を元にしたデータを作成し、その後DFAを構築する。まず、NFAのntransからnnodeへの変換を考える。 struct Nnode { char ch; int to; Nnode* next; } *nnode[MAX]; nnod…

2007-03-10

■

general regex general regex

前回考えた擬似コーディングを元に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; </iostream>…

2007-03-09

■

general regex general regex

NFAのデータ構造をどうするか考えてみた。状態番号ではなく状態遷移に着目して以下のような構造を考える struct ntrans { char ch; int from; int to; }; chは文字で空文字の場合は「-1」としてセットしておく。 fromはどの遷移元の状態番号でtoは遷移先の…