詞法分析是編譯器工作的第一階段，它的工作就是從輸入（原始碼）中取得token，以作為parser（語法分析）的輸入，一般在詞法分析階段都會把一些無用的空白字元（white space，即空格、tab和換行）以及注釋剔除，以降低下一步分析的複雜度，詞法分析器一般會提供一個gettoken()這樣的方法，parser可以在做語法分析時調用詞法分析器的這個方法來得到下一個token，所以詞法分析器並不是一次性遍歷所有原始碼，而是採取這種on-demand的方式：只在parser需要時才工作，並且每次只取一個token。
token和lexeme
首先，token不等於lexeme。token和lexeme的關係就類似於面向對象語言中“類”和“實例”（或“對象”）之間的關係，這個用中文不知該如何解釋才好，比如語言中的變數a和b，它們都屬於同一種token：identifier，而a的lexeme是”a”，b則是”b”，而每個關鍵字都是一種token。token可以附帶有一個值屬性，例如變數a，當調用詞法分析器的gettoken()時，會返回一個identifier類型的token，這個token帶有一個屬性“a”，屬性可以是多樣的，例如表示數字的token可以帶有一個表示數字值的屬性，它是整型的。
如下代碼：
int age = 23;
int count = 50;
可以依次提取出8個token：int(值為”int”)，id(值為”age”)，assign(值為”=”)，number(值為整型數值23)，int(值為”int”)，id(值為”count”)，assign(值為”=”)，number(值為50)
正則表達式
正則表達式可以用來描述字元串模式，例如我們可以用digit+來表示number的token，其中digit表示單個數字（這裡說正則表達式並不完全和實現的正則引擎所識別的正則表達式等價，這裡只是為了描述問題而已）。
然而像c語言的的多行注釋，用正則表達式來描述就比較麻煩，此時更傾向於直接用有窮自動機（finite automaton）來描述，因為用它來描述非常直觀且很容易。
有窮自動機(finite automata)
有窮自動機也稱為有限狀態機，狀態在輸入字元的作用下發生遷移，因此，它可以用來識別token，也因此，我們只要畫得出fa，之後再用代碼實現這個fa，那詞法分析器也就差不多弄好了。
有窮自動機分確定性（dfa）和非確定性（nfa）兩種，如果對於同一個輸入，只會有一個確定的狀態遷移路線，也就是只有一個確定的“下一狀態”，那就是dfa，否則就是nfa。
因為dfa對於同一個輸入只有一個確定的下一狀態，所以詞法分析器當然優先採用它，那nfa拿來幹嘛用呢？nfa用來做描述用時更方便，我們可以非常迅速地畫出一個識別token的nfa圖，但要想直接畫出個dfa那要動不少腦筋。
根據正則表達式構建nfa
如上所述，nfa更容易畫出，那我們就先研究nfa，在定義token時，我們可以用正則表達式來描述它，因為正則表達式幹這行很合適，例如一個digit+就可以描述數字，多方便。因此，我們需要根據正則表達式畫出與之等價的nfa。而這個算法非常簡單，就是tompson’s construction，這個書上寫得很清楚了。
將nfa轉化成dfa（nfa的確定化）
對於計算機來說，面對同一個輸入，如果有多個下一狀態，那計算機就不清楚要轉到哪個狀態，所以我們期望能從正則表達式得到dfa，而不是nfa，因為這樣將來編程實現時比較自然（同一輸入有確定的一個下一狀態），而幸運的是，每個nfa都可以轉化成dfa。為什麼nfa可以轉化成dfa？因為fa(finite automata)中的狀態都是我們自己畫的，只要fa能正確的識別token，那就ok了，也就是，如果nfa和dfa都可以達到一樣的效果：識別token，那其它的我們就不管了。