編譯原理課設-(中版)

1、編譯原理課程設計簡單編譯器學 院（系）：電子信息與電氣工程學部 學 生 姓 名：李夢珂 學 號：201181216 班 級：電計1101 同 組 人 ：宮麗迪 電計1101 201181306陳笛 電計1101 201181326大連理工大學Dalian University of Technology1編譯原理課程設計簡單編譯器目 錄1 詞法分析21.1 實驗目的21.2 實驗要求21.2.1待分析的簡單的詞法21.2.2 各種單詞符號對應的種別碼：21.2.3 詞法分析程序的功能：31.3 詞法分析程序的算法思想：31.3.1 主程序示意圖：31.3.2 掃描子程序的算法思想：41.3.3

2、 詞法分析程序的C語言程序源代碼：61.3.4 結果分析：61.3.5 總結：72 語法分析82.1 實驗目的82.2實驗要求82.2.1 待分析的簡單語言的語法82.2.2 實驗算法結構8語法分析程序的算法思想82.3 結果分析：132.4 總結：153 語義分析程序163.1 實驗目的：163.2 實驗要求：163.3 算法思想：163.3.1 程序結構圖163.3.2 設置語義過程203.3.3 函數lrparser 在原來語法分析的基礎上插入相應的語義動作：將輸入串翻譯成四元式序列。在實驗中我們只對表達式、賦值語句進行翻譯。213.3.4 簡單賦值語句的翻譯文法213.4 結果分析22

3、3.5 總結：251 詞法分析(李夢珂 201181216 負責)1.1 實驗目的設計、編制并調試一個詞法分析程序，加深對詞法分析原理的理解。1.2 實驗要求設計、編制并調試一個詞法分析程序，三人一組。1.2.1待分析的簡單的詞法（1）關鍵字： int if then else while do read write所有的關鍵字都是小寫。（2）運算符和界符： := = + - + - * / < <= != > >= = ; ( ) #（3）其他單詞是標識符（ID）和整型常數（SUM），通過以下正規(guī)式定義：ID = letter (letter | digit)*NUM

4、 = digit digit*（4） 空格有空白、制表符和換行符組成?？崭褚话阌脕矸指鬒D、SUM、運算符、界符和關鍵字，詞法分析階段通常被忽略。 1.2.2 各種單詞符號對應的種別碼：表1.1 各種單詞符號對應的種別碼單詞符號種別碼 單詞符號種別碼int1+17If2-18Then3:=19else4<20while5!=21do6<=22read7>23write8>=24lettet（letter|digit）*10=25dight dight*11;26=12(27+13)28-1430*15!31/16:32 ,3335 36 1.2.3 詞法分析程序的功能：

5、輸入：所給文法的源程序字符串。輸出：二元組（syn,token或sum）構成的序列。其中：syn為單詞種別碼； token為存放的單詞自身字符串； sum為整型常數。例如：對源程序輸入如下： Int x,y; X:=2*y; If(x>5) Then x:=2*x+2/3;#后經詞法分析輸出如下序列：( 35 (int 1)(x 10)(, 33)(y 10) (；26)(x 10)1.3 詞法分析程序的算法思想：算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。1.3.1 主程序示意圖：主程序示意圖

6、如圖1.1所示。其中初始包括以下兩個方面： 關鍵字表的初值。關鍵字作為特殊標識符處理，把它們預先安排在一張表格中（稱為關鍵字表），當掃描程序識別出標識符時，查關鍵字表。如能查到匹配的單詞，則該單詞為關鍵字，否則為一般標識符。關鍵字表為一個字符串數組，其描述如下：Char *rwtab6 = “int”, “if”, “then”, “else”,“while”, “do”, “read”,”write”; 圖1.1（2）程序中需要用到的主要變量為syn,token和sum 1.3.2 掃描子程序的算法思想：首先設置3個變量：token用來存放構成單詞符號的字符串；sum用來整型單詞；syn用來

7、存放單詞符號的種別碼。掃描子程序主要部分流程如圖1.2所示。 圖 1.21.3.3 詞法分析程序的C語言程序源代碼：1.3.4 結果分析：輸入如下： Int x,y; X:=2*y; If(x>5) Then x:=2*x+2/3;#后經詞法分析輸出如下序列：( 35 (int 1)(x 10)(, 33)(y 10) (；26)(x 10) 如圖1.3所示： 圖1.31.3.5 總結：詞法分析的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。通過本試驗的完成，更加加深了對詞法分析原理的理解。 2 語法分

8、析2.1 實驗目的編制一個遞歸下降分析程序，實現(xiàn)對詞法分析程序所提供的單詞序列的語法檢查和結構分析。2.2實驗要求利用C語言編制遞歸下降分析程序，并對簡單語言進行語法分析。2.2.1 待分析的簡單語言的語法用擴充的BNF表示如下：<程序>：=<聲明><語句串><語句串>：=<語句>；<語句><語句>：=<賦值語句><賦值語句>：=ID：=<表達式><表達式>：=<項>+<項> | -<項><項>：=<因子>

