實驗5 LL(1)語法分析程序的設計與實現(xiàn)(C語言)

1、班級: 學號: 姓名:實驗五 LL(1)文法識別程序設計一、實驗目的通過LL(1)文法識別程序的設計理解自頂向下的語法分析思想。二、實驗重難點FIRST集合、FOLLOW集合、SELECT集合元素的求解，預測分析表的構造。三、實驗內(nèi)容與要求實驗內(nèi)容：1 閱讀并理解實驗案例中LL(1)文法判別的程序?qū)崿F(xiàn)；2 參考實驗案例，完成簡單的LL(1)文法判別程序設計。四、實驗學時4課時五、實驗設備與環(huán)境 C語言編譯環(huán)境六、實驗案例1 實驗要求參考教材93頁預測分析方法，94頁 圖5.11 預測分析程序框圖，編寫表達式文法的識別程序。要求對輸入的LL(1)文法字符串，程序能自動判斷所給字符串是否為所給文法

2、的句子，并能給出分析過程。表達式文法為：EE+T|TTT*F|FFi|(E) 2 參考代碼為了更好的理解代碼，建議將圖5.11做如下標注：/* 程序名稱： LL(1)語法分析程序 */* E->E+T|T */* T->T*F|F */* F->(E)|i */*目 的: 對輸入LL(1)文法字符串，本程序能自動判斷所給字符串是否為所給文法的句子，并能給出分析過程。/*/* 程序相關說明 */* A=E' B=T' */* 預測分析表中列號、行號 */* 0=E 1=E' 2=T 3=T' 4=F */* 0=i 1=+ 2=* 3=( 4=)

3、 5=# */*/#include"iostream"#include "stdio.h"#include "malloc.h"#include "conio.h"/*定義鏈表這種數(shù)據(jù)類型參見：struct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;/*p指向終結符線性鏈表的頭結點，h指向動態(tài)建成的終結符線性鏈表節(jié)點，top和base分別指向非終結符堆棧的頂和底*/char curchar; /存放當前待比較的字符:終結符ch

4、ar curtocmp; /存放當前棧頂?shù)淖址悍墙K結符int right;int table56=1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0;/*存放預測分析表，1表示有產(chǎn)生式，0表示無產(chǎn)生式。*/int i,j; void push(char pchar) /*入棧函數(shù)*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp->char_ch=pchar;temp->next=top;top=temp; void pop(void) /*出棧函數(shù)*/curtocmp

5、=top->char_ch;if(top->char_ch!='#')top=top->next;void doforpush(int t) /*根據(jù)數(shù)組下標計算的值找對應的產(chǎn)生式，并入棧*/switch(t)case 0:push('A');push('T');break;case 3:push('A');push('T');break;case 11:push('A');push('T');push('+');break;case 20:push

6、('B');push('F');break;case 23:push('B');push('F');break;case 32:push('B');push('F');push('*');break;case 40:push('i');break;case 43:push(')');push('E');push('(');/*根據(jù)curchar和curtocmp轉為數(shù)字以判斷是否有產(chǎn)生式*/void changchart

7、oint()switch(curtocmp) /*非終結符：棧頂*/case 'E':i=0;break;case 'A':i=1;break;case 'T':i=2;break;case 'B':i=3;break;case 'F':i=4;switch(curchar) /*終結符：待識別的表達式中*/case 'i':j=0;break;case '+':j=1;break;case '*':j=2;break;case '(':j=3;bre

8、ak;case ')':j=4;break;case '#':j=5;/*識別算法*/void dosome(void)int t;for(;)pop();/*讀取棧頂?shù)淖址鎐urtocmp中*/curchar=h->char_ch; /*讀取輸入字符鏈表h中一個字符存入curchar*/printf("n%ct%c",curchar,curtocmp);if(curtocmp='#' && curchar='#') /*如果都是終結符 P94 圖5.11圈1、圈5、圈7*/break;

9、 if(curtocmp='A'|curtocmp='B'|curtocmp='E'|curtocmp='T'|curtocmp='F') /*如果curtocmp不是終結符 P94 圖5.11圈1*/if(curtocmp!='#') /*如果curtocmp不是終結符，也不是結束符，則根據(jù)預測分析表找到產(chǎn)生式并入棧 P94 圖5.11圈1*/changchartoint();if(tableij) /*1.1有產(chǎn)生式P94 圖5.11圈2*/t=10*i+j; /*計算產(chǎn)生式在數(shù)組中的位置*/d

