编译原理课程设计LR语法分析构造器的设计

1、前言计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术，编译原理技术是计算机科学中发展的最迅速、最成熟的一个分支，它集中体现了计算机发展成果与精华。未来计算机工作者，都应该掌握这门基础的专业基础知识。“编译原理”是计算机及其相关专业的重要专业基础课，主要研究设计和构造编译程序的原理和方法。全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技。编译原理蕴涵着计算机学科中解决问题的思路、形式化问题和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启

2、发和指导作用，编译程序构造的原理和技术在软件工程、语言转换等许多领域中有着广泛应用。语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子，目前语法分析常用的方法有自顶向下分析和自顶向上分析两大类。自顶向上分析包括确定分析和不确定分析，自顶向上分析又包括算符优先分析和lr分析。鉴于此，运用这些分析方法构造一个简单的分析程序是很有实践意义的。目 录编译原理课程设计任务书 .3第1章 概述.5 1.1 背景.5 1.2 目的.5 1.3 软件定义.51.4 开发环境.5第2章 需求分析.6 2.1 问题陈述.6 2.2 需完成的功能.6第3章 逻辑设

3、计. 7 3.1 模块设计.7 3.1.1 lr（1）项目集规范族的构造算法.8 3.1.2 lr（1）分析表的构造算法.8 3.2 流程图.9第4章 总体设计.15 4.1 构造项目集规范族模块.15 4.2 构造预测分析表模块.15 4.3 分析串程序模块.15第5章 界面设计.16小结.33致谢.34参考文献.35 附录 源程序清单.36编译原理课程设计任务书1、本课题的目的及意义课程设计实践对学生巩固所学基础专业课程知识、进行编译系统基本技能训练、培养实践动手能力，从而掌握编译系统的基本工作原理、基本方法和基本开发技术，最终达到具有一定的编译系统的实际开发能力有重要意义。通过课程设计，

4、主要达到以下目的：1.帮助学生深入理解编译原理的有关理论和巩固编译原理相关知识。2. 巩固学生学习的编译原理、程序设计语言、数据结构等课程的基础知识，训练学生分析和解决编译系统的相关问题的能力，提高学生的综合素质。3. 从软件工程的角度来看，编译原理课程设计是一个很好的实例，可以训练学生软件设计的能力以及编码调试能力。2、本课题任务的主要内容本课程设计主要内容包括以下几点:1、根据选定的题目，查阅资料，熟悉相关理论、方法；（1）掌握文献检索方法，以获得编译系统开发技术等相关资料；（2）学习并熟练使用一种4gl开发平台（如vc+、java、dephi、pb、vb等）；2、分析问题，确定系统逻辑结

5、构；3、确定系统所需模块及模块结构，并用流程图描述各模块；4、编码及调试程序；5、撰写课程设计说明书。3、提交的成果1、一份符合课程设计说明书撰写规范的课程设计说明书。2、一套系统原型。附录一：课程设计说明书撰写要求1、基本要求：（1）能反映完成了设计内容要求；（2）要求撰写不少于5000个文字（20页）的文档；（3）文档中至少要包括：数据流图、逻辑结构图、系统功能图、算法流程图。（4）用户界面设计：附界面的抓图或手工绘图，及其主要核心部分代码。2、文档格式要求（参考课程设计参考模板）（1）封面（2）前言（3）目录（4）课程设计任务书（5）正文（分章、层次等，每一章从新一页开始）概述 包括项目

6、背景、编写目的、软件定义、开发环境等内容。需求分析 问题陈述、需完成的功能。以数据流图和数据字典表达。逻辑设计 描述系统组织和基本工作流程。以总体逻辑结构图表达。总体设计 画出软件功能图，描述每一个功能所完成的任务情况。界面设计 界面设计要合理，给出主要界面和主要代码并有适当的说明。（6）小结（7）参考文献对于引用的参考文献，列出主要参考文献（至少10篇）的题录及摘要或参考文献原文。（8）其他图表原始资料或参考资料附录第1章 概述1.1 背景“编译原理”是计算机及其相关专业的重要专业基础课，主要研究设计和构造编译程序的原理和方法。全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分

