2022年詞法分析小結(jié)

1、高品質(zhì)文檔2022年詞法分析小結(jié) 詞法分析是編譯器工作的第一階段，它的工作就是從輸入（源代碼）中取得token，以作為parser（語(yǔ)法分析）的輸入，一般在詞法分析階段都會(huì)把一些無(wú)用的空白字符（white space，即空格、tab和換行）以及解釋剔除，以降低下一步分析的簡(jiǎn)單度，詞法分析器一般會(huì)供應(yīng)一個(gè)gettoken()這樣的方法，parser可以在做語(yǔ)法分析時(shí)調(diào)用詞法分析器的這個(gè)方法來(lái)得到下一個(gè)token，所以詞法分析器并不是一次性遍歷全部源代碼，而是實(shí)行這種on-demand的方式：只在parser需要時(shí)才工作，并且每次只取一個(gè)token。 token和lexeme 首先，token不等

2、于lexeme。token和lexeme的關(guān)系就類(lèi)似于面對(duì)對(duì)象語(yǔ)言中“類(lèi)”和“實(shí)例”（或“對(duì)象”）之間的關(guān)系，這個(gè)用中文不知該如何解釋才好，比如語(yǔ)言中的變量a和b，它們都屬于同一種token：identifier，而a的lexeme是”a”，b則是”b”，而每個(gè)關(guān)鍵字都是一種token。token可以附帶有一個(gè)值屬性，例如變量a，當(dāng)調(diào)用詞法分析器的gettoken()時(shí)，會(huì)返回一個(gè)identifier類(lèi)型的token，這個(gè)token帶有一個(gè)屬性“a”，屬性可以是多樣的，例如表示數(shù)字的token可以帶有一個(gè)表示數(shù)字值的屬性，它是整型的。 如下代碼： int age = 23; int count

3、 = 50; 可以依次提取出8個(gè)token：int(值為”int”)，id(值為”age”)，assign(值為”=”)，number(值為整型數(shù)值23)，int(值為”int”)，id(值為”count”)，assign(值為”=”)，number(值為50) 正則表達(dá)式 正則表達(dá)式可以用來(lái)描述字符串模式，例如我們可以用digit+來(lái)表示number的token，其中digit表示單個(gè)數(shù)字（這里說(shuō)正則表達(dá)式并不完全和實(shí)現(xiàn)的正則引擎所識(shí)別的正則表達(dá)式等價(jià)，這里只是為了描述問(wèn)題而已）。 然而像c語(yǔ)言的的多行解釋?zhuān)谜齽t表達(dá)式來(lái)描述就比較麻煩，此時(shí)更傾向于直接用有窮自動(dòng)機(jī)（finite autom

4、aton）來(lái)描述，因?yàn)橛盟鼇?lái)描述特別直觀(guān)且很簡(jiǎn)單。 有窮自動(dòng)機(jī)(finite automata) 有窮自動(dòng)機(jī)也稱(chēng)為有限狀態(tài)機(jī)，狀態(tài)在輸入字符的作用下發(fā)生遷移，因此，它可以用來(lái)識(shí)別token，也因此，我們只要畫(huà)得出fa，之后再用代碼實(shí)現(xiàn)這個(gè)fa，那詞法分析器也就差不多弄好了。 有窮自動(dòng)機(jī)分確定性（dfa）和非確定性（nfa）兩種，假如對(duì)于同一個(gè)輸入，只會(huì)有一個(gè)確定的狀態(tài)遷移路線(xiàn)，也就是只有一個(gè)確定的“下一狀態(tài)”，那就是dfa，否則就是nfa。 因?yàn)閐fa對(duì)于同一個(gè)輸入只有一個(gè)確定的下一狀態(tài)，所以詞法分析器當(dāng)然優(yōu)先采納它，那nfa拿來(lái)干嘛用呢？nfa用來(lái)做描述用時(shí)更便利，我們可以特別快速地畫(huà)出一個(gè)

5、識(shí)別token的nfa圖，但要想直接畫(huà)出個(gè)dfa那要?jiǎng)硬簧倌X筋。 依據(jù)正則表達(dá)式構(gòu)建nfa 如上所述，nfa更簡(jiǎn)單畫(huà)出，那我們就先討論nfa，在定義token時(shí)，我們可以用正則表達(dá)式來(lái)描述它，因?yàn)檎齽t表達(dá)式干這行很合適，例如一個(gè)digit+就可以描述數(shù)字，多便利。因此，我們需要依據(jù)正則表達(dá)式畫(huà)出與之等價(jià)的nfa。而這個(gè)算法特別簡(jiǎn)潔，就是tompsons construction，這個(gè)書(shū)上寫(xiě)得很清晰了。 將nfa轉(zhuǎn)化成dfa（nfa的確定化） 對(duì)于計(jì)算機(jī)來(lái)說(shuō)，面對(duì)同一個(gè)輸入，假如有多個(gè)下一狀態(tài)，那計(jì)算機(jī)就不清晰要轉(zhuǎn)到哪個(gè)狀態(tài)，所以我們期望能從正則表達(dá)式得到dfa，而不是nfa，因?yàn)檫@樣將來(lái)編程實(shí)

