中南大学编译原理实验报告

中南大学编译原理

实验报告班级:计科1205姓名:赵越学号:0909122209实验ー词法分析程序设计与实现ー、实验目的加深对词法分析器的工作过程的理解;加强对词法分析方法的掌握;能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。二、实验内容自定义ー种程序设计语言,或者选择已有的・种高级语言,编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中,识别出各个具有独立意义的单词,即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”,然后跳过错误部分继续显示）三、实验要求:.对单词的构词规则有明确的定义；.编写的分析程序能够正确识别源程序中的单词符号；.识别出的单词以く种别码,值〉的形式保存在符号表中,正确设计和维护符号表;.对于源程序中的词法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺利完成整个源程序的词法分析；四、实验步骤.定义目标语言的可用符号表和构词规则；.依次读入源程序符号,对源程序进行单词切分和识别,直到源程序结束;.对正确的单词,按照它的种别以〈种别码,值〉的形式保存在符号表中；.对不正确的单词,做出错误处理。五、设计思路和实现过程本实验是词法分析器,我是用的是MFC实现的,我的设计思路就是按照书上提示的算法,先将儿个词法分析器所需的基本函数用C++的形式实现,然后使用循环语句读入输入串的每ー个字符,然后用if…else…语句实现,具体判断方式如下:1、如果读入的是字母,那么继续读入，知道读入的字符不是字母或者数字为止,对照标识符表,如果是标识符,则显示该串及对应标识符；如果不是,则显示该串和“$ID”；2、如果读入的是数字,则继续读入,知道不是数字为止,并显示该串和“$INT”；3、如果读入的是“则分别输出该串和"ASSIGN”，”$PLUS”,'SEMICOLON","$LPAR","$RPAR","$LBRACE","$RBRACE”；4、如果读入的是那么继续读入,如果下ー个是则输出该串和"$POWER〃;否则输出该串和‘'$STAR",并将指针回退;5、如果独到输入串末尾,则退出。六、错误处理创建一个键,如果读岀的字符不属于以上任何情况,则把此键置为真,通知程序退出循环,从而实现对错误的处理。七、关键代码voidCWordanalysisDlg::GetChar()(ch=minput.GetAt(pointer);pointer++;voidCWord_analysisDlg::Concat()(strToken+=ch;}voidCWord_analysisDlg::GetBC()(while(ch==1')GetChar();voidCWord_analysisDlg::Retract(){pointerーー;ch二’'；intCWordanalysisDlg::Reserve()(//if(strcmp(stricken,))inti;for(i=l;iく15;i++)if(strcmp(strToken,Token[i])==0)returni;return0;boolCWord_analysisDlg::IsLetter(){if(ch〉ニ'a'&&ch<='z'||ch>='A'&&ch<='Z')returntrue;elsereturnfalse;I7ヽboolCWordanalysisDlg::IsDigit(){if(ch>=O'&&ch<='9')returntrue;elsereturnfalse;voidCWord_analysisDlg::0nAnalysis()(//TODO:Addyourcontrolnotificationhandlercodeherem_list.DeleteAllItems();pointer=0;UpdateDataO;m_input+='\0';while(pointer<m_input.GetLength()-1)(if(end)break;Analysis();)voidCWord_analysisDlg::Analysis()strToken=;GetCharO;GetBC();if(IsLetterO){while(IsLetter()|IlsDigitO){ConcatO;GetCharO;}Retract();code=Reserve();if(code==0)(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,〃$ID");index++;return;)else(m_list.Insertltem(index,strToken);m_list.SetltemText(index,1,Token[code]);index++;return;elseif(IsDigit())(while(IsDigit()){Concat();GetCharO;}Retract();m_list.InsertItern(index,strToken);m_list.SetltemText(index,1,*$INT*);index++;return;)elseif(ch=='二’)Insertltem(index,strToken);mlist.SetltemText(index,1,"$ASSIGN");index++;return;)elseif(ch=='+')(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,"$PLUS");index++;return;)elseif(ch=='*')(GetCharO;if(ch=='*')(m_list,InsertItem(index,strToken);m_list.SetltemText(index,1,”$POWER〃)；index++;return;)else(Retract();(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,”$STAR");index++;return;)elseif(ch==';)lnsertltem(index,strToken);mlist.SetltemText(index,1,?z$SEMIC0L0N*);index++;return;)elseif(ch=='(')(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,*$LPAR#);index++;return;)elseif(ch==')')(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,*$RPAR/Z);index++;return;)else if(ch=='{')(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,ZZ$LBRACE/Z);index++;return;)elseif(ch=='}')(m_list.InsertItem(index,strToken);mlist.SetltemText(index,1,”$RBRACE");index++;return;)elseif(ch=='\0,)end=l;return;else(AfxMessageBox("出入错误”)；pointer=rainput.GetLengthO;return;)实验二LL(1)文法语法分析设计一.实验目的.熟悉判断LL(1)文法的方法及对某输入串的分析过程。.学会构造表达式文法的预测分析表。二.实验内容编写ー个语法分析程序,对于给定的输入串,能够判断识别该串是否为给定文法的句型。三.实验步骤从键盘读入输入串,并判断正误;若无误,由程序自动构造FIRST、FOLLOW集以及SELECT集合,判断是否为LL(1)文法;若符合LL(1)文法,由程序自动构造LL(1)分析表;由算法判断输入符号串是否为该文法的句型【源代码】#include“stdio.h"#include"stdlib.h"#defineMaxRuIeNum8defineMaxVnNum5defineMaxVtNum5defineMaxStackDepth20defineMaxPLength20defineMaxStLength50structpRNode/・产生式右部结构・/(intrCursor;/・右部序号・/structpRNode*next;｝；structpNode/・产生式结点结构*/(intICursor;/・左部符号序号・/intrLength;/・右部长度・//・注当rLength=1时,rCursor=T为空产生式・/structpRNode*rHead;/・右部结点头指针・/)；charVn[MaxVnNum+1];/*非终结符集・/intvnNum;charVt[MaxVtNum+1];/・终结符集・/intvtNum;structpNodeP[MaxRuIeNum];/・产生式・/intPNum;/・产生式实际个数・/charbuffer[MaxPLength+1];charch;/*符号或stringch;*/charst[MaxStLength];/*要分析的符号串・/structcolIectNode/・集合元素结点结构*/(intnVt;/・在终结符集中的下标・/structcolIectNode*next;);structcoIIectNode*first[MaxVnNum+1];"first集・/structcoIIectNode*follow[MaxVnNum+1];"follow集・/intanaIyseTabIe[MaxVnNum+1][MaxVtNum+1+1];"预测分析表存放为产生式的编号,+1用于存放结束符,多+1用于存放#(T)*/intanaIyseStack[MaxStackDepth+1];"分析栈・/inttopAnalyse;"分析栈顶・/"intreverseStack[MaxStackDepth+1];"颠倒顺序栈・/"inttopReverse;"倒叙栈顶・/voidInit();"初始化・/intIndexCh(charch);"返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,7表示未找到・/voidInputVt();"输入终结符・/voidInputVnO;/・输入非终结符・/voidShowChArray(char*collect,intnum);"输出Vn或Vt的内容・/voidInputP();/・产生式输入・/boolCheckP(char*st);/・判断产生式正确性・/voidFirst(intU);/・计算first集,LH>xx...*/voidAddFirst(intU,intnCh);"加入first集・/boolHaveEmpty(intnVn);"判断first集中是否有空(T)*/voidFollow(intV);"计算千〇IIow集・/voidAddFolIow(intV,intnCh,intkind);"加入follow集,kind=0表加入follow集,kind=1加入first集・/voidShowCoIIect(structcolIectNode**collect);"输出first或follow集・/voidFirstFollow()；/・计算first和folIow*/voidCreateAT();/・构造预测分析表・/voidShowAT();"输出分析表・/voidIdentify(char*st);"主控程序,为操作方便・/"分析过程显示操作为本行变换所用,与教程的显示方式不同・/voidInitStackO;/・初始化栈及符号串・/voidShowStack();/・显示符号栈中内容・/voidPop();"栈顶出栈・/voidPush(intr);/・使用产生式入栈操作・/#incIude"LL1.hvoidmain(void)chartodo,ch;Init();InputVn();InputVt();InputPO;getchar();FirstFollow();printf("所得first集为:");ShowCoIlect(first);printf(“所得follow集为:つ;ShowCoIlect(foIIow);CreateAT0;ShowAT();todo二'y'；whiIeCy*=todo)(printf("\n是否继续进行句型分析?(y/n):");todo=getchar();whileCy'!=todo&&'n'!=todo)(printf("\n(y/n)?");todo=getchar();}if('y'=todo)(inti;InitStackO;printf("请输入符号串(以#结束)：“)；ch=getchar();i=0;while，#'!=ch&&i<MaxStLength)(ifC'!=ch&&''n'!=ch)(st[i++]=ch;}ch=getchar();)ifC#'=ch&&i<MaxStLength)(st[i]=ch;Identify(st);eIseprintf("输入出错!\n");1}getchar();}voidInit()(inti,j;vnNum=0;vtNum=0;PNum=0;for(i=0;i<=MaxVnNum;i++)Vn[i]ハ(X;for(i=0;i<=MaxVtNum;i++)Vt[i]=](X；for(i=0;i<MaxRuleNum;i++)(P[i].ICursor=NULL;P[i].rHead=NULL;P[i].rLength=0;}PNum=0;for(i=0;i<=MaxPLength;i++)buffer[i]=1\0,;for(i=0;i<MaxVnNum;i++)(first[i]=NULL;follow[i]=NULL;)for(i=0;i<=MaxVnNum;i++)(for(j=0;j<=MaxVnNum+1;j++)analyseTable[i][j]=-1;)}/・返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,7表示未找到*/intIndexCh(charch)(intn;n=0;/*isVn?*/while(ch!=Vn[n]&&‘、〇’!=Vn[n])n++;ifC\0*!=Vn[n])return100+n;n=0;/*isVt?*/while(ch!=Vt[n]&&'、〇’!=Vt[n])n++;if('、〇'!=Vt[n])returnn;return-1;)/・输出Vn或Vt的内容・/voidShowChArray(char*collect)(intk=0;whiIe(''〇'!=collect[k])(printfC%c’、coIIect[k++]);}printf("'n");)/・输入非终结符・/voidInputVn()(intinErr=1;intn,k;charch;whiIe(inErr)(printf("'n请输入所有的非终结符,注意:“);printf("请将开始符放在第一位,并以#号结束:'n〃)；ch='';n=0;/・初始化数组・/whiIe(n<MaxVnNum)[Vn[n++]='\0';)n=0;while(('r!=ch)&&(n<MaxVnNum))(if(''!=ch&&''n'!=ch&&-1=IndexCh(ch))Vn[n++]=ch;vnNum++;ch=getchar()：)Vn[n]=，#，；/・以“ダ标志结束用于判断长度是否合法・/k=n;/*k用于记录n以便改Vn[n]='、0’*/if('#'!=ch)(if('#'!=(ch=getchar()))(while('#'!=(ch=getchar()))printf("\n符号数目超过限制!'n");inErr=1;continue;))/・正确性确认,正确则,执行下下面,否则重新输入・/Vn[k]='、〇';ShowChArray(Vn);ch='';while('y'!=ch&&'n'!=ch)Iif('\n"!=ch)Iprintf("输入正确确认?(y/n):");)scanf("%c”,&ch);)if('n'=ch)(printf("录入错误重新输入!'n");inErr=1;)eIse[inErr=0;/・输入终结符・/voidInputVt()(intinErr=1;intn,k;charch;while(inErr)(printf("\n请输入所有的终结符,注意:")；printf("以#号结束:、n");ch='';n=0：/・初始化数组・/whiIe(n<MaxVtNum)(Vt[n++]='\0';)n=0：while(C#'!=ch)&&(n<MaxVtNum))(ifC'!=ch&&'\n'!=ch&&-1=IndexCh(ch))(Vt[n++]=ch;vtNum++;)ch=getchar();)Vt[n]= ;/・以u#n标志结束・/k=n;/*k用于记录n以便改Vt[n]='、0'*/if('#'!=ch)(if('#'!=(ch=getchar()))(whileC#'!=(ch=getchar()))printf(''、n符号数目超过限制!、n");inErr=1;continue;))/*正确性确认,正确则,执行下下面,否则重新输入*/Vt[k]='、〇';ShowChArray(Vt);chゴ’；whileCy'!=ch&&'n'!=ch)(if('\n'!=ch)(printf("输入正确确认?(y/n):");}scanfぐ’％c",&ch);}ifCn*=ch)(printf("录入错误重新输入!'n〃)；inErr=1;1eIse(inErr=0;}}1/・产生式输入・/voidInputPO(charch;inti=0,n,num;printf(“请输入文法产生式的个数:")；scanf("%d",&num);PNum=num;getchar();/・消除回车符*/printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式:“，num);printf("\n");whiIe(iくnum)(printf("第%d个:“，i);/・初始化・/for(n=0;n<MaxPLength;n++)buffer[n]二‘、。';/・输入产生式串・/ch二',;n二。;while,'n'!=(ch二getchar())&&n<MaxPLength)(if(''!=ch)buffer[n++]二ch;)buffer[n]二，'〇';/*printf("%s",buffer);*/if(CheckP(buffer))(/・填写入产生式结构体・/pRNode*pt,*qt;P[i].ICursor二|ndexCh(buffer[0]);pt=(pRNode*)maIloc(sizeof(pRNode));pt->rCursor=IndexCh(buffer[3]);pt->next=NULL;P[i].rHead=pt;n=4;while(‘、〇’!=buffer[n])Iqt=(pRNode*)maIIoc(sizeof(pRNode));qt->rCursor=IndexCh(buffer[n]);qt->next=NULL;pt->next=qt;pt=qt;n++;}P[i].rLength=n-3;i++；/・调试时使用・/)eIseprintf(〃输入符号含非法在成分,请重新输入!、バ)；})/・判断产生式正确性・/booICheckP(char*st)(intn;if(100>IndexCh(st[0]))returnfalse;ifCコ!=stロ])returnfalse;ifO'!=st[2])returnfalse;for(n=3;'、〇'!=st[n];n++)(if(-1==IndexCh(st[n]))returnfalse;)returntrue;)/*=========ニニ=first&f〇||ow二======ニニニニニ二=ニニ*//・计算fjrst集,U->xx...*/voidFirst(intU)inti,j;for(i=0;i<PNum;i++)(if(P[i].ICursor=U)(structpRNode*pt;pt=P[i].rHead;j=0；while(j<P[i].rLength)(if(100>pt->rCursor)(/・注:此处因编程出错,使空产生式时rlength同样是!,故此处同样可处理空产生式・/AddFirst(U,pt->rCursor);break;)eIse(if(NULL=first[pt->rCursor-100])(First(pt->rCursor);)AddFirst(U,pt->rCursor);if(!HaveEmpty(pt->rCursor))(break;)eIse(pt=pt->next;))j++；)if(j>=P[i].rLength)/・当产生式右部都能推出空时・/AddFirst(U,-1);/・加入first集・/voidAddFirst(intU,intnCh)/・当数值小于100时nCh为Vt*//・当处理非终结符时,AddFirst不添加空项(-1)*/structcolIectNode*pt,*qt;intch;/・用于处理Vn*/pt=NULL;qt=NULL;if(nCh<100)(pt=first[U-100];whiIe(NULL!=pt)(if(pt->nVt==nCh)break;eIse(qt=pt;pt=pt->next;})if(NULL=pt)(pt=(structcollectNode*)maIIoc(sizeof(structcolIectNode));pt->nVt=nCh;pt->next=NULL;if(NULL=first[U-100])(first[U-100]=pt;}eIse(qt->next=pt;/*qt指向first集的最后ー个元素・/)pt=pt->next;eIse(pt=first[nCh-100];while(NULL!=pt)(ch=pt->nVt;if(-1!=ch)[AddFirst(U,ch);pt=pt->next;)/・判断first集中是否有空(T)*/booIHaveEmpty(intnVn)(if(nVn<100)/・为终结符时(含ー1),在follow集中用到・/returnfalse;structcolIectNode*pt;pt=first[nVn-100];whiIe(NULL!=pt)(if(-1==pt->nVt)returntrue;pt=pt->next;)returnfalse;I/・计算follow集,例:U->xVy,U->xV.(注:初始符必含#——"-1")*/voidFollow(intV){inti;structpRNode*pt;if(100=V)/・当为初始符时・/AddFollow(V,-1,0);for(i=0;i<PNum;i++)(pt=P[i].rHead;while(NULL!=pt&&pt->rCursor!=V)/・注此不能处理:Uー〉xVyVz的情况・/pt=pt->next;if(NULL!=pt)(pt=pt->next;/*V右侧的符号・/if(NULL=pt)/*当V后为空时Vー〉xV,将左符的follow集并入V的follow集中・/(if(NULL=follow[P[i].ICursor-100]&&P[i].ICursor!=V)(Follow(P[i].ICursor);}AddFoIIow(V,P[i].ICursor,0);)else/・不为空时Vー〉xVy,(注意:y-»»调用AddFollow加入Vt或y的first集・/(while(NULL!=pt&&HaveEmpty(pt->rCursor))AddFollow(V,pt->rCursor,1)：/*y的前缀中有空时,加如first集・/pt=pt->next;}if(NULL=pt)/・当后面的字符可以推出空时・/(if(NULL=follow[P[i].ICursor-100]&&P[i],ICursor!=V)(Follow(P[i].ICursor);)AddFoIIow(V,P[i].ICursor,0);}else/・发现不为空的字符时・/(AddFollow(V,pt->rCursor,1);))))}/・当数值小于100时nCh为Vt*//*#用T表示,kind用于区分是并入符号的first集,还是follow集kind=〇表加入follow集,kind=1加入first集・/voidAddFollow(intV,intnCh,intkind)(structcoIIectNode*pt,*qt;intch;/・用于处理Vn*/pt=NULL;qt=NULL;if(nCh<100)/・为终结符时・/Ipt=follow[V-100];while(NULL!=pt)(if(pt->nVt==nCh)break;eIse(qt=pt;pt=pt->next;}Iif(NULL=pt)pt=(structcolIectNode*)ma11oc(sizeof(structcolIectNode));pt->nVt=nCh;pt->next=NULL;if(NULL=follow[V-100])(follow[V-100]=pt;}eIseIqt->next=pt;/*qt指向follow集的最后ー个元素・/}pt=ptー〉next;))else/・为非终结符时,要区分是加first还是follow*/Iif(0=kind)(pt=follow[nCh-100]：whiIe(NULL!=pt)(ch=pt->nVt;AddFollow(V,ch,0);pt=pt->next;))eIse(pt=first[nCh-100];whiIe(NULL!=pt)(ch=pt->nVt;if(-1!=ch)(AddFoIIow(V,ch,1);)pt=pt->next;)/・输出first或follow集・/voidShowCo11ect(structcolIectNode**coIIect)structcolIectNode*pt;i=0；while(NULL!=collect[i])(pt=coIIect[i];printf("\n%c:\t",Vn[i]);whiIe(NULL!=pt)(if(-1!=pt->nVt)[printf("紀”,Vt[pt->nVt]);)eIseprintf("#");pt=pt->next;)i++；}printf("\n");)/・计算first和f011ow*/voidFirstFollow()(inti;i=0；whileC\0'!=Vn[i])(if(NULL=first[i])First(100+i);i++；]i=0;whileC\0'!=Vn[i])(if(NULL=follow[i])Follow(100+i);i++;}}/*==== ===构造预测分析表,例:U::xyz */voidCreateAT()(inti;structpRNode*pt;structcolIectNode*ct;for(i=0;i<PNum;i++)pt=P[i].rHead;whiIe(NULL!=pt&&HaveEmpty(pt->rCursor))(/・处理非终结符,当为终结符时,定含空为假跳出・/ct=first[pt->rCursor-100];whiIe(NULL!=ct)[if(-1!=ct->nVt)analyseTable[P[i],(Cursor-100][ct->nVt]=i;ct=ct->next;}pt=pt->next;)if(NULL=pt)(/*NULL=pt,说明xyz->,用到follow中的符号・/ct=follow[P[i].ICursor-100];whiIe(NULL!=ct)(if(-1!=ct->nVt)analyseTable[P[i],ICursor-100][ct->nVt]=i;else/・当含有#号时・/analyseTable[P[i],ICursor-100][vtNum]=i;ct=ct->next：))eIse(if(100<=pt->rCursor)/・不含空的非终结符・/(ct=first[pt->rCursor-100];whiIe(NULL!=ct)(analyseTable[P[i].ICursor-100][ct->nVt]=i;ct-ct->next;))else/・终结符或者空・/Iif(-1=pt->rCursor)/*-1为空产生式时・/ct=follow[P[i],ICursor-100];whiIe(NULL!=ct)(if(-1!=ct->nVt)analyseTable[P[i].ICursor-100][ct->nVt]=i;else/・当含有#号时・/analyseTable[P[i].ICursor-100][vtNum]=i;ct=ct->next;))else/・为终结符・/(analyseTable[P[i].ICursor-100][pt->rCursor]=i;)))))/*输出分析表・/voidShowAT()(inti,j;printf("构造预测分析表如下:'n");printf("\t|Vt");for(i=0;i<vtNum;i++)(printf("%c\t”,Vt[i]);1printf("#\t\n");printf \t| \t");for(i=0;i<=vtNum;i++)printfぐ’ \t");printf("\n");for(i=0;i<vnNum;i++)(printf("%c\tI\t",Vn[i]);for(j=0;j<=vtNum;j++)(if(-1!=analyseTable[i][j])printf("R(%d)\t",analyseTable[i][j]);elseprintf("error、ピ);)printf("\n");))/*============主控程序=============*/voidIdentify(char*st)(intcurrent,step,r;/*r表使用的产生式的序号・/printf("\n%s的分析过程:、n”,st);printf("步骤ゝt分析符号栈、t当前指示字符、t使用产生式序号、n");step=0;current=0;/・符号串指示器・/printf("%d\t”,step);ShowStack();printf(z/\t\t%c\t\t \n”,st[current]);while。#'!=st[current])(if(100>anaIyseStack[topAnaIyse])/・当为终结符时・/(if(anaIyseStack[topAnaIyse]=IndexCh(st[current]))(/・匹配出栈,指示器后移・/Pop0;current++;step++;printf("%d\t”,step);ShowStack();printf("\t\t%c\t\t出栈、后移、n〃,st[current]);eIse(printf("%c-%c不匹配!”，anaIyseStack[topAnaIyse],st[current]);printf(〃此串不是此文法的句子!'n");return;11else/・当为非终结符时・/(r=anaIyseTabIe[anaIyseStack[topAnaIyse]-100][IndexCh(st[current])];if(-1!=r)(Push(r);/・产生式右部代替左部,指示器不移动・/step++;printf("%d\t",step);ShowStack();printf(，，\t\t%c\t\t%d\n，，1st[current],r)：1else(printf("无可用产生式,此串不是此文法的句子!'n");return;)))if('#'==st[current])(if(O==topAnaIyse&&'#'=st[current])(step++;printfぐ‘％d\t”,step);ShowStack();printf("\t\t%c\t\t分析成功!\n”,st[current]);printf("%s是给定文法的句子!'n”,st);eIse{while(topAnaIyse>0){if(100>anaIyseStack[topAnaIyse])/・当为终结符时・/{ printf(“无可用产生式,此串不是此文法的句子!'n〃)；return;1eIse{r=anaIyseTabIe[anaIyseStack[topAnaIyse]-100][vtNum];if(-1!=r){Push(r);/・产生式右部代替左部,指示器不移动・/step++;printf("%d't",step);ShowStack();if(0==topAnaIyse&&'#'=st[current]){printf("'t't%c't't分析成功!'n”,st[current]);printf("%s是给定文法的句子!'n”,st);)eIseprintf("\t\t%c\t\t%d\n",st[current],r); }eIse{printf(〃无可用产生式,此串不是此文法的句子!'n");return;}1)))/*初始化栈及符号串・/voidInitStack()Iinti;/・分析栈的初始化・/for(i=0;i<MaxStLength;i++)st[i]=[0,；analyseStack[O]=-1;/*#(-1)入栈*/analyseStack[1]=100;/・初始符入栈*/topAnaIyse=1;)/・显示符号栈中内容*/voidShowStack(){inti;for(i=0;i<=topAnaIyse;i++){if(100<=analyseStack[i])printf(，z%cz，,Vn[anaIyseStack[i]-100]);eIse{if(-1!=anaIyseStack[i])printf(/z%czz,Vt[anaIyseStack[i]]);elseprintf(/z#zz);11)/・栈顶出栈*/voidPop(){topAnaIyse—;1/・使用产生式入栈操作・/voidPush(intr){inti;structpRNode*pt;Pop()；pt=P[r].rHead;if(-1==pt->rCursor)/・为空产生式时・/return;topAnaIyse+=P[r].rLength;for(i=0;i<P[r].rLength;i++){/・不为空产生式时・/anaIyseStack[topAnaIyse-i]=ptー〉rCursor;/・逆序入栈*/pt-pt->next;レ・循环未完时pt为空,则说明rLength记录等出错・/四.实验结果请辆人所有的非终结符,汪怠:请将开始存放在弟一包,幵以4号结兎:SHMAttSHNA输入正确确认?<y/n>：V输入正确确认?<y/n>：y请输入所有的终结符,注意:以苗号结束:adbe输入正破确认?(y/n):y看输入受法产生式的个数」漬输入文法的7个产生式，并以回车分隔每个产生式:第0个:S->aH第1个:H->aMd第2个:H->d第3个:M->Ab第4个:M->第5个:A->aM第6个:A->e所得£i»st集为:所得fol103集为:adbeItSR<0>errorerrorerrorerrorR<1>R<2>errorerrorerrorMR<3>R<4>R<4>R<3>errorAR<5>errorerrorR<6>errory■■是构造预测分析表如下:SHMA请输入符号串（以・结束）:■N的，分析过程,步彝 分析符号栈 当前指示字符 使用产生式序号无可用产生式,此串不是此文法的句子!是否继续进行句型分析?<y/n>：<y/n>?V<y/n>?<y/n>?y请输入符号串（以・结束）:aaabdttaaabd*的分;步骤则..栈程号过符当前指示字符使用产生式序号。 USa——1 UHca02 MHa出栈、后移3 ItdMaa14 ttdh1a出栈、后移5 ttdbAa36 ttdbMaa57 ttdbMb出栈、后移8 Vdl)b4dユ0 nA中氯易物UabdJt是ム定文法的句子!n分柝战功!是否继续进行句型分析?<y/n>：五.实验总结通过这次的实验,我深入了解了词法分析器和LL（1）文法预测分析法设计和实现,增强了我的自学能力和独立思考能力,也让我对程序设计有了更大的兴趣,自己通过查找资料、复习课本、编程调试，写实验报告等环节,进ー步掌握了以前学到的知识，并且还对编译原理应用有了更深入的认识与掌握。在完成这个程序后，真的很开心，也了使我解到编译原理的魅カ所在，激发了我要解决更多更难问题的决心。实验ーLR分析器设计与实现第一章概述本课程设计完成了以下内容:.实现了对任意给定的文法G,识别文法活前缀的OE4、。必的状态转化矩阵及ムマ(0)项目集规范族的构造;.判断该文法是否为厶Z?(0)文法,实现了以?(0)分析表的构造,并输出到指定文件中;.实现了厶/?(0)分析器总控程序,对输入的表达式进行文法分析。第二章 设计的基本原理本课程设计的核心算法”主要有三点:L识别文法活前缀的OFA、。必的状态转化矩阵及ムR(0)项目集规范族的构造;2.厶/?(0)分析表的构造;3.厶7?(0)分析器总控程序的构造。识别文法的LR(O)项目集规范族的构造采用e-QLOSURE(闭包)的构造ー个文法G的ムZ?(0)项目规范簇。假定，是文法G，的任一项目集,定义和构造，的闭包。厶。SURE")的算法:/的任何项目都属于CLOSURE^)；(2)若A-aB0属于CLOSURE⑴,那么,对任何关于5的产生式8fア,项目8fア也属于CLOSURE(I)；(3)重复执行上述两个步骤直至CLOSURE^)不再增大。其中初始，={S，fE},5，为对文法G进行拓广构造G,而引进的不出现在G中的非终结符。定义状态转换函数GO,GO(/,X)的第一个变元/是一个项目集,第二个变元X是ー个文法符号。函数值GO(/,X)定义为GOa,X)=CLOSURE(1/)。其中J={任何形如AfaXタ的项目丨AraXタ属于/}LR(O)分析表的构造假定C={/°,ム,…/“}。令每个项目集ム的下标作为分析器的状态。特别是,令那个包含项目S->S的集合人的下标k为分析器的初态。分析表的AC77ON子表和GOT。子表可按如下方法构造:(1)若项目Afa。タ属于ム且GO(4，a)=/,，a为终结符,则置ACTIONlk©为“把(j,a)移近栈”,简记为“5ノ”。(2)若项目Afa属于/*,那么对于任何终结符a(或结束符#),置AC77ON伙,a］为“用产生式Afタ进行规约”,简记为“ゲ(假定产生式Afa是文法G"的第j个产生式)⑶若项目SIS属于/*,则置AC77ON伙,a］为“接受”,简记为“acc”。(4)若GO(/*,A)=ム,则置ACTION伙,A］=j.(5)分析表中凡不能用规则1〜4填入信息的空白处均置上“报错标志”。如果分析表中任何ー项被重复填入，则说明分析表的入口不是唯一的,项目集中存在冲突项目，该文法不是厶R(0)文法。LR(O)分析器总控程序构造ムR(0)分析表包括量部分，“动作”AC77ON表和“状态转换”GOTO表。ん。7y。y中,0规定了当状态5面临输入符号。时应采取什么动作。GOTO［s,X］规定了状态s面对文法符号X时下ー状态是什么。每ー项ACTION［s,a］所规定的动作不外乎是下述四种可能之ー。(1)移进把(s,a)的下一状态s，=GOTQs,X］和输入符号。推进栈,下ー输入符号变成现行输入符号。(2)归约指用某ー产生式A-タ进行规约。假若月的长度为「,规约的动作是,去除栈顶的r个项,使状态s,〜变成栈顶状态,然后把0-4)的下ー状态『=GOTO［s吁八川推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。(3)接受宣布分析成功,停止分析器工作(4)报错发现源程序含有错误,调用出错处理程序。第三章 程序设计程序总体构架本课程设计开发的程序主要由4张表组成,分别为:符号表Sig〃一List、产生式表Formula_List>L/?(0)表LRO_Table和项目集规范簇表Closure_List〇同时,项目集规范簇表包含ー个分析栈作为ムZ?(0)分析器总控程序。产生式表包含符号表作为子表,项目集规范簇表包含产生式表、ZJ?(O)表作为子表。程序工作流程:.读取含有文法规则的文件，为该文法中的每一个不同的文法符号(终结符和非终结符分配ー个编号),记录文法符号的属性(终结符/非终结符)，存储于ー,张符号表Sign_List中;.再次读取文件,将产生式存储于产生式表ド。/厶ぶ中;.根据产生式构建厶Z?(0)项目集规范族,存储于表Closure_List中;.根据构建的ン?(0)项目集规范族构建厶/?(0)分析表,填写厶/?(0)分析表同时检查该文法是否为厶Z?(0)文法;.对于输入的表达式，レ?(0)分析器根据构建的n?(0)分析表进行文法分析,给出分析结果。

程序存储结构符号表存储结构Ararry_Index动态数组下标,同时作为符号的编号Identity标识符Is_Vn是否为非终结符产生式表存储结构Formula_Num产生式标号Vn_Name非终结符标号（与Sign_Lisi中的Ararry_Index一致）Formula指示当前非终结符V〃ーName的产生式Formula_Length当前非终结符い〃ーName产生式的长度,用于帮助区分一个产生式的不同项目,即项目个数等于Formula_Length+1Next_Vn指示下ー个非终结符Sign_Name一个产生式中的标识符名（与Sign_List中的Ararry_Index一致）Next_Signー个产生式中的下ー个标识符1)定义二兀组:Item_Name_Type=<Formula_Num,Formula_Item>Formula_Num:产生式标号,与Formula一List中的Formula_Num一致Formula_Item:ー个产生式的第,个项目,可由Z7。ケ%か。_Lis/中的Formula_Length帮助确定如:产生式Wー>E：W->E<1,1>,W->E<1,2>Closure_List结构:Current_State当前状态编号Next_State指示下一状态Item指示闭包中的项目Item_Name闭包中的项目名Destination当前项目的GotoSet产生的新状态的编号,即状态转移的目的地状态编号Next_Item闭包中的下ー个项目GoToSet_Parent待构造的GoTo项目的闭包的ParentGoToSet_Child待构造的GoTo项目的闭包Current_Parent待构造状态的ParentCurrent_Child待构造状态的项目LRQ_Table_Child指示表头的孩子结点LRO_Table_Parent指示表头的后继结点Operation指示该表项的操作Oprand指示该表项的操作数Has_Been_Filled指示该表项是否被填写过,用于判断文法是否为レ?(0)文法3.3程序算法3.1项目集规范族的构造(初始化)将初始条件作为该状态头结点的第一个孩子结点,并构造该孩子结点的闭包,连接其后,GoToSejPare〃，指向第一个状态头结点,GoToSet_Child指向第一个状态头结点的第一个孩子结点;查看GoToSet_Parent,若为空,停止;若不为空,转3；查看GoToSet_Child,若为空，转4；若不为空,构造GoToSef_C/n/"的GoToSet,检査该状态与之前构造的状态有无重复,若重复,则停止构造,GoToSerー。J〃イ的。esガ〃両沁〃填写重复的已存在的状态的编号；若不重复,则作为ー个新状态,连接于arre〃f_Pare而，并构造其闭包连接其后，GoToSet_Child指向Next_State。转2；GoToSet_Pare〃，指向下ー状态,若下一状态为空,则结束,否则,GoToSet_Child指向下ー状态头结点的第一个孩子结点,转3〇具体细节:设GoToSer_C7n7d所指项目为<，">,因为要对其构造闭包,该项目一定不是终态，所以区分项目的圆点符号位于第，个标识符的左侧。现在构造<"/>的闭包,分两个步骤实现:.构造GoToSet_Child的GoToSet：查看Formula_Length中编号为i的产生式，取得该产生式的长度属性Formula_Length若j之Formula_Length+1,则停止构造当前闭包（已是终态）,此时GoToSet_Child的Destination项填ー1;2）否则,将+ 作为该闭包的第一个项目设机,此时GoToSejCが，d的Destination项填该新状态的状态编号。.构造该孩子结点的闭包:查看Formula_List中编号为i的产生式的第，+1个标识符,取得该标识符的Sign_Name,查看Sign_Lisi中该标识符的类别属性/3）若为1（非终结符）,则查看ドorm”ルーLisf非终结符Sig”的所有产生式,记这些产生式的编号为Sig〃.,将所有的<Sign_Name_i,1>加入闭包4）否则,结束.检查该状态与之前构造的状态有无重复:断言:任意两个状态,只要G%5々不同,则即为不同状态。3.3.2LR（O）分析表构造对于编号为，•的状态,现依据其项目＜「国〉填写ン?（0）分析表:.如果该项目形如Xf…丫…,查看该项目的Destination属性,k=Destinationi）若丫为终结符,则在表的状态，对应行,对应列,填写s*,表示将把伏,わ移进栈2）若y为非终结符,则在表的状态i对应行,’「对应列，填写ス,表示状态转移至え状态.如果该项目形如xfy1）若ド为起始符号,则置在表的状态i对应行,#对应列,填写acc,表示接受。2）否则,对任何终结符或结束符#,则在表的状态i对应行,’「对应列,填写（,表示用产生式p进行规约。第四章程序测试以文法G为例:W-£E^aAElbBAfcAAfdBtcBBid程序模块输入:含上述文法的文件,下面展示个模块的输出结果1符号表测试continue11010100k01234567ooooooooNNNNNNNNPcontinue11010100k01234567ooooooooNNNNNNNNP输出F-3KWJZr4-H3443(=1图6符号表测试与预期结果相同产生式表测试drC：\VmOYS\systea32\cad.exe|e<w>ー）!《e〉1<E>->2<a>3<A>1<E>>>4<b>5<B>3<A>->6<c>3<A>□<A>->7<d>5<B>->6<c>5<B>5<B>->7<d>?i*essanykeytocontinue...图7产生式表测试输出结果与读入的文件中的产生式相同,且产生式中符号的编号正确项目集规范族表测试 e01r012345678911P・>yeXZ1KZVZ10H11__k! e01r012345678911P・>yeXZ1KZVZ10H11__k!14711-11-，，**********33y1222322322，,n**********46a1123245367くく<<<<<<<<<<s::s<4,1,5>,く<4,1,5>く6,1，8>.tocont

