語(yǔ)法分析器實(shí)驗(yàn)報(bào)告

1、南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報(bào)告實(shí)驗(yàn)（實(shí)習(xí)）名稱 LL（1）文法語(yǔ)法分析設(shè)計(jì) 實(shí)驗(yàn)（實(shí)習(xí)）日期 11月28日 得分 指導(dǎo)教師 林美華 系 計(jì)算機(jī) 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 年級(jí) 2011 班次 計(jì)科3班 姓名 王欣 學(xué)號(hào) 20112308915 一 實(shí)驗(yàn)?zāi)康?熟悉判斷LL（1）文法的方法及對(duì)某一輸入串的分析過(guò)程。2學(xué)會(huì)構(gòu)造表達(dá)式文法的預(yù)測(cè)分析表。二 實(shí)驗(yàn)內(nèi)容編寫(xiě)一個(gè)語(yǔ)法分析程序，對(duì)于給定的輸入串，能夠判斷識(shí)別該串是否為給定文法的句型。三 實(shí)驗(yàn)步驟從鍵盤(pán)讀入輸入串，并判斷正誤；若無(wú)誤，由程序自動(dòng)構(gòu)造FIRST、FOLLOW集以及SELECT集合，判斷是否為L(zhǎng)L（1）文法；若符合LL（1）文法，由程

2、序自動(dòng)構(gòu)造LL（1）分析表；由算法判斷輸入符號(hào)串是否為該文法的句型【源代碼】#include "stdio.h"#include "stdlib.h"#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pRNode /*產(chǎn)生式右部結(jié)構(gòu)*/ int rCursor; /*右部序號(hào)*/ struct pRNode

3、*next;struct pNode /*產(chǎn)生式結(jié)點(diǎn)結(jié)構(gòu)*/ int lCursor; /*左部符號(hào)序號(hào)*/ int rLength; /*右部長(zhǎng)度*/ /*注當(dāng)rLength = 1 時(shí)，rCursor = -1為空產(chǎn)生式*/ struct pRNode *rHead; /*右部結(jié)點(diǎn)頭指針*/;char VnMaxVnNum + 1; /*非終結(jié)符集*/int vnNum;char VtMaxVtNum + 1; /*終結(jié)符集*/int vtNum;struct pNode PMaxRuleN

4、um; /*產(chǎn)生式*/int PNum; /*產(chǎn)生式實(shí)際個(gè)數(shù)*/char bufferMaxPLength + 1;char ch; /*符號(hào)或string ch;*/char stMaxStLength; /*要分析的符號(hào)串*/struct collectNode /*集合元素結(jié)點(diǎn)結(jié)構(gòu)*/ int nVt; /*在終結(jié)符集中的下標(biāo)*/ struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first集*/struct collectNo

5、de* followMaxVnNum + 1; /*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*預(yù)測(cè)分析表存放為產(chǎn)生式的編號(hào)，+1用于存放結(jié)束符，多+1用于存放#(-1)*/int analyseStackMaxStackDepth + 1; /*分析棧*/int topAnalyse; /*分析棧頂*/*int reverseStackMaxStackDepth + 1; /*顛倒順序棧*/*int topReverse; /*倒敘棧頂*/void Init();/*初始化*

6、/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt(); /*輸入終結(jié)符*/void InputVn();/*輸入非終結(jié)符*/void ShowChArray(char* collect, int num);/*輸出Vn或Vt的內(nèi)容*/void InputP();/*產(chǎn)生式輸入*/bool CheckP(char * st);/*判斷產(chǎn)生式正確性*/void First(int U);/*計(jì)算first集,U->xx.*/void AddFirst(int U, int nCh);&

7、#160;/*加入first集*/bool HaveEmpty(int nVn); /*判斷first集中是否有空(-1)*/void Follow(int V);/*計(jì)算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集， kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(struct collectNode *collect);/*輸出first或follow集*/void FirstFollow();/*計(jì)算first和follow*/void Cr

8、eateAT();/*構(gòu)造預(yù)測(cè)分析表*/void ShowAT();/*輸出分析表*/void Identify(char *st);/*主控程序,為操作方便*/*分析過(guò)程顯示操作為本行變換所用，與教程的顯示方式不同*/void InitStack();/*初始化棧及符號(hào)串*/void ShowStack();/*顯示符號(hào)棧中內(nèi)容*/void Pop();/*棧頂出棧*/void Push(int r);/*使用產(chǎn)生式入棧操作*/#include "LL1.h"void main(void) char todo,ch;  Init();

