自上而下語(yǔ)法實(shí)驗(yàn)

1、自上而下語(yǔ)法分析1、 實(shí)驗(yàn)?zāi)康模?.根據(jù)某一文法編制調(diào)試遞歸下降分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。（選做）2.根據(jù)某一文法編制調(diào)試LL（1）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。（必做）2、 本次實(shí)驗(yàn)的目的主要是加深對(duì)自上而下分析法的理解。實(shí)驗(yàn)內(nèi)容：（1） 程序的功能描述LL（1）分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL（1）分析表，對(duì)輸入符號(hào)串自上而下的分析過(guò)程。具體描述如下： 對(duì)下列文法，對(duì)任意輸入的符號(hào)串進(jìn)行分析：（1）E->TG（2）G->+TG （3）G->（4）T->FS（5）S->*FS（6）S->

2、（7）F->(E)（8）F->i輸入一以#結(jié)束的符號(hào)串(包括+*/（）i#)：輸出結(jié)果：包括分析棧、數(shù)組中的剩余字符串以及所用的產(chǎn)生式，形如：分析棧剩余輸入串所用產(chǎn)生式Ei+i*i#E->TG其中有如下兩點(diǎn)要求：1.表達(dá)式中允許使用運(yùn)算符（+-*/）、分割符（括號(hào)）、字符I，結(jié)束符#；2.如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息（該信息越詳細(xì)越好）；（二）LL（1）分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法XVN#S進(jìn)棧，當(dāng)前輸入符送sym上托棧頂符號(hào)放入X若產(chǎn)生式為X® X1X2Xn按逆序即XnX2X1入棧出錯(cuò)X=#XVTX=aMX,sym是產(chǎn)生式嗎出錯(cuò)X=讀入下一個(gè)符號(hào)結(jié)束是是是

3、是否否否否否是三、程序設(shè)計(jì)的過(guò)程以及關(guān)鍵函數(shù)的功能（一）模塊結(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)分析表對(duì)表達(dá)式符號(hào)串進(jìn)行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯(cuò)誤則顯示簡(jiǎn)單的錯(cuò)誤提示。（二）程序的整體流程及關(guān)鍵函數(shù)解析：1、定義一個(gè)棧，用于存放非終結(jié)符2、 將終結(jié)符和非終結(jié)符各存放在一個(gè)數(shù)組中，用于判斷棧頂元素是否是終結(jié)符或非終結(jié)符，然后根據(jù)情況判斷接下來(lái)是查表，還是進(jìn)行匹

4、配移進(jìn)。3、 定義一個(gè)全局變量f，用于指示從文件中讀出的匹配后的剩余字符串中的首個(gè)字符在數(shù)組中的位置。當(dāng)輸出棧時(shí)，同時(shí)輸出剩余字符串。4、對(duì)于chaxun( )函數(shù)，X在 v25中的位置相當(dāng)于表的行位置，sym在v16中的位置，相當(dāng)于表的列位置。根據(jù)查表操作可以判斷（X，sym）對(duì)于的表中是否有產(chǎn)生式。bool chaxun(char X,char sym)int m=feizhongjie(X );int n=iszhongjie(sym);char str10; strcpy(str,tablemn);if (strlen(str)=0)return false;elseif (str0!

5、='')for (int i=strlen(str)-1;i>=0;i-) push(stri);print();cout<<'t'<<v2m<<"->"<<str<<endl;return true;5、 讀文件，并將文件里的內(nèi)容讀入數(shù)組b 中。6、根據(jù)表中的產(chǎn)生式，對(duì)棧頂元素根據(jù)情況進(jìn)行移進(jìn)匹配操作，知道剩余表達(dá)式中無(wú)非終結(jié)符為止，即匹配成功。否則，則匹配失敗，給出的字符表達(dá)式無(wú)法由給定的文法推出。while (flag&&!cuo) X=pop();

