之所以說(shuō)是“簡(jiǎn)要實(shí)現(xiàn)”一方面是因?yàn)樗惴ú凰愀呱?，算法的?shí)現(xiàn)也不精致，甚至連我對(duì)其的理解也不夠本質(zhì)。
我只不過(guò)不想在工作若干年后還是一個(gè)只會(huì)打字的程序員。學(xué)點(diǎn)什么東西，真正精通點(diǎn)什么東西才對(duì)得起喜歡
技術(shù)的自己。
附件中的代碼粗略實(shí)現(xiàn)了《編譯原理》龍書中的幾個(gè)算法。包括解析正則表達(dá)式，建立NFA，然后用NFA去匹
配目標(biāo)字符串；或者從NFA建立DFA，然后匹配。解析正則表達(dá)式我用了比較繁瑣的方法，有詞法和語(yǔ)法分析
過(guò)程。詞法分析階段將字符和一些操作符整理出來(lái)，語(yǔ)法分析階段在建立語(yǔ)法樹的過(guò)程中對(duì)應(yīng)地建立NFA。
當(dāng)然，因?yàn)檎Z(yǔ)法樹在這里并沒(méi)有用處，所以并沒(méi)有真正地建立。
從正則表達(dá)式到NFA比較簡(jiǎn)單，很多編譯原理書里都提到過(guò)，如：s|t表達(dá)式對(duì)應(yīng)于下面的NFA:
代碼中用如下的結(jié)構(gòu)描述狀態(tài)和狀態(tài)機(jī)中的轉(zhuǎn)換：
#define E_TOK (0)
/* transition */
struct tran
{
char c;
struct state *dest;
struct tran *next;
};
struct state
{
/* a list of transitions */
struct tran *trans;
/* inc when be linked */
int ref;
};
即，每一個(gè)狀態(tài)都有一個(gè)轉(zhuǎn)換列表，每個(gè)轉(zhuǎn)換都有一個(gè)目標(biāo)狀態(tài)（即該轉(zhuǎn)換指向的狀態(tài)）以及轉(zhuǎn)換字符。
貌似通過(guò)以上方法建立出來(lái)的狀態(tài)機(jī)每個(gè)狀態(tài)最多只會(huì)有2個(gè)轉(zhuǎn)換？
建立好NFA后，由NFA匹配目標(biāo)字符串使用了一種構(gòu)造子集法（《編譯原理》3.7.2節(jié)）：
這個(gè)算法里針對(duì)NFA的幾個(gè)操作，如e-closure、move等在由NFA轉(zhuǎn)換DFA時(shí)也被用到，因此代碼里單獨(dú)
做了封裝（state_oper.c）。這個(gè)算法本質(zhì)上貌似就是一次步進(jìn)（step）多個(gè)狀態(tài)。
至于由NFA轉(zhuǎn)DFA,則是相對(duì)簡(jiǎn)單的子集構(gòu)造法：
在我以前編譯原理課考試的前一天晚上（你懂的）我就對(duì)這些算法頗為疑惑。在以后看各種編譯
原理教材時(shí)，我始終不懂NFA是怎么轉(zhuǎn)到DFA的。就算懂了操作步驟（我大學(xué)同學(xué)曾告訴我這些步驟，雖然
不知道為什么要那樣做），一段時(shí)間后依然搞忘。很喜歡《編譯原理》龍書里對(duì)這個(gè)算法最本質(zhì)的說(shuō)明：
源代碼我是用GCC手工編譯的，連makefile也沒(méi)有。三個(gè)test_XXX.c文件分別測(cè)試幾個(gè)模塊。test_match.c
基本依賴除掉test外所有c文件，全部鏈接在一塊即可。當(dāng)然，就經(jīng)驗(yàn)而言我知道是沒(méi)幾個(gè)人會(huì)去折騰我的這些
代碼的。這些在china的領(lǐng)導(dǎo)看來(lái)對(duì)工作有個(gè)鳥用的代碼讀起來(lái)我自己也覺(jué)得費(fèi)力，何況，我還不倫不類地用了
不知道算哪個(gè)標(biāo)準(zhǔn)的c寫了這些。
你不是真想下載。對(duì)于這種代碼，有BUG是必然的，你也不用在此文若干個(gè)月后問(wèn)我多少行是什么意思，因?yàn)?/p>
那個(gè)時(shí)候我也忘了:D。