- 相關(guān)推薦
詞法分析小結(jié) -總結(jié)
詞法分析是編譯器工作的第一階段，它的工作就是從輸入（源代碼）中取得token，以作為parser（語法分析）的輸入，一般在詞法分析階段都會把一些無用的空白字符（white space，即空格、tab和換行）以及注釋剔除，以降低下一步分析的復(fù)雜度，詞法分析器一般會提供一個gettoken()這樣的方法，parser可以在做語法分析時調(diào)用詞法分析器的這個方法來得到下一個token，所以詞法分析器并不是一次性遍歷所有源代碼，而是采取這種on-demand的方式：只在parser需要時才工作，并且每次只取一個token，
詞法分析小結(jié)
。
token和lexeme
首先，token不等于lexeme。token和lexeme的關(guān)系就類似于面向?qū)ο笳Z言中“類”和“實例”（或“對象”）之間的關(guān)系，這個用中文不知該如何解釋才好，比如語言中的變量a和b，它們都屬于同一種token：identifier，而a的lexeme是”a”，b則是”b”，而每個關(guān)鍵字都是一種token。token可以附帶有一個值屬性，例如變量a，當調(diào)用詞法分析器的gettoken()時，會返回一個identifier類型的token，這個token帶有一個屬性“a”，屬性可以是多樣的，例如表示數(shù)字的token可以帶有一個表示數(shù)字值的屬性，它是整型的。
如下代碼：
int age = 23;
int count = 50;
可以依次提取出8個token：int(值為”int”)，id(值為”age”)，assign(值為”=”)，number(值為整型數(shù)值23)，int(值為”int”)，id(值為”count”)，assign(值為”=”)，number(值為50)
正則表達式
正則表達式可以用來描述字符串模式，例如我們可以用digit+來表示number的token，其中digit表示單個數(shù)字（這里說正則表達式并不完全和實現(xiàn)的正則引擎所識別的正則表達式等價，這里只是為了描述問題而已）。
然而像c語言的的多行注釋，用正則表達式來描述就比較麻煩，此時更傾向于直接用有窮自動機（finite automaton）來描述，因為用它來描述非常直觀且很容易。
有窮自動機(finite automata)
有窮自動機也稱為有限狀態(tài)機，狀態(tài)在輸入字符的作用下發(fā)生遷移，因此，它可以用來識別token，也因此，我們只要畫得出fa，之后再用代碼實現(xiàn)這個fa，那詞法分析器也就差不多弄好了。
有窮自動機分確定性（dfa）和非確定性（nfa）兩種，如果對于同一個輸入，只會有一個確定的狀態(tài)遷移路線，也就是只有一個確定的“下一狀態(tài)”，那就是dfa，否則就是nfa。
因為dfa對于同一個輸入只有一個確定的下一狀態(tài)，所以詞法分析器當然優(yōu)先采用它，那nfa拿來干嘛用呢？nfa用來做描述用時更方便，我們可以非常迅速地畫出一個識別token的nfa圖，但要想直接畫出個dfa那要動不少腦筋。
根據(jù)正則表達式構(gòu)建nfa
如上所述，nfa更容易畫出，那我們就先研究nfa，在定義token時，我們可以用正則表達式來描述它，因為正則表達式干這行很合適，例如一個digit+就可以描述數(shù)字，多方便。因此，我們需要根據(jù)正則表達式畫出與之等價的nfa。而這個算法非常簡單，就是tompson’s construction，這個書上寫得很清楚了。
將nfa轉(zhuǎn)化成dfa（nfa的確定化）
對于計算機來說，面對同一個輸入，如果有多個下一狀態(tài)，那計算機就不清楚要轉(zhuǎn)到哪個狀態(tài)，所以我們期望能從正則表達式得到dfa，而不是nfa，因為這樣將來編程實現(xiàn)時比較自然（同一輸入有確定的一個下一狀態(tài)），而幸運的是，每個nfa都可以轉(zhuǎn)化成dfa。為什么nfa可以轉(zhuǎn)化成dfa？因為fa(finite automata)中的狀態(tài)都是我們自己畫的，只要fa能正確的識別token，那就ok了，也就是，如果nfa和dfa都可以達到一樣的效果：識別token，那其它的我們就不管了。
而nfa確定化的本質(zhì)，就是將原來多個狀態(tài)改用一個狀態(tài)來表示，新狀態(tài)其實是一個狀態(tài)集，比如nfa中狀態(tài)s1在輸入a下可以到達s2和s3，那么，在dfa中，就把s2和s3合起來認為是一個狀態(tài)。還有一個問題是nfa中的空轉(zhuǎn)換（?輸入），如果s1在?輸入下可以到達s2，就表示s1可以無條件地轉(zhuǎn)移到s2，那s1和s2自然可以合并起來作為dfa中的一個狀態(tài)，于是nfa轉(zhuǎn)dfa的算法也就好理解了。但首先得先定義下空閉包（?-closure）：
?-closure: 狀態(tài)s的?-closure即s經(jīng)過?轉(zhuǎn)換可以到達的狀態(tài)集，s的?-closure永遠都會包含s自身，
總結(jié)
《詞法分析小結(jié)》(http://www.ishadingyu.com)。一個狀態(tài)集的?-closure即該狀態(tài)集中各狀態(tài)的?-closure的集合。nfa確定化算法(subset construction)：
從開始狀態(tài)開始，計算它的?-closure，得到狀態(tài)集set1，然后考察set1在某個輸入a的作用下會遷移到哪些狀態(tài)，把這些狀態(tài)集中到一起，再求這個集合的?-closure，得到set2，這樣我們就可以畫兩個圈，一個標上set1，另一個標上set2，然后畫條從set1到set2的線把這兩圓連起來，在線上標上a，這樣dfa的一部分就畫好了，然后我們再考察set1在其它輸入下可以達到的狀態(tài)集的?-closure，同樣畫圈連線，以此類推，最后的時候，把包含了原nfa中終結(jié)狀態(tài)（final state或acceptin state）的dfa狀態(tài)（在轉(zhuǎn)換后的dfa中，每個狀態(tài)都是包含了一個或多個原nfa中的狀態(tài)）標記為終結(jié)狀態(tài)。
最小化dfa狀態(tài)數(shù)
由一個正則表達式，可以構(gòu)建出一個等價的nfa，然后nfa又可以確定化成dfa，似乎到此事情搞完了，但事實證明（有時也可以顯然地發(fā)現(xiàn)），最終構(gòu)成的這dfa似乎有些復(fù)雜，有些狀態(tài)好像很冗余，呃，是的，dfa是可以最小化的。
最小化dfa狀態(tài)數(shù)算法的思想是，在開始時，假設(shè)是最完美的情況，整個dfa只有兩個狀態(tài)，一個終結(jié)狀態(tài)，一個開始（難道不能有只有一種狀態(tài)的情況么？如果原dfa中存在非終結(jié)狀態(tài)，當然就不能，非終結(jié)態(tài)怎么可以和終結(jié)態(tài)合并�。�，當然，這是假設(shè)，不是真的，所以這個算法，就是在這個完美的假設(shè)下，對假設(shè)進一步考察，如果發(fā)現(xiàn)有些狀態(tài)不能合并，那就分出來吧，這樣重復(fù)考察，直到發(fā)現(xiàn)沒有狀態(tài)會不能合并時，就做完了，此時不也正是最優(yōu)解么。
嗯，就是這個，所以一開始，我們把所有非終結(jié)狀態(tài)用一個袋子包起來，看成是一個狀態(tài)，把所有終結(jié)狀態(tài)也用另一袋子包起來，也看成是一個狀態(tài)，注意，別把原dfa中各狀態(tài)間的連線給扯斷了。然后，我們抽出其中一個袋子，考察其中的各個狀態(tài)，我們準備好所有的可能輸入，然后逐個拿出來測試，如果該袋子中的所有狀態(tài)在某個輸入a下達到的狀態(tài)正好都在這個袋子中，那就說明，這個袋子中的這些狀態(tài)“在目前看來”是可以合并的，也就是說，如果在所有的可能輸入的作用下，袋子中的狀態(tài)達到的新狀態(tài)正好也都是這個袋子中的狀態(tài)，那它們就可以合并。而如果，在某個輸入a下，袋子中的一部分狀態(tài)會轉(zhuǎn)移到同一袋子中的其它狀態(tài)，而有幾個叛徒，假設(shè)是s1和s2，竟然在輸入a下會遷移到其它袋子中的狀態(tài)，那就說明s1和s2是不可以和其它轉(zhuǎn)移到同一袋子中的狀態(tài)合并的，于是，我們就把s1和s2裝成一個新袋子，從原袋子中分出來，當然，現(xiàn)在還是假設(shè)s1和s2可以合并，所以才把它們裝一起，究竟真的可不可以合并呆會還要再考察�？疾焱贻斎隺，還要接著考察其它的可能輸入。如果在考察完一個袋子后，發(fā)現(xiàn)所有狀態(tài)在a輸入下都可以轉(zhuǎn)移到本袋子中的狀態(tài)，那么最后的dfa它們就被合并成一個狀態(tài)，并且在a輸入下，它有一個到自身的狀態(tài)遷移。
實現(xiàn)詞法分析器
對于一個token，比如用來表示數(shù)字的token：num，我們可以用正則表達式描述它，然后畫出nfa，再將nfa轉(zhuǎn)化成dfa，再最小化dfa的狀態(tài)，但是我們的詞法分析器是不是分析一個token，所以我們要把所有類型的token的dfa合并成一個dfa，這樣，這個dfa也就可以識別語言的所有token了，如果在某一連串的輸入下，dfa達不到終結(jié)狀態(tài)，那就說明源代碼有錯誤了。
我用c#實現(xiàn)了一個用于《compiler construction: principles and practice》中tiny語言的詞法分析器，tiny語言有關(guān)鍵字：if, then, else, end, repeat, until, read, write，有操作符+，-，*，/，=，<，(，)，;，:=（全角逗號不算，是文章的分隔符）這10個，然后其余的token有number (一或多個數(shù)字)和identifier(一或多個字母)，其dfa如下圖：
上面這張圖和《編譯原理及實踐》中的一樣，其中的帶中括號的輸入說明這個輸入是lookahead的，在匹配成功后是要重新放回輸入流中的，比如識別num時，如果發(fā)現(xiàn)個非digit的，那就說明識別到了一個number，但是最后識別的那個非digit字符是要放回輸入流的，因為它要留著下一次識別。
其中從start到done的那個other，指所有非white space，非{，非letter，非digit，也非:的字符，它有可能是合法的+, *, /這些，也可能是不合法的其它輸入，如#號。因此，done這個狀態(tài)只是說本次gettoken已經(jīng)結(jié)束，狀態(tài)機是有可能因為不合法的輸入而進入done狀態(tài)的。究竟從start到done是因為合法的，如+號導(dǎo)致的，還是由不合法的如#號導(dǎo)致的，將在代碼中實現(xiàn)判斷，但可以肯定的是，不管是+號還是#號作用于start狀態(tài)，都會進入done狀態(tài)。
【詞法分析小結(jié) -總結(jié)】相關(guān)文章：
國土資源局先進性教育分析評議階段工作小結(jié) -總結(jié)08-02
國土資源局先進性教育分析評議階段工作小結(jié) -總結(jié)07-21
軍訓(xùn)小結(jié)范文 -總結(jié)09-23
學(xué)期小結(jié)范文 -總結(jié)06-08
客房工作小結(jié) -總結(jié)07-22
黨課學(xué)習(xí)小結(jié) -總結(jié)07-31
個人小結(jié) -總結(jié)07-29
晚會工作小結(jié) -總結(jié)08-05