语法实验报告

1、编译原理实验报告题目:语法分析学生姓名：班 级：学 号：指导教师： -成 绩： 西安邮电大学计算机学院2015 年5 月28日一：实验目的掌握一种语法分析规则，并且能够动态的生成算符优先表或预测分析表。二：实验要求（一）对于如下的文法，试编写调试一个语法分析程序：E t E+T | TT t T*F | FF t pF| PPt （ E ） | i要求和提示：（ 1）可选择一种你感兴趣的语法分析方法（ LL（1） 、算符优先、递归下降、 SLR（1）等）作为编制语法分析程序的依据。（ 2）对于所选定的分析方法， 如有需要， 应选择一种合适的数据结构， 以构造所给文法的机内表示。（ 3）能进行分

2、析过程模拟。 如输入一个句子， 能输出与句子对应的语法树， 能对语法树生成过程进行模拟；能够输出分析过程每一步符号栈的变化情况。（二）First 集和 Follow 集生成算法模拟【问题描述】设计一个由给定文法生成 First 集和 Follow 集并进行简化的算法动态模拟。（算法参见教材 ）【基本要求】动态模拟算法的基本功能是：1）输入一个文法 G；2）输出由文法 G 构造 FIRST 集的算法；3）输出 First 集；4）输出由文法 G 构造 FOLLOW 集的算法；5）输出 FOLLOW 集。测试数据】输入文法：E-TEE-+TE | T-FTT-*FT | F-（E）|i（三）Fir

3、stVT 集和 LastVT 集生成算法模拟【问题描述】设计一个由给定文法生成 FirstVT 集和 LastVT 集的算法动态模拟。 （算法参见教材 P90 92FirstVT 和 LastVT 的构造算法 ）【基本要求】动态模拟算法的基本功能是：（ 1） 输入一个文法 G；（2） 输出由文法 G 构造 FIRSTVT 集的算法；（ 3） 输出 FirstVT 集；（4）输出由文法 G 构造 LastVT 集的算法；（ 5）输出 LastVT 集。【测试数据】 输入文法： E-TEE-+TE | T-FTT-*FT | F-（E）|i三：实验内容完成实验一和选作题的第二个四：采用的数据结构在

4、第二个实验的时候要用到栈，来存放一些信息，这里采用链表来构建栈。struct nodechar ch2;struct node *next;/ / 栈顶指针static struct node *stack=NULL;五：算法描述实验（一）：采用 yacc 语法分析程序自动的帮助完成一系列的分析工作，自己只需要编写完 整的（ .y ）代码，描述清楚所要实现的文法，并且要自己处理，文法中存在的冲突问题，解 决办法按照标准要求写明。实验（ 3）：FIRSTVT 算法思想 :设置一个 int 型数组，行号对应为非终结符，列号对应为终结符。 将数组元素全部初始化为 0.a. 对于每个产生式寻找满足形如

5、U-b或U-Vb的产生式，将对应数组U,b的值置为1，并且将对应的（非终结符，终结符）压栈。b. 当栈不为空的时候，出栈顶元素（非终结符，终结符），记为（Q a）。对每个产生式寻找满足形为P-Q，的产生式，如果P,a=O时，将对应元素 P，a 的值置为 1，并且压栈。c. 直到栈为空时得到的二维数组为每行值对应为 1 的终结符为该行非终结符 的 FIRSTVT集根据同样的算法思想可以得到 LISTVT 集合。 优先关系表的构建思想：对于每个产生式 P-X1X2X3XN如果 Xi 和 Xi+1 都终结符在，则对应的优先关系为 =如果 Xi 和 Xi+2 都为终结符，并且 Xi+1 为非终结符，则

