本文主要記錄一下編譯原理的學習路徑，由于龍書等著作已近給出了詳細介紹，本文只給出算法介紹；本文不會寫的特別嚴謹，主要是介紹算法。

詞法分析器的實現(xiàn)主要有幾個核心概念：
1，正則表達式
2，抽象語法樹
3，NFA(不確定有窮狀態(tài)機)
4, DFA(確定有窮狀態(tài)機)

1，正則表達式:
通俗理解：
可以看成一個符號序列，中間含若干確定運算符；最基礎的正則表達式就是字符；每個正則表達式唯一對應一個該正則表達式表達的語言，語言指的是以字符串序列為元素的確定集合；正則表達式的復合對應的語言集合的復合。
因此正則表達式在數(shù)學上可以看成是一系列集合運算；每個正則表達式就對應唯一一個集合，正則表達式的運算對應集合的運算，集合運算的結果仍然是集合

下文中用表示正則表達式對應的語言。

定義:
1)給定兩個字符串則表示兩者前后相連所得字符串;
2)如果是一個字符串序列的集合,也是一個字符串序列的集合，則 表示中任意一個字符串后接中任意一個字符串所得的集合
3)是一個字符串序列組成的集合，則(共i個S),當i=0時，定義為（空串）
4) : =

正則表達式官方定義:

1. 是一個正則表達式，
2. 給定符號集S,則S中每個元素x都是一個正則表達式，其對應語言為
   3)如果是正則表達式，則也是正則表達式，且
3. 如果是兩個正則表達式；則
   是一個正則表達式，
   4)是一個正則表達式，
   5)是一個正則表達式，表示語言

可以用以正則表達式定義的語言叫做正則集合

2,正則表達式的抽象語法樹
通俗解釋: 由于正則表達式只包含2元和1元運算符，因此正則表達式可以表示為一棵樹的形狀
舉例: (a|b)*abb 的抽象語法樹為:

                _
             /       \         
           _         b
         /    \
       _      b
     /    \
    *     a
    |
    (|)
   /   \
 a      b

其中用 _ 表示兩個正則表達式連接

3,NFA:
通俗解釋：可以看成一個不含重邊的有向圖，圖的有向邊上關聯(lián)著符號，同一個節(jié)點發(fā)出的多條邊上可能關聯(lián)相同的符號；
4，DFA:
基本同上，不過同一個節(jié)點發(fā)出的多條邊上的符號都不相同

下面基于以上概念快速實現(xiàn)詞法分析器:
一個DFA基本上等價于一個詞法分析器了，而輸入的詞法單元可以對應為一門語言，也就對應到一個正則表達式；

因此，實現(xiàn)詞法分析器的過程，也就是：
根據(jù)正則表達式 構建 DFA的過程，方法為:
正則表達式-> 抽象語法樹-> NFA->DFA

1,正則表達式 -> 抽象語法樹
這一步基本沒什么難度，手寫都可以，略去

2,抽象語法樹->NFA
給抽象語法樹的所有非葉子節(jié)點標上數(shù)字（隨意標，不重復即可，不過一般從1,遞增標）這些數(shù)字稱為節(jié)點的位置，可同時也 稱為節(jié)點上符號的位置（一個符號允許對應多個位置）
計算 每個節(jié)點的三個參數(shù):
nullable, firstpos, lastpos ,
和每個位置 的 followpos
定義：
nullable(n) :是一個bool值，當且僅當 以n為根的子樹對應的正則表達式的語言中 包含
firstpos(n): 是一個位置集合，一個位置屬于該集合 當且僅當 以n為根的子樹對應正則表達式的語言中存在一個符號串滿足其首字母 按照這顆樹解析時 剛好解析到這個位置；
lastpos(n): 位置集合 ，一個位置屬于該集合 當且僅當 n為根的子樹對應的正則表達式的語言中存在一個符號串 滿足其尾字母 按照這顆樹解析時 剛好解析到這個位置；
followpos(p): 是一個和位置p相關的位置集合。 一個位置q屬于該集合當且僅當 L中的某個川 按照抽象語法樹解析時，和某個匹配而 和匹配
算法：
每種類型對應的 nullabel 值 和 firstpos值 分別為:
葉子節(jié)點: true ,
位置為i的葉子節(jié)點: false , {i}
or節(jié)點: ,
cat-節(jié)點 : ,

start-節(jié)點:
由對稱性容易推出 lastpos的公式，略過;
followpos計算法則如下:
1,如果n是 cat節(jié)點，左右子節(jié)點為,則中每個位置 ,中所有都位于 中
2,如果是節(jié)點，并且是中的一個位置，中的所有位置都位于 中

按照以上方法，計算出nullabel,firstpos,lastpos,followpos之后，可以用一個有向圖 來表示 followpos, 每個位置對應圖中一個節(jié)點，位置i到位置j 存在一條有限邊當且僅當 j在followpos(i)中，
然后做三件事:
1把該圖firstpos所有位置設為 開始狀態(tài)
2每條i到j的有向邊上添加位置i上的符號
3 把和結尾#關聯(lián)的位置作為接受狀態(tài)
至此，得到 NFA

3，NFA -> DFA
之后利用以下偽代碼算法就可以計算出 DFA了：
初始化Dstates, 使之只包含未標記狀態(tài) firstpos(n_0)$ n_0為抽象語法樹根節(jié)點
while( Dstates 中存在未標記的狀態(tài)S){
標記S,
for( 每個輸入符號a){
U :=S中和a對應的所有位置p的followpos(p)的并集 （和a對應的意思NFA中該位置的節(jié)點有一個用a標記的發(fā)出邊）
if(U不在Dstates中）將U作為未標記態(tài)加入Dstates;
Dtran[S,a] = U;
}
}
注：其中Dran的就是待求DFA的狀態(tài)邊轉移關系，也就是狀態(tài)S通過標記了a的有向邊轉換到 U;

之后，還有一些優(yōu)化減少DFA節(jié)點數(shù)目，這里略過；

至此，我們快速的實現(xiàn)了一個詞法分析器。