7、析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、目标代码生成。语法分析是整个编译程序的核心部分，而lr分析方法对文法要求比起其他分析方法能力较强lr（k）分析方法是1965年knuth提出的，括号中的k表示向右查看输入串符号的个数。这种方法比起自顶向下的ll（1）分析方法和自低向上的优先分析方法对文法的限制要少的多，也就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的lr分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。自低向上分析的关键问题是在分析过程中如何确定句柄。lr分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表

8、示）和向右顺序查看输入串的k个（k0）符号就可惟一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一地确定句柄。lr分析法的归约过程是规范推到的逆过程，所以lr分析过程是一种规范归约的过程。1.2目的因为lr（0）分析过程中不需要向右查看输入符号，因而它可以对文法的限制较大，对绝大多数的高级语言的语法分析器是不能适用的，所以，要分析绝大多数的高级语言编译程序的需要，采用向后查看一个输入符号的方法，即lr（1）的方法。（1）掌握并深刻理解有穷自动机在lr分析法中的应用（即lr分析器）。（2）掌握lr分析法的思想，学会特定分析表的构造方法，利用给出的分析表进行lr分析。1.3 软件

9、定义对任意给定的上下文无关文法g，构造其lr（1）项目集规范族、预测分析表，并且在此基础上进一步构造其lr（1）分析表。1.4 开发环境软件：windows 7操作系统 , microsoft visual c+ 6.0；编程语言：c+第2章 需求分析2.1问题陈述设计的题目是要对lr（1）类文法判定及其分析器进行构造。如果一个文法的lr（1）分析表不含多重入口时，（即任何一个lr（1）项目集中无移进归约冲突或归约归约冲突），则称该文法为lr（1）文法，所构造的相应分析表称为lr（1）分析，使用lr（1）分析表的分析器称为lr（1）分析器或称规范的lr分析器。所以，要判断一个文法是否是lr（1

10、）类文法，则主要是看是否存在两个冲突。2.2 需完成的功能一个lr分析器由3个部分组成：（1）总控程序：也可以成为驱动程序。对所有的lr分析器总控程序都是相同。（2）分析表或分析函数：不同的文法分析表将不同，同一个文法采用的lr分析器不同时，分析表也不同，分析表又可分为动作（action）表和状态转换（goto）表两个部分，它们都可用二维数组表示。（3）分析栈：包括文法符号栈和相应的状态栈。它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定（lr(0)分析器不需要向前查看输入符号）。综上所述，要实现本次设计所需工作主要有以下方面：1、 构造项目集规范族；2、 构造预测分析表；3、

11、 设计总控程序，完成分析过程。第3章 逻辑设计3.1 模块设计 lr分析器工作过程示意图如图1.1所示。其中sp为栈指针，si为状态栈，xi为文法符号栈。状态转换表内容按关系gotosi,x=si确定，该关系式是指当栈顶状态为si，遇到当前文法符号为x时应转向状态sj。x为终结符或非终结符。 actionsi,a规定了栈顶状态si时遇到输入符号a应执行的动作。动作有4种可能：（1） 移进： 当si=gotosi,a成立，则把si移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。spsns1xnnx1x0s0. 总控程序action表goto表输入串xxxxxxxx#输出图1-1 lr分

12、析器工作过程示意图（2） 归约： 当在栈顶形成句柄为时，则用归约为相应的非终结符a，即当文法中有a的产生式，而的长度为r（即|=r），则从状态和文法符号栈中自顶向下去掉r个符号，即栈指针sp减去r。并把a移入文法符号栈内，再把满足sj=gotiosi,a的状态移入状态栈，其中si为修改指针后的栈顶状态。（3） 接受acc： 当归约到文法符号栈中只剩文法的开始符号s时，并且输入符号串已结束即当输入是#，则为分析成功。（4） 报错： 当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法所能接受的句子。lr分析器的关键部分是分析表的构造。构造lr分析表，那么先解决lr项目

