實(shí)現(xiàn)C語言的詞法分析器

1、編譯原理實(shí)驗(yàn)二一 學(xué)習(xí)經(jīng)典的詞法分析器。a) 實(shí)驗(yàn)分析：詞法分析器，有的教材又稱掃描器，我倒是覺得掃描器更加符合其本意，因?yàn)樵~法分析器的主要作用是將文本代碼流解析成一個(gè)個(gè)記號，供語法分析使用。由于上一次實(shí)驗(yàn)，TINY編譯器已經(jīng)相對比較熟悉，這一次主要關(guān)注詞法分析器的部分，即SCAN.C。就詞法分析器本身的寫法而言，并沒有所謂的標(biāo)準(zhǔn)代碼，不過經(jīng)典代碼還是很有參考價(jià)值的，而修改經(jīng)典的過程也是體會(huì)經(jīng)典的最佳形式。b) 實(shí)驗(yàn)過程：1. 閱讀已有編譯器的經(jīng)典詞法分析源程序：我選擇的仍然是TINY編譯器，它的詞法分析部分是SCAN.C文件。i. 調(diào)用詞法分析器的形式：在主函數(shù)中有如上語句是調(diào)用SCAN.C

2、中的getToken()函數(shù)。getToken()即詞法分析器進(jìn)行狀態(tài)轉(zhuǎn)換的核心部分。ii. 詞法分析器中的常量：1） 狀態(tài)枚舉：枚舉的最大好處在于能夠用字符（狀態(tài)）代替數(shù)字，而且將這些封裝在一個(gè)結(jié)構(gòu)中。2） TokenString是為了存儲保留字的標(biāo)識符3） 以下變量是為了處理輸入緩存以及當(dāng)前指針位置的相關(guān)存儲：4） 保留字的結(jié)構(gòu)體，這一部分可以清晰的看到所有保留字：iii. 詞法分析器的相關(guān)函數(shù)：1) 處理文件輸入相關(guān)：這兩個(gè)函數(shù)是一對，前者是從緩存中讀取下一個(gè)字符，后者則將當(dāng)前讀取的字符重新放回緩存。后者存在的最大的價(jià)值在于，當(dāng)用下一字符的情況判斷將跳轉(zhuǎn)到什么狀態(tài)時(shí)，如果該字符不屬于當(dāng)前

3、標(biāo)示符，則放回緩存，以保證下一標(biāo)示符的獲取不受影響。 2) 判斷字符是否為保留字：對于讀入的單詞，我們需要知道其到底是一個(gè)變量名還是一個(gè)保留字，這個(gè)時(shí)候就需要調(diào)用該函數(shù)。利用for循環(huán)在所有保留字中搜尋，有匹配的就說明是一個(gè)保留字，否則就是變量名。3) DFA實(shí)現(xiàn)算法：TINY采用的是while和多層switch判斷相結(jié)合的跳轉(zhuǎn)形式，這種寫法和EDA實(shí)驗(yàn)中的狀態(tài)裝換如出一轍，非常簡便而且容易理解。但是缺點(diǎn)也很明顯：不容易擴(kuò)充，顯得比較雜亂。其邏輯很清楚：從START狀態(tài)開始，每獲取一個(gè)字符，就根據(jù)字符情況跳轉(zhuǎn)到相應(yīng)的下一狀態(tài)，如果跳轉(zhuǎn)到接受態(tài)DONE，則輸出。輸出是調(diào)用UTIL.C文件完成的。

