詞法分析小結

詞法分析是編譯器工作的第一階段，它的工作就是從輸入(源**)中取得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，那其它的我們就不管了。

詞法分析小結

詞法分析小結

詞法分析報告

編譯原理詞法分析

詞法分析小結

詞法分析小結

詞法分析報告

編譯原理 詞法分析

相關推薦

編譯原理詞法分析