输出结果为く状态编号〉:く产生式编号,产生式项目编号,项目转移的目标状态〉与预期结果相同LR(0)分析表测试,|D|x|state计010020

ard006926539746ssrsrrsrrrC005825538746ssrsrrsrrrB0001

0001000

gb300020530746srrrrrr0

A004001000000

state计010020

ard006926539746ssrsrrsrrrC005825538746ssrsrrsrrrB0001

0001000

gb300020530746srrrrrr0

A004001000000

9gtoa200020530746

s1*rrrrrynsse0000000000r图9レ?(0)分析表测试输出结果为厶/?(0)分析表,与预期结果相同LR(O)分析器测试以输入字符串acccd#和acad#为例|caC：\fIID0fS\syste»32\cad.exeLccdttNoerrorfoundacadtterrorat3pressanykeytocontinue.表达式的分析结果正确第五章 总结和展望完成了编译原理课程设计之后,我感到十分的疲惫,但是那ー份富有成就感的欣喜却胜过了那十分的疲惫。由于本次选题匆忙,选了一道比较有难度的题目,在做课程设计的过程中,我翻阅了很多相关资料,对课本中点到即止的知识进行了更加深入的学习,有了更加深入的理解。做课程设计的过程是痛苦的,我在这ー个星期内多次熬夜战斗,有时甚至顾不上吃饭,只为了揪出程序中的错误,只为了精益求精的完成这个课程设计。就在我写这份总结的时候,我发现自己我ー点也不累了,反而很兴奋,很有成就感。通过本次课程设计，我发现实践是检验学习深度、学习成果的唯一途径，课本上的知识点都是浓缩的精华,在理论阐述上不可能做到面面俱到,学到的知识当然也不可能直接运用到实际情况上。在实践的过程中,我们需要将我们学习到的知识进行ー定程度的扩充,本次课程设计涉及到算法,LR分析器自动构造程序的机制原理以及C++语言。在用C++语言实现本次课程设计的过程中,我更加熟悉了C++语言的语法机制，语言规范;在实现LR分析器自动构造程序的过程中,我更加熟悉了其构造程序的原理以及与之相关的算法。由于时间匆忙,我完成的课程设计还有很多不足之处,很多工作还可以继续完善，在提交作业之后,我不会把它放在那里一看不看的,我会继续完善它,让它更加人性化,具有可操作性,比如做个可视化的界面出来,丰富它的功能,相信以后的工作将更加多彩丰富,更加有成就感!参考文献[1]陈火旺,刘春林,谭庆平,赵克佳,刘越程序设计语言编译原理国防エ业出版社2006[2]谭浩强C++程序设计清华大学出版社2007附录说明:本附录中包含了本次课程设计的所有代码ClosureList.h#ifndefCLOSURE_LIST_HttdefineCLOSURE，IST_H#include"FormulaList,h”#include"LR0_Table.h"structItem_Name_Type{intFormula_Num;intFormula_Item;};structClosure_ChiIdNode(Item_Name_TypeItemName;intDestination;Closure_Child_Node*Next」tem;};structClosure_Parent_Node(intCurrent_State;C1osure_Parent_Node*Next_State;C1osure_Chi1d_Node*Item;};classClosureListprivate:C1osure_Parent_Node*Closure_List_head;Closure_Parent_Node*GoToSet_Parent;ClosureParentNode*CurrentParent;Closure_Child_Node*GoToSet_ChiId;ClosureChildNode*Current_Child;intAmountOfState;Formula_Listsub_Formula_List;LROTablesubLROTable;public:ClosureList():subFormulaList(),subLROTable()(Closure_List_head=NULL;GoToSetParent=NULL;Current_Parent=NULL;GoToSetChild=NULL;Current_Child=NULL;AmountOf_State=0;Create_Closure_List(););、Closure_List();voidprint_Closure_List();voidmake_LR0_Table();voidprintLROTable();voidOutput_LRO_Table_ToFile();boolSentence_Analyse(constcharSentence[50]);private:voidAdd_Clousure();boolAddGoToSet();voidSet_Initial_State();voidCreate_Closure_Ust();boolIs_Same_State_Exist(constintFormula_Num,constintFormula」tem,int&Same_State_Num);voidDestroy_Closure_List();};#endifFormula_List.h#ifndefFORMULALISTII^defineFORMULA，IST_H#include*Sign_List.h*structFormulaListChilditem(intSignName;Formu1a_List_Childltem*Next_Sign;)；structFormulaListParentitem(intFormulaNum;intVn_Name;intFormulaLength;Formu1a_List_Parentitem*Next_Vn;FormulaListChilditem*Formula;}；classFormula_List{private;Formu1a_List_Parentltem*Formu1a_List_head;Formula_List_ChiIdltern*current_Formula_Itern;Formula_List_ParentItem*current_VnNode;Sign_ListSub_Sign_List;public:Formula_List():Sub_Sign_List()(Formu1a_List_head=NULL;current_Formula_Item=NULL;current_VnNode=NULL;Create_Formula_Ust(););Formula_List();voidprint_Formula_List();intint_checkSignName(constcharword);charchar_check_Sign_Name(constintSign_Name);intGetFormulaLength(constintFormulaNum);intGet_Sign_Name(constintFormula_Num,constintItem_Num);intGetFormulaLeftVn(constintFormulaNum);boolIs_Sign_Name_Vn(constintSignName);intGetAmountOf_Identity();private:voidDestroy_Formula_List();voidCreateFormulaList0;｝；ttendifLR0_Table.h#ifndefLROTABLE_H^defineLRO_TABLE_H#include<iostream>#include<fstream>usingnamespacestd;^include"ConstValue.h"structLRO_Table_Child(charOperation;intOprand;boolHas_Been_Filled;LRO_Table_ChiId*Next_Table_ChiId;｝；structLR0_Tab1e_Parent(LRO_Table_Child*Table_Child;.RO_Table_Parent*Next_Tab1e_Parent;｝；classLR0_Tableprivate:LROTableParent*LROTablehead;LRO_Table_Parent*Current_Parent;LROTableChild*CurrentChild;public:LROTable0;"LRO_Table();voidinitial(constintAmountOfState,constintAmountOfIdentity);boolFill_In_Table(constintState_Num,constintIdentity_Num,constcharcharOpration,constintintOprand);void_OutputToFile();voidprintLROTableO;voidVisit_LRO_Tab1e(constintState_Num,constintIdentity_Num,char&charOpration,int&intOprand);private:voidDe