中北大學軟件學院

　實 驗 報 告

　 專

　業

　 課程名稱

　 學

　號

　姓

　名

　輔導教師

　 成績

　 實驗日期 2014.12.03 實驗時間

　10:00—11：30 1、實驗名稱

　語法分析器的設計與實現

　2、實驗目的 掌握自上而下語法分析方法、自下而上語法分析方法

　3、實驗要求 (1)實驗內容：四選一

　① 設計及實現能夠識別表達式的預測分析程序。

　文法如下：

　G[E]：E->E+T|T

　T->T*F|F

　F->(E)|i

　② 設計及實現能夠識別表達式的 LR分析程序。

　 文法如下：

　G[E]：E->E+T|T

　 T->T*F|F

　 F->(E)|i

　③

　設計及實現能夠識別表達式的算符優先分析程序。

　 文法如下：

　G[E]：E->E+T|T

　 T->T*F|F

　 F->P↑F|P

　 P->(E)|i

　 ④設計及實現計算表達式的計算器。

　表達式中可包含+、-、*、/、（、）運算符。

　(2)實驗要求：

　對已給的一個二元式形式表達式，能夠檢查有無語法錯誤。并指定出錯位置。

　將表達式的語法樹輸出（或將語法分析過程輸出）。

　4、實驗原理 根據自上而下和自下而上的語法分析思想實現語法分析程序。

　5、實驗步驟 (1)根據文法構造語法分析表。

　(2)編寫總控程序實現語法分析。

　6、狀態轉換圖及詞法分析程序

　（1）狀態轉換圖

　 否

　 （2）語法分析器源代碼

　#include<stdio.h>

　#include<string.h>

　char *action[12][6]={"S5#",NULL,NULL,"S4#",NULL,NULL,

　 /*ACTION 表*/

　NULL,"S6#",NULL,NULL,NULL,"acc",

　LL(1) 文報錯判 斷有結讀入文法開 始

　NULL,"r2#","S7#", NULL,"r2#","r2#",

　NULL,"r4#","r4#", NULL,"r4#","r4#",

　"S5#",NULL,NULL, "S4#",NULL,NULL,

　NULL,"r6#","r6#", NULL,"r6#","r6#",

　"S5#",NULL,NULL, "S4#",NULL,NULL,

　"S5#",NULL,NULL, "S4#",NULL,NULL,

　NULL,"S6#",NULL, NULL,"S11#",NULL,

　NULL,"r1#","S7#", NULL,"r1#","r1#",

　NULL,"r3#","r3#", NULL,"r3#","r3#",

　NULL,"r5#","r5#", NULL,"r5#","r5#"};

　int goto1[12][3]={1,2,3,

　 /*QOTO 表*/

　0,0,0,

　0,0,0,

　0,0,0,

　8,2,3,

　0,0,0,

　0,9,3,

　0,0,10,

　0,0,0,

　0,0,0,

　0,0,0,

　0,0,0};

　char vt[6]={"i","+","*","(",")","#"};

　/*存放終結符*/

　char vn[3]={"E","T","F"};

　 /*存放非終結符*/

　char*LR[7]={"M->E#","E->E+T#","E->T#","T->T*F#","T->F#","F->(E)#","F->i#"};

　/*存放產生式*/

　int a[20];//數組 a 實現狀態棧

　char b[20],c[20],c1;//數組 b 實現符號棧，數組 c 存放輸入的字符串

　int top1,top2,top3,top,m,n;

　int main()

