編譯原理實驗(遞歸向下語法分析法實驗)附C語言源碼-成功測試

1、實驗二 遞歸向下分析法一、 實驗目和要求根據(jù)某一文法編制調(diào)試遞歸下降分析程序，以便對任意輸入的符號串進行分析。 本次實驗的目的主要是加深對遞歸下降分析法的理解。 二、 實驗內(nèi)容 （1） 功能描述 1、遞歸下降分析法的功能 詞法分析器的功能是利用函數(shù)之間的遞歸調(diào)用模擬語法樹自上而下的構造過程。 2、遞歸下降分析法的前提 改造文法：消除二義性、消除左遞歸、提取左因子，判斷是否為 LL（1）文法， 3、遞歸下降分析法實驗設計思想及算法 為 G 的每個非終結符號 U 構造一個遞歸過程,不妨命名為 U。 U 的產(chǎn)生式的右邊指出這個過程的代碼結構： 1)若是終結符號，則和向前看符號對照， 若匹配則向前進一

2、個符號；否則出錯。 2)若是非終結符號，則調(diào)用與此非終結符對應的過程。當 A 的右部有多個產(chǎn)生式時,可 用選擇結構實現(xiàn)。 具體為： （1） 對于每個非終結符號U->u1|u2|un處理的方法如下：U( ) ch=當前符號; if(ch可能是u1字的開頭) 處理u1的程序部分; else if(ch可能是u2字的開頭)處理u2的程序部分; else error() （2） 對于每個右部u1->x1x2xn的處理架構如下： 處理x1的程序； 處理x2的程序； 處理xn的程序；（3）如果右部為空，則不處理。 （4）對于右部中的每個符號xi 

3、0;如果xi為終結符號： if(xi= = 當前的符號)  NextChar()；  return;   else 出錯處理  如果xi為非終結符號，直接調(diào)用相應的過程xi()  說明： NextChar為前進一個字符函數(shù)。 （2） 程序結構描述 程序要求： 程序輸入/輸出示例： 對下列文法，用遞歸下降分析法對任意輸入的符號串進行分析： （1）E->TG （2）G->+TG|TG （3）G-> （4）T->FS （5）S->*FS| / FS （6）S-> （7）F->(E

4、) （8）F->i 輸入出的格式如下： (1)E 盤建立一個文本文檔" 222.txt"存儲一個以#結束的符號串(包括+*/（）i#)，在此 位置輸入符號串例如：i+i*i# (2)輸出結果：i+i*i#為合法符號串 備注：輸入一符號串如 i+i*#,要求輸出為“非法的符號串” 函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關系圖。 程序所用主要參數(shù)和頭文件說明： #include<stdio.h> #include<stdlib.h>#include<string.h> FILE *fp; /定義一個全局文件指針變量

5、 char ch; /定義一個全局字符變量 #define N 20 /定義一個數(shù)組大小常量 char stringN; /定義一個用于存儲算式字符串的數(shù)組 char *p; /定義一個全局字符指針變量 函數(shù)說明：1） 非終結符函數(shù) E() 函數(shù)功能描述：根據(jù)以上文法要求 E->TG,所以從主函數(shù)開始調(diào)入第一個非終結符函數(shù) 執(zhí)行，顯示調(diào)用產(chǎn)生式，依次嵌套調(diào)用非終結符函數(shù) T（）和 G（） ，進行遞歸向下分析。 void E()printf("E->TG.%cn",ch); T(); G(); 2） 非終結符函數(shù) T() 函數(shù)功能描述：根據(jù)以上文法要求 T->

6、;FS,首先顯示算式匹配所用的顯示調(diào)用的產(chǎn)生式， 依次嵌套調(diào)用非終結符函數(shù) F（）和 S（） ，進行遞歸向下分析。 void T() printf("T->FS.%cn",ch); F(); S(); 3） 非終結符函數(shù) G() 函數(shù)功能描述：根據(jù)以上文法要求 G->+TG|TG ，G->，如果當前字符變量 ch 為“+” ，則顯示調(diào)用產(chǎn)生式，首先嵌套調(diào)用 test()函數(shù)判斷是算式遞歸向下分析是否結束，若沒有 結束則繼續(xù)依次嵌套調(diào)用非終結符函數(shù) T（）和 G（） ；如果當前字符變量 ch 為“-” ，則顯 示調(diào)用產(chǎn)生式，從文件文檔中讀取下一個字符，讓字符