6、現(xiàn)時(shí)比較自然（同一輸入有確定的一個(gè)下一狀態(tài)），而幸運(yùn)的是，每個(gè)nfa都可以轉(zhuǎn)化成dfa。為什么nfa可以轉(zhuǎn)化成dfa？因?yàn)閒a(finite automata)中的狀態(tài)都是我們自己畫(huà)的，只要fa能正確的識(shí)別token，那就ok了，也就是，假如nfa和dfa都可以達(dá)到一樣的效果：識(shí)別token，那其它的我們就不管了。 而nfa確定化的本質(zhì)，就是將原來(lái)多個(gè)狀態(tài)改用一個(gè)狀態(tài)來(lái)表示，新?tīng)顟B(tài)其實(shí)是一個(gè)狀態(tài)集，比如nfa中狀態(tài)s1在輸入a下可以到達(dá)s2和s3，那么，在dfa中，就把s2和s3合起來(lái)認(rèn)為是一個(gè)狀態(tài)。還有一個(gè)問(wèn)題是nfa中的空轉(zhuǎn)換（?輸入），假如s1在?輸入下可以到達(dá)s2，就表示s1可以無(wú)條件

7、地轉(zhuǎn)移到s2，那s1和s2自然可以合并起來(lái)作為dfa中的一個(gè)狀態(tài)，于是nfa轉(zhuǎn)dfa的算法也就好理解了。但首先得先定義下空閉包（?-closure）： ?-closure: 狀態(tài)s的?-closure即s經(jīng)過(guò)?轉(zhuǎn)換可以到達(dá)的狀態(tài)集，s的?-closure永久都會(huì)包含s自身。一個(gè)狀態(tài)集的?-closure即該狀態(tài)集中各狀態(tài)的?-closure的集合。 nfa確定化算法(subset construction)： 從開(kāi)頭狀態(tài)開(kāi)頭，計(jì)算它的?-closure，得到狀態(tài)集set1，然后考察set1在某個(gè)輸入a的作用下會(huì)遷移到哪些狀態(tài)，把這些狀態(tài)集中到一起，再求這個(gè)集合的?-closure，得到set2

8、，這樣我們就可以畫(huà)兩個(gè)圈，一個(gè)標(biāo)上set1，另一個(gè)標(biāo)上set2，然后畫(huà)條從set1到set2的線(xiàn)把這兩圓連起來(lái)，在線(xiàn)上標(biāo)上a，這樣dfa的一部分就畫(huà)好了，然后我們?cè)倏疾靤et1在其它輸入下可以達(dá)到的狀態(tài)集的?-closure，同樣畫(huà)圈連線(xiàn)，以此類(lèi)推，最終的時(shí)候，把包含了原nfa中終結(jié)狀態(tài)（final state或acceptin state）的dfa狀態(tài)（在轉(zhuǎn)換后的dfa中，每個(gè)狀態(tài)都是包含了一個(gè)或多個(gè)原nfa中的狀態(tài)）標(biāo)記為終結(jié)狀態(tài)。 最小化dfa狀態(tài)數(shù) 由一個(gè)正則表達(dá)式，可以構(gòu)建出一個(gè)等價(jià)的nfa，然后nfa又可以確定化成dfa，好像到此事情搞完了，但事實(shí)證明（有時(shí)也可以明顯地發(fā)覺(jué)），最終

