編譯原理實驗報告-詞法分析

1、+*編譯原理課程實驗報告實驗1：詞法分析姓名院系軟件學院學號任課教師陳鄞老師指導教師郭勇老師實驗地點軟件學院三樓機房實驗時間2016/10/23/星期日實驗課表現(xiàn)出勤、表現(xiàn)得分實驗報告得分實驗總分操作結(jié)果得分一、需求分析得分要求：闡述詞法分析系統(tǒng)所要完成的功能 詞法分析是編譯的第一個階段，主要任務是讀入源程序的輸入字符，將它們組成詞素，生成并輸出一個詞法單元序列，每個詞法單元對應于一個詞素。在本詞法單元中，基本功能要求實現(xiàn)以下幾類單詞：Ø 標識符（由大小寫字母、數(shù)字以及下劃線組成，但必須以字母或者下劃線開頭）Ø 關(guān)鍵字（類型關(guān)鍵字：整型、浮點型、布爾型、記錄型；分支結(jié)構(gòu)中的

2、if和else；循環(huán)結(jié)構(gòu)中的do和while；過程聲明和調(diào)用中的關(guān)鍵字）本詞法分析器可以識別C語言的32個關(guān)鍵字，其中包括："char","int","short","long", "float","double","bool","enum","struct","if","else","do","while","switch&q

3、uot;,"case","continue","for", "void","goto","extern","const","typedef","union","static","auto","register","default","sizeof", "return","signed&qu

4、ot;,"unsigned","volatile"。Ø 運算符（算術(shù)運算符；關(guān)系運算符；邏輯運算）本詞法分析器可以識別的運算符：“ * ” 乘法運算符；“ / ” 除法運算符；“ % ” 取余運算符； “ + ” 加法運算符；“ - ” 減法運算符；<< 左移運算符；>> 右移運算符；<、<=、>、>= 關(guān)系運算符； “ = ” 等于運算符；“ != ” 不等于運算符； “ & ” 按位與運算符 ；“ ” 按位異或運算符； “ | ” 按位或運算符； “&&” 邏輯與運算符

5、； “ | ” 邏輯或運算符；” ! “ 非運算符；=、 +=、 -=、 *=、 /=、 %=、 &=、 =、 |=、 <<=、 >>= 賦值運算符。Ø 界符（用于賦值語句的界符，如“=”；用于句子結(jié)尾的界符，如“；”；用于數(shù)組表示的界符，如“”和“”；用于浮點數(shù)表示的界符“.”）本詞法分析器可以識別的界符：'','','','','(',')',',','','.','=','?

6、9;,':'Ø 常數(shù)（無符號整數(shù)和浮點數(shù)，包括科學計數(shù)法，字符串常數(shù)等）Ø 注釋（/*/形式）Ø 八進制數(shù)和十六進制數(shù)Ø 字符常數(shù)二、文法設計得分要求：對如下內(nèi)容展開描述（1） 給出各類單詞的詞法規(guī)則描述（正則文法或正則表達式）（2） 各類單詞的轉(zhuǎn)換圖（1） 1）標識符的正則定義：letter_ -> a-zA-Z_digit -> 0-9id -> letter_(letter_|digit)*說明：關(guān)鍵字的正則定義與標識符是一樣的，但是為了區(qū)別關(guān)鍵字和標識符，我采取初始化時就將各個關(guān)鍵字保留起來，識別時先進行判斷是不

7、是關(guān)鍵字，如果不是關(guān)鍵字再進行判斷是不是標識符。 2）運算符的正則定義： operator -> + | - | * | / | += | -= | *= | /= | % | + | - | != | = | > | < | >= | <= | >> | << | | | | & | && | | | ! 3) 界符的正則定義： Boundary -> | | | | ( | ) | , | ; | : | ? | 4)常數(shù)的正則定義： digit -> 0-9 digits -> digit d

8、igit* number -> digits (.digits)? (E +-? digits)? 5)注釋的正則定義： NOTE -> /*other*/ Other指代任意字符 6）八進制數(shù)和十六進制數(shù)的正則定義： OCT -> 0(1|2|3|4|5|6|7)（0|1|2|3|4|5|6|7）* HEX-> 0x(1|9|a|f) (0|9|a|f)*（2）1）標識符和關(guān)鍵字的轉(zhuǎn)換圖2）運算符的轉(zhuǎn)換圖說明：因為運算符過多，本出的轉(zhuǎn)換圖只給出部分，其他可類似構(gòu)造。3）界符的轉(zhuǎn)換圖4）常數(shù)的轉(zhuǎn)換圖有問題。5）注釋的轉(zhuǎn)換圖 6)八進制的轉(zhuǎn)換圖： 十六進制的轉(zhuǎn)換圖： 字符

