編譯原理語法試驗(yàn)

1、實(shí)驗(yàn)二：自上而下語法分析、實(shí)驗(yàn)?zāi)康模焊鶕?jù)某一文法編制調(diào)試遞歸下降分析程序，以便對任意輸入的符號串進(jìn)行分析。根據(jù)某一文法編制調(diào)試 LL (1)分析程序，以便對任意輸入的符號串進(jìn)行分析。 本次實(shí)驗(yàn)的目的主要是加深對自上而下分析法的理解。、實(shí)驗(yàn)預(yù)習(xí)提示自下而上分析法的前提改造文法：消除二義性、消除左遞歸、提取左因子，判斷是否為LL (1)文法A 遞歸下降1、遞歸下降分析法的功能詞法分析器的功能是利用函數(shù)之間的遞歸調(diào)用模擬語法樹自上而下的構(gòu)造過程。2、遞歸下降分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法為 G 的每個(gè)非終結(jié)符號 U 構(gòu)造一個(gè)遞歸過程 ,不妨命名為 U。U 的產(chǎn)生式的右邊指出這個(gè)過程的代碼結(jié)構(gòu)：(1) 若是

2、終結(jié)符號，則和向前看符號對照，,可用選擇結(jié)構(gòu)實(shí)若匹配則向前進(jìn)一個(gè)符號；否則出錯(cuò)。(2) 若是非終結(jié)符號，則調(diào)用與此非終結(jié)符對應(yīng)的過程。當(dāng)A 的右部有多個(gè)產(chǎn)生式時(shí)現(xiàn)。具體為：(1)對于每個(gè)非終結(jié)符號 U->u1|u2|un處理的方法如下：U( )ch= 當(dāng)前符號 ;if(ch 可能是 u1 字的開頭 ) 處理 u1 的程序部分 ;else if(ch 可能是 u2 字的開頭 )處理 u2 的程序部分 ;else error()(2)對于每個(gè)右部Ul->XiX2xn的處理架構(gòu)如下: 處理 x1 的程序；處理 X2 的程序；J處理xn的程序；( 3)如果右部為空，則不處理。( 4)對于右

3、部中的每個(gè)符號Xi如果 Xi 為終結(jié)符號：if(Xi= = 當(dāng)前的符號 )NeXtChar() ； return;else出錯(cuò)處理如果xi為非終結(jié)符號，直接調(diào)用相應(yīng)的過程xi()說明：NextChar為前進(jìn)一個(gè)字符函數(shù)。B LL (1)分析法1、LL (1)分析法的功能LL (1)分析法的功能是利用LL (1 )控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號以及LL (1)分析表，對輸入符號串自上而下的分析過程。1閱讀課本有關(guān)章節(jié)，2考慮好設(shè)計(jì)方案；3設(shè)計(jì)出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初步編制好程序。(二) 上課上機(jī)：將源代碼拷貝到機(jī)上調(diào)試，發(fā)現(xiàn)錯(cuò)誤，再修改完善。第二次上機(jī)調(diào)試通過。(三) 程序要求：程序輸入

4、/輸出示例：對下列文法，用兩種分析法對任意輸入的符號串進(jìn)行分析：(1) E->TG(2) G->+TG(3) G-> &(4) T->FS(5) S->*FS(6) S-> s(7) F->(E)(8) F->i輸出的格式如下：(1) 遞歸下降分析程序輸入一以#結(jié)束的符號串(包括+*/ () i#):在此位置輸入符號串例如：i+i*i#輸出結(jié)果：匡匣為合法符號串備注：輸入一符號串如i+i*#,要求輸出為“非法的符號串”。(2) LL ( 1)分析:輸入一以#結(jié)束的符號串(包括+*/()i#):在此位置輸入符號串例如：i+i*i#輸出結(jié)果：

5、為合法符號串1表達(dá)式中允許使用運(yùn)算符(+-*/)、分割符(括號)、字符I，結(jié)束符# ；2如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息(該信息越詳細(xì)越好)；3對學(xué)有余力的同學(xué)，可以詳細(xì)的輸出推導(dǎo)的過程，即詳細(xì)列出每一步使用的產(chǎn)生式。分析棧剩余輸入串所用產(chǎn)生式Ei+i*i#E->TG4與讀文件有關(guān)的函數(shù)：FILE *fp;if(fp=fope n( "E:222.txt","門)=NULL)/讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個(gè)字符fprin tf(stderr,"error ope nin g.n");exit(1);fgetc

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

7、析表對表達(dá)式符號串進(jìn)行堆棧(或其他)操作，輸 出分析結(jié)果，如果遇到錯(cuò)誤則顯示簡單的錯(cuò)誤提示。部分代碼示例：#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>#in clude<dos.h>struct Stackchar s30;int top; /* 棧頂指針 */S1;char v16='i','+','*','(',')','#'/* 終結(jié)符 */char v25='E

8、9;,'G','T','S','F'/* 非終結(jié)符 */*用二維數(shù)組保存預(yù)測分析表，可用符號A來代替£，注意字符串結(jié)束位自動加'0'*/char table564=“TG”, ”, ”,”, ”TG”, ”, , , , , , , , void print()/* 輸出分析棧 */int a;/* 指針 */for(a=0;a<S1.top;a+)cout<<S1.sa;cout<<endl;/*print*/void intialstack() S1.top=0;void

