實現詞法分析器
對於一個token，比如用來表示數字的token：num，我們可以用正則表達式描述它，然後畫出nfa，再將nfa轉化成dfa，再最小化dfa的狀態，但是我們的詞法分析器是不是分析一個token，所以我們要把所有類型的token的dfa合併成一個dfa，這樣，這個dfa也就可以識別語言的所有token了，如果在某一連串的輸入下，dfa達不到終結狀態，那就說明原始碼有錯誤了。
我用c#實現了一個用於《compiler construction: principles and practice》中tiny語言的詞法分析器，tiny語言有關鍵字：if, then, else, end, repeat, until, read, write，有操作符+，-，*，/，=，<，(，)，;，:=（全形逗號不算，是文章的分隔設定）這10個，然後其餘的token有number (一或多個數字)和identifier(一或多個字母)，其dfa如下圖：
上面這張圖和《編譯原理及實踐》中的一樣，其中的帶中括弧的輸入說明這個輸入是lookahead的，在匹配成功後是要重新放回輸入流中的，比如識別num時，如果發現個非digit的，那就說明識別到了一個number，但是最後識別的那個非digit字元是要放回輸入流的，因為它要留著下一次識別。
其中從start到done的那個other，指所有非white space，非{，非letter，非digit，也非:的字元，它有可能是合法的+, *, /這些，也可能是不合法的其它輸入，如#號。因此，done這個狀態只是說本次gettoken已經結束，狀態機是有可能因為不合法的輸入而進入done狀態的。究竟從start到done是因為合法的，如+號導致的，還是由不合法的如#號導致的，將在代碼中實現判斷，但可以肯定的是，不管是+號還是#號作用於start狀態，都會進入done狀態。