9、;*<因子> | /<因子><因子>：=ID | NUM | （<表達式>）2.2.2 實驗算法結構輸入單詞串，以“#”結束，如果是文法正確的句子，則輸出成功信息，打印“success”，否則輸出“error”。例如： 輸入 int a,x,b; a:=9; x:=2*3; b:=a+x 輸出 success！ 語法分析程序的算法思想（1） 主程序示意圖如圖2.1所示。 圖2.1 語法分析主程序示意圖（2）遞歸下降分析程序示意圖如圖2.2所示。 圖2.2 遞歸下降分析程序示意圖（3）語句串分析過程示意圖如圖2.3所示。圖2-3 語句串分析示意圖（

10、4）statement語句分析程序流程如圖2.4、2.5、2.6、2.7所示。 圖2.4 statement語句分析函數示意圖 圖2.5 expression表達式分析函數示意圖圖 2.6 term分析函數示意圖 圖2.7 factor分析過程示意圖2.3 結果分析：輸入 后輸出success！ 如圖2.8所示：圖2.8輸入 后輸出 error 如圖2.9所示：圖2.92.4 總結：通過本次試驗，了解了語法分析的運行過程，主程序大致流程為：“置初值”à調用scaner函數讀下一個單詞符號à調用IrParseà結束。遞歸下降分析的大致流程為：“先判斷是否有聲明”&#

11、224;不是則“出錯處理”，若是則“調用scaner函數”à調用語句串分析函數à“判斷是否為end”à不是則“出錯處理”，若是則調用scaner函數à“判斷syn=0&&kk=0是否成立”成立則說明分析成功打印出來。不成立則“出錯處理”。3 語義分析程序3.1 實驗目的：通過上機實習，加深對語法制導翻譯原理的理解，掌握將語法分析所識別的語法成分變換為中間代碼的語義翻譯方法。3.2 實驗要求：采用遞歸下降語法制導翻譯法，對算術表達式、賦值語句進行語義分析并生成四元式序列。3.3 算法思想：3.3.1 程序結構圖（1）主程序示意圖如圖3.1所

12、示。 圖3.1 語法分析主程序示意圖（2）遞歸下降分析程序示意圖如圖3.2所示。（3）語句串分析過程示意圖如圖3.3所示。 圖3.2遞歸下降分析程序示意圖 圖3.3 語句串分析示意圖（4）statement語句分析程序流程如圖3.4、3.5、3.6、3.7所示。 圖3.4 statement語句分析函數示意圖 圖3.5 expression表達式分析函數示意圖圖 3.6 term分析函數示意圖圖2-7 factor分析過程示意圖3.3.2 設置語義過程（1）emit(char *result,char *ag1,char *op,char *ag2)該函數的功能是生成一個三地址語句送到四元式表

13、中。四元式表的結構如下：structchar result8;char ag18;char op8;char ag28;quad20; (2) char *newtemp()該函數回送一個新的臨時變量名，臨時變量名產生的順序為T1，T2，char *newtemp(void)char *p; char m8; p=(char *)malloc(8); k+; itoa(k,m,10); strcpy(p+1,m); p0=t; return(p);3.3.3 函數lrparser 在原來語法分析的基礎上插入相應的語義動作：將輸入串翻譯成四元式序列。在實驗中我們只對表達式、賦值語句進行翻譯。3.

14、3.4 簡單賦值語句的翻譯文法SID ­n ifD ¯n­ p = E ­x 若ID定義,則emit ¯x (n=x) ;否則錯誤E ­x T ­q + T ­r x=newtemp ;emit ¯x ¯q¯r (x=q + r)T ­x F ­q * F ­r x=newtemp ;emit ¯x ¯q¯r (x=q * r)F ­x ID ­n ifD ¯n­ p ；x=n F &#

15、173;x ( E ­q ) x=qF ­x NUM­ lexval ifD¯ lexval ­ p ; x= lexval ifD過程表示在符號表中查找標識符，若不存在，則報告“變量未定義而使用”的錯誤，若存在，返回標識符在符號表中的入口地址p。在執(zhí)行語義規(guī)則，輸出四元式時， 參數可用變量名、臨時變量名以及整常數代替。 newtemp()函數用來產生臨時變量, 如產生臨時變量t1 : N=N+1; “t”| ITOS(N) ;emit()函數產生四元式代碼: 例如用輸出函數輸出：t1=q+r 例如：翻譯x=sum*(b+c)； 四元式是： t1=b+c t2=sum*t1 x=t2;在下面的遞歸下降語法制導翻譯程序中，sym和symval 讀取詞法分析結果中的單詞二元式. 如：對于單詞二元式 (ID sum）, 則ID存入syn中，sum存入scaner中。3.4 結果分析3.5 總結：通過本次試驗，了解了語法分析的運行過程，主程