10、oforpush(t); /*找對應t的產(chǎn)生式并入棧P94 圖5.11圈3*/continue;else/*1.2沒有產(chǎn)生式P94 圖5.11圈4*/right=0; /*出錯*/break;else if(curtocmp!=curchar) /*如果curtocmp不是終結符，并且是結束符，判斷終結符鏈表字符是否也為終結符P94 圖5.11圈1、1、5、6*/right=0; /*出錯*/break;elsebreak; /*正確P94 圖5.11圈1、1、5、7*/else if(curtocmp!=curchar) /* 如果curtocmp是終結符,并且不等于當前終結符鏈表中的終結符

11、，則出錯。P94 圖5.11圈1、8、9*/right=0; /*出錯*/break;else /*如果curtocmp是終結符,并且等于當前終結符鏈表中的終結符，則匹配成功，可以讀取下一個鏈表頭的終結符P94 圖5.11圈10*/h=h->next; /*讀取下一字符*/continue;int main(void)char ch;right=1;base=(struct Lchar*)malloc(sizeof(Lchar); /*初始化非終結符堆棧，棧底為#，棧頂為文法開始符號*/base->next=NULL; base->char_ch='#'tem

12、p=(struct Lchar*)malloc(sizeof(Lchar);temp->next=base;temp->char_ch='E'top=temp; /*初始化非終結符堆棧，棧底為#，棧頂為文法開始符號E*/*初始化存放待識別的表達式（終結符）的線性鏈表頭*/h=(struct Lchar*)malloc(sizeof(Lchar);h->next=NULL;p=h; /*開辟了一個空的鏈表空間,p和h同時指向該空間,該空間將作為終結符鏈表的頭部。*/printf("請輸入要分析的字符串(#號結束)n");do /*輸入待識別的

13、表達式*/ch=getch();putch(ch); /在屏幕上輸出一個字符if(ch='i'|ch='+'|ch='*'|ch='('|ch=')'|ch='#') /*將輸入的ch存入鏈表*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp->next=NULL;temp->char_ch=ch;h->next=temp;h=h->next;/*如果輸入正確，h不斷的指向新輸入的字符，而p始終指向輸入終結符字符串的頭位置，即前面開

14、辟的空的鏈表空間。*/elsetemp=p->next; /*如果輸入錯誤，提示輸入有錯，請重新輸入，讓temp指向輸入字符串的頭部，并將前面正確輸出的字符串再次輸出*/printf("nInput a wrong char!Input again:n");for(;)if (temp!=NULL)printf("%c",temp->char_ch);elsebreak;temp=temp->next;while(ch!='#');p=p->next; /*消去第一個空頭節(jié)點，并使頭結點指向非空線性鏈表表頭*/*如

15、果輸入正確，h不斷的指向新輸入的字符，而輸入字符串的頭位置被記錄在p里面。*/h=p; /*h重新指向頭結點，以便后面識別操作*/dosome();/*開始識別*/if(right)printf("n成功! 輸入的表達式可以被該文法識別！n"); elseprintf("n錯誤! 表示輸入的表達式不可以被該文法識別！n"); getch();return 0;3 測試數(shù)據(jù)及運行結果七、簡單LL(1)文法判別程序設計1、判斷以下文法是不是LL（1）文法，寫出詳細的判斷過程：EE+T|E-T|TTT*F|T/F|FFi|(E)（1） 消除左遞歸，文法變?yōu)椋篍

16、TEE+TE | -TE | TFTT*FT | /FT |Fi | (E)（2） 可推出的非終結符表為：EETTF否是否是否（3） 各非終結符的FIRST集合為：FIRST(E) = (,iFIRST(E) =+,-,FIRST(T)=(,iFIRST(T) =*,/,FIRST(F) =(,i（4） 各非終結符的FOLLOW集合為：FOLLOW(E) = ）,#FOLLOW(E)= ）,#FOLLOW(T) = ）,#,+,-FOLLOW(T)= ）,#,+,-FOLLOW(F) = *,/,+,-,）,#（5） 各產(chǎn)生式的SELECT集合為：SELECT(ETE)=(,iSELECT(E

17、+TE)=+SELECT(E-TE)=-SELECT(E)= ）,#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T/FT)=/SELECT(T)= +,-,）,#SELECT(F(E)=(SELECT(Fi)=i（6） 有相同左部產(chǎn)生式的SELECT集合的交集是否為空？該文法是否為LL（1）文法？（7） 該文法的預測分析表為:i+-*/()#E+TETEE+TE-TETFTT*FT/FTFi(E)2、設計LL(1)文法判別程序設計，源代碼如下：/* 程序名稱： LL(1)語法分析程序 */* E->E+T|E-T/T */* T->T*F|T/F/F *

18、/* F->(E)|i */*目 的: 對輸入LL(1)文法字符串，本程序能自動判斷所給字符串是否為所給文法的句子，并能給出分析過程。/*/* 程序相關說明 */* A=E' B=T' */* 預測分析表中列號、行號 */* 0=E 1=E' 2=T 3=T' 4=F */* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */*/#include"iostream"#include "stdio.h"#include "malloc.h"#include "conio.

19、h"/*定義鏈表這種數(shù)據(jù)類型參見：struct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;/*p指向終結符線性鏈表的頭結點，h指向動態(tài)建成的終結符線性鏈表節(jié)點，top和base分別指向非終結符堆棧的頂和底*/char curchar; /存放當前待比較的字符:終結符char curtocmp; /存放當前棧頂?shù)淖址悍墙K結符int right;int table58=1,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1

20、,0,0,0,0,1,0,0;/*存放預測分析表，1表示有產(chǎn)生式，0表示無產(chǎn)生式。*/int i,j; void push(char pchar) /*入棧函數(shù)*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp->char_ch=pchar;temp->next=top;top=temp; void pop(void) /*出棧函數(shù)*/curtocmp=top->char_ch;if(top->char_ch!='#')top=top->next;void doforpush(int t) /*根據(jù)數(shù)組下

21、標計算的值找對應的產(chǎn)生式，并入棧*/switch(t)case 0:push('A');push('T');break;case 5:push('A');push('T');break;case 11:push('A');push('T');push('+');break;case 12:push('A');push('T');push('-');break;case 20:push('B');push('F&#

22、39;);break;case 25:push('B');push('F');break;case 33:push('B');push('F');push('*');break;case 34:push('B');push('F');push('/');break;case 40:push('i');break;case 45:push(')');push('E');push('(');break;/*根

23、據(jù)curchar和curtocmp轉為數(shù)字以判斷是否有產(chǎn)生式*/void changchartoint()switch(curtocmp) /*非終結符：棧頂*/case 'A':i=1;break;case 'B':i=3;break;case 'E':i=0;break;case 'T':i=2;break;case 'F':i=4;switch(curchar) /*終結符：待識別的表達式中*/case 'i':j=0;break;case '+':j=1;break;case

24、 '-':j=2;break;case '*':j=3;break;case '/':j=4;break;case '(':j=5;break;case ')':j=6;break;case '#':j=7;/*識別算法*/void dosome(void)int t;for(;)pop();/*讀取棧頂?shù)淖址鎐urtocmp中*/curchar=h->char_ch; /*讀取輸入字符鏈表h中一個字符存入curchar*/printf("n%ct%c",curchar,

25、curtocmp);if(curtocmp='#' && curchar='#') /*如果都是終結符 P94 圖5.11圈1、圈5、圈7*/break; if(curtocmp='A'|curtocmp='B'|curtocmp='E'|curtocmp='T'|curtocmp='F') /*如果curtocmp不是終結符 P94 圖5.11圈1*/if(curtocmp!='#') /*如果curtocmp不是終結符，也不是結束符，則根據(jù)預測分析

26、表找到產(chǎn)生式并入棧 P94 圖5.11圈1*/changchartoint();if(tableij) /*1.1有產(chǎn)生式P94 圖5.11圈2*/t=10*i+j; /*計算產(chǎn)生式在數(shù)組中的位置*/doforpush(t); /*找對應t的產(chǎn)生式并入棧P94 圖5.11圈3*/continue;else/*1.2沒有產(chǎn)生式P94 圖5.11圈4*/right=0; /*出錯*/break;else if(curtocmp!=curchar) /*如果curtocmp不是終結符，并且是結束符，判斷終結符鏈表字符是否也為終結符P94 圖5.11圈1、1、5、6*/right=0; /*出錯*/b

27、reak;elsebreak; /*正確P94 圖5.11圈1、1、5、7*/else if(curtocmp!=curchar) /* 如果curtocmp是終結符,并且不等于當前終結符鏈表中的終結符，則出錯。P94 圖5.11圈1、8、9*/right=0; /*出錯*/break;else /*如果curtocmp是終結符,并且等于當前終結符鏈表中的終結符，則匹配成功，可以讀取下一個鏈表頭的終結符P94 圖5.11圈10*/h=h->next; /*讀取下一字符*/continue;int main(void)char ch;right=1;base=(struct Lchar*)

28、malloc(sizeof(Lchar); /*初始化非終結符堆棧，棧底為#，棧頂為文法開始符號*/base->next=NULL; base->char_ch='#'temp=(struct Lchar*)malloc(sizeof(Lchar);temp->next=base;temp->char_ch='E'top=temp; /*初始化非終結符堆棧，棧底為#，棧頂為文法開始符號E*/*初始化存放待識別的表達式（終結符）的線性鏈表頭*/h=(struct Lchar*)malloc(sizeof(Lchar);h->next=

29、NULL;p=h; /*開辟了一個空的鏈表空間,p和h同時指向該空間,該空間將作為終結符鏈表的頭部。*/printf("請輸入要分析的字符串(#號結束)n");do /*輸入待識別的表達式*/ch=getchar();putchar(ch); /在屏幕上輸出一個字符if(ch='i'|ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#') /*將輸入的ch存入鏈表*/temp=(struct Lchar*

30、)malloc(sizeof(Lchar);temp->next=NULL;temp->char_ch=ch;h->next=temp;h=h->next;/*如果輸入正確，h不斷的指向新輸入的字符，而p始終指向輸入終結符字符串的頭位置，即前面開辟的空的鏈表空間。*/elsetemp=p->next; /*如果輸入錯誤，提示輸入有錯，請重新輸入，讓temp指向輸入字符串的頭部，并將前面正確輸出的字符串再次輸出*/printf("nInput a wrong char!Input again:n");for(;)if (temp!=NULL)printf("%c",temp->char_ch);elsebreak;temp=temp->next;while(ch!='#');p=p->next; /*消去