6、/把符號(hào)棧的式子付給xif (X='#') if(sym=X)cout<<"輸入的是合法符號(hào)串"<<endl;flag=false;elsecout<<"非法的符號(hào)串"<<endl;else if(iszhongjie(X)!=-1) /如果是終結(jié)符跳到if if(X=sym) f+; sym=fgetc(fp); else printf("錯(cuò)誤"); else if(!chaxun(X,sym) cuo=true;四、運(yùn)行結(jié)果：輸入文件內(nèi)容：i+i*i若輸入i+i*i，

7、顯示如下：若輸入i*(i+i)，顯示如下：五、實(shí)驗(yàn)總結(jié) 通過(guò)本次實(shí)驗(yàn)，我初步掌握了ll（1）文法，在寫代碼的過(guò)程中也加深了我對(duì)棧的理解，老師課上已經(jīng)講解了許多，而且實(shí)驗(yàn)時(shí)也指導(dǎo)了我們一些該注意的地方，中間還是有一些小問(wèn)題但是，在判斷輸入串是否匹配的時(shí)候，還是有些問(wèn)題，不過(guò)總體目標(biāo)還是完成了，當(dāng)然問(wèn)題最多的還是棧頂元素與剩余字符串的移進(jìn)匹配過(guò)程，這一點(diǎn)我老是搞不太清楚。不過(guò)在同學(xué)的幫助和指導(dǎo)下這些問(wèn)題都慢慢的解決了。不過(guò)總體來(lái)說(shuō)，使我的編程能力得到了很大的提高。附錄:#include<iostream.h>#include<stdio.h>#include<stdl

8、ib.h>#include<string.h>#include<dos.h>#include <fstream.h>#define error 0struct Stackchar s30;int top; /棧頂指針S1;int f=0;char b20;char v16='i','+','*','(',')','#'/終結(jié)符char v25='E','G','T','S','F'

9、;/非終結(jié)符 /*用二維數(shù)組保存預(yù)測(cè)分析表，可用符號(hào)來(lái)代替，注意字符串結(jié)束位自動(dòng)加'0' */char table564="TG"," "," ","TG"," "," "," ","+TG"," "," ","","","FS"," "," ","FS",&qu

10、ot; "," "," ","","*FS"," ","","","i"," "," ","(E)"," "," "void printbiao()cout<<"TG TG "<<endl; cout<<" +TG "<<endl; cout

11、<<"FS FS "<<endl; cout<<" *FS "<<endl; cout<<"i (E) "<<endl;void print()/*輸出分析棧 */int a;/*指針*/for(a=0;a<S1.top;a+)cout<<S1.sa;cout<<'t'int len=strlen(b);for(int n=f;n<len;n+)cout<<bn;/*print*/void intia

12、lstack() S1.top=0;void push(char ch) S1.sS1.top=ch;S1.top+;char pop( ) S1.top-;return S1.sS1.top; int iszhongjie(char X )for(int k=0;k<6;k+)if (X=v1k) return k; return -1;/判斷X是否為終結(jié)符，是返回?cái)?shù)組下標(biāo)int feizhongjie(char f )for(int k=0;k<5;k+)if (f=v2k) return k; return -1;/判斷X是否為非終結(jié)符，是返回?cái)?shù)組下標(biāo)bool chabiao

13、(char X,char sym)int m=feizhongjie(X );int n=iszhongjie(sym);char str10; strcpy(str,tablemn);if (strlen(str)=0)/cout<<"匹配失??！"<<endl;return false;elseif (str0!='')for (int i=strlen(str)-1;i>=0;i-) push(stri);print();cout<<'t'<<v2m<<"->

14、;"<<str<<endl;return true;/*判斷X是否為非終結(jié)符，sym是否為終結(jié)符，若是查找預(yù)測(cè)表對(duì)應(yīng)表格是否為空白,是則出錯(cuò)，否則進(jìn)棧*/void main() printbiao();ifstream file("d:111.txt");file.getline(b,sizeof file);FILE *fp; char sym,X; bool flag,cuo; if(fp=fopen("D:111.txt","r")=NULL) /讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個(gè)字符 fprintf(stderr,"讀取文件失敗!n"); exit(1); intialstack();push('#');push('E');sym=fgetc(fp);/把第一個(gè)輸入符號(hào)讀進(jìn)symflag=true;cuo=false;print();cout<<endl;while (flag&&!cuo)