6、对应的 Xi 和 Xi+2的优先关系为 =如果Xi为终结符Xi+1为非终结符，则将 FIRSTVT(Xi+1 )中的每个元素 a, 置对应XiXi+1.六：运行结果hpEhp-u-neva： *-/byyl/F1rt* Q旦即1? 11皐H岬h巾“减四一专 cd tivyl/Ftrgt hp(hpLn9c! -/SyjiX nrst& “11 l.c 1-tMt 3.C3l.c i.ltXt 22-C- a.E 4hpfhp - Lencivoi /tnryl/first$F ERSm ：hpihp -L-ewMO! -/IwmI /ftrs-tS Ifli 电 flFCft51VT-：E=*

7、i*J*1.!lP( FCRSWUTt*,*) FCRSTVTjF-.I.C) FCRSWTip.-ft j FEesm；A=sLA5TWT；ALAETVT： LAETVT： LASTVT： LMTVT; I AETVT：e:心S 5 J) 居5X.l.tMt CS5.txt!.tKt- StACk l.Hehp#Q “ 网0:$*7/1+4ti 43 S 4H 1M7 爲BID0E1或TP-=-T*F*T*F ，TF- T- E-： 堆*E*Thphp Lenovo -/byylS (B+2J/S-1P-iP-E*TF-；T-：P-T*FTE-TTEP七：调试情况+*t()f.(E1FPAP