9、0;InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf("所得first集為："); ShowCollect(first); printf("所得follow集為："); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y' while('y' = todo) &#

10、160; printf("n是否繼續(xù)進(jìn)行句型分析？(y / n):");  todo = getchar();  while('y' != todo && 'n' != todo)     printf("n(y / n)? ");   todo = getchar();    if('y' = todo) 

11、60;   int i;   InitStack();   printf("請(qǐng)輸入符號(hào)串(以#結(jié)束) : ");   ch = getchar();   i = 0;   while('#' != ch && i < MaxStLength)       if(' ' !=

12、ch && 'n' != ch)         sti+ = ch;        ch = getchar();      if('#' = ch && i < MaxStLength)       sti = ch;

13、0;   Identify(st);      else     printf("輸入出錯(cuò)！n");    getchar();void Init() int i,j; vnNum = 0; vtNum = 0; PNum = 0; for(i = 0; i <= MaxVnNum; i+)  Vni = '0'&#

14、160;for(i = 0; i <= MaxVtNum; i+)  Vti = '0' for(i = 0; i < MaxRuleNum; i+)   Pi.lCursor = NULL;  Pi.rHead = NULL;  Pi.rLength = 0;  PNum = 0; for(i = 0; i <= MaxPLength; i+)  bufferi = '0' for(i

15、 = 0; i < MaxVnNum; i+)   firsti = NULL;  followi = NULL;  for(i = 0; i <= MaxVnNum; i+)   for(j = 0; j <= MaxVnNum + 1; j+)   analyseTableij = -1; /*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/int IndexCh(char ch)  in

16、t n; n = 0; /*is Vn?*/ while(ch != Vnn && '0' != Vnn)  n+; if('0' != Vnn)  return 100 + n; n = 0; /*is Vt?*/ while(ch != Vtn && '0' != Vtn)  n+; if('0' != Vtn)  return n;&#

17、160;return -1;/*輸出Vn或Vt的內(nèi)容*/void ShowChArray(char* collect) int k = 0; while('0' != collectk)   printf(" %c ", collectk+);  printf("n");/*輸入非終結(jié)符*/void InputVn() int inErr = 1; int n,k; char ch; while(inErr)  

