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

《中南大学编译原理实验报告.pdf》由会员分享，可在线阅读，更多相关《中南大学编译原理实验报告.pdf（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中南大学编译原理实验报告班级：计科1205姓名：赵越学号:0909122209实验一词法分析程序设计与实现一、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用-种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。二、实验内容自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“E r r o r”，然后跳过错

2、误部分继续显示）三、实验要求：1 .对单词的构词规则有明确的定义；2 .编写的分析程序能够正确识别源程序中的单词符号；3.识别出的单词以种别码，值 的形式保存在符号表中，正确设计和维护符号表；4 .对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；四、实验步骤1 .定义目标语言的可用符号表和构词规则；2 .依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束;3 .对正确的单词，按照它的种别以种别码，值 的形式保存在符号表中；4 .对不正确的单词，做出错误处理。五、设计思路和实现过程本实验是词法分析器，我是用的是M F C实现的，我

3、的设计思路就是按照书上提示的算法，先将儿个词法分析器所需的基本函数用C+的形式实现，然后使用循环语句读入输入串的每一个字符，然后用i f e l s e语句实现，具体判断方式如下：1、如果读入的是字母，那么继续读入，知道读入的字符不是字母或者数字为止，对照标识符表，如果是标识符，则显示该串及对应标识符；如果不是，则显示该串和“$I D ；2、如果读入的是数字，则继续读入，知道不是数字为止，并显示该串和“$I N T”；3、如果读入的是“=则分别输出该串和 A S S I G N ，“$P L U S ,$S E M I C O L O N ,$L P A R”,$R P A R ,$L B R

