实验5LL-语法分析程序地设计实现计划(C语言-).doc

《实验5LL-语法分析程序地设计实现计划(C语言-).doc》由会员分享，可在线阅读，更多相关《实验5LL-语法分析程序地设计实现计划(C语言-).doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验实验五五 LL(1)文法识别程序设计一、实验目的一、实验目的通过 LL(1)文法识别程序的设计理解自顶向下的语法分析思想。二、实验重难点二、实验重难点FIRST 集合、FOLLOW 集合、SELECT 集合元素的求解，预测分析表的构造。三、实验内容与要求三、实验内容与要求实验内容：1 阅读并理解实验案例中 LL(1)文法判别的程序实现； 2 参考实验案例，完成简单的 LL(1)文法判别程序设计。四、实验学时四、实验学时4 课时五、实验设备与环境五、实验设备与环境C 语言编译环境六、实验案例六、实验案例 1 实验要求 参考教材 93 页预测分析方法，94 页 图 5.11 预测分析程序框图，

2、编写表达式文法的 识别程序。要求对输入的 LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法 的句子，并能给出分析过程。 表达式文法为： EE+T|T TT*F|F Fi|(E) 2 参考代码为了更好的理解代码，建议将图 5.11 做如下标注：/* 程序名称： LL(1)语法分析程序 */ /* E-E+T|T */ /* T-T*F|F */ /* F-(E)|i */ /*目 的: 对输入 LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句 子，并能给出分析过程。 /*/ /* 程序相关说明 */ /* A=E B=T */ /* 预测分析表中列号、行号 */ /

3、* 0=E 1=E 2=T 3=T 4=F */ /* 0=i 1=+ 2=* 3=( 4=) 5=# */ /*/ #include“iostream“ #include “stdio.h“ #include “malloc.h“ #include “conio.h“/*定义链表这种数据类型参见： http:/ 5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8X WSQCeVTjXvy9lxLQ_mZXeS#*/ struct Lchar char char_ch; struct Lchar *next