9、常量的轉(zhuǎn)換圖： 注：狀態(tài)1到狀態(tài)3的letter是a-z的字母 狀態(tài)2到3的letter是指可以構(gòu)成轉(zhuǎn)義字符的字母，比如a,t,b等。三、系統(tǒng)設計得分要求：分為系統(tǒng)概要設計和系統(tǒng)詳細設計。（1） 系統(tǒng)概要設計：給出必要的系統(tǒng)宏觀層面設計圖，如系統(tǒng)框架圖、數(shù)據(jù)流圖、功能模塊圖等以及相應的文字說明。1） 先給出系統(tǒng)的總體數(shù)據(jù)流圖：本詞法分析器主要針對C語言的源程序進行識別，可以通過在輸入?yún)^(qū)寫入程序，也可以通過文件導入的方式導入程序，經(jīng)過詞法分析器的分析以后輸出流為詞法單元和DFA轉(zhuǎn)換表。2） 系統(tǒng)框架：說明：本詞法分析器主要包括三大塊，分別是符號表（用于儲存符號），控制器（核心部分，用于識別各個單

10、詞），用戶界面（view模塊，用于圖形化操作），三個大模塊下面含各個小模塊，圖里有詳細內(nèi)容，就不贅述。（2）系統(tǒng)詳細設計：對如下工作進行展開描述ü 核心數(shù)據(jù)結(jié)構(gòu)的設計主要的數(shù)據(jù)結(jié)構(gòu)有兩種，一種是為了識別FA轉(zhuǎn)換表而設計的Tuple類；1）Tuple類的主要功能：導入FA轉(zhuǎn)換表時，以三元組的形式記錄FA轉(zhuǎn)換表的各個過程，所以Tuple類負責儲存FA轉(zhuǎn)換表。Tuple類可以存儲三元組Tuple<T1,T2,T3>，其中T1表示某狀態(tài)，T2表示輸入的文法符號,T3是T1遇到T2后的狀態(tài)。2）第二種數(shù)據(jù)結(jié)構(gòu)是數(shù)組；數(shù)組的功能：充當符號表，為了能夠識別關(guān)鍵字，運算符，界符等單詞，必

11、須按照其類型將其存儲，而這里實現(xiàn)單詞存儲功能的就是數(shù)組，包括char數(shù)組和string數(shù)組。ü 主要功能函數(shù)說明本詞法分析器核心功能涉及到三個類。1） IDcontent類功能：充當符號表的角色，主要是用來保存關(guān)鍵字，運算符，界符，轉(zhuǎn)義字符等各類單詞。主要函數(shù)：bool isConstCh(string str)/判斷是否轉(zhuǎn)義字符bool isLetter_(char c)/判斷是否字母或下劃線bool isDigit(char c)/判斷是否數(shù)字bool isBlank(char c)/ 判斷是否是空格、制表符、換行、回車bool isKeyWord(string str)/判斷是

12、否關(guān)鍵字bool isBoundary(char c)/ 判斷是否是邊界符號bool isOperator(string ch)/判斷是否運算符2） Identifier類功能：識別單詞的核心類主要函數(shù)：string isID(string str, ref int i)/是否是標識符string isSixteen(string str, ref int i,out bool right)/是否16進制數(shù)string isEight(string str,ref int i,out bool right)/是否8進制數(shù)string isNumber(string str, ref int i

13、, out bool right)/是否是常數(shù)string isOperator(string str, ref int i, out bool right)/是否是運算符string isNote(string str, ref int i, out bool right)/是否注釋string isBoundary(string str, ref int i,out bool right)/是否界符string isChar(string str, ref int i, out bool right)/是否字符常數(shù)3） Form1類功能：負責界面輸入和輸出，以及判斷邏輯的應用主要函數(shù)：vo