13、集规范族的构造。 lr项目集规范族的项目类型分为如下四种：1、 移进项目圆点后为终结符的项目，形如aa，其中、v*，avt，相应状态为移进状态。2、 规约项目圆点在产生式右部的最后的项目，形如a其中v*，对于=的项目为a（对应的产生式为a），相应状态为归约状态。3、待约项目圆点后为非终结符的项目，形如ab，其中、v*，bvn，这表明用产生式a的右部归约时，首先要将b的产生式右部归约为b，对a的右部才能继续进行分析。也就是期待着继续分析过程中首先能进行归约得到b。4、接受项目当归约项目为ss时则表明已分析成功，即输入串为该文法的句子，相应状态为接受状态。3.1.1 lr（1）项目集规范族的构造算

14、法以ss，#属于初始项目集中，把“#”号作为向前搜索符，表示活前缀为（若是有关s产生式的某一右部）要归约成s时，必须面临输入符为“#”号才行。我们对初始项目ss，#求闭包后再用转换函数逐步求出整个文法的lr（1）项目集族。具体构造步骤如下：（1） 构造lr（1）项目集的闭包函数。 假定i是一个项目集，i的任何项目都属于closure(i)。 ab，a属于closure(i)，b是文法中的产生式，若有项目v*，bfirst(a)，则b，b也属于closure(i)中。 重复直到closure(i)不再增大为止。（2） 构造转换函数。lr（1）转换函数的构造与lr（0）的相似，go（i，x）= c

15、losure(j)其中i是lr（1）的项目集，x是文法符号：j=任何形如lr（1）分析表的构造ax，a的项目| ax，a i对文法g的lr（1）项目集族的构造仍以ss，#为初态的初始项目，然后对其求闭包和转换函数，直到项目集不再增大。3.1.2 lr（1）分析表的构造算法由于一个lr（1）项目可以看成两个部分组成，一部分和lr（0）项相同，这部分称为心，另一部分为向前搜索符合集。因而lr（1）分析表的构造与lr（0）分析表的构造在形式上基本相同，只是归约项目的归约动作取决于归约项目的向前搜索符集，即只有当面临的输入符属于向前搜索符的集合，才做归约动作，其他情况均出错。具体构造过程如下：若已构造

16、出某文法的lr（1）项目集族c。c=i0，i1，.，in其中的ik的k为分析器的状态，则动作action表和状态转换goto表构造方法如下：(1) 若项目aa，b属于ik，且go（ik，a）=ij，其中avt，则置actionk，a=sj。其sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈。(2) 若项目a，a属于ik，则置actionk，a=rj，其中avt，rj的含义为把当前栈顶符号串归约为a（即用产生式a归约）。j为在文法中对产生式a的编号。(3) 若项目ss，#属于ik，则置action，=“”，表示接受。(4) 若（ik，），其中avn ，则置gotok，a=j。表示转入j

17、状态，则置当前文法符号栈顶为a，状态栈顶为j。(5) 凡不能用规则（1）（4）填入分析表中的元素，均置“报错标志”。可以填入空白以表示。3.2 流程图图1-2(a) 构造lr（1）项目集规范族流程图图1-2（b） 构造lr（1）项目集规范族流程图图1-2（c） 构造lr（1）项目集规范族流程图图1-3 构造lr（1）分析表流程图1-4 lr（1）串分析程序流程图第4章 总体设计功能设计为能实现本次课程设计的功能，同时减小工作量，根据需求，构造lr（1）项目集规范族需要用到first集，主要思路是采用替换策略以及删除重复的元素。数据结构使用的是链表。这不是核心部分，所以不再赘述。将功能分为三个大

18、模块，即构造项目集规范族、分析表、和分析串程序。以下是对构造项目集规范族、分析表、和分析串程序的设计叙述：4.1 构造项目集规范族模块项目集规范族是整个设计的基础。数据结构：实现其构造，在数据结构选用方面要求能够方便查找、而且能够节省空间。据此，主要采用了c+中stl中队列、集合、向量，作为主要数据存放的容器，并用结构体存放重要产生式的重要信息。算法设计：由课本上关于构造项目集规范族的叙述，联想到了图的广度遍历，所以将扩展后的文法ss,#作为核放在队列中，由核求闭包，每求出一个就放入集合中（主要是可以去除重复的）如果插入集合成功，就把结构体插入向量中，插入队列中，直到队列空，说明由核产生的项目