4、; Lchar,*p,*h,*temp,*top,*base; /*p 指向终结符线性链表的头结点，h 指向动态建成的终结符线性链表节点，top 和 base 分 别指向非终结符堆栈的顶和底*/char curchar; /存放当前待比较的字符:终结符 char curtocmp; /存放当前栈顶的字符：非终结符 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 表示有产生式，0 表示无产生式。*/ int i,j;void push(char p

5、char) /*入栈函数*/ temp=(struct Lchar*)malloc(sizeof(Lchar); temp-char_ch=pchar; temp-next=top; top=temp; void pop(void) /*出栈函数*/ curtocmp=top-char_ch; if(top-char_ch!=#) top=top-next; void doforpush(int t) /*根据数组下标计算的值找对应的产生式，并入栈*/ switch(t) case 0:push(A);push(T);break; case 3:push(A);push(T);break; c

6、ase 11:push(A);push(T);push(+);break; case 20:push(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(); /*根据 curchar 和 curtocmp 转为数字以判断是否有产生式*/ void changchartoint() switch(curtocmp) /*非终结符：栈顶*/ case E:i=0;break

7、; 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;break; case ):j=4;break; case #:j=5; /*识别算法*/ void dosome(void) int t; for(;) pop();/*读取栈顶的字符存 curtocmp 中*/ curchar=h-char_ch; /*读取输入字

8、符链表 h 中一个字符存入 curchar*/ printf(“n%ct%c“,curchar,curtocmp); if(curtocmp=# if(curtocmp=A|curtocmp=B|curtocmp=E|curtocmp=T|curtocmp=F) /*如果 curtocmp 不是终结符 P94 图 5.11 圈 1*/ if(curtocmp!=#) /*如果 curtocmp 不是终结符，也不是结束符，则根据预测分析表 找到产生式并入栈 P94 图 5.11 圈 1*/ changchartoint(); if(tableij) /*1.1有产生式 P94 图 5.11 圈

9、2*/ t=10*i+j; /*计算产生式在数组中的位置*/ doforpush(t); /*找对应 t 的产生式并入栈 P94 图 5.11 圈 3*/ continue; else/*1.2没有产生式 P94 图 5.11 圈 4*/ right=0; /*出错*/ break; else if(curtocmp!=curchar) /*如果 curtocmp 不是终结符，并且是结束符，判断终结 符链表字符是否也为终结符 P94 图 5.11 圈 1、1、5、6*/ right=0; /*出错*/ break; else break; /*正确 P94 图 5.11 圈 1、1、5、7*/

10、 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*)malloc(sizeof(Lchar)

11、; /*初始化非终结符堆栈，栈底为#，栈顶为文法开 始符号*/ 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=NULL; p=h; /*开辟了一个空的链表空间,p 和 h 同时指向该空间,该空间将作为终结符链表

12、的头部。 */ printf(“请输入要分析的字符串(#号结束)n“); do /*输入待识别的表达式*/ 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 始终指向输入终结 符字符串的头位置，即前面开辟的空的链表空间。*/ el

13、se temp=p-next; /*如果输入错误，提示输入有错，请重新输入，让 temp 指向输入字 符串的头部，并将前面正确输出的字符串再次输出*/ printf(“nInput a wrong char!Input again:n“); for(;) if (temp!=NULL) printf(“%c“,temp-char_ch); else break; temp=temp-next; while(ch!=#);p=p-next; /*消去第一个空头节点，并使头结点指向非空线性链表表头*/*如果输入正确， h 不断的指向新输入的字符，而输入字符串的头位置被记录在 p 里面。*/ h=p

14、; /*h 重新指向头结点，以便后面识别操作*/ dosome();/*开始识别*/ if(right) printf(“n 成功! 输入的表达式可以被该文法识别！n“); else printf(“n 错误! 表示输入的表达式不可以被该文法识别！n“); getch(); return 0; 3 测试数据及运行结果七、简单七、简单 LL(1)文法判别程序设计文法判别程序设计1、判断以下文法是不是 LL（1）文法，写出详细的判断过程： EE+T|E-T|T TT*F|T/F|F Fi|(E)（1）消除左递归，文法变为：ETE E+TE | -TE | TFT T*FT | /FT | Fi |

15、 (E)（2）可推出的非终结符表为：EETTF否是否是否（3）各非终结符的 FIRST 集合为：FIRST(E) = (,i FIRST(E) =+,-, FIRST(T)=(,i FIRST(T) =*,/, FIRST(F) =(,i（4）各非终结符的 FOLLOW 集合为： FOLLOW(E) = ）,#FOLLOW(E)= ）,# FOLLOW(T) = ）,#,+,- FOLLOW(T)= ）,#,+,- FOLLOW(F) = *,/,+,-,）,#（5）各产生式的 SELECT 集合为： SELECT(ETE)=(,i SELECT(E+TE)=+ SELECT(E-TE)=-S

16、ELECT(E)= ）,# SELECT(TFT)=(,i SELECT(T*FT)=* SELECT(T/FT)=/SELECT(T)= +,-,）,# SELECT(F(E)=( SELECT(Fi)=i（6）有相同左部产生式的 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 */* F-(E)|i */*目 的: 对输入

17、 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.h“/*定义链表这种数据类型参见：http:/ Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*

18、top,*base;/*p 指向终结符线性链表的头结点，h 指向动态建成的终结符线性链表节点，top 和base 分别指向非终结符堆栈的顶和底*/char curchar; /存放当前待比较的字符:终结符char curtocmp; /存放当前栈顶的字符：非终结符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,0,0,0,0,1,0,0;/*存放预测分析表，1 表示有产生式，0 表示无产生式。*/int i,j;void push(char pchar) /*入栈函数

19、*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp-char_ch=pchar;temp-next=top;top=temp;void pop(void) /*出栈函数*/curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next;void doforpush(int t) /*根据数组下标计算的值找对应的产生式，并入栈*/switch(t)case 0:push(A);push(T);break;case 5:push(A);push(T);break;case 11:push(A);push(T);pu

20、sh(+);break;case 12:push(A);push(T);push(-);break;case 20:push(B);push(F);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;/*根据 curchar 和 curtocmp 转为数字以判断是否有产生式*/void changchartoi

21、nt()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 -: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)in

22、t t;for(;)pop();/*读取栈顶的字符存 curtocmp 中*/curchar=h-char_ch; /*读取输入字符链表 h 中一个字符存入 curchar*/printf(“n%ct%c“,curchar,curtocmp);if(curtocmp=# if(curtocmp=A|curtocmp=B|curtocmp=E|curtocmp=T|curtocmp=F) /*如果 curtocmp 不是终结符 P94 图 5.11 圈 1*/if(curtocmp!=#) /*如果 curtocmp 不是终结符，也不是结束符，则根据预测分析表找到产生式并入栈 P94 图 5.1

23、1 圈 1*/changchartoint();if(tableij) /*1.1有产生式 P94 图 5.11 圈 2*/t=10*i+j; /*计算产生式在数组中的位置*/doforpush(t); /*找对应 t 的产生式并入栈 P94 图 5.11 圈 3*/continue;else/*1.2没有产生式 P94 图 5.11 圈 4*/right=0; /*出错*/break;else if(curtocmp!=curchar) /*如果 curtocmp 不是终结符，并且是结束符，判断终结符链表字符是否也为终结符 P94 图 5.11 圈 1、1、5、6*/right=0; /*出

24、错*/break;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=

25、(struct Lchar*)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=NULL;p=h; /*开辟了一个空的链表空

26、间,p 和 h 同时指向该空间,该空间将作为终结符链表的头部。*/printf(“请输入要分析的字符串(#号结束)n“);do /*输入待识别的表达式*/ch=getchar();putchar(ch); /在屏幕上输出一个字符if(ch=i|ch=+|ch=-|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 始终指向输入

27、终结符字符串的头位置，即前面开辟的空的链表空间。*/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; /*消去第一个空头节点，并使头结点指向非空线性链表表头*/*如果输入正确，h 不断的指向新输入的字符，而输入字符串的头位

28、置被记录在 p 里面。*/h=p; /*h 重新指向头结点，以便后面识别操作*/dosome();/*开始识别*/if(right)printf(“n 成功! 输入的表达式可以被该文法识别！n“); elseprintf(“n 错误! 表示输入的表达式不可以被该文法识别！n“); getch();return 0;3、测试数据及运行结果,运行结果截图应包含姓名或学号信息.截图应包含一个正例 i*(i+i)-i/i# 一个反例i*(i+i)-i-/i# 正例成功截图如下：反例成功截图如下：4、实验总结、心得体会在进行此次实验上机前应该做好准备：按照老师提供的教材 P93 页的图 4.11 预测分

29、析程序的流程图熟悉预测分析的工作过程。计算出要分析的文法的 FIRST 集合、FOLLOW集合和 SELECT 集合。根据得出的各个集合得出构造预测分析表。在老师讲解其实验目的、要求和分析后，选择相应的数据，使用 C 语言参照算法中的流程编写词法分析的程序。将编写好的程序上次调试（包括正例和反例）。通过此次程序设计，更加清楚的明白了LL(1)分析法的过程，从而也比较熟练掌握了自上而下语法分析的基本思想，此外，在老师的讲解下初步认识了数据结构的知识，加上自己的理解，与所学知识加以联系，将知识归纳在系统中。在实现和调试时采取模块化的思想，是的本次课程设计比较顺利，增强了自己的信心，提高了自己的编程

30、能力和动手能力以及独立分析问题、解决问题的能力和综合运用所学知识的能力。5.思考：词法分析与语法分析的不同区别：顾名思义，词法分析器检查的是词法，语法分析器分析的是语法， 什么是词法，什么是语法。 所谓词法，源代码由字符流组成，字符流中包括关键字，变量名，方法名，括 号等等符号，其中变量名要满足不能包括标点符号，不能以数字开头的数字与 字母的字符串这个条件，对于括号要成对出现等等，这就是词法;而语法，词法 没有问题才能进入语法分析，语法就是词排列的方法，字面意义， 语法分析器 就是分析类似这样的语法的。教师评语：教师评语：是否完成实验程序的预备设计？ 是： 不是：程序能否正常运行？ 是： 不是：有无测试数据及结果分析 是： 不是：是否在本次规定时间完成所有项目？ 是： 不是：实验成绩等级：实验成绩等级：教师签名：教师签名：N0:N0: 时间：时间：