4、可以看到的是，如果一個(gè)語言越復(fù)雜，其包含的字符形式越多，這種case討論將會(huì)越復(fù)雜，至此我已經(jīng)可以想象得到C語言詞法分析器的“宏偉”程度了。2. 改變DFA的實(shí)現(xiàn)算法：通過分析TINY的詞法分析器，我們很快可以找到我們的DFA實(shí)現(xiàn)形式與其的差別。我們是建立了一個(gè)狀態(tài)轉(zhuǎn)換表，并將其存儲在了一個(gè)二維結(jié)構(gòu)中，通過輸入與當(dāng)前狀態(tài)的對應(yīng)得到下一狀態(tài)的，并將這一狀態(tài)變成當(dāng)前狀態(tài)，反復(fù)進(jìn)行上述操作，直到進(jìn)入接受態(tài)。如果要改變DFA的實(shí)現(xiàn)算法，過程很明顯：建立二維結(jié)構(gòu)存儲狀態(tài)轉(zhuǎn)移，查表進(jìn)行狀態(tài)轉(zhuǎn)移。接下來將進(jìn)行操作和分析：1） 在修改之前，先觀察原有的詞法分析器正常運(yùn)行的結(jié)果，以便修改后比對：為了測試輸出結(jié)果

5、，我們在主函數(shù)（TINY_XH）中將詞法分析追蹤（TraceScan）賦值為TRUE，這樣在進(jìn)行編譯的輸出中就可以看到詞法分析的結(jié)果，方便用來對比。TraceScan一旦使能，這里就可以輸出到屏幕上。在修改程序之前，截屏如上，左邊是源程序，右邊是編譯的詞法分析的結(jié)果2） 建立狀態(tài)轉(zhuǎn)換表，通過分析源程序可知如下狀態(tài)轉(zhuǎn)換圖：（該圖是我用VISIO繪制）原程序使用while大循環(huán)下的switch和case進(jìn)行狀態(tài)轉(zhuǎn)換，這里完全可以換成上次我們寫的通用DFA形式。所謂通用DFA就是指狀態(tài)轉(zhuǎn)換的核心部分不會(huì)隨著狀態(tài)或者輸入的改變而改變，狀態(tài)轉(zhuǎn)換的跳轉(zhuǎn)和狀態(tài)存儲的二維表有關(guān)，只用修改存儲狀態(tài)的二維表，既可

6、以方便的修改或者擴(kuò)充編譯器的詞法處理能力。狀態(tài)圖轉(zhuǎn)換成狀態(tài)表可得：通過狀態(tài)轉(zhuǎn)換情況，將其保存在狀態(tài)轉(zhuǎn)換表中，具體形式如上。就二維表而言，有很多種寫法，比如我把一些輸入合并到other類型，是為了減輕狀態(tài)表的冗余狀態(tài)數(shù)量。這個(gè)二維表中沒有冗余狀態(tài)。判斷冗余的方法很簡單，如果有兩列/兩行完全相同，這兩列/兩行就可以合并成一列/一行。3） 修改狀態(tài)轉(zhuǎn)換代碼以及附屬屬性部分的實(shí)現(xiàn)：有了狀態(tài)轉(zhuǎn)換表，狀態(tài)轉(zhuǎn)移只用一句話就可以解決：可以說就狀態(tài)轉(zhuǎn)移這一部分而言，非常簡單。但是為了方便輸出，需要知道獲取的標(biāo)示符是什么類型的，因此需要進(jìn)行賦值。比如如下修改：4） 測試結(jié)果：（和修改前完全一致）c) 實(shí)驗(yàn)問題：1