18、; printf("n請(qǐng)輸入所有的非終結(jié)符，注意：");  printf("請(qǐng)將開(kāi)始符放在第一位，并以#號(hào)結(jié)束:n");   ch = ' '  n = 0;  /*初始化數(shù)組*/  while(n < MaxVnNum)     Vnn+ = '0'    n = 0;  while(&#

19、39;#' != ch) && (n < MaxVnNum)     if(' ' != ch && 'n' != ch && -1 = IndexCh(ch)       Vnn+ = ch;    vnNum+;      ch = getchar();  &#

20、160; Vnn = '#' /*以“#”標(biāo)志結(jié)束用于判斷長(zhǎng)度是否合法*/  k = n; /*k用于記錄n以便改Vnn='0'*/  if('#' != ch)     if( '#' != (ch = getchar()       while('#' != (ch = getchar()   

21、      printf("n符號(hào)數(shù)目超過(guò)限制！n");    inErr = 1;    continue;       /*正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入*/  Vnk = '0'  ShowChArray(Vn);  ch = ' '  

22、while('y' != ch && 'n' != ch)     if('n' != ch)       printf("輸入正確確認(rèn)?(y/n):");      scanf("%c", &ch);    if('n' = ch) 

23、60;   printf("錄入錯(cuò)誤重新輸入！n");   inErr = 1;    else     inErr = 0;   /*輸入終結(jié)符*/void InputVt() int inErr = 1; int n,k; char ch; while(inErr)   printf("n請(qǐng)輸入所有的終結(jié)符，注意：

24、");  printf("以#號(hào)結(jié)束:n");   ch = ' '  n = 0;  /*初始化數(shù)組*/  while(n < MaxVtNum)     Vtn+ = '0'    n = 0;  while('#' != ch) && (n < MaxVtNum)&#

25、160;    if(' '!= ch && 'n' != ch && -1 = IndexCh(ch)       Vtn+ = ch;    vtNum+;      ch = getchar();    Vtn = '#' /*以“#”標(biāo)志結(jié)束*/

26、60; k = n; /*k用于記錄n以便改Vtn='0'*/  if('#' != ch)     if( '#' != (ch = getchar()       while('#' != (ch = getchar()        printf("n符號(hào)數(shù)目超過(guò)限制！n&quo

27、t;);    inErr = 1;    continue;       /*正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入*/  Vtk = '0'  ShowChArray(Vt);  ch =' '  while('y' != ch && 'n' != ch)  

28、   if('n' != ch)       printf("輸入正確確認(rèn)?(y/n):");      scanf("%c", &ch);    if('n' = ch)     printf("錄入錯(cuò)誤重新輸入！n");  &

29、#160;inErr = 1;    else     inErr = 0;   /*產(chǎn)生式輸入*/void InputP() char ch; int i = 0, n,num; printf("請(qǐng)輸入文法產(chǎn)生式的個(gè)數(shù)："); scanf("%d", &num); PNum = num; getchar(); /*消除回車(chē)符*/ printf(&q

30、uot;n請(qǐng)輸入文法的%d個(gè)產(chǎn)生式,并以回車(chē)分隔每個(gè)產(chǎn)生式：", num); printf("n"); while(i < num)   printf("第%d個(gè)：", i);  /*初始化*/  for(n =0; n < MaxPLength; n+)   buffern = '0'  /*輸入產(chǎn)生式串*/  ch = ' ' &

31、#160;n = 0;  while('n' != (ch = getchar() && n < MaxPLength)     if(' ' != ch)    buffern+ = ch;        buffern = '0'/*  printf("%s", buffer);*/ 

32、 if(CheckP(buffer)     /*填寫(xiě)入產(chǎn)生式結(jié)構(gòu)體*/   pRNode *pt, *qt;   Pi.lCursor = IndexCh(buffer0);   pt = (pRNode*)malloc(sizeof(pRNode);   pt->rCursor = IndexCh(buffer3);   pt->next = NULL; 

33、60; Pi.rHead = pt;   n = 4;   while('0' != buffern)       qt = (pRNode*)malloc(sizeof(pRNode);    qt->rCursor = IndexCh(buffern);    qt->next = NULL;    pt-

34、>next = qt;    pt = qt;    n+;      Pi.rLength = n - 3;   i+;   /*調(diào)試時(shí)使用*/    else   printf("輸入符號(hào)含非法在成分，請(qǐng)重新輸入！n"); /*判斷產(chǎn)生式正確性*/bool CheckP(char * st

35、) int n; if(100 > IndexCh(st0)  return false; if('-' != st1)  return false; if('>' != st2)  return false; for(n = 3; '0' != stn; n +)   if(-1 = IndexCh(stn)   return false;  r

36、eturn true;/*=first & follow=*/*計(jì)算first集,U->xx.*/void First(int U) int i,j; for(i = 0; i < PNum; i+)   if(Pi.lCursor = U)     struct pRNode* pt;   pt = Pi.rHead;   j = 0;   while(j < Pi.rLengt

37、h)       if(100 > pt->rCursor)         /*注:此處因編程出錯(cuò),使空產(chǎn)生式時(shí)     rlength同樣是1,故此處同樣可處理空產(chǎn)生式*/     AddFirst(U, pt->rCursor);     break; &

38、#160;      else         if(NULL = firstpt->rCursor - 100)           First(pt->rCursor);             

39、;  AddFirst(U, pt->rCursor);     if(!HaveEmpty(pt->rCursor)           break;          else          

40、0;pt = pt->next;             j+;      if(j >= Pi.rLength) /*當(dāng)產(chǎn)生式右部都能推出空時(shí)*/    AddFirst(U, -1);   /*加入first集*/void AddFirst(int U, int nCh) /*當(dāng)數(shù)值小于100時(shí)nCh為

41、Vt*/*當(dāng)處理非終結(jié)符時(shí),AddFirst不添加空項(xiàng)(-1)*/ struct collectNode *pt, *qt; int ch; /*用于處理Vn*/ pt = NULL; qt = NULL; if(nCh < 100)   pt = firstU - 100;  while(NULL != pt)     if(pt->nVt = nCh)    break; 

42、;  else       qt = pt;    pt = pt->next;       if(NULL = pt)     pt = (struct collectNode *)malloc(sizeof(struct collectNode);   pt->nVt = nCh;  

43、; pt->next = NULL;   if(NULL = firstU - 100)       firstU - 100 = pt;      else       qt->next = pt; /*qt指向first集的最后一個(gè)元素*/      pt = pt->

44、;next;    else   pt = firstnCh - 100;  while(NULL != pt)     ch = pt->nVt;   if(-1 != ch)       AddFirst(U, ch);      pt = pt->next;  

45、 /*判斷first集中是否有空(-1)*/bool HaveEmpty(int nVn)  if(nVn < 100) /*為終結(jié)符時(shí)(含-1)，在follow集中用到*/  return false; struct collectNode *pt; pt = firstnVn - 100; while(NULL != pt)   if(-1 = pt->nVt)   return true;  pt = pt-

46、>next;  return false;/*計(jì)算follow集,例：U->xVy,U->xV.(注：初始符必含#"-1")*/void Follow(int V) int i; struct pRNode *pt  if(100 = V) /*當(dāng)為初始符時(shí)*/  AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i+)   pt = Pi.rHead;  while

47、(NULL != pt && pt->rCursor != V) /*注此不能處理：U->xVyVz的情況*/   pt = pt->next;  if(NULL != pt)     pt = pt->next; /*V右側(cè)的符號(hào)*/   if(NULL = pt) /*當(dāng)V后為空時(shí)V->xV，將左符的follow集并入V的follow集中*/    

48、0;  if(NULL = followPi.lCursor - 100 && Pi.lCursor != V)         Follow(Pi.lCursor);        AddFollow(V, Pi.lCursor, 0);      else /*不為空時(shí)V->xVy,(注意：y->)，調(diào)用A

49、ddFollow加入Vt或y的first集*/       while(NULL != pt && HaveEmpty(pt->rCursor)    AddFollow(V, pt->rCursor, 1); /*y的前綴中有空時(shí)，加如first集*/     pt = pt->next;        if(N

50、ULL = pt) /*當(dāng)后面的字符可以推出空時(shí)*/         if(NULL = followPi.lCursor - 100 && Pi.lCursor != V)           Follow(Pi.lCursor);          AddFollow(

51、V, Pi.lCursor, 0);        else /*發(fā)現(xiàn)不為空的字符時(shí)*/         AddFollow(V, pt->rCursor, 1);           /*當(dāng)數(shù)值小于100時(shí)nCh為Vt*/*#用-1表示,kind用于區(qū)分是并入符號(hào)的first集，還是follow集ki

52、nd = 0表加入follow集，kind = 1加入first集*/void AddFollow(int V, int nCh, int kind) struct collectNode *pt, *qt; int ch; /*用于處理Vn*/ pt = NULL; qt = NULL; if(nCh < 100) /*為終結(jié)符時(shí)*/   pt = followV - 100;  while(NULL != pt)    

53、60;if(pt->nVt = nCh)    break;   else       qt = pt;    pt = pt->next;       if(NULL = pt)     pt = (struct collectNode *)malloc(sizeof(struct c

54、ollectNode);   pt->nVt = nCh;   pt->next = NULL;   if(NULL = followV - 100)       followV - 100 = pt;      else       qt->next = pt; /*qt指向fo

55、llow集的最后一個(gè)元素*/      pt = pt->next;    else /*為非終結(jié)符時(shí)，要區(qū)分是加first還是follow*/   if(0 = kind)     pt = follownCh - 100;   while(NULL != pt)       ch = pt->

56、nVt;    AddFollow(V, ch, 0);    pt = pt->next;       else     pt = firstnCh - 100;   while(NULL != pt)       ch = pt->nVt;   

57、0;if(-1 != ch)         AddFollow(V, ch, 1);        pt = pt->next;      /*輸出first或follow集*/void ShowCollect(struct collectNode *collect) int i; struct collectNode *pt; 

58、i = 0; while(NULL != collecti)   pt = collecti;  printf("n%c:t", Vni);  while(NULL != pt)     if(-1 != pt->nVt)       printf(" %c", Vtpt->nVt);     &

59、#160;else    printf(" #");   pt = pt->next;    i+;  printf("n");/*計(jì)算first和follow*/void FirstFollow() int i; i = 0; while('0' != Vni)   if(NULL = firsti)   Firs

60、t(100 + i);  i+;  i = 0; while('0' != Vni)   if(NULL = followi)   Follow(100 + i);  i+; /*=構(gòu)造預(yù)測(cè)分析表,例：U:xyz=*/void CreateAT() int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i < PNum; i+)

61、   pt = Pi.rHead;  while(NULL != pt && HaveEmpty(pt->rCursor)      /*處理非終結(jié)符，當(dāng)為終結(jié)符時(shí)，定含空為假跳出*/   ct = firstpt->rCursor - 100;   while(NULL != ct)       if(-1 != ct->

62、nVt)     analyseTablePi.lCursor - 100ct->nVt = i;    ct = ct->next;      pt = pt->next;    if(NULL = pt)     /*NULL = pt，說(shuō)明xyz->,用到follow中的符號(hào)*/   ct = fo

63、llowPi.lCursor - 100;   while(NULL != ct)       if(-1 != ct->nVt)     analyseTablePi.lCursor - 100ct->nVt = i;    else /*當(dāng)含有#號(hào)時(shí)*/     analyseTablePi.lCursor - 100vtNum =

64、 i;    ct = ct->next;       else     if(100 <= pt->rCursor) /*不含空的非終結(jié)符*/       ct = firstpt->rCursor - 100;    while(NULL != ct)   &#

65、160;     analyseTablePi.lCursor - 100ct->nVt = i;     ct = ct->next;          else /*終結(jié)符或者空*/       if(-1 = pt->rCursor) /*-1為空產(chǎn)生式時(shí)*/  &

66、#160;      ct = followPi.lCursor - 100;     while(NULL != ct)           if(-1 != ct->nVt)       analyseTablePi.lCursor - 100ct->nVt = i;  &

67、#160;   else /*當(dāng)含有#號(hào)時(shí)*/       analyseTablePi.lCursor - 100vtNum = i;      ct = ct->next;             else /*為終結(jié)符*/    

68、0;    analyseTablePi.lCursor - 100pt->rCursor = i;          /*輸出分析表*/void ShowAT() int i,j;1  printf("構(gòu)造預(yù)測(cè)分析表如下：n"); printf("t|t"); for(i = 0; i < vtNum; i+)   printf(&q

69、uot;%ct", Vti);  printf("#tn");2  printf("- - -t|- - -t"); for(i = 0; i <= vtNum; i+)  printf("- - -t"); printf("n");3  for(i = 0; i < vnNum; i+)   printf("%ct|t", Vni);  for

70、(j = 0; j <= vtNum; j+)     if(-1 != analyseTableij)    printf("R(%d)t", analyseTableij);   else    printf("errort");    printf("n"); /*=主控程序=*/void Identify(char

71、 *st) int current,step,r; /*r表使用的產(chǎn)生式的序號(hào)*/ printf("n%s的分析過(guò)程：n", st); printf("步驟t分析符號(hào)棧t當(dāng)前指示字符t使用產(chǎn)生式序號(hào)n");  step = 0; current = 0; /*符號(hào)串指示器*/ printf("%dt",step); ShowStack(); printf("tt%ctt- -n", stcurrent);4

72、  while('#' != stcurrent)   if(100 > analyseStacktopAnalyse) /*當(dāng)為終結(jié)符時(shí)*/     if(analyseStacktopAnalyse = IndexCh(stcurrent)       /*匹配出棧，指示器后移*/    Pop();    current

73、+;    step+;    printf("%dt", step);    ShowStack();    printf("tt%ctt出棧、后移n", stcurrent);      else       printf("%c-%c不匹配！"

74、, analyseStacktopAnalyse, stcurrent);    printf("此串不是此文法的句子！n");    return;       else /*當(dāng)為非終結(jié)符時(shí)*/     r = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcurrent);   i

75、f(-1 != r)       Push(r); /*產(chǎn)生式右部代替左部，指示器不移動(dòng)*/    step+;    printf("%dt", step);    ShowStack();    printf("tt%ctt%dn", stcurrent, r);    &#

76、160; else       printf("無(wú)可用產(chǎn)生式，此串不是此文法的句子！n");    return;       if('#' = stcurrent) 5   if(0 = topAnalyse && '#' = stcurrent)     s

77、tep+;   printf("%dt", step);   ShowStack();   printf("tt%ctt分析成功！n", stcurrent);   printf("%s是給定文法的句子！n", st);    else     while(topAnalyse > 0)       if(100 > analyseStacktopAnalyse) /*當(dāng)為終結(jié)符時(shí)*/