傳統(tǒng)的系統(tǒng)調(diào)用是怎樣的？    —— int 0x80的時代

....             ；通過寄存器傳參
mov $n ,eax      ；將系統(tǒng)調(diào)用號放到eax中
int 0x80

sysenter/sysexit的出場

        在一個Kernel.org的郵件列表中，有一封郵件討論了“"Intel P6 vs P7 system call performance”，最后得出的結(jié)論是采用傳統(tǒng)的int 0x80的系統(tǒng)調(diào)用浪費了很多時間（具體原因可以看參考資料1），而sysenter/sysexit可以彌補這個缺點，所以決定在linux內(nèi)核中用后都替換前者（最終在2.6版本的內(nèi)核中才加入了此功能，即采用sysenter/sysexit）。

        在替換之前首先需要知道滿足如下條件的ntel機器才會有sysenter/sysexit指令對：Family >= 6，Model >= 3，Stepping >= 3

        如何用替換sysenter/sysexit替換以前的int 0x80呢？linux kenerl 需要考慮到這點：有的機器并不支持sysenter/sysexit  ， 于是它跟glibc說好了，“你以后調(diào)用系統(tǒng)調(diào)用的時候就從我給你的這個地址調(diào)用，這個地址指向的內(nèi)容要么是int 0x80調(diào)用方式，要么是sysenter/sysexit調(diào)用方式，我會根據(jù)機器來選擇其中一個”（kernel與glibc的配合是如此的默契），這個地址便是vsyscall的首地址。

         可以將vdso看成一個shared objdect file（這個文件實際上不存在）,內(nèi)核將其映射到某個地址空間，被所有程序所共享。（我覺得這里用到了一個技術(shù)：多個虛擬頁面映射到同一個物理頁面。即內(nèi)核把vdso映射到某個物理頁面上，然后所有程序都會有一個頁表項指向它，以此來共享，這樣每個程序的vdso地址就可以不相同了）

hex108@ubuntu:~/program$ uname -a
Linux ubuntu 2.6.35-22-generic #33-Ubuntu SMP Sun Sep 19 20:34:50 UTC 2010 i686 GNU/Linux
hex108@ubuntu:~/program$ sudo sysctl -w kernel.randomize_va_space=0     //這個是必須的，否則vdso的地址是隨機的(vsyscall的地址也會相應

                                                                        // 地發(fā)生變化 )，在下面dd的時候就會出現(xiàn)錯誤

                                                                        //dd: reading `/proc/self/mem': Input/output error

                                                                        
kernel.randomize_va_space = 0
hex108@ubuntu:~/program$ cat /proc/self/maps 
00110000-0012c000 r-xp 00000000 08:01 260639     /lib/ld-2.12.1.so
0012c000-0012d000 r--p 0001b000 08:01 260639     /lib/ld-2.12.1.so
0012d000-0012e000 rw-p 0001c000 08:01 260639     /lib/ld-2.12.1.so
0012e000-0012f000 r-xp 00000000 00:00 0          [vdso]
0012f000-00286000 r-xp 00000000 08:01 260663     /lib/libc-2.12.1.so
00286000-00287000 ---p 00157000 08:01 260663     /lib/libc-2.12.1.so
00287000-00289000 r--p 00157000 08:01 260663     /lib/libc-2.12.1.so
00289000-0028a000 rw-p 00159000 08:01 260663     /lib/libc-2.12.1.so
0028a000-0028d000 rw-p 00000000 00:00 0 
08048000-08051000 r-xp 00000000 08:01 130326     /bin/cat
08051000-08052000 r--p 00008000 08:01 130326     /bin/cat
08052000-08053000 rw-p 00009000 08:01 130326     /bin/cat
08053000-08074000 rw-p 00000000 00:00 0          [heap]
b7df0000-b7ff0000 r--p 00000000 08:01 660864     /usr/lib/locale/locale-archive
b7ff0000-b7ff1000 rw-p 00000000 00:00 0 
b7ffd000-b7ffe000 r--p 002a1000 08:01 660864     /usr/lib/locale/locale-archive
b7ffe000-b8000000 rw-p 00000000 00:00 0 
bffdf000-c0000000 rw-p 00000000 00:00 0          [stack]