7、） 程序進(jìn)入死循環(huán)，或者一直報(bào)錯(cuò)：程序不能正確執(zhí)行，肯定出在細(xì)節(jié)處，我開始以為是邏輯處出錯(cuò)，一直在檢查語句，結(jié)果很長時(shí)間都沒有發(fā)現(xiàn)問題。后來排除了所有可能，我檢查了一下最開始制作的二維狀態(tài)轉(zhuǎn)移表，果然就發(fā)現(xiàn)了問題的所在：狀態(tài)轉(zhuǎn)換中本應(yīng)跳轉(zhuǎn)到DONE，因?yàn)槭д`寫成了START，結(jié)果跳轉(zhuǎn)到了START。糾正結(jié)果后，程序完全正確，但是這個(gè)錯(cuò)誤確實(shí)消耗了我很長的時(shí)間去檢查。d) 實(shí)驗(yàn)結(jié)果：對SCAN.C的解釋，在上面的報(bào)告中已經(jīng)給出。SCAN.C的修改版本在CODE文件夾中。如果要運(yùn)行完整的程序，在“CODE完整的VS工程”目錄中，可以用Visual Studio運(yùn)行，其中sample.tny在該工程

8、的debug文件夾下，方便用CMD運(yùn)行。e) 實(shí)驗(yàn)心得：由于有了第一次的實(shí)驗(yàn)的基礎(chǔ)，轉(zhuǎn)化成一個(gè)DFA的思想是非常清晰而簡單的，然而實(shí)現(xiàn)的過程不是一帆風(fēng)順的，中間任何一個(gè)環(huán)節(jié)都可能會(huì)出現(xiàn)很多小問題，一個(gè)小細(xì)節(jié)沒有處理好，可能會(huì)導(dǎo)致整個(gè)程序的崩潰，所以需要耐心和細(xì)心。我在做的過程中，曾經(jīng)因?yàn)橐粋€(gè)狀態(tài)打錯(cuò)，導(dǎo)致跳轉(zhuǎn)時(shí)有誤，開始一直懷疑是邏輯問題，不曾檢查狀態(tài)表的錯(cuò)誤，導(dǎo)致延誤了很久。我覺得糾錯(cuò)的過程就像是推理和演繹，雖然有DEBUG，不過我使用的比較少，單純通過輸出推測出錯(cuò)的地方會(huì)是哪里，我喜歡這個(gè)過程。當(dāng)一個(gè)完整的詞法分析結(jié)果出現(xiàn)在CMD中時(shí)，突然覺得這是最美的文字。二 實(shí)現(xiàn)一門語言的詞法分析器a

9、) 實(shí)驗(yàn)分析：通過上面的實(shí)驗(yàn)我們已經(jīng)了解了簡單的詞法分析器，實(shí)戰(zhàn)莫過于新編一個(gè)語言的編譯器。而一個(gè)語言的詞法分析器，我們首先要知道它含有什么關(guān)鍵字，有哪些專用符號，什么是特殊標(biāo)記，以及其他符號或者注釋情況。b) 實(shí)驗(yàn)過程：1. 語言確定：我選擇C-語言，因?yàn)橐谝院蟮膶?shí)驗(yàn)中繼續(xù)完善其他部分，所以我希望按照一個(gè)完整的工程制作。因此仿照TINY編譯器的形式，將每一部分的功能集中在一個(gè)文件中，有g(shù)lobals文件對全局變量進(jìn)行定義，有util專職輸出，有C_XH文件作為主函數(shù)，調(diào)用其他的函數(shù)。然后定義SCAN函數(shù)進(jìn)行詞法分析。我希望這種高耦合低內(nèi)聚的形式成為我以后編碼的風(fēng)格和習(xí)慣。2. 編寫詞法分析

10、器：1） 確定C-語言的慣用詞法，并在globals.c文件中定義：一、定義關(guān)鍵字，關(guān)鍵字都是保留字：else if int return void while1在globals.h里面寫入保留字信息2在scan里面選擇關(guān)鍵字信息更改二、專用符號：+ - * / < <= > >= = != = ; , ( ) /* */三、其他標(biāo)記是I D和N U M，通過下列正則表達(dá)式定義：四、空格由空白、換行符和制表符組成。當(dāng)然這些是要被忽略的。五、注釋用符號/ * . . . * /圍起來。完成了常量的定義之后，應(yīng)該是如下圖的形式（在GLOBALS.C文件中）。其中，尤其需要注

11、意，MAXRESERVED變量必須有一個(gè)值，否則在檢查保留字的時(shí)候，會(huì)出現(xiàn)循環(huán)訪問范圍有誤。由于我們一共有6個(gè)保留字，所以賦值為6。2） 狀態(tài)轉(zhuǎn)移分析：由于C-的詞法更加復(fù)雜，所以狀態(tài)也比TINY多很多，我定義了11個(gè)狀態(tài)。主要因?yàn)橐韵聵?biāo)示符是由多字符組成，所以不得不為每一種生成狀態(tài)記錄：字母，數(shù)字，<=，>=，=，！=，/*，*/在SCAN.C中的狀態(tài)定義如下：狀態(tài)圖大致如上，這個(gè)圖只有大致的輪廓，限于篇幅，這里有很多自環(huán)沒有畫出，而且一些狀態(tài)轉(zhuǎn)移可能看不清楚。其中最下面的一串狀態(tài)轉(zhuǎn)移，與上次試驗(yàn)中的下圖類似：事實(shí)上，這個(gè)正是用來判斷注釋部分的狀態(tài)轉(zhuǎn)移。/* oooooooooo

12、ooooo */（注：除了這張圖是從老師的文檔中拷來，其他全部是自己創(chuàng)作，工具是VISIO）3） DFA實(shí)現(xiàn)代碼：這一次采用TINY的switch-case格式，因?yàn)檫@種形式更加方便。部分代碼如上。由于無論是字符還是狀態(tài)都增加了很多，代碼量也稍有增加。4） 加上主函數(shù)，調(diào)用詞法分析器：由于只做了詞法分析器，所以只調(diào)用了getToken()5） 修改輸出函數(shù)：UTIL.C文件中的關(guān)鍵語句關(guān)系到詞法分析的輸出，因此需要重新寫。以便能夠在CMD中看到詞法分析的結(jié)果。由于篇幅比較長，因此只截取部分如下：3. 至此C-的一個(gè)編譯器C_XH制作好了，運(yùn)行結(jié)果如下：左圖是一個(gè)C-語言的源程序。詞法分析結(jié)果如

13、下，正確性已經(jīng)得到了我的驗(yàn)證：有一個(gè)有趣的測試數(shù)據(jù)：（注釋代碼中含有中文）結(jié)果表明注釋中出現(xiàn)的中文對結(jié)果沒有影響。c) 實(shí)驗(yàn)問題：1. 其實(shí)原本可以自己寫一個(gè)簡單的主函數(shù)調(diào)用Scan和一些有用的參數(shù)即可。但是為了試驗(yàn)的可延續(xù)性，我保持TINY的風(fēng)格，將數(shù)據(jù)變量全部儲存在Globals中，util用來輸出，scan進(jìn)行詞法分析。不過這樣做也是有代價(jià)的，就是寫起來工程量比較大，于是我參考著TINY，經(jīng)過多次修改錯(cuò)誤，才算完成。2. 就詞法分析器本身而言，并不一定要按照TINY的形式寫，其實(shí)可以自己創(chuàng)造數(shù)據(jù)存儲格式，自己逐單詞判斷，比如用hash表來實(shí)現(xiàn)存儲，以此實(shí)現(xiàn)DFA。只不過不好繼續(xù)擴(kuò)展。我本想自己重新用一種方法，后來發(fā)現(xiàn)時(shí)間有限，就放棄了。3. 不該顯示的部分顯示在結(jié)果中，原因在注釋的DFA狀態(tài)跳轉(zhuǎn)錯(cuò)誤。為了方便看，我故意用了中文，注釋部分總是會(huì)有輸出。開始我百思不得其解，還以為是輸出部分沒有寫好，后來才發(fā)現(xiàn)是跳轉(zhuǎn)錯(cuò)誤。得到注釋結(jié)束后，不應(yīng)該跳往DONE，這樣表示找到一個(gè)標(biāo)示符，需要輸出。由于注釋是完全屏蔽的，所以應(yīng)該在注釋結(jié)束后直接跳往start而是不是done狀態(tài)。接受到“注釋部分”結(jié)束