19、已经构造完，下一步只需从向量中取出项目进行闭包运算，直到把向量中所有元素取完，这样就可以把整个规范族求出。程序流程主要是一个while循环和switch语句控制。4.2 构造预测分析表模块预测分析是分析过程的依据。数据结构：用的是结构体存放数据，数据信息主要包括：action表，当前输入符、是移进还是归约的控制符号，归约的产生式编号和移进的状态。goto表，遇到的非终结符、转到的状态号。算法设计：这里主要是查找，利用上一步求出的项目集规范族，找出输入符号以后所转向的状态，或者是归约的产生式编号。4.3 分析串程序模块 分析串程序是最终功能的具体表示。数据结构：用的是两个先进先出栈，即状态栈和符

20、号栈，另外还用一个string类型输入串。算法设计：根据预测分析表，开始时把0压入状态栈，把#压入符号栈中，根据状态栈的栈顶元素和输入串的串首字符两个线索，在分析表中查找，找到相应的动作，并实现。如果找到，则继续分析，否则，说明该输入串是不能接受的。根据题目需要，还要判断是否是lr（1）文法，我们知道一个二义性文法绝不是lr类文法，对于这一功能也以与实现。主要的实现方法是通过分析表，如果分析表里有两个入口，也就是存在两个冲突，那么就说明不是。第5章 界面设计 图1-5 开始界面输入产生式文件代码如下：void main() void first(struct vn pv2,int i,sq f

21、irst,int c,char s2,char vn1); int find(pseqstack s,sq st,int v); void dels(sq st,int i);void project_set(char vn1,int c,struct set2 select,string ft); int forecast_analyse(char vn1,int c);/进行预测分析 int i,n,t,h=0,j=0,c=0,l;char vn,t=; pl s1;string ft10; pseqstack s;sq first20,p;char vn120,string20,scan

22、out20,s22=-,; file *fp; pv1=pv;pv4=pv2; s=init_seqstack(); cout t * 说明 *n t *本系统设计了一些产生式分别存放在 *n t * 以下文件中：1.txt,f.txt,h.txt *n t *in.txt,l.txt,l2.txt,ll.txt,lr.txt *n t *wd.txt结果输出存放在文件result.txt*n t *中，请用户按照上述文件名书写规范进*n t *行操作使用 *n t * 制作人：计算机071 李亚龙 *n t *欢迎使用*n t *=*n; printf(请输入所用产生式的文件名：); sca

23、nf(%s,scanout);if(fp=fopen(scanout,r)=null)printf(n打开文件出错了!n);exit(0);getchar(); s22=0; cout 所用的文法是：endl; while(fgets(string,20,fp)!=null&!feof(fp)/从文件读入产生式 coutlength,s1 ); strinsert(pv2t.p, pv2t.p-length,s1 ); h+; vn1c=0; fclose(fp);/ 图1-6 构造出产生式项目集规范族代码如下：void project_set(char vn1,int c,struct se

24、t2 select,string ft)queuequ;/队列item product_item70;/小集合容器setitem_set;/大集合vectorvt; container pi,pi3,pi150,product_it;vectorpi2;int i,j,k,n,n1,z=1,v=-1,l=0,q=0,q1=0,flat=0;static f=0;char ch;bool bl;string str,str1,str2,str3;item_container product1,product2,product3; fstream of;product1.s=.s;product1

25、.s2=0;product1.pcode=0;product1.front=#;product1.go=s;product1.point_pos=0;product1.vn=s;product_itemq.insert (product1.vn+-+product1.s+,+product1.front);qu.push(product1); pi.push_back(product1); pi1q1.push_back(product1);while(flat!=100) switch(flat)case 0:if(!qu.empty() product2=qu.front();/队首元素

