实验四 非递归预测分析

编译原理实验-lr分析仪计算机科学与技术学院计算机科学与技术专业及1403班学校编号1408030322名字：朱浩日期：2017年5月29日一、实验的目标和任务设计一个非递归预测分析器来分析表达式语言，理解自顶向下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。二、实验要求建立以语法为代表的数据结构及其LL(1)分析表，设计并实现相应的预测分析器，并对词法分析后源程序生成的二进制码流进行预测分析。如果输入字符串是语法定义的句子，输出“是”，否则输出“否”。三、语法描述和LL(1)分析表表达式语言的语法规则如下：1.程序表达；2.|表达式。程序3.表达式表达式项4.|项5.项目项目*因素6.|因素7.因子编号或id8.|(表达式)将该语言的语法转换为LL(1)语法，如下所示：1 prgmexpr；prgm 8术语因素术语2 prgm prgm 9术语*因子术语3 prgm 10项4 expr 术语expr 11因子 (expr)5 expr 12因子 num6 expr term expr 13 system _ goalprgm7 expr第一语言语法的第一语言分析表如下：TNNum*（)；#prgm111prgm 2223expr4455expr 677学期88术语“1091010因素1211系统目标131313为语法中的每个语法符号指定一个常数值。符号编码表如下：语法符号不变价值评论（Num)；*#4625130终结符(#是输入结束标志)Exprexpr 学期术语“因素prgmprgm 系统目标258260259262261256257263非终结符四、语法和LL(1)分析表数据结构一代代的语法可以存储在数组Yy_pushtab中。数组的第一个下标是生产编号，第一个生产的序列号是0；每列以相反的顺序存储生成右侧每个符号的常数值，以0结束。表达式语言XL的L1(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 256prgm 257expr 258术语259expr 260因子261术语262系统目标263数组Yy_pushtab的具体内容和表示如下：V.预测分析仪通用控制程序结构预测分析器的通用控制程序使用上述两个表Yy_pushtab、Yy_d和一个分析堆栈(元素类型为int)，其结构如下：初始化；/*将开始符号的常数值按入分析站，并指向第一个输入符号*/同时(分析堆栈不为空)如果(堆栈顶部常数表示终止符)如果(该常数不等于输入符号的常数)报告语法错误；否则从堆栈顶部弹出一个数字；前进读取下一个输入符号；else /*堆栈顶部的常数表示非终止符*/待办事项=栈顶常数当前输入符号的常数；如果(待办事项=-1)报告语法错误；否则从堆栈中弹出堆栈顶部元素；将Yy _ pushtab待办事项中列出的所有常量按入分析堆栈；请执行此程序。将输出堆栈内容的功能添加到程序中，以便与手动模拟分析过程进行比较。六、预测分析控制程序测试用例使用预测分析器和手动模拟来分析语法句子12；用于分析。综合分析过程可由下表表示。堆栈(符号)堆栈(值)输入语符列做什么系统目标prgmprgm ；exprprgm ；expr 术语prgm ；expr term 因子prgm ；expr term Numprgm ；expr term prgm ；expr prgm ；expr 术语prgm ；expr 术语prgm ；expr term 因子prgm ；expr term Numprgm ；expr term prgm ；expr prgm ；prgm 263256257 1 258257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260257 1 260 259 2257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260257 1 260 2622571 2；#1 2；#1 2；#1 2；#1 2；#1 2；#2；#2；#2；#2；#2；#2；#；#；#；#120371195711962思考：请考虑如何设计和实现LL(1)分析表的自动生成程序。七.实验代码根据LALR(1)分析表压缩表示方法，完成了LR分析器的程序设计，增加了输出状态堆栈内容的功能。用上面表达式语法中的一个句子作为输入进行测试。实验源程序：#包括#包括char *action103=S3# ， S4# ，空，/*行动桌子*/空，空， acc ，S6# ， S7# ，空，S3# ， S4# ，空，r3# ， r3# ，NULL，空，空， r1# ，S6# ， S7# ，空，空，空， r3# ，r2# ， r2# ，NULL，空，空， R2 # ；102=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，# ；/*存储非终结符*/2=南，北；/*商店终端*/char *LR4=E-S# ， S-BB# ， B-aB# ， B-B # ；/*存储生产*/国际10；char b10，c10，C1；int top1，top2，top3，top，m，n；void main()int g，h，I，j，k，l，p，y，z，countchar x，copy10，copy 110；top 1=0；top 2=0；top 3=0；top=0；a0=0；y=a0；b0=#；计数=0；z=0；编译原理课程设计；PRINTF(-王新- n )；printf(-20170527- n )；PRINTF ( - n )请输入表达式；做scanf(“% c”，C1)；c前3名=C1；top 3=top 3 1；同时(c1！=#)；printf( step t state stack t t symbol stack t t输入字符串 t t 操作 tGoto n n )；做y=z。m=0；n=0；/*y，z指向状态堆栈的顶部*/g=顶部；j=0；k=0；x=ctop；计数；printf(“% d t”，计数)；而(m=top1) /*输出状态堆栈*/printf(“% d”，am)；m=m1；printf( t t )；而(n=top2) /*输出符号堆栈*/printf(%c ，bn)；n=n1；printf( t t )；而(g=top3) /*输出输入字符串*/printf(“% c”，cg)；g=G1；printf( t t )；同时(x！；j=2；if(j=2x！()printf( error n )；返回；如果(行动yj=空)printf( error n )；返回；其他(副本，行动yj)；如果(复制0=S)/*处理移到*/z=复制1-0；top 1=top 11；top 2=top 2 1；atop 1=z；b前2名=x；top=top 1；I=0；同时(复制i )!=#)printf(“% c”，复制I)；我；printf( n )；如果(复制0=r)/*处理减少*/I=0；同时(复制i )!=#)printf(“% c”，复制I)；我；h=复制1-0；strcpy(copy1，LRh)；而(复制10！=k)k；l=strlen(左h)-4；top 1=top 1-l 1；top 2=top 2-l 1；y=排名前1-1；k；a前1名=p；b排名第2=第1名排名第0；z=p；printf( t )；printf(“% d n”，p)；而(行动y)j！= ACC )；printf( ACC n )；getch