《编译原理LL(一)语法分析实验报告要点.docx》由会员分享，可在线阅读，更多相关《编译原理LL(一)语法分析实验报告要点.docx（12页珍藏版）》请在三一文库上搜索。
1、学号20102798专业 软件工程姓名 薛建东实验日期2013.04.08教师签字成绩实验报告【实验名称 】LL（1）语法分析【实验目的 】通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能， 掌握语法分析程序设计的原理和构造方法， 训练掌握开发应用程序的基本方法。【实验内容 】根据某一文法编制调试LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。分析法的功能是利用LL （ 1）控制程序根据显示栈栈顶内容、向前看符号以及LL（ 1）分析表，对输入符号串自上而下的分析过程
2、。【 设计思想 】（ 1）、LL（ 1）文法的定义LL(1) 分析法属于确定的自顶向下分析方法。LL(1) 的含义是： 第一个 L 表明自顶向下分析是从左向右扫描输入串，第2 个 L 表明分析过程中将使用最左推导，1 表明只需向右看一个符号便可决定如何推导，即选择哪个产生式( 规则 ) 进行推导。LL(1) 文法的判别需要依次计算FIRST 集、FOLLOW集和 SELLECT集 , 然后判断是否为LL(1)文法 , 最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1) 分析法中，每当在符号栈的栈顶出现非终极符时， 要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断
3、其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1) 分析方法要求文法满足如下条件： 对于任一非终极符A 的两个不同产生式A,A，都要满足下面条件：SELECT(A) SELECT(A)=（ 2）、预测分析表构造LL(1) 分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用 M表示 LL(1) 分析表，则M可表示如下：M: VN VTP ErrorM(A, t) = A，当 tselect(A )，否则M(A, t) = Error其中 P 表示所
4、有产生式的集合。（ 3）、语法分析程序构造LL(1) 分析中 X 为符号栈栈顶元素， a 为输入流当前字符， E 为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素MA，a 中的下标A表示非终结符， a 为终结符或句子括号 #，二维数组中存放的是一条关于A 的产生式， 表明当非终结符A 向下推导时， 面临输入符a 时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。LL(1) 分析过程主要包括以下四个动作：替换：当 X VN时选相应产生式的右部去替换 X。此时 X 出栈，逆序入栈
5、。匹配：当 X VT时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将 X 退栈并将输入流指针向前移动一位，否则报错。接受：当格局为（#，空 #）时报告分析成功。报错：出错后，停止分析。并给出相应的错误提示信息。【实验要求】1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。【流程图】1. 总体思路分析及流程图给定一个正规文法G，在 LL(1) 预测分析中， 必须先求出First集和 Follow集，然后求出 Select集，通过 Select集判断是否是LL1 文法，如果是的话，构造预测分析表。求出预测分析表之后，再
6、输入一个字符串，依据LL1 分析表单步输出字符串的分析过程。1读取正规文法求文法的 First 集求文法的 Follow 集求文法的 Select 集键盘输入字符串字符串分析功能模块分解图（1）主程序流程图2开始输入文法判断文法是否为LL(1) 文法Y构造预测分析表输入要分析的符号串出错处理N判断该符号串是否可被该文法识别Y提示 i*i+i#为可接受的字符串结束（ 2）核心算法流程图N出错处理1. 计算非终结符的 First 集的算法及流程：First集合的构造算法：（ 1）若 X VT，则 First （ X） =X 。（ 2）若 X VN，且有产生式X a，则把a 加入到 First(X)
7、 中；若 X 也是一条产生式，则把 也加到 First (X)中。（ 3）若X Y是一个产生式且YVN，则把First (Y)中的所有非 - 元素都加到First(X) 中；若 X Y1Y2Yk 是一个产生式，Y1， Yi-1都是非终结符，而且，对于任何 j ， 1 j i-1 ， First (Yj)都含有 （即 Y1 Yi-1*），则把First (Yj)中的所有非- 元素都加到First(X) 中；特别是，若所有的First(Yj) 均含有 ， j=1,2,， k，则把加到 First (X)中。连续使用上面的规则，直至每个集合First不再增大为止。3开始读取一个非终结符 V遍历所有产
8、生式，查找左部是 V的产生式添加一个删除取出得到的一空的标志为条产生式trueV* 是不是有推导规产生式右部第一个符则 V*- 空号 V* 是终结符？将该终结符V*加入 V 的 First 集中空标志为真删除空，得到V 的 First 集剩有非终结符？结束2. 计算非终结符的 Follow 集：Follow 集合的具体构造算法如下：（ 1）对于文法的开始符号S，置 #于 Follow(S)中；（ 2）若 A B 是一个产生式，则把First( )| 加至 Follow(B)中；（ 3）若 A B 是一个产生式， 或 A B 是一个产生式而 （即 First( ) ），则把 Follow(A)
9、加至 Follow(B) 中。连续使用上面的规则，直至每个集合Follow 不再增大为止。4开始取得一个非终结符V查找产生式的右部含有 V 的产生式YV 后一个字符 V* 是V 是不是最后一个字符N否为终结符Y添加 #到V 的 FollowYY集中N是否遍历完所有右添加 V* 到V 的 Follow 中部含有 V 的产生式Y将V* 的First 集加入到 V 的Follow 集中是否有未求解过的N完成非终结符3. 预测分析控制程序的算法流程5输入要分析的字符串Y判断字符串是否正确N # E进栈，当前终结符号送入 a若产生式为A A1A2 An, 按逆序即显示分析步骤An A2A1入栈显示栈中内
10、容NY显示剩余输入串接受产生式右部为空？A Vt?YYNA=#？Y匹配字符串？NN显示产生式N产生式不存Y出错在？Y出错读入下一符号YA= a？N【源代码】#include#include#include6#includechar A20;/*分析栈 */char B20;/*剩余串 */char v120=i,+,*,(,),#;/*终结符*/char v220=E,G,T,S,F;/*非终结符*/int j=0,b=0,top=0,l;/*L为输入串长度*/typedef struct type/*产生式类型定义*/char origin;/*大写字符*/char array5;/*产生式
11、右边字符*/int length;/*字符个数*/type;type e,t,g,g1,s,s1,f,f1;/*结构体变量*/type C1010;/*预测分析表*/void print()/*输出分析栈*/int a;/*指针 */for(a=0;a=top+1;a+)printf(%c,Aa);printf(tt);/*print*/void print1()/*输出剩余串 */int j;for(j=0;jb;j+)/*输出对齐符 */printf( );for(j=b;j=l;j+)printf(%c,Bj);printf(ttt);/*print1*/void main()int m
12、,n,k=0,flag=0,finish=0;char ch,x;type cha;/*用来接受Cmn*/* 把文法产生式赋值结构体*/e.origin=E;strcpy(e.array,TG);7e.length=2;t.origin=T;strcpy(t.array,FS);t.length=2;g.origin=G;strcpy(g.array,+TG);g.length=3;g1.origin=G;g1.array0=;g1.length=1;s.origin=S;strcpy(s.array,*FS);s.length=3;s1.origin=S;s1.array0=;s1.leng
13、th=1;f.origin=F;strcpy(f.array,(E);f.length=3;f1.origin=F;f1.array0=i;f1.length=1;for(m=0;m=4;m+)/*初始化分析表 */for(n=0;n=5;n+)Cmn.origin=N;/*全部赋为空 */*填充分析表 */C00=e;C03=e;C11=g;C14=g1;C15=g1;C20=t;C23=t;C31=s1;C32=s;C34=C35=s1;C40=f1;C43=f;printf(提示 : 本程序只能对由i,+,*,(,)构成的以 #结束的字符串进行分析 ,n);printf(请输入要分析的字
14、符串:);do/*读入分析串 */scanf(%c,&ch);if (ch!=i) &(ch!=+) &(ch!=*)&(ch!=()&(ch!=)&(ch!=#)printf(输入串中有非法字符n);exit(1);Bj=ch;8j+;while(ch!=#);l=j;/*分析串长度 */ch=B0;/*当前分析字符 */Atop=#; A+top=E;/*#,E进栈 */printf(步骤 tt分析栈 tt剩余字符tt所用产生式n);dox=Atop-;/*x为当前栈顶字符*/printf(%d,k+);printf(tt);for(j=0;j=5;j+)/*判断是否为终结符*/if(x=
15、v1j)flag=1;break;if(flag=1)/*如果是终结符 */if(x=#)finish=1;/*结束标记 */printf(acc!n);/*接受 */getchar();getchar();exit(1);/*if*/if(x=ch)print();print1();printf(%c匹配 n,ch);ch=B+b;/*下一个输入字符*/flag=0;/*恢复标记 */*if*/else/*出错处理 */print();print1();printf(%c出错 n,ch);/*输出出错终结符*/exit(1);/*else*/*if*/else/*非终结符处理 */9for(j=0;j=4;j+)if(x=v2j)m=j;/* 行号 */break;for(j=0;j,cha.origin);/*输出产生式 */for(j=0;j=0;j-)/*产生式逆序入栈*/A+top=cha.arrayj;if(Atop=)/*为空则不进栈*/top-;/*if*/else/*出错处理 */print();print1();printf(%c出错 n,x);/*输出出错非终结符*/exit(1);/*else*/*else*/while(finish=0);/*main*/【运行结果 】1011