26、qu.pop();/删除队首元素 if(isvn(vn1,product2.go,c)/判断点后是否为非终结符 k=0; for(i=0,n=0;product2.sproduct2.point_pos+1!=vn1i;n+=pv2i.tag,i+);/找到非终结符的下标 k=pv2i.tag;/该非终结符的产生式个数n1=n;for(j=0;j+product1.s+,+product1.front).second=true)qu.push(product1);pi.push_back(product1);pi1q1.push_back(product1); flat=0; else fla

27、t=1; break;case 1: bl=item_set.insert(product_itemq).second; if(bl=true) f+; pi2.push_back(pi1q1); if(!vt.empty()flat=3;elseif(vq|v=f)/flat=100;else flat=2; v+;break; case 2: if(vq|v=f)flat=100;else i=0; for(vector:iterator it=pi2.begin();iv;it+,i+); product_it=*it; for(vector:iterator vi=product_it

28、.begin();vi!=product_it.end();vi+) vt.push_back(*vi).vn+-+(*vi).s+,+(*vi).front); flat=3; break;case 3: str=vt.back(); vt.pop_back(); flat=4; break; case 4:for(vector:iterator vc=pi.begin();vc!=pi.end();vc+)/找到str对应的产生式 product3=*vc; if(product3.vn+-+product3.s+,+product3.front)=str&product3.go!=$&p

29、roduct3.go!=) ch=product3.go; str2=product3.s; str2.replace(product3.point_pos,1,1,product3.go); product3.point_pos+=1; str2.replace(product3.point_pos,1,1,.); product3.s=str2; if(product3.sproduct3.point_pos+1=0) product3.go=$; else product3.go=product3.sproduct3.point_pos+1; qu.push(product3); pi.

30、push_back(product3); product_item+q.insert(product3.vn+-+product3.s+,+product3.front); pi1+q1.push_back(product3);z=0; break; if(z=0)if(ch!=$)for(vector:iterator vv=vt.begin();vv!=vt.end();vv+)/找到相同输入符str1=*vv; for(vector:iterator vc1=pi.begin();vc1!=pi.end();vc1+) product1=*vc1; if(product1.go!=$)i

31、f(product1.go=ch&(product1.vn+-+product1.s+,+product1.front)=str1) str3=product1.vn+-+product1.s+,+product1.front; str2=product1.s; str2.replace(product1.point_pos,1,1,product1.go); product1.point_pos+=1; str2.replace(product1.point_pos,1,1,.); product1.s=str2;if(product1.sproduct1.point_pos+1!=0)pr

32、oduct1.go=product1.sproduct1.point_pos+1;else product1.go=$;product_itemq.insert(product1.vn+-+product1.s+,+product1.front); qu.push(product1); pi.push_back(product1); pi1q1.push_back(product1);vector:iterator i=find(vt.begin(),vt.end(),str3); if(i!=vt.end()vt.erase(i); vv-; break;else vt.pop_back()

33、;l=1; break; z=1; if(l=1) l=0; break; flat=0; break; of.open(result.txt,ios:out);if(!of)cerr打开文件失败!endl;abort();cout 构造的项目集规范族是：（按回车键继续）endl;getchar();z=0;for(vector:iterator vc2=pi2.begin();vc2!=pi2.end();vc2+) pi=*vc2;coutiz:endl;ofiz:endl; z+;for(vector:iterator pl=pi.begin();pl!=pi.end();pl+)cou

34、t(*pl).vn(*pl).s,(*pl).frontendl;of(*pl).vn(*pl).s,(*pl).frontendl;getchar();coutendl;ofendl;of.close();/*构造预测分析表*/ i=-1;for(vector:iterator vc3=pi2.begin();vc3!=pi2.end();vc3+) pi=*vc3; i+;j=0; int t=-1; for(vector:iterator pl=pi.begin();pl!=pi.end();pl+) product1=*pl;if(product1.vn+-+product1.s=s-s.)tablei.actj.ch=#; tablei.actj.control=a; tablei.actj.data=0;j+;else if(product1.vn+-+product1.s=product1.vn+-+.) for(k=0;product1.frontk!=0;k+) tablei.actj.ch=product1.frontk; tablei.actj.control=r; tablei.actj.data=product1.pcode; j+; else if(product1.point_pos=selectproduct1.pcode.len