语法分析器实验报告(可运行).

计算机科学与工程系xx大学XX系实验报告XX至XX学年第X学期课程名称编译原理学号XXX学生姓名XXX年级XXX级专业XXX教学班号XXX实验地点XXX实验时间XXXX主讲教师XXX辅导教师计算机科学与工程系2实验（二）实验名称语法分析软件环境WindowsxpVC++硬件环境P4实验目的一、实验目的：根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。二实验要求:1.LL（1）分析法的前提:改造文法:消除二义性,消除左递归,提取左因子.2.设计出模块结构,测试数据,初步编制好程序3.程序要求:生成LL（1）分析表:程序输入输出示例:对文法用LL（1）分析法对任意输入的符号串进行分析,输出的格式如下:(1)LL（1）分析程序，编制人：姓名，学号，班级(2)输入以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：步骤分析栈剩余输入串所用产生式1Ei+i*i#E→TG(4)输入符号串为非法符号串(或者为合法符号串)4.模块结构:（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。实验内容（应包括实验题目、实验要求、实验任务等）计算机科学与工程系3功能描述:LL（1）分析法是一种不带回溯的非递归的自上而下的分析法.其基本思想是根据输入串的当前输入符号来唯一确定选用某条规则来进行推倒,当这个输入符号与推倒的第一个符号相同时再取输入串的下一个符号,继续确定下一个推倒应选的规则,如此下去,直到推倒出被分析的输入串为止.LL（1）分析法实验设计思想及算法:实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）#和文法开始符号进栈第一个输入符号读进a栈顶符号托出去放X中XX弹弹栈栈，，将将yy11yy22……yykk逆逆序序放放入入SS栈栈中中，，若若右右部部符符号号串串为为εε，，则则εε不不进进栈栈X=a?XVT?X=‘#’?查M[X,a]=X→y1y2…ykX=a?将下一个输入符号读进aXVT?出错出错SSTTOOPPYYYYYYYYYYNNNNNNNNNN计算机科学与工程系程序流程图:实验过程记录：实验过程中对文法修改后且输入相同的符号串后所形成的分析表是一样的，这是一处错误，另外输入某个符号串后进行无休止运行，以上两种错误通过上网查询以及和同学交流得以解决。实验总结：LL(1)分析器又称预测分析法，是一种不带回溯的非递归自上而下分析法，一个LL(1)分析器由一张LL(1)分析表、一个先进后出分析栈和一个控制程序组成。附录（可包括源程序清单或其它说明）源程序：#includeiostream.h#includestdio.h#includestring.h#includestdlib.h#includectype.h计算机科学与工程系5#definePro_MidSym_Max2#definePro_RightSym_Max10#defineUnTInfo_Fir_Max10#defineUnTInfo_Fol_Max10#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstructProNode{//产生式结构charleftSym;//产生式左边的符号charmidSym[Pro_MidSym_Max];//产生式推导符号charrightSym[Pro_RightSym_Max];//产生式右边的符号，不超过十个intlength;//产生式长度}ProNode;typedefstructUnTInfo{//每个非终结符的信息结构，包括first和follow集合charfirst[UnTInfo_Fir_Max];charfollow[UnTInfo_Fol_Max];}UnTInfo;typedefstruct{//构造顺序栈,存储符号char*base;char*top;计算机科学与工程系6intstacksize;}SqStack;typedefstructQNode{//构造单链队列，存储输入符号串chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;intproNum;//产生式个数charUnTerminate[15];//非终结符表charTerminate[15];//终结符表charProNull[20];//记录能产生空字符的非终结符ProNodesheet[15][15];//分析表charselect[15][15];//select集合，以便于构造分析表LinkQueueRemain;//剩余符号串计算机科学与工程系7voidInitUnTInfo(UnTInfounTInfo[],intunTInfoNum);//初始化函数，对每个非终结符的信息结构进行初始化voidInitProNode(ProNodeproNode[],intproNum);//初始化函数，对每个非终结符的产生式结构进行初始化voidInitStack(SqStack&s);//初始化栈voidInitQueue(LinkQueue&q);//初始化队列voidEnQueue(LinkQueue&q,charc);//在队尾插入新的元素voidExit();//栈溢出处理函数voidError();//出错处理voidPush(SqStack&s,charc);//入栈charPop(SqStack&s);//出栈voidInitSheet(ProNode**sheet,intm,intn);//初始化分析表函数boolReadPro(ProNodeproNode[],charfileName[]);//从文件读取产生式函数voidPrintPro(ProNodeproNode[],intproNum);//显示产生式voidSetUnTerminate(charUnTerminate[],ProNodeproNode[],intproNum);//设置非终结符表voidSetTerminate(charUnTerminate[],ProNodeproNode[],intproNum);//设置终结符表intGetNumofUT(charUnTerminate[]);//获得非终结符个数intGetNumofT(charTerminate[]);//获得终结符个数intGetUTLoaction(charUnTerminate[],charc);//获得非终结符在非终结符表中的位置intGetTLocaction(charUnTerminate[],charc);//获得终结符在终结符表中的位置voidFirst(ProNodeproNode[],UnTInfounTInfo[]);//计算各非终结符的First集voidFollow(ProNodeproNode[],UnTInfounTInfo[]);//计算各非终结符的Follow集计算机科学与工程系8voidAddChar(charchArray[],charc);//将非终结符的所有first值加入First集voidAddCharToChar(charchArray[],charotherArray[]);//将非终结符的所有first集加入First集voidAddFollow(charfollow[],charc);//将非终结符的所有follow值加入Follow集boolIsNull(charc);//非终结符能否产生空字符boolIsTerminate(charc);//判断是否为终结符号voidSetSheet(ProNodeproNode[],UnTInfounTInfo[]);//设置分析表voidSetSelect(ProNodeproNode[],UnTInfounTInfo[]);//设置Select集合voidInputSym();//输入字符串函数voidScan();//分析扫描的主控程序charGetSym(LinkQueue&q);//获取下一字符voidPrintSym(SqStack&s);//显示符号栈符号voidPrintRemain(LinkQueue&q);//显示剩余符号串voidPrintSheet(introw,intcol);//显示所使用产生式voidSuccess();//分析成功voidmain(){charfileName[10];cout编制人：涂君兰，20042003，三班endl;计算机科学与工程系9cout请输入放有产生式的文件（如：pro.txt）:endl;cinfileName;ProNodeproNode[20];InitProNode(proNode,20);if(ReadPro(proNode,fileName)){/*输出文法产生式*/cout该文法产生式为：endl;PrintPro(proNode,proNum);/*设置非终结符表和终结符表*/SetUnTerminate(UnTerminate,proNode,proNum);SetTerminate(Terminate,proNode,proNum);/*输出First集*/intNumofUT=GetNumofUT(UnTerminate);intNumofT=GetNumofT(Terminate);UnTInfounTinfo[20];InitUnTInfo(unTinfo,20);/*输出First集*/First(proNode,unTinfo);/*输出Follow集*/Follow(proNode,unTinfo);/*设置select*/计算机科学与工程系10SetSelect(proNode,unTinfo);/*输出sheet*/coutendl分析表:endl;SetSheet(proNode,unTinfo);cout\t;for(intjj=0;jjNumofT;jj++)coutTerminate[jj]\t;coutendl;for(intmm=0;mmNumofUT;mm++){coutUnTerminate[mm]\t;for(intmn=0;mnNumofT;mn++){PrintSheet(mm,mn);cout\t;}coutendl;}InputSym();//输入字符串Scan();//主控程序}elseError();}计算机科学与工程系11voidInitProNode(ProNodeproNode[],intproNum){//初始化函数，对每个非终结符的产生式结构进行初始化for(inti=0;iproNum;i++){proNode[i].leftSym='\0';memset(proNode[i].midSym,0,Pro_MidSym_Max);memset(proNode[i].rightSym,0,Pro_RightSym_Max);proNode[i].length=0;}}voidInitUnTInfo(UnTInfounTInfo[],intunTInfoNum){//初始化函数，对每个非终结符的信息结构进行初始化for(inti=0;iunTInfoNum;i++){intfirLength=strlen(unTInfo[i].first);i