自上而下語法實驗

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

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

3、是否否否否否是三、程序設(shè)計的過程以及關(guān)鍵函數(shù)的功能（一）模塊結(jié)構(gòu)：1、定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。2、初始化：設(shè)立LL(1)分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體等）；3、運行程序：讓程序分析一個text文件，判斷輸入的字符串是否符合文法定義的規(guī)則；4、利用LL(1)分析算法進行表達式處理：根據(jù)LL(1)分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示簡單的錯誤提示。（二）程序的整體流程及關(guān)鍵函數(shù)解析：1、定義一個棧，用于存放非終結(jié)符2、 將終結(jié)符和非終結(jié)符各存放在一個數(shù)組中，用于判斷棧頂元素是否是終結(jié)符或非終結(jié)符，然后根據(jù)情況判斷接下來是查表，還是進行匹

4、配移進。3、 定義一個全局變量f，用于指示從文件中讀出的匹配后的剩余字符串中的首個字符在數(shù)組中的位置。當輸出棧時，同時輸出剩余字符串。4、對于chaxun( )函數(shù)，X在 v25中的位置相當于表的行位置，sym在v16中的位置，相當于表的列位置。根據(jù)查表操作可以判斷（X，sym）對于的表中是否有產(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)生式，對棧頂元素根據(jù)情況進行移進匹配操作，知道剩余表達式中無非終結(jié)符為止，即匹配成功。否則，則匹配失敗，給出的字符表達式無法由給定的文法推出。while (flag&&!cuo) X=pop();

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

7、顯示如下：若輸入i*(i+i)，顯示如下：五、實驗總結(jié) 通過本次實驗，我初步掌握了ll（1）文法，在寫代碼的過程中也加深了我對棧的理解，老師課上已經(jīng)講解了許多，而且實驗時也指導(dǎo)了我們一些該注意的地方，中間還是有一些小問題但是，在判斷輸入串是否匹配的時候，還是有些問題，不過總體目標還是完成了，當然問題最多的還是棧頂元素與剩余字符串的移進匹配過程，這一點我老是搞不太清楚。不過在同學的幫助和指導(dǎo)下這些問題都慢慢的解決了。不過總體來說，使我的編程能力得到了很大的提高。附錄:#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ù)測分析表，可用符號來代替，注意字符串結(jié)束位自動加'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é)符，是返回數(shù)組下標int feizhongjie(char f )for(int k=0;k<5;k+)if (f=v2k) return k; return -1;/判斷X是否為非終結(jié)符，是返回數(shù)組下標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<<"匹配失?。?quot;<<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ù)測表對應(yīng)表格是否為空白,是則出錯，否則進棧*/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)容，并返回文件指針，該指針指向文件的第一個字符 fprintf(stderr,"讀取文件失敗!n"); exit(1); intialstack();push('#');push('E');sym=fgetc(fp);/把第一個輸入符號讀進symflag=true;cuo=false;print();cout<<endl;while (flag&&!cuo)