　{

　int g,h,i,j,k,l,p,y,z,count;

　char x,copy[20],copy1[20];

　top1=0;top2=0;top3=0;top=0;

　a[0]=0;y=a[0];b[0]="#";

　count=0;z=0;

　//輸入要識別的字符串

　printf("請輸入表達式\n");

　do{

　scanf("%c",&c1);

　c[top3]=c1;

　//字符數組 c[10]存放輸入的字符串

　top3=top3+1;//最后 top3=5

　}while(c1!="#");

　//輸出分析結果

　printf("步驟\t 狀態棧\t\t 符號棧\t\t 輸入串\t\tACTION\tGOTO\n");

　do{

　y=z;m=0;n=0;

　/*y,z 指向狀態棧棧頂*/

　g=top;j=0;k=0;

　x=c[top];

　//將輸入符號賦給 x

　count++;

　printf("%d\t",count);//輸出步驟序號

　while(m<=top1)

　{

　/*輸出狀態棧*/

　printf("%d",a[m]);

　m=m+1;

　}

　printf("\t\t");

　while(n<=top2)

　{

　/*輸出符號棧*/

　printf("%c",b[n]);

　n=n+1;

　}

　printf("\t\t");

　while(g<=top3)

　{

　/*輸出輸入串*/

　printf("%c",c[g]);

　g=g+1;

　}

　printf("\t\t");

　while(x!=vt[j]&&j<=5) //獲取當前 x 對應 j 的值

　j++;

　if(j==5&&x!=vt[j])//如果 x 不是終結符則報錯

　{

　printf("error\n");

　return 0;

　}

　if(action[y][j]==NULL){

　printf("error\n");

　return 0;

　}

　else

　strcpy(copy,action[y][j]);

　if(copy[0]=="S")

　{

　/*處理移進*/

　z=copy[1]-"0";//因為狀態從 0 開始

　top1=top1+1;

　top2=top2+1;

　a[top1]=z;//數組 a 實現狀態棧

　b[top2]=x;//數組 b 實現符號棧

　top=top+1;//輸入符號串數組 c的頂

　i=0;

　while(copy[i]!="#")//例 "S3#"

　輸出 ACTION

　{

　printf("%c",copy[i])

　return 0;

　i++;

　}

　printf("\n");

　}

　if(copy[0]=="r")

　{

　/*處理歸約*/

　i=0;

　while(copy[i]!="#")//例 "S3#"

　輸出 ACTION

　{

　printf("%c",copy[i])

　return 0;

　i++;

　}

　h=copy[1]-"0";//因為狀態從 0 開始

　strcpy(copy1,LR[h]);

　while(copy1[0]!=vn[k]) //獲取當前 k 值

　k++;

　l=strlen(LR[h])-4;

　top1=top1-l+1;

　top2=top2-l+1;

　y=a[top1-1];

　p=goto1[y][k];

　a[top1]=p;

　b[top2]=copy1[0];

　z=p;

　printf("\t");

　printf("%d\n",p);

　}

　}while(action[y][j]!="acc");

　printf("acc\n");

　getchar（）；

　}

　 7、測試及結果

　確定是否為 LL（1）文法

　8、心得 通過本次的實驗，使我真正的了解語法分析器的實現過程，讓我更加深刻領悟語法分析器的實現原理。雖然在本次實驗中遇到了各種各樣的困難和錯誤，但在老師和同學們的幫助下我都一一克服了，使得語法分析器能夠正確的識別相應的語法和表達式。

　在做實驗的過程中，發現自己在編寫程序過程中，總是會忽略各種細節，從而導致經常修改一些很小的低級錯誤才能使程序正常運行，不僅浪費時間，還影響對其他地方的修改，并且在很多步驟處理上，方法不正確。使結果不能符合要求，深刻體會到了自己在編程方面與別人的差距，在今后的學習中，我會注意改正自己在這方面的缺點，促使自己的編程水平不斷進步。編譯原理是一門專業學科，對于現階段的我來說，只能掌握它的一些基本原理和概念，對于一些更深層的知識還是有很多難以理解的地方。但在這次實驗過程中，鍛煉了自己的思考能力，也鍛煉了自己的動手編程能力，對于將知識的轉化有了很大的幫助。

推薦訪問： 編譯 語法 原理