hex108@ubuntu:~/program$ dd if=/proc/self/mem of=gate.so bs=4096 skip=$[0x12e] count=1
dd: `/proc/self/mem': cannot skip to specified offset
1+0 records in
1+0 records out
4096 bytes (4.1 kB) copied, 0.00176447 s, 2.3 MB/s
hex108@ubuntu:~/program$ file gate.so 
gate.so: ELF 32-bit LSB shared object, Intel 80386, version 1 (SYSV), dynamically linked, stripped
hex108@ubuntu:~/program$ objdump -d gate.so 

gate.so:     file format elf32-i386


Disassembly of section .text:

ffffe400 <__kernel_sigreturn>:
ffffe400:	58                   	pop    %eax
ffffe401:	b8 77 00 00 00       	mov    $0x77,%eax
ffffe406:	cd 80                	int    $0x80
ffffe408:	90                   	nop
ffffe409:	8d 76 00             	lea    0x0(%esi),%esi

ffffe40c <__kernel_rt_sigreturn>:
ffffe40c:	b8 ad 00 00 00       	mov    $0xad,%eax
ffffe411:	cd 80                	int    $0x80
ffffe413:	90                   	nop

ffffe414 <__kernel_vsyscall>:
ffffe414:	cd 80                	int    $0x80
ffffe416:	c3                   	ret    

 

syscall 才是最后的贏家？

         x86 64位從AMD引進了syscall指令（我在x86 64的機器上，看到的結(jié)果是syscall取代了sysenter/sysexit（所有的系統(tǒng)調(diào)用用的都是syscall）），但是vdso,vsyscall的機制依舊未變，只是kernel決定只在遇到以下幾個系統(tǒng)調(diào)用gettimeofday,time和getcpu（通過內(nèi)核里vsyscall.h中enum vsyscall_num的聲明看出來，或者在glibc源代碼中搜索“VSYSCALL_ADDR_”(

#define VSYSCALL_ADDR_vgettimeofday    0xffffffffff600000

#define VSYSCALL_ADDR_vtime            0xffffffffff600400

#define VSYSCALL_ADDR_vgetcpu          0xffffffffff600800

)）時才采用vdso機制（間接調(diào)用syscall，具體可以參看資料2），其他系統(tǒng)調(diào)用直接用指令syscall，原因是：

---

 

         "快速系統(tǒng)調(diào)用指令"比起中斷指令來說，其消耗時間必然會少一些，但是隨著 CPU 設計的發(fā)展，將來應該不會再出現(xiàn)類似 Intel Pentium4 這樣懸殊的差距。而"快速系統(tǒng)調(diào)用指令"比起中斷方式的系統(tǒng)調(diào)用方式，還存在一定局限，例如無法在一個系統(tǒng)調(diào)用處理過程中再通過"快速系統(tǒng)調(diào)用指令"調(diào)用別的系統(tǒng)調(diào)用。因此，并不一定每個系統(tǒng)調(diào)用都需要通過"快速系統(tǒng)調(diào)用指令"來實現(xiàn)。比如，對于復雜的系統(tǒng)調(diào)用例如 fork，兩種系統(tǒng)調(diào)用方式的時間差和系統(tǒng)調(diào)用本身運行消耗的時間來比，可以忽略不計，此處采取"快速系統(tǒng)調(diào)用指令"方式?jīng)]有什么必要。而真正應該使用"快速系統(tǒng)調(diào)用指令"方式的，是那些本身運行時間很短，對時間精確性要求高的系統(tǒng)調(diào)用，例如 getuid、gettimeofday 等等。因此，采取靈活的手段，針對不同的系統(tǒng)調(diào)用采取不同的方式，才能得到最優(yōu)化的性能和實現(xiàn)最完美的功能。      ----引自參考資料1

---

      

 

ps:文中的內(nèi)核版本為2.6.36，glibc版本為2.11

參考資料:

1.  Linux 2.6 對新型 CPU 快速系統(tǒng)調(diào)用的支持: http://www.ibm.com/developerworks/cn/linux/kernel/l-k26ncpu/index.html  (這篇我覺得最好)

2. System Calls ： http://www.win.tue.nl/~aeb/linux/lk/lk-4.html（里面有程序可以用來搜索vsyscall等的地址，很直接）

3. What is linux-gate.so.1 ： http://www.trilithium.com/johan/2005/08/linux-gate/

4. Intel手冊，里面有各種資料，手冊還是很重要的，也是最基本的

     摘要: lisp的功能還是挺強大的，簡單的幾行代碼就搞定了一個小的“數(shù)據(jù)庫”（經(jīng)驗：調(diào)試macro的時候可以用macroexpand-1展開該macro，看是否與設想的一樣。）。  閱讀全文

最近《hackers & painters》學到的印象最深的一點是：lisp比你想像中的還強大，用lisp吧！

1. 安裝運行環(huán)境

a. 下載emacs，解壓即可。

b. 下載slime，解壓即可

c. 下載sbcl，安裝

d. 配置emacs

       首先需要確定emacs會加載哪里的.emacs配置文件（即emacs的HOME目錄為什么），可以通過改注冊表(新添注冊表項HKEY_CURRENT_USER\Software\GNU\Emacs(新建一個GNU項，然后在GNU項下新建一個子項Emacs)，新增一個項HOME,設置其字符串值為emacs解壓后的目錄)

       在emacs解壓后的目錄中，新建一個.emacs文件，添加如下幾行:

;for lisp mode
(add-to-list 'load-path "D:\\slime\\") ; 注：在windows下路徑分隔符為\\而不是\，否則會被解釋為 D:slime， 或者改成另外一種寫法 D:/slime
(setq inferior-lisp-program "D:\\SteelBankCommonLisp\\sbcl.exe")   ;注：如果此處路徑有空格，在M-x slime時會出現(xiàn)問題：apply: Spawning child process: invalid argument
;(setq inferior-lisp-program "D:\\clisp-2.49\\clisp.exe") 
(require 'slime-autoloads)   ;注意這里加載的是 slime-autoloads，而不是 slime，要不然C-c C-c等很多功能都沒有
(slime-setup '(slime-fancy))
;(slime-setup)

2. 編譯運行

如果要進入用戶交互界面，輸入 M-x slime即可

如果要編譯lisp文件里的函數(shù)：a. 只編譯某個函數(shù),可以將光標放在該函數(shù)上，然后按C-c C-c

b. C-c C-c只能編譯單個函數(shù)，如果文件內(nèi)一些函數(shù)有關(guān)聯(lián)，則這種方式就不好用了，此時可以編譯整個文件

   (load  “lisp_file”)

c. load 某個文件后，如果又修改了該文件中的某個函數(shù)，則可以再用C-c C-c編譯該函數(shù)而不需要重新load該文件

    一個內(nèi)存地址存著一個對應的值，這是比較容易理解的。

    如果程序員必須清楚地知道某塊內(nèi)存存著什么內(nèi)容和某個內(nèi)容存在哪個內(nèi)存地址里了，那他們的負擔可想而知。
    匯編語法對“一個內(nèi)存地址存著一個對應的數(shù)”，作了簡單的“抽象”：把內(nèi)存地址用變量名代替了，對內(nèi)存地址的取值和賦值方式不變。
    c語言對此進行了進一步的抽象：變量 <==> （一個內(nèi)存地址，對應的值）（這里忽略類型等信息）。

    把C語言中的基本類型(int,long,float等),指針，數(shù)組等還原為（一個內(nèi)存地址，對應的值）后，就能更清淅地理解它們了。

    內(nèi)存就相當于(addr,val)的大hash表,c語句的語義基本就是改變hash值。

    為了下文的方便，特定義如下語義（遵循C的標準語義）：

---

    var  <==>  (addr, val)  (var為一個變量名，addr為var在內(nèi)存中的首地址,val為var 的值)
    &var <==> addr
    var  <==> var作為左值出現(xiàn)（即等式左邊）時，var等價于 addr;
               var作為右值出現(xiàn)（即等式左邊）時，var等價于 val;
    *var <==> val

---

    注：符號"<==>" 右邊出的等式 x = y(x是一個內(nèi)存地址，y是一個值); 表示將內(nèi)存地址為x的內(nèi)容置為值y，如addr = 3表示置內(nèi)存addr里的值為3


    現(xiàn)在利用上面的語義解釋一下這些例子：
    int i = 3;
    假設 i的內(nèi)存地址為 0x8049320 ,那么這句話的語義是0x8049320 = 3，經(jīng)過i = 3后，i為(0x8049320,3)

    int b = i;
    假設 b的內(nèi)存地址為 0x8049324 ,那么這句話的語義是0x8049324 = i對應的val = 3,此時b為(0x8049324,3)

    int *p = &b
    指針p也是一個變量，int **p,int *p[8],在這些申明中p都只是一個指針變量，它和其他的變量的不同之處在于它的大小是定的，它的類型信息只是編譯器用來進行類型檢查和其他一些作用的(如果沒有類型檢查，你可以用任何的方式對一個變量進行操作如int i; ****i = 3)。假設p的地址為0x8049328,則根據(jù)p = &b的語義p.addr = b.addr，p為(0x8049328,0x8049324)

    *p = 5;
    語義為 0x8049324 = 5,此時只改變了內(nèi)存地址為0x8049324的值，即改變了b的值(0x8049324,5)，而p的值并未改變

    int **q = &p; //如果寫為int **q = &&i; gcc編譯不通過
    假設q的內(nèi)存地址為0x8049330,語義為 0x8049330 = addr(p) = 0x8049328;所以q為(0x8049330, 0x8049328)
    (int **q = &&i, 要是編譯過了則q應該表示為(0x8049330, x),內(nèi)存地址為x的地方表示為(x,0x8049320)，那么地址x為多少呢? )

    **q = 6
    語義為 val(val(q)) = val(0x8049328) = 0x8049324 = 6,將內(nèi)存地址為0x8049324的內(nèi)容置為6,即將b的值置為6,b為(0x8049324,6)
    
    對于結(jié)構(gòu)，這些語義也適用，因為結(jié)構(gòu)里的成員也是有對應地址的，也能表示為(addr,val)的形式。    
   
    對“一個內(nèi)存地址存著一個對應的值”的抽象程度越高，越不用關(guān)心底層，如java。 
    Haskell已經(jīng)沒有副作用之說了，更不用關(guān)心這些了。

    就這些。       這里有作者之一Dave Thomas在敏捷2009大會上關(guān)于此書的演講(http://www.infoq.com/cn/presentations/dt-pragmatic-programmer)

      這本書的成書方式很有意思。作者非常喜歡program，以至于將這本書的寫作當成了軟件工程，全書用plain text寫成，以soruce code(應 該是他們自己發(fā)明的領(lǐng)域語言DSL~)的方式組織而成，用他們自己寫成的工具build一下后就成了此書，相信他們也以某種版本管理工具對此進行了管理(方便查看版本之間的變化等)，并對書中的code進行了單元測試。
      想像一下他們怎么寫書的(借用HTML的格式猜想一下):
     
      Test時會自動測試書中的程序，如：game.sh；Build之后本書便完成了（書中的code文件會自動讀入）。
     
      這真是一個很成功的“項目”：
      * Automate Everything.
      * 如果需要，則設計自己的小語言
        Perl有一個作解釋器的包http://search.cpan.org/~dconway/Parse-RecDescent-1.965001/lib/Parse/RecDescent.pm
      * Fix Broken Windows
        --Fix small thing,Then big thing will not happen.
      * Don't repeat yourself(DRY)
        -- code duplication
        解決方法: 做成函數(shù)，模塊，類；采用code generators；采用元程序設計(The art of metaprogramming:http://www.ibm.com /developerworks/linux/library/l-metaprog1.html)；采用設計模式(作者覺得采用模式有可能把問題弄復雜)；convertions；metaphors；
        -- Project Duplication
        Fix by producing procduts; Fix with data-driven designs.
      * Do one thing better.
        簡單，低耦合。
      * Do Nothing Twice.
      * 代碼之前，測試先行。
      * 選擇好的編碼工具能有效地提高效率，避免編碼中的小錯誤。
 
    《怎樣練習一萬小時》，有一些覺得比較有用的觀點，再加些自己的所看到的所學到的。

  1. 只在學習區(qū)學習

    不要對未知的事物感到本能性的恐懼，相信自己能行的。

    “心理學家把人的知識和技能分為層層嵌套的三個圓形區(qū)域：最內(nèi)一層是“舒適區(qū)”，是我們已經(jīng)熟練掌握的各種技能；最外一層是“恐慌區(qū)”，是我們暫時無法學會 的技能，二者中間則是“學習區(qū)”。只有在學習區(qū)里面練習，一個人才可能進步。有效的練習任務必須精確的在受訓者的“學習區(qū)”內(nèi)進行，具有高度的針對性。在 很多情況下這要求必須要有一個好的老師或者教練，從旁觀者的角度更能發(fā)現(xiàn)我們最需要改進的地方。”

  2. 學到的東西只有多用，多實踐才能化為己用。

     紙上得來終覺淺。

  3. 多寫下自己的所得。

     寫下的東西可能比在大腦中記下的更有條理，在寫的過程中可能會觸發(fā)新的思路，且有助于理清思路   (這就是為什么一個問題在自言語中為什么有時候會出現(xiàn)答案自己跑出來的情況)所以要多寫。
     最近發(fā)現(xiàn)Vimwiki是個好東西。

  4. 優(yōu)秀是一種習慣。

     好習慣的養(yǎng)成很重要（eg:今日事今日畢就是很重要的）

  5. 多看經(jīng)典之作，不要把時間浪費在無用的東西上。

  6. 堅持是最重要的，這樣才會有柳暗花明的一天 。

  7. 有什么想做的事就大膽去做吧，誰保證以后還會有機會？
       
     借用《明朝那些事》里的一句話“按照自己的方式去活才是最大的成功”。
自動化法則

    計算機原本就該從事簡單重復的工作。只要把任務指派給它們，它們就可以一遍又一遍毫不走樣地重復執(zhí)行，而且速度很快。但卻經(jīng)常看見一種奇怪的現(xiàn)象：人們在計算機上手工做一些簡單重復的工作，計算機則在大半夜里扎堆閑聊取笑這些可憐的用戶。

    我們應該利用作為程序員的優(yōu)勢，看到普通用戶無法看到的東西，培養(yǎng)larry所說的“懶惰，急躁和傲慢”讓計算機高效地為我們工作：命令行是如此地高效，腳本是如此地方便，銜接兩個小工具能達到如此神奇的效果。。。

古代哲人

1. 亞里斯多德的“事物本質(zhì)性質(zhì)和附屬性質(zhì)”理論：致力本質(zhì)復雜性，去除附屬復雜性。你現(xiàn)在想解決問題A,在解決A的問題中遇到了問題B,接著你去解決問題B，戲劇性的是你遇到了很多接二連三的問題C,D,E，或者在很多年后，程序才出現(xiàn)問題C,D,E，可是你的最初問題是A，不是嗎？B,C,D等等都是附屬性質(zhì)，當這些附屬性質(zhì)越來越多，越來越復雜的時候，也是開始思考另一個解決A的辦法的時候了。(如果作為學習，可以試著去解決那些附屬性質(zhì))

2. 笛米特法則：任何一個對象或者方法，它應該只能調(diào)用下列對象：該對象本身，作為參數(shù)傳遞進來的對象，在方法內(nèi)創(chuàng)建的對象。這么做的主要目的是信息隱藏,同時使類的耦合更加松散。

3. “古老”的軟件傳說。了解歷史才能更好地創(chuàng)造歷史。讀讀那些“古老”的“寶典”（如《程序員修煉之道》《人月神話》《Smalltalk Best Practice Patterns》），會學到很多有用的東西，或許你會發(fā)出一生驚嘆。“當你的老板要求你使用一個低質(zhì)量的代碼庫時，不需要在崩潰中咬牙切齒，告訴他：你正“站在侏儒的肩膀”上的陷阱中，然后他就會明白不僅僅只有你才覺得那是個壞主意。”

擁抱多語言編程

   “每個語言都有自己擅長的地方”（我的想法）。比如perl特別適合文本處理，用來處理網(wǎng)頁也很好（畢竟有些從服務器上返回的數(shù)據(jù)就是用perl返回的，所以用perl也會比較合適）。

    計算機語言就像鯊魚，要是保持靜止就會死。

    Java的創(chuàng)造都們實際上創(chuàng)造了兩樣東西：Java語言和Java平臺。后者就是我們擺脫歷史包袱的途徑（Java語言的特性包含了一些它本該可以忽略的東西，如Java程序初始化的順序和從0開始的數(shù)組）。讀到本文我才開始理解平臺的深刻意義。

    舉兩個例子（Groovy和Jaskell）說明。

    Groovy是一種開源的編程語言，它給Java帶來了動態(tài)語言的語法和功能，它會生成Java字節(jié)碼，因此可以在Java平臺上運行。在Java之后十多年里浮現(xiàn)出來的各種語言很大程序上影響著Groovy的語法：Groovy支持裝飾，較松散的類型系統(tǒng)，“理解”迭代的集合，以及很多現(xiàn)代編程語言的改進特性。而且它可以編譯成純正的Java字節(jié)碼。用Groovy寫成的代碼簡潔且并不比用Java寫的代碼效率低多少，而且能充分借用Java平臺的優(yōu)勢。

    Jaskell是運行在Java平臺上的Haskell版本。Jaskell擁有函數(shù)式程序設計語言的優(yōu)勢：函數(shù)不改變外界的狀態(tài)，純粹的函數(shù)式語言壓根沒有“變量”概念；函數(shù)式語言對多線程的支持比命令式語言要強得多，用函數(shù)式語言更容易寫出強壯的線程安全的代碼，對并發(fā)支持也比較好（我想這是Erlang流行的原因）。同時Jaskell也能借用Java平臺的優(yōu)勢。

     Java平臺借用這些多語言特性，一定會走得更好，走得更遠。不過，在帶來好處的同時，也帶來了一個問題：多語言應用程序更難高度，解決這個問題最簡單的辦法也跟現(xiàn)在一樣：靠嚴格的單元測試來避免在調(diào)試器上浪費時間。

     多語言開發(fā)風格會把我們帶向領(lǐng)域特定語言(Domain-specific Language,DSL)。我們會以一些專門的語言為基礎(chǔ)，創(chuàng)造出非常有針對性的，非常專注某一問題域的DSL。抱定一種通用語言不放的年代就快結(jié)束了，我們正在進入一個專業(yè)細分的新時代。大學時代的Haskell教材還在書架頂上蒙塵嗎？該給它撣撣灰了。

     ps: 我們也可以以C++為基礎(chǔ)，來創(chuàng)造一種DSL，思考。



鏈接： 卓有成效的程序員

    "A useful way to get some insight into what linkers and loaders do is to look at their part in the development of computer programming systems."

一. 目標

1. 理解Linker和Loader的大致工作過程。
2. 寫一個關(guān)于elf的小loader。
3. 會感染ELF和PE文件。

二. 有用的鏈接

1. 本書《Linkers and Loaders 》的網(wǎng)址：http://linker.iecc.com/
一． 簡介

    該正則表達式暫時能識別 *,|,(,)等特殊符號，如(a|b)*abc。不過擴展到其他符號（如?）也相對比較容易，修改NFA中的構(gòu)建規(guī)則即可。

二． 引擎的構(gòu)建

    該正則表達式引擎的構(gòu)建以《Compilers Principles,Techniques & Tools》3.7節(jié)為依據(jù)，暫時只能識別*,|,(,)這幾個特殊的字符，其工作過程為：構(gòu)建NFA -> 根據(jù)NFA構(gòu)建DFA -> 用DFA匹配。

1. 構(gòu)建NFA
該NFA的構(gòu)建以2條基本規(guī)則和3條組合規(guī)則為基礎(chǔ)，采用歸納的思想構(gòu)建而成。
1）2條基本的規(guī)則是:
a. 以一個空值ε構(gòu)建一個NFA

b. 以一個字符a構(gòu)建一個NFA

2) 3條組合規(guī)則是：
a. r = s | t （其中s和t都是NFA）

b. r = s t（其中s和t都是NFA）

c. r = s *（其中s為NFA）

3) 如果需要識別如”?”等特殊符號，則可再加一些組合規(guī)則。

在具體的程序中，可以以下面的BNF為結(jié)構(gòu)來實現(xiàn)。（具體見源程序regexp.cpp）


2. 構(gòu)建DFA
主要是求ε閉包的過程，從一個集合的ε閉包轉(zhuǎn)移到一個集合的ε閉包。
以a*c為例，其NFA圖如下所示（用dot畫的）

為例:
起始結(jié)點3的ε閉包集為 A = {3,1,4}
A遇上字母a的轉(zhuǎn)移為MOV(A,a) = { 2 }，其ε閉包集為B = { 2,1,4 }
A遇上字母c的轉(zhuǎn)移為MOV(A,c) = { 6 }，其ε閉包集為B = { 6 }
同理可求出其他轉(zhuǎn)移集合，最后得到的DFA如下所示:

3. 匹配
每匹配成功一個字符則DFA移動到下個相應的結(jié)點。

三． 改進

1. 如龍書中所說，有時候模擬NFA而不是直接構(gòu)建DFA可能達到更好的效果。
2. 每次匹配不成功都需要回溯，這個地方也可以借鑒KMP算法（不過KMP對此好像有點不適用）
3. 其他改進方法可以看看《柔性字符串匹配》和龍書《Compilers Principles,Techniques & Tools》3.7節(jié)。

四． 代碼下載

svn checkout http://regexp.googlecode.com/svn/trunk/ regexp-read-only

或 regexp.rar