general
GNU screenのコンフィグに「hardstatus alwayslastline ...」を書いていると一番下のラインにそのterminalのシェル(zshやbash)の文字列が表示されるが、どこのterminalで何の作業をしているか忘れてしまった場合全て「zsh」などと表示されていて見分けがつか…
SilverlightとJavaFXが気になる。 Silverlightは軽いらしくしかもFlushキラーとのことで今までなんかもっさりしてたWeb2.0的なサイトが軽くなるのかな？ JavaFXはサーバ側Javaとの連携がどの程度取れるんだろ？ObjectのSerializationとか出来たら便利っぽい…
以前apacheのソースを読んでて、APRにあるマクロで #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do { \ APR_RING_PREV((ep1), link) = (lep); \ APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link); \ APR_RING_PREV(APR_RING_NEXT((lep), l…
正規表現コーディング完了。 ./RegeX '(a*|b+)de(f|c)' adef こんなんとかちゃんと認識してくれた。（adefは左記の正規表現を満たす） いやー ちゃんと動くと楽しいねやっぱ。 NFAからDFAへの変換メイン部は以下の感じ void DfaClass::nfaToDfa(NfaClass& nf…
DFAのコーディング完了 ε遷移をDFAの状態に追加する部分がちょっとおかしいのでデバッグ中。
NFAからDFAへの変換アルゴリズムを以下のように変更 ※「状態」と単体で書いた場合はDFAの状態とする Dtrans ... nnodeの状態番号のリストを保持させる Dnode .... 二つの状態を表しそれをe_node, e_transitionとし、それぞれ、「DFAの状態」と「その状態から…
昨日の続き。 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;>…
前回のコーディングでntransというNFA用のデータ構築まで出来、次はnnodeという状態番号を元にしたデータを作成し、その後DFAを構築する。 まず、NFAのntransからnnodeへの変換を考える。 struct Nnode { char ch; int to; Nnode* next; } *nnode[MAX]; nnod…
前回考えた擬似コーディングを元に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>…
NFAのデータ構造をどうするか考えてみた。 状態番号ではなく状態遷移に着目して以下のような構造を考える struct ntrans { char ch; int from; int to; }; chは文字で空文字の場合は「-1」としてセットしておく。 fromはどの遷移元の状態番号でtoは遷移先の…
とりあえず前回作った規則を元にC++でコーディング (a|b)とか(a+|b)とかa+|b*|cとか((a+|b)|c*)とかを正しくTREEにしてくれた。 次はこの木構造を元にNFAを作成するクラスを作る予定 #include <iostream> using namespace std; #define eleft e.child.left #define eri</iostream>…
どうも「Cプログラマのためのアルゴリズム（以下参考文献①)」に書いてある正規表現の構文規則がしっくりこないので何故か考えてみた。以下の正規表現の定義と規則が完全に一致してないからだと思った。 （おそらく著者の頭の中では既に正規表現の構文規則が…
以下のフェーズを考える 1．正規表現の文法を考える 2. 1の文法が構文解析した時にあいまい（解析木が複数通りある）で無い事を確かめるため、LL(1)文法を満たしているかを考察する まず1だけど、文法（構文規則）を考える。 正規表現の定義は前回与えた通り…
NFA、DFAを勉強したので以下の定義を満たす最小構成(＋α）の正規表現をコーディングしてみようかと思う アルファベットA上の正規表現とは以下の以下の規則によって作られる 表現の事である (1) ε(空記号列)は正規表現である (2) Aの要素a (a⊆A)は正規表現で…
文字列解析のBM法で、文字をスキップするためのテーブルに入れる値を 考えていた時に、iをx軸上において考えれば楽なんじゃないかと思って 思考してみた 検索される文字列をtextとし、探索する文字列をpatternと呼ぶ。 textの文字配置位置をX軸上の整数値と…
C++(C)で探索アルゴリズムのB木（その他ハッシュのチェイン法オープンアドレス法とかクイックソート、マージソートとか）を定義のみ見て書いてみたんですが、、添え字のiとかjとかkとかi-1とかj+1とかk