14、id analysis(string str)/負責詞法分析邏輯void addDFAItem(string column1, string column2)/輸出DFA轉(zhuǎn)換表void 幫助ToolStripMenuItem_Click(object sender, EventArgs e)/導入FA轉(zhuǎn)換表void 操作ToolStripMenuItem_Click_1(object sender, EventArgs e)/導入測試文件ü 程序核心部分的程序流程圖 說明：進入不同DFA轉(zhuǎn)換表必須使輸入的字符滿足相應的終結(jié)符，所以程序核心部分先進行輸入字符的判斷，然后再進入相應的DF

15、A轉(zhuǎn)換表進行判斷。 注意：為了不使圖太復雜和混亂，這里沒畫出當不滿足相應DFA轉(zhuǎn)換表時的輸出結(jié)果，比如在是否常數(shù)判斷是，答案是否（即不滿足相應的DFA轉(zhuǎn)換表），則輸出錯誤信息，其他判斷也是同樣的處理方式，不滿足相應的DFA轉(zhuǎn)換表時，則輸出相應的錯誤信息。四、系統(tǒng)實現(xiàn)及結(jié)果分析得分要求：對如下內(nèi)容展開描述。（1） 系統(tǒng)實現(xiàn)過程中遇到的問題；（2） 針對某測試程序輸出其詞法分析結(jié)果；（3） 輸出針對此測試程序?qū)脑~法錯誤報告；（4） 對實驗結(jié)果進行分析。注：其中的測試樣例自行產(chǎn)生。（1） 系統(tǒng)實現(xiàn)過程中遇到的主要問題1） 如何導入FA轉(zhuǎn)換表進行基于DFA的詞法分析器設計問題描述：如何設計轉(zhuǎn)換表的

16、格式，使其能夠被程序識別，識別以后如何基于FA轉(zhuǎn)換表，設計詞法分析器？解決：為了能夠識別FA轉(zhuǎn)換表，轉(zhuǎn)換表的格式設計為三元組的形式，即待輸入狀態(tài)->終結(jié)符->輸出狀態(tài)，這樣子便能將整個FA轉(zhuǎn)換表識別。同時設計了Tuple<T1,T2,T3>的數(shù)據(jù)結(jié)構(gòu)用來保存FA轉(zhuǎn)換表，Tuple是一個三元組的數(shù)據(jù)結(jié)構(gòu)，T1表示待輸入狀態(tài)，T2表示輸入的字符，T3表示輸出狀態(tài)。 為了基與DFA轉(zhuǎn)換表設計詞法分析器，我采用查表的方式實現(xiàn)，根據(jù)起始狀態(tài)和輸入字符查詢?nèi)M，得到輸出狀態(tài)，再以輸出狀態(tài)作為下一次的輸入狀態(tài)，再加上輸入的字符去查DFA轉(zhuǎn)換表，以此來實現(xiàn)基于DFA的詞法分析器。2） 如何根據(jù)輸入的程序，識別各類單詞問題描述：當讀入源程序后，如何分割各個字符，使其進入正確的DFA轉(zhuǎn)換表進行識別，然后分別進行識別輸出？解決：為了能夠識別各類單詞，使其進入正確的DFA轉(zhuǎn)換表進行識別，我采用逐個字符讀入的方式，根據(jù)讀入的起始字符進入相應的DFA轉(zhuǎn)換表，如果未達到DFA轉(zhuǎn)換表的終止狀態(tài)，則報錯，顯示輸入的錯誤單詞和相應的行號，如果成功達到終止狀態(tài)則退出轉(zhuǎn)換表并顯示識別的單詞和Token序列3） 單詞識別時，如何用程序表示DFA轉(zhuǎn)換表問題描述：因為要基于DFA設計詞法分析器，DAF轉(zhuǎn)換表中主要對應的各個狀