资源描述：
《实验二 LL(1)预测分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《编译原理》实验指导13非师实验二LL(1)分析的设计与实现开课实验室：A201，A207实验项目LL(1)分析的设计与实现实验类型设计实验学时4一、实验目的根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。掌握LL(1)分析法的基本原理，LL(1)分析表的构造方法，LL(1)驱动程序的构造方法。二、设备与环境1.硬件设备：PC机一台2.软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如CC++Java等编程语言环境。三、实验要求1.输入文法G的非终结符、终结符和产生式；（1）输出非终结符的FIRST集；（2）输出非终结符的F
2、OLLOW集；（3）构造文法G的预测分析表；（4）对输入符号串进行分析。2、编程语言不限。四、实验原理1.程序功能（流程图参考）：第24页《编译原理》实验指导13非师2.计算FIRST集合：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。²直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中²反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。算法
3、描述：见教材P80①)若X∈Vt,则FIRST(X)={X}; ②)若X∈Vn,且有产生式X->a……,a∈Vt，则a∈FIRST(X); ③)若X∈Vn,X->e,则e∈FIRST(X) ④)若X,Y1,Y2,Y3,Y4…………Yn都∈Vn,而产生式X->Y1,Y2……Yn.当Y1,Y2,Y3,Y4…………Yn都能=>e，那么FIRST(X)=并集的FIRST(Yi)-{e}(0<=i<=n) ⑤)若Yi=>e(i=1,2,3……)，则FIRST(X)=并集的FIRST(Yi)-{e}并上{e} 3.计算FOLLOW集合：Follow集合是针对非终结符而言的，
4、Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。²直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中；²直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)直接收入到Follow(U)中；²直接收取：若为文法开始符号S，则把#收入FOLLOW(S)；²反复传送：对形如U－…P的产生式（其中P是非终结符），应把Follow(U)中的全部内容传送到Follow(P)中。算法描述：见教材P82①)若为文法开始符号S，则FOLLOW(S)={#}②)若为文法A->aBb是一个产生式
5、，则把FIRST（b）的非空元素加入FOLLOW(B)中。如果b->@则把FOLLOW(A)也加入FOLLOW(B)中。4.构造预测分析表：(1)对于文法的每条产生式A®a，若aÎFIRST(a)，则M[A,a]=A®a；(2)若eÎFIRST(a)，bÎFOLLOW(a)则M[A,b]=A®a；(3)分析表M的其他元素均为出错标志error。5.预测分析程序流图：见课本P93-P94五、程序源码#include"stdio.h"#include"stdlib.h"第24页《编译原理》实验指导13非师#defineMaxRuleNum8#defineMaxVnNum5#defineMaxV
6、tNum5#defineMaxStackDepth20#defineMaxPLength20#defineMaxStLength50structpRNode/*产生式右部结构*/{intrCursor;structpRNode*next;};structpNode{intlCursor;intrLength;/*右部长度*/structpRNode*rHead;/*右部结点头指针*/};charVn[MaxVnNum+1];/*非终结符集*/intvnNum;charVt[MaxVtNum+1];/*终结符集*/intvtNum;structpNodeP[MaxRuleNum];intPN
7、um;charbuffer[MaxPLength+1];charch;charst[MaxStLength];/*要分析的符号串*/structcollectNode{intnVt;structcollectNode*next;};structcollectNode*first[MaxVnNum+1];/*first集*/structcollectNode*follow[MaxVnNum+1];/*follow集*/in
