实验2预测分析算法设计和实现.doc

《实验2预测分析算法设计和实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二预测分析算法的设计与实现（8学时）一、实验目的通过预测分析算法的设计与实现，加深对自上而下语法分析方法的理解，尤其是对自上而下分析条件的理解。二、实验要求输入文法及待分析的输入串，输出其预测分析过程及结果。三、实验步骤1.参考数据结构(1)/*定义产生式的语法集结构*/typedefstruct{charformula[200];//产生式}grammarElement;grammarElementgramOldSet[200];//原始文法的产生式集(2)/*变量定义*/charterSymbol[200];//终结符号charnon_ter[200];//非终结符号charallSy

2、mbol[400];//所有符号charfirstSET[100][100];//各产生式右部的FIRST集charfollowSET[100][100];//各产生式左部的FOLLOW集intM[200][200];//分析表2.判断文法的左递归性，将左递归文法转换成非左递归文法。（该步骤可以省略，直接输入非左递归文法）。3.根据文法求FIRST集和FOLLOW集。（1）/*求First集的算法*/beginifX为终结符(XÎ)在所有产生式中查找X所在的产生式if产生式右部第一个字符为终结符或空(即X®a（aÎ）或X®e)then把a或e加进FIRST(X)if产生式右部第一个字符为非终结

3、符thenif产生式右部的第一个符号等于当前字符then跳到下一条产生式进行查找if当前非终结符还没有求其FIRST集then查找它的FIRST集并标识此符号已求其FIRST集求得结果并入到X的FIRST集if当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then获取右部符号下一个字符在所有字符集中的位置if此字符的FIRST集还未查找then找其FIRST集，并标其查找状态为1把求得的FIRST集并入到X的FIRST集if当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X®,若对一切1£i£k,均有eÎFIRST(),则将eÎ符号加进FIRST(X))then把空

4、字加入到当前字符X的FIRST集else不能推出空字则结束循环标识当前字符X已查找其FIRST集。end（2）/*求FOLLOW集的算法*/beginifX为开始符号then#ÞFOLLOW(X)对全部的产生式找一个右部含有当前字符X的产生式ifX在产生式右部的最后(形如产生式A®aX)then查找非终结符A是否已经求过其FOLLOW集.避免循环递归if非终结符A已经求过其FOLLOW集then把FOLLOW(A)中的元素加入FOLLOW(X)继续查下一条产生式是否含有Xelse求A的FOLLOW集，并标记为A已求其FOLLOW集elseifX不在产生式右部的最后(A®aBb)thenif右部

5、X后面的符号串b能推出空字ethen查找b是否已求过其FOLLOW集.避免循环递归if已求过b的FOLLOW集then把FOLLOW(A)中的元素加入FOLLOW(B)结束本次循环elseifb不能推出空字then求FIRST(b)把FIRST(b)中所有非空元素加入到FOLLOW(B)中　　　　　标识当前要求的非终结符X的FOLLOW集已求过end4.构造预测分析表。/*构造分析表*///在AÎ所在行,aÎ所在列,M[A,a]的填写方法如下:if(A®dÎPandaÎFIRST(d))doM[A,a]=‘A®d’if(dÞ*e(eÎFIRST(d))andaÎFOLLOW(A))doM[A,

6、a]=‘A®d’;elsedoM[A,a]=‘ERR’.5.构造总控程序。程序流程图如图1所示：N$和文法开始符号进S栈第一个输入符号读进aS栈顶符号上托出去放X中XÎ?X=a?X=’$’?将下一个输入符号读进aX=a?查M[X,a]=x→y1y2…yn?将y1y2…yn逆序放入S栈中,若右部符号串为e,则e不进S栈出错正确出错出错YNYNYNYYN图16.对给定的输入串，给出分析过程及结果。四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。程序代码:#in

7、clude"stdio.h"#include"stdlib.h"#defineMaxRuleNum8#defineMaxVnNum5#defineMaxVtNum5#defineMaxStackDepth20#defineMaxPLength20#defineMaxStLength50structpRNode/*产生式右部结构*/{intrCursor;structpRNode*next;};st