編譯原理語法分析實驗報告.doc

《編譯原理語法分析實驗報告.doc》由會員分享，可在線閱讀，更多相關(guān)《編譯原理語法分析實驗報告.doc（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

南華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院 實 驗 報 告 （ 2007 ~2008 學(xué)年度 第二學(xué)期 ） 課程名稱 編譯原理 實驗名稱 語法分析 姓名 尋友旭 學(xué)號 20054350227 專業(yè) 軟件工程 班級 軟件工程052班 地點 6—413 教師 陳星 1.實驗?zāi)康募耙? 編制一個遞歸下降分析程序，實現(xiàn)對詞法分析程序所提供得單詞序列得語法檢查和結(jié)構(gòu)分析。 軟件、硬件環(huán)境 VC6.0 要求： 利用C語言編制遞歸下降分析程序，并對簡單語言進(jìn)行語法分析。 待分析的簡單語言得語法： EE+T | E-T | T TT*F | T/F |F F(E) | i 輸入單詞串，以“#”結(jié)束，如果是文法正確的句子，則輸出成功信息，打印“Accept! Right Expression!”，否則輸出“Error!!!”。 語法分析： a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左遞歸。用直接改寫法消除左遞歸，得到如下： E TE’ E’ +TE’ | ?TE’|ε T FT’ T’ *FT’ | /FT’|ε F (E) | i b) 對于以上改進(jìn)的方法?？傻茫? 對于E’: FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε} 對于T’: FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε} 而且： FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪FIRST(i)={(，i } 由此我們?nèi)菀椎贸龈鞣墙K結(jié)符的FOLLOW集合如下： FOLLOW( E )= { )，#} FOLLOW(E’)= FOLLOW(E)={ )，#} FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#} FOLLOW( T’ ) = FOLLOW( T ) ={+，?，)，#} FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#} 由以上FOLLOW集可以我們可以得出SELECT集如下： 對E SELECT（ETE’）=FIRST(TE’)=FIRST(T)={ (，i } 對E’ SELECT（E’ +TE’）={ + } SELECT（E’ ?TE’）={ ? } SELECT（E’ ε）={ε，)，#} 對T SELECT（TFT’）={(，i} 對T’ SELECT（T’ *FT’）={ * } SELECT（T’ ∕FT’）={ ∕ } SELECT（T’ ε）={ε，+，?，)，#} 對F SELECT（F(E) ）={ ( } SELECT（Fi）={ i } ∴ SELECT(E’ +TE’)∩SELECT（E’ ?TE’）∩SELECT（E’ ε）=F SELECT(T’ *FT’)∩SELECT（T’ ∕FT’）∩SELECT（T’ ε）=F SELECT（F(E) ）∩SELECT（Fi）= F 由上可知，有相同左部產(chǎn)生式的SELECT集合的交集為空，所以文法是LL（1）文法。因此，轉(zhuǎn)化后的文法可以用遞歸下降分析法作語法分析。 2.實驗步驟 1、 分析試驗資料，結(jié)合書本得出實驗大體思路； 2、 根據(jù)資料畫出語法分析程序的流程圖； 3、 根據(jù)流程圖與程序大體框架完善程序； 4、 將代碼輸入電腦中，調(diào)試； 5、 根據(jù)資料中數(shù)據(jù)測試程序得基本功能； 6、 根據(jù)測試結(jié)果，設(shè)計測試數(shù)據(jù)完善程序； 7、 根據(jù)實驗結(jié)果分析總結(jié)。 3. 實驗內(nèi)容 詞法分析程序的主要子函數(shù)模塊流程圖 \ 程序： #include #include #include #include char a[50] ,b[50],d[200],e[10]; char ch; int n1,i1=0,flag=1,n=5; int total=0; int E(); int E1(); int T(); int G(); int S(); int F(); void input(); void input1(); void output(); void main() /*遞歸分析*/ { int f,p,j=0; char x; d[0]=E; d[1]==; d[2]=>; d[3]=T; d[4]=G; d[5]=#; printf("Please input character string(length<50,end of #):\n"); do{ scanf("%c",&ch); a[j]=ch; j++; }while(ch!=#); n1=j; ch=b[0]=a[0]; printf("步驟\t文法\t分析串\t\t分析字符\t剩余串\n"); f=E1(); if (f==0) return; if (ch==#) { printf("\nAccept! Right Expression!\n\n"); p=0; x=d[p]; while(x!=#) { printf("%c",x);p=p+1;x=d[p]; /*輸出推導(dǎo)式*/ } } else { printf("\nError!!!\n"); printf("回車返回\n"); getchar();getchar(); return; } printf("\n"); printf("回車返回\n"); getchar(); getchar(); } int E1() { int f,t; printf("%d\tE-->TG\t",total);total++; flag=1; input(); input1(); f=T(); if (f==0) return(0); t=G(); if (t==0) return(0); else return(1); } int E() { int f,t; printf("%d\tE-->TG\t",total);total++; e[0]=E;e[1]==;e[2]=>;e[3]=T;e[4]=G;e[5]=#; output(); flag=1; input(); input1(); f=T(); if (f==0) return(0); t=G(); if (t==0) return(0); else return(1); int T() { int f,t; printf("%d\tT-->FS\t",total);total++; e[0]=T;e[1]==;e[2]=>;e[3]=F;e[4]=S;e[5]=#; output(); flag=1; input(); input1(); f=F(); if (f==0) return(0); t=S(); if (t==0) return(0); else return(1); } int G() { int f; if(ch==+) { b[i1]=ch; printf("%d\tG-->+TG\t",total);total++; e[0]=G;e[1]==;e[2]=>;e[3]=+;e[4]=T;e[5]=G;e[6]=#; output(); flag=0; input(); input1(); ch=a[++i1]; f=T(); if (f==0) return(0); G(); return(1); } printf("%d\tG-->^\t",total);total++; e[0]=G;e[1]==;e[2]=>;e[3]=^;e[4]=#; output(); flag=1; input();input1(); return(1); } int S() { int f,t; if(ch==*) { b[i1]=ch;printf("%d\tS-->*FS\t",total);total++; e[0]=S;e[1]==;e[2]=>;e[3]=*;e[4]=F;e[5]=S;e[6]=#; output(); flag=0; input();input1(); ch=a[++i1]; f=F(); if (f==0) return(0); t=S(); if (t==0) return(0); else return(1);} printf("%d\tS-->^\t",total);total++; e[0]=S;e[1]==;e[2]=>;e[3]=^;e[4]=#; output(); flag=1; a[i1]=ch; input(); input1(); return(1); } int F() { int f; if(ch==() { b[i1]=ch;printf("%d\tF-->(E)\t",total);total++; e[0]=F;e[1]==;e[2]=>;e[3]=(;e[4]=E;e[5]=);e[6]=#; output(); flag=0; input(); input1(); ch=a[++i1]; f=E(); if (f==0) return(0); if(ch==)) { b[i1]=ch;printf("%d\tF-->(E)\t",total);total++; flag=0;input();input1(); ch=a[++i1]; } else { printf("\nError!!!\n"); return(0); } } else if(ch==i) { b[i1]=ch;printf("%d\tF-->i\t",total);total++; e[0]=F;e[1]==;e[2]=>;e[3]=i;e[4]=#; output(); flag=0;input();input1(); ch=a[++i1]; } else {printf("\nError!!!\n");return(0);} return(1); } void input() { int j=0; for (;j<=i1-flag;j++) printf("%c",b[j]); /*輸出分析串*/ printf("\t\t"); printf("%c\t\t",ch); /*輸出分析字符*/ } void input1() { int j; for (j=i1+1-flag;j;d[n+2]=#;n=n+2;i=n; i=i-2; while(d[i]!=>&&i!=0) i=i-1; i=i+1; while(d[i]!=e[0]) i=i+1; q=i; m=q;k=q; while(d[m]!=>) m=m-1; m=m+1; while(m!=q) { d[n]=d[m];m=m+1;n=n+1; } d[n]=#; for(j=3;e[j]!=#;j++){ d[n]=e[j]; n=n+1; } k=k+1; while(d[k]!==) { d[n]=d[k];n=n+1;k=k+1; } d[n]=#; } 4.實驗結(jié)果 5. 實驗總結(jié)分析 通過這次實驗，我對語法分析有了更深刻的了解，對它的形成有了更清楚得認(rèn)識。本次實驗我主要是基于試驗資料上的程序流程圖和程序框架完成的。由一個簡單一些的產(chǎn)生式得出程序的各個分函數(shù)。 此次所編寫的語法分析程序是遞歸下降語法分析分析器，通過分析文法產(chǎn)生式得FFIRST、FOLLOW和SELECT集合來判斷LL（1）方法，然后用遞歸下降語法分析法分析LL（1）方法得基本遞歸流，用C語言編程實現(xiàn)分析器。 本次所寫的語法分析器過于簡單，相信以后會再接再厲寫出更復(fù)雜，更好的分析器來。