詞法分析小結

詞法分析小結》簡介：

詞法分析是編譯器工作的第一階段，它的工作就是從輸入（源**）中取得token，以作為parser（語

《詞法分析小結》正文開始》

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

而nfa確定化的本質，就是將原來多個狀態改用乙個狀態來表示，新狀態其實是乙個狀態集，比如nfa中狀態s1在輸入a下可以到達s2和s3，那麼，在dfa中，就把s2和s3合起來認為是乙個狀態。還有乙個問題是nfa中的空轉換（輸入），如果s1在輸入下可以到達s2，就表示s1可以無條件地轉移到s2，那s1和s2自然可以合併起來作為dfa中的乙個狀態，於是nfa轉dfa的演算法也就好理解了。但首先得先定義下空閉包（-closure）：

-closure: 狀態s的-closure即s經過轉換可以到達的狀態集，s的-closure永遠都會包含s自身。乙個狀態集的-closure即該狀態集中各狀態的-closure的集合。

nfa確定化演算法(subset construction)：

從開始狀態開始，計算它的-closure，得到狀態集set1，然後考察set1在某個輸入a的作用下會遷移到哪些狀態，把這些狀態集中到一起，再求這個集合的-closure，得到set2，這樣我們就可以畫兩個圈，乙個標上set1，另乙個標上set2，然後畫條從set1到set2的線把這兩圓連起來，**上標上a，這樣dfa的一部分就畫好了，然後我們再考察set1在其它輸入下可以達到的狀態集的-closure，同樣畫圈連線，以此類推，最後的時候，把包含了原nfa中終結狀態（final state或acceptin state）的dfa狀態（在轉換後的dfa中，每個狀態都是包含了乙個或多個原nfa中的狀態）標記為終結狀態。

最小化dfa狀態數

由乙個正規表示式，可以構建出乙個等價的nfa，然後nfa又可以確定化成dfa，似乎到此事情搞完了，但事實證明（有時也可以顯然地發現），最終構成的這dfa似乎有些複雜，有些狀態好像很冗餘，呃，是的，dfa是可以最小化的。

最小化dfa狀態數演算法的思想是，在開始時，假設是最完美的情況，整個dfa只有兩個狀態，乙個終結狀態，乙個開始（難道不能有只有一種狀態的情況麼？如果原dfa中存在非終結狀態，當然就不能，非終結態怎麼可以和終結態合併！），當然，這是假設，不是真的，所以這個演算法，就是在這個完美的假設下，對假設進一步考察，如果發現有些狀態不能合併，那就分出來吧，這樣重複考察，直到發現沒有狀態會不能合併時，就做完了，此時不也正是最優解麼。

嗯，就是這個，所以一開始，我們把所有非終結狀態用乙個袋子包起來，看成是乙個狀態，把所有終結狀態也用另一袋子包起來，也看成是乙個狀態，注意，別把原dfa中各狀態間的連線給扯斷了。然後，我們抽出其中乙個袋子，考察其中的各個狀態，我們準備好所有的可能輸入，然後逐個拿出來測試，如果該袋子中的所有狀態在某個輸入a下達到的狀態正好都在這個袋子中，那就說明，這個袋子中的這些狀態「在目前看來」是可以合併的，也就是說，如果在所有的可能輸入的作用下，袋子中的狀態達到的新狀態正好也都是這個袋子中的狀態，那它們就可以合併。而如果，在某個輸入a下，袋子中的一部分狀態會轉移到同一袋子中的其它狀態，而有幾個叛徒，假設是s1和s2，竟然在輸入a下會遷移到其它袋子中的狀態，那就說明s1和s2是不可以和其它轉移到同一袋子中的狀態合併的，於是，我們就把s1和s2裝成乙個新袋子，從原袋子中分出來，當然，現在還是假設s1和s2可以合併，所以才把它們裝一起，究竟真的可不可以合併呆會還要再考察。

考察完輸入a，還要接著考察其它的可能輸入。如果在考察完乙個袋子後，發現所有狀態在a輸入下都可以轉移到本袋子中的狀態，那麼最後的dfa它們就被合併成乙個狀態，並且在a輸入下，它有乙個到自身的狀態遷移。

實現詞法分析器

對於乙個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狀態。

一、詞法分析程式產生器lex的用法

1．1 lex概述

程式語言從機器語言發展到今天的象pascal, c等這樣的高階語言，使人們可以擺脫與機器有關的細節進行程式設計。但是用高階語言寫程式時程式設計師必須在程式中詳盡地告訴計算機系統怎樣去解決某個問題，這在某種程度上說也是一件很複雜的工作。

人們希望有新的語言——非常高階的語言，用這種語言程式設計師僅僅需要告訴計算機系統要解決什麼問題，計算機系統能自動地從這個問題的描述去尋求解決問題的途徑，或者說將這個問題的描述自動地轉換成用某種高階語言如c、fortran表示的程式。這個程式就可以解決給定的問題，這種希望雖然還沒有能夠完全變成現實，但是在某些具體的問題領域裡已經部分地實現了。

這裡要介紹的lex和下章要介紹的yacc就是在編譯程式設計這個領域裡的兩種非常高階的語言。用它們可以很方便的描述詞法分析器和語法分析器，並自動產生出相應的高階語言（c）的程式。

lex是乙個詞法分析器（掃瞄器）的自動產生系統，它的示意圖如圖1.1。

lex源程式是用一種面向問題的語言寫成的。這個語言的核心是正規表示式（正規式），用它描述輸入串的詞法結構。在這個語言中使用者還可以描述當某乙個詞形被識別出來時要完成的動作，例如在高階語言的詞法分析器中，當識別出乙個關鍵字時，它應該向語法分析器返回該關鍵字的內部編碼。

lex並不是乙個完整的語言，它只是某種高階語言（稱為lex的宿主語言）的擴充，因此lex沒有為描述動作設計新的語言，而是借助其宿主語言來描述動作。我們只介紹c作為lex的宿主語言時的使用方法，在unix系統中，fortran語言的一種改進形式ratfor也可以做lex的宿主語言。

詞法分析小結

詞法分析小結

詞法分析報告

編譯原理詞法分析

詞法分析小結

詞法分析小結

詞法分析報告

編譯原理 詞法分析

相關推薦

編譯原理詞法分析