8、t 叫ElTFPAr( ETFFAPEETFPAJ ETFPA, J A-A：E0帆) ETFRAJ+*!(j +*t()rEETFFA,#ETFPA,# 惯先？t :EFI Pft,X 吒八叫I；甘止+*!()*1 ETFPk上在生成FIRST时换取不同的文法时，程序发生了死循环。在WINDOS下创建的文法文件每行结束时是以/r/n占用两个字节，而在LINUX下换行只占用一个In字节。八：设计技巧及体会设计技巧：对于文法中的 在写如文件时，已经做过一些处理，方便自己在以后的程序中的处理。体会：使用YACC，虽然开始时完全不了解，但是通过基本的学习，还是会一些使 用，这样通过这个工具， 使自己

9、方便了自己的编写程序，节约了好多时间，并且比自己独立的去完成的更好，还是值得去学习和应用的九：源程序清单Yacc程序II说明部分%#in clude#in clude void yyerror(char *msg)fprin tf(stderr,%s 出错 n,msg);%toke n DIGIT定义一个终结符%left +-运算符优先顺序%left * T%II语法规则line : e n printf（%dn,$）;e: e + t| e - t| tJ printf（ 使用产生式 E-E+T ）; printf（ 将 E+T 归约为 En）; $=$1+$3; printf（ 使用产生式

10、 E-E-T ）; printf（ 将 E-T 归约为 En）; $=$1-$3; printf（ 使用产生式 E-T）; printf（ 将 T 归约为 En）;t :t * f printf（ 使用产生式 T-T*F ）; printf（ 将 T*F 归约为 Tn）;$=$1*$3; | t / f printf（ 使用产生式 T-T*F ）; printf（ 将 T/F 归约为 Tn）;$=$1/$3; | f printf（ 使用产生式 T-F ）;Jprintf（ 将 F 归约为 Tn）;f :p A f printf（ 使用产生式 F-PAF ）; printf（ 将 PAF 归约

11、为 Fn）; $=$1A$3;| p printf（ 使用产生式 F-P ）; printf（ 将 P 归约为 Fn）;p : （ e ） printf（ 使用产生式 P-（E）,）;printf（将（E）归约为 Pn）;$=$2; | DIGIT printf（ 使用产生式 P-i,）;printf（将 %d 归约为 Pn,$1）;%/程序段int main（void）return yyparse（）;int yylex()int c;c=getchar();if(isdigit(c)yylval=c-0;return DIGIT;return c; 栈链表文件程序/#include#inc

12、ludestruct nodechar ch2;struct node *next;/栈顶指针static struct node *stack=NULL;/入栈int push(char a)struct node *p;p=(struct node *)malloc(sizeof(struct node);if(NULL=p)printf( 内存申请失败 !n);return 0;elsep-next=NULL;p-ch0=a0;p-ch1=a1;if(stack=NULL)stack=p;elsep-next=stack;stack=p; return 1;/出栈void pop(cha

13、r cha)struct node *p; p=stack-next; cha0=stack-ch0; cha1=stack-ch1; free(stack);stack=p;/判断栈是否为空 int is_empty()if(stack=NULL)return 0;elsereturn 1;/打印栈中元素 void print_stack()int i;struct node *p;p=stack;while(p!=NULL)printf(%d %sn,i+,p-ch); p=p-next; 优先表代码 #include #include #include #include #include

14、stack_l.h #define MAX 10 /查找 int in_char(char a,char b) int len;int i;int key=0; len=strlen(a); for(i=0;ilen;i+)if(ai=b)key=1;break;return key;/返回字符串中，特定字符的位置int lookup_char(char a,char b)int i,k=MAX;for(i=0;istrlen(a);i+)if(ai=b)k=i;return k;void delete_n(char a)int len;int i=0;len=strlen(a);alen-1

15、=0;/以表格的形式输出内容void print_table(char a,char b,int *c)int i,j;printf(%5c, );for(i=0;istrlen(a);i+)printf(%8c,ai);printf(n);for(i=0;istrlen(b);i+)printf(%5c,bi);for(j=0;jstrlen(a);j+) printf(%8d,cij);printf(n);/以集合的形式输出void print_set(char a,char b,int *c,int key)int i,j;int k;int number;char fi=FIRSTVT

16、,la=LASTVT; k=key;for(i=0;istrlen(a);i+)number=0;if(k=0)printf(%s:,fi);elseprintf(%s:,la);printf(%c=,ai); for(j=0;jstrlen(b);j+)if(cij=1 & number=0) printf(%c,bj); number+;else if(cij=1 & number!=0) i+;printf(,%c,bj); number+;printf(n);int main(void)int i=0,j=0,hang=0;FILE *fp;char cssMAXMAX;char zj

17、fMAX;char fzjfMAX;int zjfsize=0,fzjfsize=0;/ int *fvt,*lvt;extern struct node *stack; char zf2;char *yxb; fp=fopen(css.txt,r); if(NULL=fp)printf( 打开文件失败！ return 0;else/保存产生式/保存终结符/保存非终结符 终结符和非终结符的个数/保存一个非终结符和对应的终结符/优先表n);while(fgets(cssi,MAX,fp)!=NULL)/ 每次从文件中读出一行但是包含一个换行符fclose(fp);hang=i;for(i=0;i

18、hang;i+)/ 除去换行标志delete_n(cssi);for(i=0;ihang;i+)for(j=0;j continue;if(cssij=0)break;else if(isupper(cssij)/ 如果是大些字符，为非终结符if(in_char(fzjf,cssij)=0) fzjffzjfsize=cssij;fzjfsize+;elseif(in_char(zjf,cssij)=0)zjfzjfsize=cssij;zjfsize+;/用 malloc 创建二维数组 fvt=(int*)malloc(fzjfsize*sizeof(int *); lvt=(int*)ma

19、lloc(fzjfsize*sizeof(int *); yxb=(char*)malloc(zjfsize*sizeof(char *);for(i=0;ifzjfsize;i+)fvti=(int*)malloc(zjfsize*sizeof(int); lvti=(int*)malloc(zjfsize*sizeof(int);/初始化for(i=0;ifzjfsize;i+)for(j=0;jzjfsize;j+)fvtij=0;lvtij=0;for(i=0;izjfsize;i+) yxbi=(char*)malloc(zjfsize*sizeof(char);for(j=0;jb

20、. 和 U-Vb. 的初始 for(i=0;ihang;i+) for(j=0;jb.,zf0=cssi0; zf1=zjfj;fvtlookup_char(fzjf,cssi0)j=1; if(push(zf)=0)printf( 如栈失败 1！ n);if( cssi4=zjfj & lookup_char(fzjf,cssi3)!=MAX) /满足 U-Vbfvtlookup_char(fzjf,cssi0)j=1;zf0=cssi0; zf1=zjfj; if(push(zf)=0) printf( 入栈失败 2！ n); /如果栈不为空 while(is_empty() pop(zf

21、);for(i=0;i.b 和 U-.bV 的初始int k; for(i=0;ihang;i+) k=strlen(cssi);for(j=0;jbzf0=cssi0;zf1=zjfj;lvtlookup_char(fzjf,cssi0)j=1;if(push(zf)=0)printf( 如栈失败 1！ n);if( cssik-2=zjfj & lookup_char(fzjf,cssik-1)!=MAX)/满足 U- bVlvtlookup_char(fzjf,cssi0)j=1;zf0=cssi0;zf1=zjfj;if(push(zf)=0)printf( 入栈失败 2！ n);/如果栈不为空while(is_empty()pop(zf);for(i=0;ihang;i+)k=strlen(cssi);if(zf0=cssik-1) if(lvtlookup_char(fzjf,cssi0)lookup_char(zjf,zf1)=0) lvtlookup_char(fzjf,cssi0)lookup_char(zjf,zf1)=1; zf0=cssi0;if(push(zf)=0)printf( 入栈失败 3!n