9、構(gòu)成的這dfa好像有些簡(jiǎn)單，有些狀態(tài)似乎很冗余，呃，是的，dfa是可以最小化的。 最小化dfa狀態(tài)數(shù)算法的思想是，在開(kāi)頭時(shí)，假設(shè)是最完善的狀況，整個(gè)dfa只有兩個(gè)狀態(tài)，一個(gè)終結(jié)狀態(tài)，一個(gè)開(kāi)頭（莫非不能有只有一種狀態(tài)的狀況么？假如原dfa中存在非終結(jié)狀態(tài)，當(dāng)然就不能，非終結(jié)態(tài)怎么可以和終結(jié)態(tài)合并?。?dāng)然，這是假設(shè)，不是真的，所以這個(gè)算法，就是在這個(gè)完善的假設(shè)下，對(duì)假設(shè)進(jìn)一步考察，假如發(fā)覺(jué)有些狀態(tài)不能合并，那就分出來(lái)吧，這樣重復(fù)考察，直到發(fā)覺(jué)沒(méi)有狀態(tài)會(huì)不能合并時(shí)，就做完了，此時(shí)不也正是最優(yōu)解么。 嗯，就是這個(gè)，所以一開(kāi)頭，我們把全部非終結(jié)狀態(tài)用一個(gè)袋子包起來(lái)，看成是一個(gè)狀態(tài)，把全部終結(jié)狀態(tài)也用另

10、一袋子包起來(lái)，也看成是一個(gè)狀態(tài)，留意，別把原dfa中各狀態(tài)間的連線(xiàn)給扯斷了。然后，我們抽出其中一個(gè)袋子，考察其中的各個(gè)狀態(tài)，我們預(yù)備好全部的可能輸入，然后逐個(gè)拿出來(lái)測(cè)試，假如該袋子中的全部狀態(tài)在某個(gè)輸入a下達(dá)到的狀態(tài)正好都在這個(gè)袋子中，那就說(shuō)明，這個(gè)袋子中的這些狀態(tài)“在目前看來(lái)”是可以合并的，也就是說(shuō)，假如在全部的可能輸入的作用下，袋子中的狀態(tài)達(dá)到的新?tīng)顟B(tài)正好也都是這個(gè)袋子中的狀態(tài)，那它們就可以合并。而假如，在某個(gè)輸入a下，袋子中的一部分狀態(tài)會(huì)轉(zhuǎn)移到同一袋子中的其它狀態(tài)，而有幾個(gè)叛徒，假設(shè)是s1和s2，竟然在輸入a下會(huì)遷移到其它袋子中的狀態(tài)，那就說(shuō)明s1和s2是不行以和其它轉(zhuǎn)移到同一袋子中的狀

11、態(tài)合并的，于是，我們就把s1和s2裝成一個(gè)新袋子，從原袋子中分出來(lái)，當(dāng)然，現(xiàn)在還是假設(shè)s1和s2可以合并，所以才把它們裝一起，畢竟真的可不行以合并呆會(huì)還要再考察?？疾焱贻斎隺，還要接著考察其它的可能輸入。假如在考察完一個(gè)袋子后，發(fā)覺(jué)全部狀態(tài)在a輸入下都可以轉(zhuǎn)移到本袋子中的狀態(tài)，那么最終的dfa它們就被合并成一個(gè)狀態(tài)，并且在a輸入下，它有一個(gè)到自身的狀態(tài)遷移。 實(shí)現(xiàn)詞法分析器 對(duì)于一個(gè)token，比如用來(lái)表示數(shù)字的token：num，我們可以用正則表達(dá)式描述它，然后畫(huà)出nfa，再將nfa轉(zhuǎn)化成dfa，再最小化dfa的狀態(tài)，但是我們的詞法分析器是不是分析一個(gè)token，所以我們要把全部類(lèi)型的tok

12、en的dfa合并成一個(gè)dfa，這樣，這個(gè)dfa也就可以識(shí)別語(yǔ)言的全部token了，假如在某一連串的輸入下，dfa達(dá)不到終結(jié)狀態(tài)，那就說(shuō)明源代碼有錯(cuò)誤了。 我用c#實(shí)現(xiàn)了一個(gè)用于compiler construction: principles and practice中tiny語(yǔ)言的詞法分析器，tiny語(yǔ)言有關(guān)鍵字：if, then, else, end, repeat, until, read, write，有操作符+，-，*，/，=，(，)，;，:=（全角逗號(hào)不算，是文章的分隔符）這10個(gè)，然后其余的token有number (一或多個(gè)數(shù)字)和identifier(一或多個(gè)字母)，其dfa如下圖： 上面這張圖和編譯原理及實(shí)踐中的一樣，其中的帶中括號(hào)的輸入說(shuō)明這個(gè)輸入是lookahead的，在匹配勝利后是要重新放回輸入流中的，比如識(shí)別num時(shí)，假如發(fā)覺(jué)個(gè)非digit的，那就說(shuō)明識(shí)別到了一個(gè)number，但是最終識(shí)別的那個(gè)非digit字符是要放回輸入流的，因?yàn)樗糁乱淮巫R(shí)別。 其中從start到done的那個(gè)other，指全部非white space，非，非letter，非