9、 push(char ch) S1.sS1.top=ch;S1.top+;char pop( )S1.top-;return S1.sS1.top; voidjin zha n(i nt han g,i nt lie) .intiszhongjie(char X )./*判斷X是否為終結(jié)符，返回下標(biāo) */bool chabiao(char X,char sym) /*判斷 X 是否為非終結(jié)符， sym 是否為終結(jié)符，若是查找預(yù)測表對應(yīng)表格是否為空白 ,是則出錯(cuò)，否則進(jìn)棧*/void main()FILE *fp;char sym,X;bool flag,cuo;if(fp=fopen(&quo

10、t;E:222.txt","r")=NULL)/讀取文件內(nèi)容， 并返回文件指針， 該指針指向文件的第一個(gè)字符fprintf(stderr,"error opening.n");exit(1);initialstack();push('#');push('E');sym=fgetc(fp);/* 把第一個(gè)輸入符號讀進(jìn) sym*/flag=true;cuo=falsewhile (flag&&!error) X=pop();if (X= '#') .else if iszhongjie

11、(X) else if(!chabiao(X,sym) cuo=true;(五) 練習(xí)該實(shí)驗(yàn)的目的和思路： 需要利用程序設(shè)計(jì)語言的知識和大量編程技巧，通過這個(gè)練習(xí)可大大提高軟件開發(fā)能力。通過練習(xí)， 掌握函數(shù)間相互調(diào)用的方法。(六) 為了能設(shè)計(jì)好程序，注意以下事情：1.模塊設(shè)計(jì)：將程序分成合理的多個(gè)模塊(函數(shù))，每個(gè)模塊做具體的同一事情。2.寫出(畫出)設(shè)計(jì)方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3. 編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。五、上交：實(shí)驗(yàn)報(bào)告：實(shí)驗(yàn)名稱實(shí)驗(yàn)?zāi)康暮鸵?一) 實(shí)驗(yàn)內(nèi)容(1)功能描述：該程序具有什么功能？ (2)程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式

12、、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。(3) 程序源代碼(二) 實(shí)驗(yàn)過程記錄：出錯(cuò)次數(shù)、出錯(cuò)嚴(yán)重程度、解決辦法摘要。(三) 實(shí)驗(yàn)總結(jié)：你在編程過程中花時(shí)多少？遇到了哪些難題？你是怎么克服的？你的收獲有哪些？自上而下分析算法#include<stdio.h>#include<stdlib.h>#define ERROR 0char sym; /用于臨時(shí)存儲文件中讀出的單個(gè)字符FILE *fp; /讀取文件的指針/非終結(jié)符定義的方法void e();void g();void t();void s();void f();/讀取文件中的下一個(gè)字符void a

13、dvance();void main()if(fp=fopen("E:222.txt","r")=NULL)/ 讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個(gè) 字符fprintf(stderr,"error opening.n");exit(1); e();/對應(yīng)產(chǎn)生式( 1)E->TG void e() advance(); t(); g(); if(sym='#')printf(" 輸入的為合法的字符串 n");else printf(" 非法字符串 ");：不做

14、任何處理/對應(yīng)產(chǎn)生式(2) G->+TG(3) G-> & 空void g()if(sym ='+') printf("+"); advance();t(); g(); /對應(yīng)產(chǎn)生式( 4) T->FSvoid t()f();s();/ 對應(yīng)產(chǎn)生式( 5) S->*FS( 6) S->&void s() if(sym='*') printf("*"); advance(); f(); s();/對應(yīng)產(chǎn)生式（ 7） F->（E） （ 8） F->i void f()

15、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ū)下一個(gè)字符 預(yù)測表分析法#include<stdio.h>#include<std

16、lib.h>#include<string.h>#include<dos.h>struct Stackchar s30;int top; /* 棧頂指針*/S1;int num=0;char v16='i','+','*','(',')','#'/* 終結(jié)符 */char v25='E','G','T','S','F'/* 非終結(jié)符 */*用二維數(shù)組保存預(yù)測分析表，可用符號 A來代替

17、3;，注意字符串結(jié)束位自動加'0'*/char","","",")E(","","table564="GT","","","GT","","","","GT+","","","A","A","SF",""

18、,"","SF","","","","A","SF*","","A","A ","i void print()/* 輸出分析棧 */ int a;/* 指針 */ for(a=0;a<S1.top;a+) printf("%c",S1.sa);printf("t");/*print*/ void intialstack()S1.top=0;/

19、* 初始化棧 */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!='A') push(chuani);i+;/* 進(jìn)棧操作，將符號串?dāng)?shù)組壓入棧中 */ int iszhongjie(char X )

20、for(int i=0;i<6;i+) if(X=v1i) return i;return -1;/* 判斷 X 是否為終結(jié)符，返回下標(biāo) */ int isfzhongjie(char X )for(int i=0;i<5;i+) if(X=v2i) return i;return -1;/* 判斷 X 是否為非終結(jié)符，返回下標(biāo) */ bool chabiao(char X,char sym)int hang=isfzhongjie(X);int lie=iszhongjie(sym); if(hang!=-1&&lie!=-1) if(sym!='A

21、9;) printf("%c->",X);for(int i=(strlen(tablehanglie)-1);i>=0;i-) printf("%c",tablehangliei); printf("n"); jinzhan(hang,lie); return true;elseprintf(" 錯(cuò)誤 n"); return false; /*判斷X是否為非終結(jié)符，sym是否為終結(jié)符，若是查找預(yù)測表對應(yīng)表格是否為空白，是則出錯(cuò)，否則進(jìn)棧*/void shuchuchuan()FILE *fp1;char c;int num1=0;if(fp1=fopen("E:222.txt","r")=NULL)/ 讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個(gè)字符fprintf(stderr,"error opening.n");exit(1);c=fgetc(fp1);while(c!='#')if(