7、指針變量指向下一個字符，繼續(xù)依次 嵌套調(diào)用非終結符函數(shù) T（）和 G（） ；如果當前字符變量 ch 既不為“+” 也不為“-” ，非 終結符 G 指向為空，函數(shù)只用于顯示指向為空，找不到可以和文件中字符匹配的非終結符。 void G() if (ch='+') printf("G->+TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T(); G(); else if(ch='-') printf("G->-TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T

8、(); G(); else printf("G->.%cn",ch); 4） 非終結符函數(shù) F() 函數(shù)功能描述：根據(jù)以上文法要求 F->(E)，F(xiàn)->i ，如果當前字符變量 ch 為“i” ，則顯示 調(diào)用產(chǎn)生式，從文件文檔中讀取下一個字符，讓字符指針變量指向下一個字符,如果當前字 符變量 ch 為“ ，則顯示調(diào)用產(chǎn)生式，繼續(xù)依次嵌套調(diào)用非終結符函數(shù) E(),函數(shù) E()執(zhí)行 （” 結束以后，若果 ch=“），從文件文檔中讀取下一個字符，讓字符指針變量指向下一個字符， ” 否則算式匹配失敗，程序執(zhí)行結束；若果 ch 不為“i” ，又不是“ （”則算式匹配失

9、敗，程序 執(zhí)行結束。 void F() if(ch='i') printf("F->i.%cn",ch); *p=ch; p+; ch=fgetc(fp); else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch=')') *p=ch; p+;ch=fgetc(fp); else printf("沒有右括號“)”匹配不成功！n"); exit(0); elseprintf(&q

10、uot;匹配不成功！n"); exit(0); 5） 非終結符函數(shù) S() 函數(shù)功能描述：根據(jù)以上文法要求 S->*FS| / FS，S->，如果當前字符變量 ch 為“*” ， 則顯示調(diào)用產(chǎn)生式，從文件文檔中讀取下一個字符，讓字符指針變量指向下一個字符，依次 嵌套調(diào)用非終結符函數(shù) F（）和遞歸調(diào)用自身 S（） ；如果當前字符變量 ch 為 “/” ，則顯示 調(diào)用產(chǎn)生式，從文件文檔中讀取下一個字符，讓字符指針變量指向下一個字符，依次嵌套調(diào) 用非終結符函數(shù) F （） 和遞歸調(diào)用自身 S ；如果當前字符變量 ch 既不為“*” 也不為“/” （） ， G 中找不到可以匹配的算

11、式則非終結符 G 指向為空。 void S() if(ch='*') printf("S->*FS.%cn",ch); *p=ch; p+; ch=fgetc(fp); F(); S(); else if(ch='/') printf("S->/FS.%cn",ch); *p=ch; p+; ch=fgetc(fp); F(); S(); else printf("S->.%cn",ch); 6） 主函數(shù) main（） 函數(shù)功能描述： E 盤打開一個 222.txt 文本文檔， 從 讀

12、取一個字符， 調(diào)用非終結符函數(shù) E(), 非終結符函數(shù) E(),執(zhí)行完以后，如果 ch 為“#”則算式匹配成功，否則匹配失敗。 main（） if(fp=fopen("E:222.txt","r")=NULL) /讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個字符 fprintf(stderr,"error opening.n"); exit(0); ch=fgetc(fp); /讀取字符只能讀一個 p=string; printf("遞歸下降分析所用產(chǎn)生式：n"); E(); if(ch='#

13、9;) *p=ch; printf("算式匹配成功！n 算式結果：%sn",string); else printf("算式匹配不成功！n"); fclose(fp); 函數(shù)之間的調(diào)用關系圖：調(diào)試運行結果： 1) 在文件中輸入：i+i*i# 運行結果如下圖所示：2）在文件中輸入：i+i-# 運行結果如下圖所示：3）在文件中輸入：i+(i*i)# 運行結果如下圖所示：4）在文件中輸入：i+(i*i# 運行結果如下圖所示：5）在文件中輸入：i+i*i)# 運行結果如下圖所示：三、 實驗過程記錄 本次實驗出現(xiàn) 3 次重要錯誤： （1）出錯 1：全局變量在 ma

14、in（）函數(shù)中重新定義，編譯連接執(zhí)行都沒有錯誤提示，但在 運行時候出錯； 解決方案：刪除 main（）函數(shù) FILE *fp; （2）出錯 2：算式匹配時候，如果輸入字符串中只有“ （”時，仍然是能夠正確匹配 解決方案：由于沒有考慮括號匹配是成對存在的問題，所以這種結果不符合要求，添 加右括號匹配代碼如下所示： else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch=')') *p=ch; p+; ch=fgetc(fp);else pr

15、intf("沒有右括號“)”匹配不成功！n"); exit(0); （3） 出錯 3： 調(diào)用非終結符 E()執(zhí)行完以后， 則對于一些非法的算式還是成功輸出例如 i-、 i*等； 解決方案：在主函數(shù) main（）中需要對調(diào)用非終結符 E()執(zhí)行完以后的 ch 進行判斷， 如果 ch 為“#”則算式匹配成功，否則算式匹配失敗，在主函數(shù)中添加代碼如下： if(ch='#') *p=ch; printf("算式匹配成功！n 算式結果：%sn",string); else printf("算式匹配不成功！n"); 四、實驗總結

16、通過本次上機實驗讓我認識了很多，加深了我對遞歸下降分析法的理解。自上而下語法 分析法就是從輸入串開始，逐步進行“歸約” ，直至歸約到文法的開始符號。基于第三章的 此法分析，通過實驗我對本章的語法分析也有了深刻的認識。同時通過本次編程，讓我深刻 認識編程應該注重細節(jié)，編程之前首先要做好分析準備。 五、程序源代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> FILE *fp; /定義一個全局文件指針變量 char ch; /定義一個全局字符變量 #define N 20 /定義一個數(shù)組大小常量

17、char stringN; /定義一個用于存儲算式字符串的數(shù)組 char *p; /定義一個全局字符指針變量 void E(); void T(); void G(); void F(); void S(); /非終結符 F void F() if(ch='i') printf("F->i.%cn",ch); *p=ch; p+; ch=fgetc(fp); else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch

18、=')') *p=ch; p+; ch=fgetc(fp); else printf("沒有右括號')'匹配不成功！n"); exit(0); else printf("算式匹配不成功！n"); exit(0); void G() if (ch='+') printf("G->+TG.%cn",ch); *p=ch; p+; ch=fgetc(fp);T(); G(); else if(ch='-') printf("G->-TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T();G(); else printf("G->.%cn",ch); /非終結符 T void T() printf("T->FS.%cn",ch); F(); S(); /非終結符 S void S() if(ch='*') printf("S