4、 A C E ,$R B R A C E；4、如果读入的是“*，那么继续读入，如果下一个是“*，则输出该串和$P O W E R”；否则输出该串和“$S T A R”,并将指针回退；5、如果独到输入串末尾，则退出。六、错误处理创建一个键，如果读出的字符不属于以上任何情况，则把此键置为真，通知程序退出循环，从而实现对错误的处理。七、关键代码1、v o i d CWo r d an al y s i s Dl g:Get Ch ar()(ch=m _i n p u t.Get At(p o i n t er);p o i n t er+;2、v o i d CWo r d _an al y s i

5、 s Dl g:Co n cat O(s t r To k en+=ch;)3、v o i d CWo r d _an al y s i s Dl g:Get BC()(w h i l e(ch=,)Get Ch ar ();4、v o i d CWo r d _an al y s i s Dl g:Ret r act()p o i n t er一；ch二 ；5、i n t CWo r d an al y s i s Dl g:Res er v e()/i f(s t r cm p(s t r To k en,)i n t i;fo r(i=l;i =，a&ch=A&ch=O&ch=9)r e

6、t u r n t r u e;el s er et u r n fal s e;8、v o i d CWo r d _an al y s i s Dl g:0n An al y s i s()(/TODO:Ad d y o u r co n t r o l n o t i fi cat i o n h an d l er co d e h er em _l i s t.Del et eAl l I t em s();p o i n t er=0;Up d at eDat aO;m _i n p u t+=，0;w h i l e(p o i n t er xx.*/void AddFi rs

7、t(i n t U,in t n Ch);/*加入 f i rst 集*/bool HaveEmpty(in t n Vn);/*判断 f i rst 集中是否有空(T)*/void Fol Iow(in t V);/*计算 fol low 集*/void AddFol Iow(i n t V,in t n Ch,i n t kin d);/*力 口 入 fol low 集,kin d=0 表加入 fol low 集，kin d=1 加入 f i rst 集*/void ShowCo I I ect(struct co I I ectNode*col lect);/*输出 f i rst 或

8、fol low 集*/void Fi rstFoI Iow();/*计算 f i rst 和 fol Iow*/void CreateAT();/*构造预测分析表*/void ShowAT()；/*输出分析表*/void Iden tify(char*st);/*主控程序，为操作方便*/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/void In itStackO；/*初始化栈及符号串*/vo i d ShowStack()；/*显示符号栈中内容*/void Pop();/*栈顶出栈*/void Push(in t r);/*使用产生式入栈操作*/#in clude LL1.hvo

9、 i d ma i n (vo i d)char todo,ch;I n i t();In putVn ();I n putVt();In putPO;getchar();Fi rstFol low();pr 所得 fi rst 集为：);ShowCoI Iect(fi rst);pr in tf(所得 follow 集为：“);ShowCoI Iect(foI Iow);CreateAT();ShowAT();todo 二，y，；whi Ie(*y*=todo)(prin tf(n是否继续进行句型分析?(y/n):)；todo 二 getchar();whileCy !二 todo&n !二

10、 todo)(prin tfrn(y/n)?)；todo=getchar();Jif(y =todo)in t i;In itStack();prin tf(请输入符号串(以#结 束)：)；ch=getchar();i =0;while，#!=ch&i MaxStLen gth)(if(!=ch&n !=ch)(sti +=ch;)ch 二 getchar();)if，#，=ch&i MaxStLen gth)(sti=ch;Iden tify(st);)e I sepr in tf(输入出错！n );)1getchar();)void In it()(in t i,j;vn Num=0;vt

11、Num=0;PNum=0;for(i=0;i =MaxVn Num;i+)Vn i二，(T;for(i=0;i =MaxVtNum;i+)Vti二，(T;for(i=0;i MaxRuleNum;i+)(Pi.ICursor 二 NULL;Pi,rHead=NULL;Pi.rLen gth=0;)PNum=0;for(i=0;i =MaxPLen gth;i+)bufferi=0;for(i=0;i MaxVn Num;i+)(firsti=NULL;followi=NULL;)for(i =0;i =MaxVn Num;i+)(for(j=0;j=MaxVn Num+1;j+)an alys

12、eTablei j=-1;)/)*返回Vn 在 Vn 表中的位置+100、Vt在 Vt表中的位置，7表示未找到*/i n t In dexCh(char ch)(i n t n;n =0;/*i s Vn?*/whi le(ch!=Vn n&0 !=Vn n)n+;iff Of!=Vn n)return 100+n;n =0;/*is Vt?*/whi le(ch!=Vtn&0 !=Vtn)n+;if(0 !=Vtn)return n;return -1;)/*输出Vn 或 Vt的内容*/void ShowChArray(char*collect)in t k=0;while(0 !=col

13、lectk)(pr i n tf C%c”,co I Iectk+);)pr in tf Cn，z)；)/*输入非终结符*/vo i d I n putVn ()i n t i n Err=1;i n t n,k;char ch;whiIe(i n Err)(pr in tf(n 请输入所有的非终结符，注意：)；pr in tf(请将开始符放在第一位，并以#号结束:n )；ch 二，；n =0;/*初始化数组*/whiIe(n MaxVn Num)(Vn n+=0;)n =0;whi Ie(*#*!=ch)&(n MaxVn Num)(ifC !=ch&n !=ch&-1=In dexCh(c

14、h)(Vn n+=ch;vn Num+;ch=getchar();)Vn n=，铲；/*以“#”标志结束用于判断长度是否合法*/k=n;/*k用于记录n以便改Vn n=0*/ifC#!=ch)(if(!=(ch=getchar()(whiIe C#!=(ch=getchar 0)prin tf(n 符号数目超过限制！n );i n Err=1;con t i n ue;)/*正确性确认，正确则，执行下下面，否则重新输入*/Vn k=0;ShowChArray(Vn);ch=，;while(y !=ch&n !=ch)(if C n !=ch)(pr in tf(“输入正确确认？(y/n):);

15、)scan f(%c”,&ch);)if C n =ch)(pr i n tf(录入错误重新输入！n );i n Err=1;)e I se(i n Err=0;)/*输入终结符*/vo i d I n putVt()(in t in Err=1;i n t n,k;char ch;while(in Err)prin tf(n请输入所有的终结符，注意：”)；pri n tf(以#号结束：n );ch=，;n =0;/*初始化数组*/whiIe(n MaxVtNum)(Vtn+=0;)n =0;whiIe(C#!=ch)&(n MaxVtNum)(if(,!=ch&n !=ch&-1=In de

16、xCh(ch)(Vtn+=ch;vtNum+；)ch=getchar();)Vtn /*以“#”标志结束*/k=n;/*k用于记录n以便改Vtn=。*/if(#!=ch)(if(#!=(ch=getchar()(whiIeC#!=(ch=getchar()pri n tf(n符号数目超过限制！n );in Err=1;con tin ue;)/*正确性确认，正确则，执行下下面，否则重新输入*/Vtk=0;ShowChArray(Vt);ch=;whi Ie(y !=ch&n !=ch)ifC n !=ch)(pr in tf(输入正确确认？(y/n):);scan f(%c”,&ch);ifC

17、 n =ch)(prin tf(录入错误重新输入！n );i n Err=1;)else(i n Err=0;)/*产生式输入*/void In putPO(char ch;in t i =0,n,n um;prin tf(请输入文法产生式的个数：”)；scan f(，z%d，z,&n um);PNum=n um;getchar();/*消除回车符*/pri n tf(n 请输入文法的%d j 产生式，并以回车分隔每个产生式：，n um);prin tf C V7)；wh i Ie(i n um)(pr in tf(第%d 个：，i);/*初始化*/for(n =0;n MaxPLen gth

18、;n+)buffern =0;/*输入产生式串*/ch 二，；n =0;while,n !=(ch=getchar 0)&n rCursor=In dexCh(buffer3);pt-n ext=NULL;Pi.rHead=pt;n =4;whileC O !=buffer n)(qt=(pRNode*)ma I Ioc(s i zeof(pRNode);qt-rCursor=In dexCh(buffern);qt-n ext=NULL;pt-n ext=qt;pt 二 qt;n+;)Pi.rLen gth=n -3;i+；/*调试时使用*/)elseprin tf(输入符号含非法在成分，请

19、重新输入！n)；)/*判断产生式正确性*/bool CheckP(char*st)(in t n;if(100 In dexCh(st0)return false;ifC-!=st1)return false;if C !=St2)return false;for(n =3;0 !=st n ;n +)(if(-1=In dexCh(st n)return false;)return true;)/*=f i rst&f o I I ow=*/*计算 f i rst 集,U-xx.*/void Fi rst(in t U)in t i,j;for(i=0;i PNum;i+)if(Pi.ICu

20、rsor=U)(struct pRNode*pt;pt=Pi.rHead;J=0;whiIe(j pt-rCursor)(/*注:此处因编程出错,使空产生式时r len gth同样是1,故此处同样可处理空产生式*/AddFi rst(U,pt-rCursor);break;)e I se(i f(NULL=f i rstpt-rCursor-100)(F i rst(pt-rCursor);)AddF i rst(U,pt-rCursor);if(!HaveEmpty(pt-rCursor)(break;)e I se(pt=pt-n ext;)j+；)if(j=Pi.rLen gth)/*当

21、产生式右部都能推出空时*/AddFirst(U,-1);)/*加入first集*/vo i d AddF i rst(i n t U,i n t n Ch)/*当数值小于 100 时 n Ch 为 Vt*/*当处理非终结符时,AddFi rst不添加空项(T)*/struct col I ectNode*pt,*qt;i n t ch;/*用于处理Vn*/pt=NULL;qt=NULL;if(n Ch n Vt=n Ch)break;e I se(qt=pt；pt=pt-n ext;)if(NULL=pt)(pt=(struct collectNode*)ma I Ioc(s i zeof(s

22、truct col I ectNode);pt-n Vt=n Ch;pt-n ext=NULL;i f(NULL=firstU-100)firstU-100=pt;e I se(qt-n ext=pt;/*qt指向fi rst集的最后一个元素*/)pt=pt-n ext;)e I se(pt=firstn Ch-100;while(NULL!=pt)(ch=pt-n Vt;if(-1!=ch)AddFirst(U,ch);)pt=pt-n ext;/*判断first集中是否有空(7)*/boo I HaveEmpty(i n t n Vn)(if(n Vn n Vt)return true;p

23、t=pt-n ext;)return false;)/*计算fol low集,例：U-xVy,U-xV.(注:初始符必含#void Fol Iow(in t V)in t i ;struct pRNode*pt;if(100=V)/*当为初始符时*/AddFol low(V,-1,0);for(i=0;i rCursor!=V)/*注此不能处理:U-xVyVz 的情况*/pt=pt-n ext;if(NULL!=pt)(pt=pt-n ext;/*V 右侧的符号*/if(NULL=pt)/*当 V 后为空时V-xV,将左符的fol low集并入V 的 fol low集中*/if(NULL=fo

24、llowPi,ICursor-100&Pi.ICursor!=V)(Follow(Pi.ICursor);)AddFoI Iow(V,Pi.ICursor,0);)else/*不为空时V-xVy,(注意：y-,调用AddFol low加入Vt或 y 的 fi rst集*/while(NULL!=pt&HaveEmpty(pt-rCursor)AddFol low(V,pt-rCursor,1);/*y 的前缀中有空时，加如 first 集*/pt=pt-n ext;if(NULL=pt)/*当后面的字符可以推出空时*/(if(NULL=followPi.(Cursor-100&Pi.ICurs

25、or!=V)Follow(Pi.ICursor);)AddFollow(V,Pi.ICursor,0);)else/*发现不为空的字符时*/(AddFollow(V,pt-rCursor,1);)/*当数值小于100时n Ch为Vt*/*#m T表示,kin d用于区分是并入符号的first集，还是follow集kin d=0 表加入 fol low 集，kin d=1 加入 first 集*/void AddFollow(in t V,in t n Ch,in t kin d)struct col I ectNode*pt,*qt;in t ch;/*用于处理Vn*/pt=NULL;qt=N

26、ULL;i f(n Ch n Vt=n Ch)break;e I se(qt=pt;pt=pt-n ext;)i f(NULL=pt)pt=(struct col I ectNode*)ma I Ioc(s i zeof(struct col I ectNode);pt-n Vt=n Ch;pt-n ext=NULL;i f(NULL=followV-100)(followV-100=pt;)e I se(qt-n ext=pt;/*qt指向fol iow集的最后一个元素*/)pt=pt-n ext;)else/*为非终结符时,要区分是加first还是fol low*/(if(0=kin d)

27、(pt=follown Ch-100;while(NULL!=pt)(ch=pt-n Vt;AddFol low(V,ch,0);pt=pt-n ext;)e I se(pt=f i rstn Ch-100;while(NULL!=pt)(ch=pt-n Vt;if(-1!=ch)(AddFol low(V,ch,1);)pt=pt-n ext;)/*输出 f i rst 或 fol low 集*/void ShowCoI Iect(struct col I ectNode*co11ect)i n t i;struct col I ectNode*pt;i =0;while(NULL!=col

28、lecti)pt=collecti;prin tf(n%c:t,Vn i);whiIe(NULL!=pt)(if(-1!=pt-n Vt)(pr i n tf(,%c”,Vt pt-n Vt);e I seprin tff#);pt=pt-n ext;)i+；)prin tf(n );)/*计算 f i rst 和 fo I I ow*/void Fi rstFol low()(i n t i;i =0;whi le(0 !=Vn i)(i f(NULL=firsti)First(100+i);i+；)i =0;whi leC 0 !=Vn i)(if(NULL=followi)Fol low

29、(100+i);i+；)/*=构造预测分析表,例：U:xyz=*/vo i d CreateAT()i n t i;struct pRNode*pt;struct co I I ectNode*ct;for(i=0;i rCursor)(/*处理非终结符，当为终结符时，定含空为假跳出*/ct=f i rstpt-rCursor-100;while(NULL!=ct)(i f(-1!=ct-n Vt)an alyseTablePi.I Cursor-100ct-n Vt=i;ct=ct-n ext;)pt=pt-n ext;)if(NULL=pt)(/*NULL=p t,说明xyz-,用到fol

30、low中的符号*/ct=followPi.ICursor-100;while(NULL!=ct)(if(-1!=ct-n Vt)an alyseTablePi.ICursor-100ct-n Vt=i;else/*当含有#号时*/an alyseTablePi.ICursor-100vtNum=i;ct=ct-n ext;)e I se(if(100 rCursor)/*不含空的非终结符*/(ct=fi rstpt-rCursor-100;while(NULL!=ct)(an alyseTablePi.ICursor-100ct-n Vt=i;ct=ct-n ext;)else/*终结符或者空

31、*/if(-1=pt-rCursor)/*-1 为空产生式时*/ct=followPi.ICursor-100;while(NULL!=ct)(i f(-1!=ct-n Vt)an alyseTablePi.ICursor-100ct-n Vt=i;else/*当含有#号时*/an alyseTablePi.ICursor-100vtNum=i;ct=ct-n ext;)else/*为终结符*/(an alyseTablePi.ICursor-100pt-rCursor=i;)/*输出分析表*/void ShowAT()in t i,j;1.prin tf(构造预测分析表如下：n );prin

32、 tf(t|t);for(i=0;i vtNum;i+)prin tf(%ct”,Vti);)prin tf r#tn );2.prin tf(-t|-t);for(i =0;i =vtNum;i+)pr i n tf(-t);prin tf rn，z);3.for(i=0;i vn Num;i+)(prin tf(%ct|t”,Vn i);for(j=0;j an a I yseStack topAn a I yse)/*当为终结符时*/(i f(an a IyseStacktopAn aIyse=In dexCh(st curren t)(/*匹配出栈，指示器后移*/PopO;curren

33、 t+;step+;pr i n tf(%dt”,step);ShowStack();prin tf(tt%ctt 出栈、后移n，st curren t);else(pr in tf(，z%c-%c z，,an a I yseStack topAn a I yse,st curren t);prin tf(此串不是此文法的句子！n)；return;)else/*当为非终结符时*/(r=an a IyseTabIean a IyseStack topAn aIyse-100In dexCh(st curren t);if(-1!=r)(Push(r);/*产生式右部代替左部，指示器不移动*/st

34、ep+;pr i n tf step);ShowStack();pr i n tf(，tt%ctt%dn，f st curren t,r);)else(pri n tf(无可用产生式，此串不是此文法的句子！n )；return;)if(#=二 st curren t)(5.if(O=topAn alyse&#=st curren t)(step+;pr i n tf(%dt，step);ShowStack();prin tf(tt%ctt 分析成功!n ,st curren t);prin tf(%s是给定文法的句子！n，z,st);)e I se while(topAn aIyse 0)if

35、(100 an a I yseStacktopAn a Iyse)/*当为终结符时*/prin tf(无可用产生式，此串不是此文法的句子！n )；return;)e I se r=an a IyseTabIe an a IyseStacktopAn aIyse-100vtNum;if(-1!=r)Push(r);/*产生式右部代替左部，指示器不移动*/step+;pr i n tf step);ShowStack();i f(0=topAn aIyse&#=stcurren t)pr in tf 分析成功！n”,st curren t);pr in tf(%s是给定文法的句子！n ,st);1

36、e I sepr i n tf(z，tt%ctt%dn，z,st curren t,r);e I se prin tf(无可用产生式，此串不是此文法的句子！n )；return;)/*初始化栈及符号串*/vo i d I n itStack()i n t i ;/*分析栈的初始化*/for(i=0;i MaxStLen gth;i+)sti二，0,;an alyseStack 0=-1;/*#(-1)入栈*/an alyseStack1=100;/*初始符入栈*/topAn aIyse=1;/*显示符号栈中内容*/vo i d ShowStack()I in t i;for(i=0;i =to

37、pAn aIyse;i+)if(100 rCursor)/*为空产生式时*/return;topAn aIyse+=Pr.rLen gth;for(i=0;i rCursor;/*逆序入栈*/pt=pt-n ext;/*循环未完时Pt为空,则说明rLen gth记录等出错*/四.实 验 结 果隔辆人折用的非终结伶，汪蕙：请将开始存放在弟一位，开以#号箔束:SHMAttS H M A抽入正确确认?：输入正确确认?(n：y请输入所有的终结符，注意：以。号结束：adbea d b e输入正确确认?aH：H-aMd：H-d：M-Ab：M-sA-aM：A-e区得f a s t集为SS：aH：a dn：a

38、 e t tA：a e所得fol low集为：S：t tH:t tM:d b,造预测界析表如下:adbet tsRerrorerrorerrorerrorRRerrorerrorerrornRRRRerrorARerrorerrorRerror睛输入符号串 以#结束)析过程：分析符号栈当前指示字符使用产生式序号0 its ff无可用产生式，此串不是此文法的句子!是否继续进行句型分析？：?Yy/?y请输入符号串 以#结束：aaabdit戋当前指示字符 使用产生式序号0 ttSa 1ttHaa02M Ha出栈、后移3ttdMaa14ttdMa出栈、后移5ttdbAa36ItdbMaa57ttdbM

39、b出栈、后移8ttdbb49ttdd粮、后孩tttt11n分柝一功!aaabd#是给定文法的句子！是否继续进行句型分析？：/n?五.实 验 总 结通过这次的实验，我深入了解了词法分析器和LL(1)文法预测分析法设计和实现，增强了我的自学能力和独立思考能力，也让我对程序设计有了更大的兴趣，自己通过查找资料、复习课本、编程调试，写实验报告等环节，进一步掌握了以前学到的知识，并且还对编译原理应用有了更深入的认识与掌握。在完成这个程序后，真的很开心，也了使我解到编译原理的魅力所在，激发了我要解决更多更难问题的决心。实验一 LR分析器设计与实现第一章 概 述本课程设计完成了以下内容：1.实现了对任意给定

40、的文法G,识别文法活前缀的。必、O E 4的状态转化矩阵及LR(O)项目集规范族的构造；2.判断该文法是否为LR(O)文法，实现了 LR(O)分析表的构造，并输出到指定文件中；3.实现了 LR(O)分析器总控程序，对输入的表达式进行文法分析。第二章 设计的基本原理本课程设计的核心算法主要有三点：1.识别文法活前缀的。4、O E 4 的状态转化矩阵及L R(O)项目集规范族的构造；2.L R(O)分析表的构造；3.L/?(0)分析器总控程序的构造。2.1 识别文法的L R(O)项目集规范族的构造采用-C L O S U R E (闭包)的构造一个文法G的L R(0)项目规范簇。假定/是文法G，的

41、任一项目集，定义和构造/的闭包C L O S U R E。)的算法：(1)/的任何项目都属于C L O S U R E )：(2)若A -a B 0属于CLOSURED),那么，对任何关于8的产生式8 f y ,项目8 f/也属于C L O S U R E。)；(3)重复执行上述两个步骤直至CLOSURED)不再增大。其中初始/=S，f E ,为对文法G进行拓广构造G，而引进的不出现在G中的非终结符。定义状态转换函数G O,G O(/,X)的第一个变元/是一个项目集，第二个变元X是一个文法符号。函数值GOQ,X)定义为GO(/,X)=CLOSURE(J)。其 中J=任何形如A-a X 夕的项目

42、|A-a X 夕属于/2.2 L R(0)分析表的构造假定C =/“。令每个项目集人的下标作为分析器的状态。特别是,令那个包含项目S f S的集合4的下标Z 为分析器的初态。分析表的ACTION子表和G O T O子表可按如下方法构造：(1 )若项目4 f a破 属 于 且 6。区,。)=乙，。为终结符，则置ACTIONk,G为“把行移近栈”,简 记 为“S J。(2)若项目4-a属于人，那么对于任何终结符a (或结束符#),置ACTIONS,a为“用产生式A fa进行规约”，简记为“。”(假定产生式A fa是文法G，的第j 个产生式)若 项 目 SIS属于4,则置A C 7 7 O N 伏为

43、“接受”，简记为“a c c”。(4)若G O 4,A)=/，则置A C 7 7 O N 伏,川=人(5)分析表中凡不能用规则1 4 填入信息的空白处均置上“报错标志”。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是LR(O)文法。2.3 LR(O)分析器总控程序构造LR(O)分析表包括量部分，“动作 A C 7 7 O N 表 和“状态转换”G O T O表。ACTIONS,a规定了当状态s 面临输入符号a时应采取什么动作。G O T O S X 规定了状态s 面对文法符号X时下一状态是什么。每一项ACTION s,a所规定的动作不外乎是下述四

44、种可能之一。(1)移进 把(s,a)的下一状态s，=G O T O s,X 和输入符号a 推进栈，下输入符号变成现行输入符号。(2)归约 指用某一产生式4 万进行规约。假若尸的长度为r,规约的动作是，去除栈顶的厂个项，使 状 态 变 成 栈 顶 状 态，然后把(s,4)的下一状态=3。7 0 6“_,知推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。(3)接受宣布分析成功，停止分析器工作(4)报错发现源程序含有错误，调用出错处理程序。第三章 程序设计3.1 程序总体构架本课程设计开发的程序主要由4张表组成，分别为：符号表S i g L M、产生式表 Formula _ List

45、 L/?(0)表 LRO_Table 和项目集规范簇表 Closure_ List。同时，项目集规范簇表包含一个分析栈作为L&(0)分析器总控程序。产生式表包含符号表作为子表，项目集规范簇表包含产生式表、LR(O)表作为子表。程序工作流程：1.读取含有文法规则的文件，为该文法中的每一个不同的文法符号(终结符和非终结符分配一个编号)，记录文法符号的属性(终结符/非终结符)，存储于一张符号表Sign _ List中；2 .再次读取文件，将 产 生 式 存 储 于 产 生 式 表 中；3 .根据产生式构建LR(O)项目集规范族，存储于表中；4.根据构建的Z J?(O)项目集规范族构建LR(O)分析表

46、，填写LR(O)分析表同时检查该文法是否为LR文法；5 .对于输入的表达式，LR(O)分析器根据构建的LR(O)分析表进行文法分析，给出分析结果。3.2程序存储结构3.2.1符号表存储结构Ararry _ Index动态数组下标，同时作为符号的编号Identity标识符Is_Vn是否为非终结符3.2.2产生式表存储结构Formula _ Num产生式标号Vn _ Name非终结符标号（与Sign _ List中的Ararry _ Index 一致）Formula指示当前非终结符丫Name的产生式Formula _ Length当前非终结符丫产生式的长度，用于帮助区分一个 产 生 式 的 不 同

47、 项 目，即 项 目 个 数 等 于Formula _ Length+1Next _ Vn指示下一个非终结符Sign _ Name一 个 产 生 式 中 的 标 识 符 名（与 Sign _ L ist中的Ararry _ Index 1致）Next _ Sign一个产生式中的下一个标识符3.2.3项目集规范族表存储结构1)定 义 二 兀 组：Item _ Name _ Type=Formula _ Num：产生式标号，与 Formula _ List 中的 Formula _ Num 一致Formula _ Item：一 个 产 生 式 的 第/个 项 目，可 由/。七行 中的Formula

48、 _ Length 帮助确定如：产生式 W-E ：W-E ,W-E 2)Closure _ List 结构：Current _ State当前状态编号Next _ State指示下一状态Item指示闭包中的项目Item _ Name闭包中的项目名Destination当前项目的GotoSet产生的新状态的编号，即状态转移的目的地状态编号Next _ Item闭包中的下一个项目GoToSet _ Parent待构造的GoTo项目的闭包的ParentGoToSet _Child待构造的GoTo项目的闭包Current _ Parent待构造状态的ParentCurrent _ Child待构造状态

49、的项目3.2.4 LR(O)分析表存储结构LRO _Table _Child指示表头的孩子结点LRO _ Table _ Parent指示表头的后继结点Operation指示该表项的操作Oprand指示该表项的操作数Has _ Been _ Filled指示该表项是否被填写过，用于判断文法是否为LR(0)文法3.3程序算法3.3.1 项目集规范族的构造1 .(初始化)将初始条件作为该状态头结点的第一个孩子结点，并构造该孩子结点的闭包，连接其后，Go T o S e j P a r e 而指向第一个状态头结点，GoToSet_ Child指向第一个状态头结点的第一个孩子结点；2 .查看GoToS

50、eJ Parent,若为空，停止；若不为空，转 3；3.查看GoToSet_Child,若为空，转 4；若不为空，构造Go T o S e f _。?以的GoToSet,检查该状态与之前构造的状态有无重复，若重复，则停止构造，GoToSet_Child的Destination填写重复的已存在的状态的编号；若不重复，则作为一个新状态，连接于P a r e”/,并构造其闭包连接其后，GoToSet _ Child 指向 Next _ State。转 2 ；4.Go T o S e f _ P a r e n t指向下一状态，若下一状态为空，则结束，否贝U,GoToSet_Child指向下一状态头结