实验四非递归预测分析教育相关

《实验四非递归预测分析教育相关》由会员分享，可在线阅读，更多相关《实验四非递归预测分析教育相关（10页珍藏版）》请在装配图网上搜索。

1、编译原理实验LR分析器院、系(部) 计算机科学与技术学院 专业及班级 计算机科学与技术专业1403班 学 号 1408030322 姓 名 朱浩 日 期 2017年5月29日 一、实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。二、实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。三、文法描述及其LL(1)分析表表达式语言(XL) 的语法规则如下：1 程序 表达式；2 |

2、表达式；程序3 表达式 表达式 + 项4 |项5 项 项 * 因式6 |因式7 因式 num_or_id8 |(表达式)将该语言的文法转换为如下的LL(1)文法：1 prgm expr;prgm 8 term factor term2 prgm prgm 9 term *factor term 3 prgm 10 term 4 expr term expr 11 factor (expr) 5 expr 12 factor num6 expr +term expr 13 system_goal prgm7 expr 该LL(1)文法的LL(1)分析表如下： TNNum+*();#prgm111

3、prgm2223expr4455expr677term88term1091010factor1211system_goal131313 对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注(Num+);*#4625130终结符(#为输入结束标志) Exprexprtermtermfactorprgmprgmsystem_goal258260259262261256257263非终结符四、 文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于

4、该表达式语言XL的LL(1)分析表，可用数组Yy_d存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0(表示接受) ，1(表示产生式号) ，-1(表示语法错) 。 数组Yy_d的具体内容及表示如下：0 1 2 3 4 5 6# ； + * ( ) Num-10-1-10-1021-1-11-11-14-1-1343-1-1-1-17-17-165-1-16-1-1-1-1-110-111-1998-19-1-112-1-112-112prgm 256 prgm 257 expr 258 term 259 expr 260factor 261term 262system_

5、goal 263 数组Yy_pushtab的具体内容及表示如下： 五、预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈(元素类型为int) ，其结构如下：初始化；/* 把开始符号的常数值压入分析站，输入指向第一个输入符号 */ while(分析栈非空) if(栈顶常数表示一个终结符)if(该常数与输入符号的常数不等)报语法错；else 把一个数从栈顶弹出；advance读下一输入符号；else /* 栈顶的常数表示一个非终结符 */what_to_do=Yy_d栈顶常数当前输入符号的常数；if(what_to_do= -1)报语法错；else

6、把栈顶元素弹出栈；把Yy_pushtabwhat_to_do中列出的全部常数压入分析栈；请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。六、预测分析控制程序的测试用例用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。栈(符号) 栈(数值) 输入串What_to_dosystem_goalprgmprgm ; exprprgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr termprgm ; exprprgm ; expr term+prgm ;

7、expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr termprgm ; exprprgm ; prgm263256257 1 258257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262 257 1 260 257 1 260 259 2257 1 260 259 257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260 257 1 260 262257 1+2；#1+2；#1+2；#1+2；#1+2；#

8、1+2；#+2；#+2；#+2；#2；#2；#2；#；#；#；#120371195711962思考：请考虑如何设计并实现LL(1)分析表的自动生成程序。七、实验代码根据上述LALR(1)分析表压缩表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。实验源程序：#include #include char *action103=S3#,S4#,NULL, /*ACTION表*/ NULL,NULL,acc, S6#,S7#,NULL, S3#,S4#,NULL, r3#,r3#,NULL, NULL,NULL,r1#, S6#,S7#,

9、NULL, NULL,NULL,r3#, r2#,r2#,NULL, NULL,NULL,r2#; int goto1102=1,2, /*QOTO表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0; char vt3=a,b,#; /*存放非终结符*/ char vn2=S,B; /*存放终结符*/ char *LR4=E-S#,S-BB#,B-aB#,B-b#;/*存放产生式*/ int a10; char b10,c10,c1; int top1,top2,top3,top,m,n; void main()int g,h,i,j,k,l,p,y

10、,z,count; char x,copy10,copy110; top1=0;top2=0;top3=0;top=0; a0=0;y=a0;b0=#; count=0;z=0; printf(-编译原理课程设计-n); printf(-汪鑫-n); printf(-20170527-n); printf(-请输入表达式-n); do scanf(%c,&c1); ctop3=c1; top3=top3+1; while(c1!=#); printf(步骤t状态栈tt符号栈tt输入串ttACTIONtGOTOn); do y=z;m=0;n=0;/*y,z指向状态栈栈顶*/ g=top;j=0

11、;k=0; x=ctop; count+; printf(%dt,count); while(m=top1) /*输出状态栈*/ printf(%d,am); m=m+1; printf(tt); while(n=top2) /*输出符号栈*/ printf(%c,bn); n=n+1; printf(tt); while(g=top3) /*输出输入串*/ printf(%c,cg); g=g+1; printf(tt); while(x!=vtj&j=2) j+; if(j=2&x!=vtj) printf(errorn); return; if(actionyj=NULL) printf

12、(errorn); return; else strcpy(copy,actionyj); if(copy0=S) /*处理移进*/ z=copy1-0; top1=top1+1; top2=top2+1; atop1=z; btop2=x; top=top+1; i=0; while(copyi!=#) printf(%c,copyi); i+; printf(n); if(copy0=r) /*处理归约*/ i=0; while(copyi!=#) printf(%c,copyi); i+; h=copy1-0;strcpy(copy1,LRh);while(copy10!=vnk) k+

13、; l=strlen(LRh)-4; top1=top1-l+1; top2=top2-l+1; y=atop1-1; p=goto1yk; atop1=p; btop2=copy10; z=p; printf(t); printf(%dn,p); while(actionyj!=acc); printf(accn); getchar(); 七、实验结果八、实验总结通过这次LR0分析器的实验，实现对词法分析程序所提供的单词系列进行语法检查和结构分析，进一步掌握了LR语法的分析过程，对于LR0文法有了更加深刻的理解。完成的LR0分析器只能对于一个特定的文法进行判断，完整的是要求能够对任意一种LR0文法都能够进行判断，在这方面上还需要对程序又进一步的了解才能最终实现，通过后续的努力，终能够将LR0分析器实现。10教学f