編譯原理語法實驗

1、精選優(yōu)質文檔-傾情為你奉上實驗二：自上而下語法分析一、實驗目的：根據(jù)某一文法編制調試遞歸下降分析程序，以便對任意輸入的符號串進行分析。根據(jù)某一文法編制調試LL（1）分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對自上而下分析法的理解。二、實驗預習提示自下而上分析法的前提改造文法：消除二義性、消除左遞歸、提取左因子，判斷是否為LL（1）文法A遞歸下降1、遞歸下降分析法的功能詞法分析器的功能是利用函數(shù)之間的遞歸調用模擬語法樹自上而下的構造過程。2、遞歸下降分析法實驗設計思想及算法為G的每個非終結符號U構造一個遞歸過程,不妨命名為U。U的產生式的右邊指出這個過程的代碼結構：(1)

2、若是終結符號，則和向前看符號對照，若匹配則向前進一個符號；否則出錯。(2)若是非終結符號，則調用與此非終結符對應的過程。當A的右部有多個產生式時,可用選擇結構實現(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如果xi為終結符號：if(xi= = 當前的

3、符號) NextChar()； return; else出錯處理如果xi為非終結符號，直接調用相應的過程xi()說明： NextChar為前進一個字符函數(shù)。BLL（1）分析法1、LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內容、向前看符號以及LL（1）分析表，對輸入符號串自上而下的分析過程。XVN#S進棧，當前輸入符送a上托棧頂符號放入X若產生式為X X1X2Xn按逆序即XnX2X1入棧出錯X=#XVTX=aMX,a是產生式嗎出錯X=a讀入下一個符號結束是是是是否否否否否是2、LL（1）分析法實驗設計思想及算法三、實驗過程和指導：（一）準備：1.閱讀課本有

4、關章節(jié)，2.考慮好設計方案；3.設計出模塊結構、測試數(shù)據(jù)，初步編制好程序。（二）上課上機：將源代碼拷貝到機上調試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調試通過。（三）程序要求：程序輸入/輸出示例：對下列文法，用兩種分析法對任意輸入的符號串進行分析：（1）E-TG（2）G-+TG （3）G-（4）T-FS（5）S-*FS（6）S-（7）F-(E)（8）F-i輸出的格式如下：(1)遞歸下降分析程序輸入一以#結束的符號串(包括+*/（）i#)：在此位置輸入符號串例如：i+i*i#輸出結果：i+i*i#為合法符號串備注：輸入一符號串如i+i*#,要求輸出為“非法的符號串”。(2)LL（1）分析：輸入一以#

5、結束的符號串(包括+*/（）i#)：在此位置輸入符號串例如：i+i*i#輸出結果：i+i*i#為合法符號串注意：1.表達式中允許使用運算符（+-*/）、分割符（括號）、字符I，結束符#；2.如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3.對學有余力的同學，可以詳細的輸出推導的過程，即詳細列出每一步使用的產生式。分析棧剩余輸入串所用產生式Ei+i*i#E-TG4.與讀文件有關的函數(shù)：FILE *fp; if(fp=fopen(E:222.txt,r)=NULL) /讀取文件內容，并返回文件指針，該指針指向文件的第一個字符fprintf(stderr,error opening.

6、n); exit(1); fgetc（fp） 從數(shù)據(jù)流中區(qū)下一個字符fopen 文件打開函數(shù)，返回指向文件第一個字符的指針（四）程序思路（僅供參考）：遞歸下降分析法：0.定義部分：定義常量、變量、數(shù)據(jù)結構。1.初始化：從文件將輸入符號串輸入到字符緩沖區(qū)中。2.利用遞歸下降分析法分析，對每個非終結符編寫函數(shù)，在主函數(shù)中調用文法開始符號的函數(shù)。LL（1）分析法：模塊結構：1、定義部分：定義常量、變量、數(shù)據(jù)結構。2、初始化：設立LL(1)分析表、初始化變量空間（包括堆棧、結構體等）；3、運行程序：讓程序分析一個text文件，判斷輸入的字符串是否符合文法定義的規(guī)則；4、利用LL(1)分析算法進行表達式

7、處理：根據(jù)LL(1)分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結果，如果遇到錯誤則顯示簡單的錯誤提示。部分代碼示例：#include#include#include#includestruct Stackchar s30;int top; /*棧頂指針 */S1;char v16=i,+,*,(,),#;/*終結符 */char v25=E,G,T,S,F;/*非終結符 */*用二維數(shù)組保存預測分析表，可用符號來代替，注意字符串結束位自動加0 */char table564=“TG”,”,”,”,”TG”,”,void print()/*輸出分析棧 */int a;/*指針*/for

8、(a=0;aS1.top;a+)coutS1.sa;coutendl;/*print*/void intialstack() S1.top=0;void push(char ch) S1.sS1.top=ch;S1.top+;char pop( ) S1.top-;return S1.sS1.top; void jinzhan(int hang,int lie) .int iszhongjie(char X ) ./*判斷X是否為終結符，返回下標*/bool chabiao(char X,char sym)/*判斷X是否為非終結符，sym是否為終結符，若是查找預測表對應表格是否為空白,是則出錯

9、，否則進棧*/void main() FILE *fp;char sym,X;bool flag,cuo; if(fp=fopen(E:222.txt,r)=NULL) /讀取文件內容，并返回文件指針，該指針指向文件的第一個字符fprintf(stderr,error opening.n); exit(1); initialstack();push(#);push(E);sym=fgetc(fp);/*把第一個輸入符號讀進sym*/flag=true;cuo=falsewhile (flag&!error) X=pop();if (X=#) .else if iszhongjie(X) els

10、e if(!chabiao(X,sym) cuo=true;（五）練習該實驗的目的和思路：需要利用程序設計語言的知識和大量編程技巧，通過這個練習可大大提高軟件開發(fā)能力。通過練習，掌握函數(shù)間相互調用的方法。（六）為了能設計好程序，注意以下事情：1.模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2.寫出（畫出）設計方案：模塊關系簡圖、流程圖、全局變量、函數(shù)接口等。3.編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。五、上交：實驗報告：實驗名稱實驗目的和要求（一）實驗內容（1）功能描述：該程序具有什么功能？（2）程序結構描述：函數(shù)調用格式、參數(shù)含義、返回值描述、函數(shù)

11、功能；函數(shù)之間的調用關系圖。（3）程序源代碼（二）實驗過程記錄：出錯次數(shù)、出錯嚴重程度、解決辦法摘要。（三）實驗總結：你在編程過程中花時多少？遇到了哪些難題？你是怎么克服的？你的收獲有哪些？自上而下分析算法#include#include#define ERROR 0 char sym; /用于臨時存儲文件中讀出的單個字符FILE *fp; /讀取文件的指針/非終結符定義的方法 void e();void g();void t();void s();void f();/讀取文件中的下一個字符void advance();void main() if(fp=fopen(E:222.txt,r)=

12、NULL)/讀取文件內容，并返回文件指針，該指針指向文件的第一個字符 fprintf(stderr,error opening.n); exit(1); e();/對應產生式（1）E-TGvoid e()advance();t();g();if(sym=#)printf(輸入的為合法的字符串n);else printf(非法字符串);/對應產生式（2）G-+TG （3）G- 空 ：不做任何處理void g()if(sym =+)printf(+);advance(); t();g();/對應產生式 （4）T-FSvoid t()f();s();/ 對應產生式（5）S-*FS （6）S-void

13、 s()if(sym=*)printf(*);advance();f();s();/對應產生式（7）F-(E) （8）F-ivoid f()if(sym=()advance();e(); if(sym=) advance(); else printf(非法字符串); exit(ERROR); else if(sym=i) printf(i);advance();else printf(非法字符串);exit(ERROR);void advance()sym=fgetc(fp);/ 從數(shù)據(jù)流中區(qū)下一個字符預測表分析法#include#include#include#includestruct S

14、tackchar s30;int top; /*棧頂指針 */S1;int num=0;char v16=i,+,*,(,),#;/*終結符 */char v25=E,G,T,S,F;/*非終結符 */*用二維數(shù)組保存預測分析表，可用符號來代替，注意字符串結束位自動加0 */char table564=GT,GT,GT+,SF,SF,SF*,i,)E(,;void print()/*輸出分析棧 */int a;/*指針*/for(a=0;aS1.top;a+)printf(%c,S1.sa);printf(t);/*print*/void intialstack() S1.top=0;/*初始

15、化棧*/void push(char ch) S1.sS1.top=ch;S1.top+;/*壓棧*/char pop( ) S1.top-;return S1.sS1.top; /*出棧*/void jinzhan(int hang,int lie) char *chuan;chuan=tablehanglie;chuan3=0;int i=0;while(chuani!=NULL&chuan0!=) push(chuani);i+;/*進棧操作，將符號串數(shù)組壓入棧中*/int iszhongjie(char X )for(int i=0;i6;i+)if(X=v1i)return i;re

16、turn -1;/*判斷X是否為終結符，返回下標*/int isfzhongjie(char X )for(int i=0;i,X);for(int i=(strlen(tablehanglie)-1);i=0;i-)printf(%c,tablehangliei);printf(n); jinzhan(hang,lie); return true;else printf(錯誤n);return false;/*判斷X是否為非終結符，sym是否為終結符，若是查找預測表對應表格是否為空白,是則出錯，否則進棧*/void shuchuchuan()FILE *fp1;char c;int num1

17、=0; if(fp1=fopen(E:222.txt,r)=NULL) /讀取文件內容，并返回文件指針，該指針指向文件的第一個字符fprintf(stderr,error opening.n); exit(1); c=fgetc(fp1);while(c!=#)if(num1=num)printf(%c,c);elseprintf( );c=fgetc(fp1);num1+;printf(#t);void main() FILE *fp;char sym,X;bool flag,cuo; if(fp=fopen(E:222.txt,r)=NULL) /讀取文件內容，并返回文件指針，該指針指向文件的第一個字符fprintf(stderr,error opening.n); exit(1); intialstack();push(#);push(E);sym=fgetc(fp);/*把第一個輸入