毕业设计（论文）C++6.0编译原理设计

1、摘要“编译原理”是计算机专业特别是计算机软件专业的一门重要专业课。为了使学生对高级语言的编译过程有较直观的了解，以达到辅助教学的目的，开发了编译原理的辅助教学软件。该软件包含两个部分，第一部分是pl/0 语言的cai，第二部分是供教学练习的解题系统。第二部分由五个小部分组成：语法基础部分、词法分析、语法部分、中间代码生成、基本块划分。本人完成的主要工作是：修改了语法基础部分的错误代码，使语法树能够正确显示，最左最右推导都能正确进行、完成了语法分析部分的lr（）语法分析功能和lalr(1)的语法分析功能、并且实现了四元式形式的中间代码的基本块划分。编译原理辅助教学软件的设计充分利用visual

2、c+6.0开发环境的底层控制能力和c+高级语言，c+语言中的封装、继承等概念使得编程实现简单，逻辑清楚。该软件可辅助教师教学，也有利于学生理解编译原理课程中的基本原理，同时也可以作为课程的配套练习工具。关键字： 语法分析 ，编译原理 ，面向对象技术 abstractas we all known, there are thousands of computer language existing in the world. so many languages could be applied in the computer by reason of compiler program. comp

3、iler principle is an important special course for the computer major, particularly for software major of computer department .in order to provide students with a straight and explicit understanding of complier process of senior language , we developed the computer-assisted software of complier progr

4、am to help in the class.this software is consisted of two parts: one is cai (computer-aided instruction) of pl/0, the other is an exercise system for teachers and students. the exercise system is consisted of five parts: base syntax analysis, lexical analysis, syntax analysis, intermediate code gene

5、ration, and basic block partitioning. most of my work involve: modify some code in the model of base syntax analysis to make the syntax tree can be shown correctly; add the functions of the lr (1) syntax analysis and the lalr (1) syntax analysis in the model of syntax analysis; and the whole model o

6、f basic block partitioning.computer assisted instruction of compilation, taking full advantage of the basal powerful control ability of visual c+6.0 and c+, is a good assistant software helpful for students to study and understand the course of compiler principle clearly. it could be used not only f

7、or teachers illustration in class, but also for students exercise after class.key word: syntax analysis, compiler principle, object-oriented programming目录摘要iabstractii目录iii、绪论11.1系统开发背景11.2选题目的11.3平台的选择1二、系统开发环境及其相应的技术简介22.1 面向对象技术22.2 可视化技术22.3 visual c+6.02三、系统功能的设计与实现33.1 编译原理概述33.2模块的实现技术43.2.1消

8、息映射机制43.2.2 控件及对话框53.2.3 属性页73.3 系统的整体设计83.3.1系统设计思想83.3.2 编译原理辅助教学软件功能设计说明93.4语法基础部分的设计与实现103.4.1 语法树的相关原理103.4.2功能设计103.4.3界面设计113.4.4实现中的重难点及其实现方法113.4.5运行结果演示123.5 语法分析部分的设计与实现133.5.1 lr(1)及lalr(1)分析的相关原理133.5.2 功能设计153.5.3 界面设计153.5.4 实现中的重难点及其实现方法183.5.5 运行结果演示213.6 基本块划分部分的设计与实现243.6.1 基本块划分的

9、相关原理243.6.2 功能设计243.6.3 界面设计243.6.4 实现中的重难点及其实现方法253.6.5 运行结果演示26四、教学练习系统使用说明27五、系统改进29六、结论31致谢32附录33参考文献48、绪论1.1系统开发背景本系统以编译原理为基础、以c/c+为实现语言、visual studio 6.0为开发平台，主要实现编译器的基本设计方法和一些自动构造功能。本系统是一个教学辅助软件，实现辅助教学和辅助课后习题求解的功能。本系统包含了编译器所有的组成部分，如词法分析、语法分析、语义分析、代码生成和代码优化等各个部分。编译器本身就是一个十分庞大而复杂的系统软件，涉及到许多复杂的数

10、据结构、程序设计语言和算法，要开发实现其功能，在理论上要求掌握编译技术和有关编译的抽象概念，在技术上要求具有软件开发的能力。1.2选题目的编译原理是一门对实践要求较高的课程，编译理论和技术作为计算机科学研究和工程应用的基础，受到了广泛的重视。编译原理也是大学计算机专业的必修课程，但是由于课程学时的限制，实践环节较薄弱。随着计算机科学技术的发展，计算机辅助教学作为一种新颖的教学方式，逐步进入我国教育领域各类学校的各个学科，对于计算机专业就显得更为重要，这将引起教育改革的重大变化同时也会补充和加强实践的教学环节。我选择这个课题作为毕设题目的一个重要的原因是，这个课题可以让我对编译原理有更深入的了解

11、，能帮助我更好地学习这门课程。针对该题目，本人选取vc 作为开发平台来实现该辅助教学软件的各个模块。希望通过编程实践，能够对编译原理有更加深刻的认识，了解编译器的开发过程；希望通过编程实践，能够锻炼自己的编程能力和软件开发能力。同时我也希望这个教学辅助软件能够给教师教学带来便利，学生学习提供帮助。1.3平台的选择我们开发该软件的目的是能够给老师教学、学生学习带来便利，故我们开发的软件应该功能完备、使用方便。所以我们采用可视化编程。同时，由于c+语言功能强大、能够有效地实现封装和继承，故我们是用visual studio 6.0作为开发平台，除此之外，使用visual studio 6.0还有如

12、下好处。visualc+采用的框架是mfc。mfc不仅仅是人们通常理解的一个类库。如果选择了mfc，也就选择了一种程序结构，一种编程风格。mfc早在windows3.x的时代就出现了，那时的visualc+还是16位的。经过这些年的不断补充和完善，mfc已经十分成熟。最终本系统选择了由c+/c语言实现的vc+6.0作为编译系统的开发工具，vc有classwizard 、sourcebrowser等一系列工具，还附带visual sourcesafe，install shield等强大的工具，易用性非常好1。二、系统开发环境及其相应的技术简介2.1 面向对象技术面向对象程序设计技术（oop）是目

13、前流行的系统设计开发技术，它包括面向对象分析和面向对象程序设计。oop之所以引起如此大的关注，和c+编程语言的流行是分不开的。面向对象的编程方法具有四个基本特征：抽象：抽象就是忽略一个主题中与目前目标无关的那些方面，以便更充分地注意与当前目标有关的方面6。继承：是一种联结类的层次模型，并且允许类的重用，它提供了一种明确表述共性地方法。对象的一个新类可以从现有的类中派生，这个过程成为继承类。派生类可以从它地基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更适合特殊的需要6。封装：是面向对象特征之一，是对象和类概念的主要特征。封装是把过程和数据包围起来，对数据的访问只能通过已定义的类。

14、这些对象通过一个受保护地接口访问其他对象6。多态性：是指允许不同类地对象对同一消息做出其相应的响应。比如同样的加法，将数字相加和字符串相加，是不一样的。多态性语言具有灵活、抽象行为共享、代码共享的优势，很好地解决了应用程序函数同名问题6。2.2 可视化技术可视化技术是当前发展迅速并引人注目的技术之一，它的特点是把原来抽象的数字、表格、功能逻辑等用直观的图形、图像的形式表现出来。可视化编程是它的重要应用之一。所谓可视化编程，就是指在软件开发过程中，用直观的具有一定含义的图标按钮、图形化的对象取代原来手工的抽象的编辑、运行、浏览操作，软件开发过程表现为鼠标操作和施放图形化的对象以及指定的属性、行为

15、的过程。这种可视化的编程方法易学易用，而且大大提高了工作效率6。2.3 visual c+6.0 在众多的开发软件工具中，microsoft 公司的visual c+6.0 独树一帜，将面向对象的程序设计方法和可视化的软件开发环境完美地结合起来。visual c+程序的执行速度以及对操作系统访问的权限之高，是其他许多语言无法比拟的，加上windows操作系统的支持，就使得visual c+的高级程序员对整个计算机的硬件系统和软件系统在各方面的访问和控制更加游刃有余。因此，有人说：“用visual c+的眼光看，整个计算机都是透明的，或者说是完全裸露的”6。三、系统功能的设计与实现3.1 编译原

16、理概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转化成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，下图给出了一个编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，我们将就这几个方面进行系统模块设计，实现其功能。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理5。 将

17、高级语言翻译成较低级的、面向机器的汇编语言或者某种中间表示，是非常复杂和困难的事情。通过几代计算机科学家的探索经验可以得出一套行之有效的思想，这就是，把高级语言的翻译这个问题划分成若干个相对容易解决的小问题，然后采用分而治之的策略逐个攻破。下图为编译流程图源程序词法分析、语法分析输出代码生成语义分析代码编译抽象语法树图3-1 编译流程图3.2模块的实现技术3.2.1消息映射机制本模块应用了消息映射机制，下面我具体介绍一下消息映射的基本知识。所谓消息映射，简单地讲，就是让程序员指定要某个mfc类（有消息处理能力的类）处理某个消息。mfc提供了工具classwizard来帮助实现消息映射，在处理消

18、息的类中添加一些有关消息映射的内容和处理消息的成员函数。程序员将完成消息处理函数，实现所希望的消息处理能力8。在类的头文件中声明了一系列标记为afx_msg的成员函数，如下所示：/afx_msg(类名) 标记消息处理函数/afx_msgdeclare_message_map()afx_msg宏的作用是标识成员函数为消息处理函数。在类的定义结尾处的declare_message_map()是一个宏，它为类定义了三个成员变量：一个消息映射项（afx_msgmap_entry）数组、一个afx_msgmap类型的结构和一个可以获取此结构变量的虚函数。有了这三个成员变量，mfc的核心代码就能查找到消息

19、映射列表，并调用正确的消息处理函数5。在类的实现文件（.cpp）中，除了成员函数的实现代码外，还有夹在begin_message_map宏的参数为消息映射表所属的类及其基类的名称，对于消息映射表中没有列出的消息将交给其基类处理。两个宏之间的每一项代表一条windows消息（或命令消息）和它的处理函数，对于标准的windows消息，mfc提供了on_xx_xxx形式表示消息映射宏，并使用消息处理函数原形。如下面实例所示：begin_message_map(类名, 基类名)/afx_msg_map(类名)on_bn_clicked(idc_button1, onbutton1)/ windows消

20、息和它的处理函数/afx_msg_mapend_message_map()3.2.2 控件及对话框 在本系统中使用了许多控件，下面我就对于我们不常使用但具有重要意义的控件和对话框做具体的介绍。1、web browser控件在工具条中可选择web browser控件，其主要功能：第一：浏览网页利用控件的navigate接口，原型如下：void cwebbrowser2:navigate(lpctstr url, variant* flags, variant* targetframename, variant* postdata, variant* headers)只要第一个参数填上html文件

21、的全路径名（不能使用相对路径名）,其余的参数可以为null。比如：美化界面：使用这个控件显示出来可以增加界面的美感。播放音乐：在网页中播放音乐（mid或wav），同时把控件隐藏起来，则可以实现程序背景音乐的播放。同时在设计输出时，lr（1）和lalr（1）文法等的输出都嵌入了html代码实现具体的输出，下面就表格输出为例子：out.writestring(n);out.writestring(n);out.writestring(untitled documentn);out.writestring(n);out.writestring(n);out.writestring(n);out.wr

22、itestring(n);out.writestring(n);out.writestring( n) 播放视频：可以支持asf和mpeg格式显示图片：利用web浏览器可以简单地显示gif、jpeg、bmp等图片。浏览doc文档、pdf文件：利用控件的navigate接口，可以浏览word文档和pdf文件，只要第一参数填上文件的全路径名，后面的参数都可以为null。2、tree control 在语法基础部分生成语法树中应用这个控件，控制树的层次结构。我们可以从工具条中选择tree control控件，这个控件可以从 ctreectrl 中派生一个类，它具有如下的特点： 基本拖动的实

23、现。 处理无意拖动。 能处理拖动过程中的滚动问题。 拖动过程中节点会智能展开。3、对话框在本系统中，我主要使用三种对话框，一个是简单的消息框，一个是模式对话框，还有一个就是公用对话框。（1）消息框：函数messagebox是用来创建消息框的一个定制函数，它最多可以传递三个参数。一个是显示给用户的消息文本；一个是用来显示在消息框中的标题栏；还有就是显示给用户的按牛和信息图标，可提供用户选择。我主要使用第一种，提示用户信息。（2）模式对话框：创建对话框的步骤：首先，单击resource view选项卡，选择新建对话框，进行窗体设计。然后，就可以双击对话框，添加或修改代码。在view中class w

24、izard 选项中可以为控件添加成员变量，实现变量和控件的关联。通过mfc的class wizard的消息映射选项，把消息处理函数添加到afx_msg宏里，实现消息映射，（3）公用对话框：本系统使用cfiledialog公用对话框类，选择文件名，可以保存和打开文件。3.2.3 属性页在th-ccais中的五个模块：词法分析部分、语法基础部分、语法部分、中间代码生成部分和基本块划分部分，我们使用属性页把这五个部分添加到一个窗体中。下面我就th-ccais模块为例介绍一下属性页的特点。在插入-资源-dialog，中选择多个从idd_proppage_large继承的属性页，如idd_prop1。这

25、些创建的对话框就是属性中的每一页。用classwizard为你的属性页定义新的cpropertypage继承类，如cprop1和idd_prop1等关联。用classwizard新建一个从cpropertysheet继承的cpropsheet类。有几个属性页就建几个成员变量如m_prop1和属性页关联。在cpropsheet类的两个构架函数中加入即可。具体步骤：1、通过class wizard在th-ccais中加五个属性页，以及在上面添加所要的控件。如果要显示中文，注意将属性页的语言属性改为中文。（如th-ccais界面所示）2、为每个属性页生成相应的类，基类为cpropertypage.，

26、如基础部分（class cteachbase 类）、语法部分（class cteachsyntax类）和中间代码生成部分（class cmidcode类）。3、生成一个基于cpropertysheet的表单类（class cteachsheet类）。在该类的头文件中加入几个对属性页的成员变量、设为public类型。public:cteachbase m_cteachbase;cteachsyntax m_cteachsyntax;cmidcode m_cmidcode;cteachdag m_cteachdag;teachlexsys m_cteachlex; 注意在这个头文件中要加入teac

27、hbase.h 、 teachsyntax.h 、 midcode.h、teachlexsys.h和teachdag.h的头文件。然后在表单的两构造函数中，都用addpage加上这些属性页。addpage(&m_cteachbase);addpage(&m_cteachsyntax);addpage(&m_cmidcode);addpage(&m_cteachlex);addpage(&m_cteachdag);4、在系统初始化时（bianyidlg.h类中）要使用属性页的地方，定义一个表单对象。（图如主界面所示）cteachsheet m_teachsheet;if(m_teachsheet

28、.domodal()!= idok) return;/调用属性页。3.3 系统的整体设计3.3.1系统设计思想本系统的设计思想以教学辅助为目的，我们所要达到的最终目的不仅是输出的结果，更重要的是在编译过程中的动态跟踪显示。在软件设计过程中，代码的编制要符合要求，达到代码清晰，可扩充性强；系统要达到稳定性和安全性。编译课程辅助教学软件主要是为了配合编译课程的练习题部分，通过这个模块可以解答课后的部分习题。我的主要任务是：修改语法树使其能够正确显示；完善语法分析部分，使其能够进行lr(1)和lalr(1)语法分析；对四元式形式的中间代码进行基本块的划分。下图为系统的总体设计模块图：语法基础部分最左

29、推导生成语法树最右推导中间代码生成编译原理辅助教学软件ll(1)分析法自顶向下自底向上语法部分lr(1)分析法slr(1)分析法lr(0)分析法lalr(1)分析法划分基本块词法分析nfa到dfadfa最小化正规式到nfa正规文法到正规式图3-2 系统设计整体框架图3.3.2 编译原理辅助教学软件功能设计说明为了配合编译原理的练习题，帮助教学，我们开发了一个编译原理辅助教学软件，其功能包括如下方面：1、语法基础部分：对文法符号串进行：最左或最右推导构造语法树判定输入串是否为指定文法的句子或句型（规范句型）2、词法分析：对正规式、有穷自动机和正规文法三者关系有：输入正规式可给出对应的不确定的、确

30、定的和最小的有穷自动机输入有穷自动机可进行确定化和最小化输入正规文法可给出相应正规式3、语法分析：语法分析部分可对已输入的文法：构造ll（1）、lr分析表，其中lr分析表可有四种：lr（0）、slr（1）、lalr（1）、lr（1）若所构造的分析表满足相应文法的要求，则用相应分析表可对输入的终结符串进行分析，给出分析过程，并说明输入串是否为正确句子。4、中间代码生成：该过程应可对以pascal语句格式给出的简单语句序列：生成四元式代码对含有条件语句和循环语句的语句序列可给出相应四元式代码及其回填次序。对表达式和赋值语句可生成逆波兰式。5、划分基本块对四元式形式的中间代码进行基本块的划分。3.4

31、语法基础部分的设计与实现3.4.1 语法树的相关原理1、语法树的概念：给定文法g=(，p，s)，对于g的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：（1）每个节点都有一个标记，这个标记是的一个符号。（2）根的标记是s。（3）若一节点n至少有一个它自己除外的子孙，并且有标记a，则a肯定在中。（4）如果结点n的直接子孙，从左到右的次序是结点、，其标记分别为、，那么a 一定是p中的一个产生式。52、一颗语法树表示了一个句型的种种可能性，包括最左最右推导，对于非二义文法而言一个句型对应着唯一的一颗语法树，但是对于二义文法来说一个句型并不对应着唯一的一颗语法树。53.4.2功能设

32、计在语法基础部分里，我们对文法符号串进行最左推导、最右推导、并构造语法树，同时判定输入的文法符号串是否为给定文法的句子。3.4.3界面设计图3-3 教学练习系统整体界面设计图我们采用上图所示的界面，使用该界面我们既可以从外部导入文法也可以直接输入文法。确定了文法以后，我们就可以对文法字符串进行分析，如果被分析的字符串是给定文法的句子，则可以对该句子构造相应的语法树，也可以对其进行最左推导和最右推导；如果被分析的字符串不是给定文法的句子则在分析结果说明组合框中给出相应的提示。对于新输入的文法，我们可以对其进行保存，以便于以后的分析；也可以清除文法然后重新导入或输入所需的文法。3.4.4实现中的重

33、难点及其实现方法1如何显示给定字符串的语法树？为了显示语法树，我们采用了tree control控件，来控制树的层次结构。我们可以从工具条中选择tree control控件，这个控件可以从 ctreectrl 中派生一个类，它具有如下的特点： 基本拖动的实现。 处理无意拖动。 能处理拖动过程中的滚动问题。 拖动过程中节点会智能展开。2如何用计算机实现最左推导和最右推导？对于最左推导和最右推导都需要利用字符串的语法树，故需要先生成该字符串的语法树，然后根据该语法树的扩展结点的优先规则则可得到该字符串的最左推导或者最右推导。3.4.5运行结果演示图3-4 语法基础部分运行结果示意图语法树能够正确显

34、示，最左推导和最右推导也均能正确推导3.5 语法分析部分的设计与实现3.5.1 lr(1)及lalr(1)分析的相关原理1语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。52自底向上分析法是从输入符号串开始，是自左而右扫描、最右推导的逆过程。自底向上的分析是从给定的符号串开始，自底向上的构造一棵语法树，最终试图使树根是仅是文法的开始符号，习惯上使用最左规约。具体操作步骤：（1）找出当前句型的句柄x(或句柄的变形)。（2）找出以x为右部的规则 x:=x。（3）把x规约为x，产

35、生语法树的一支。53lr分析法：适合所有上下文无关文法。一般地说，大多数用上下文无关文法描述的程序设计语言均可用lr分析器予以识别。（1）与算符优先分析法或其它的“移进-归约”技术相比，适应范围更加广泛，能力更强，而识别效率并不比它们差。（2）与普通不带回溯的自上而下预测技术相比也要好些。（3）在自左向右扫描输入串时就能发现其中的错误，并能准确地指出出错位置。5本模块主要采用lr这种分析方法实现语法分析的。4书中详细介绍了lr(0)、slr(1)、lr(1)、lalr(1)四种lr分析方法，其中的后一种分别是前一种的改进。55一个lr分析器由3部分组成：（1）总控程序，也可以成为驱动程序。对所

36、有的lr分析器总控程序都是相同的。（2）分析表和分析函数。不同的文法分析表将不同，同一个文法采用的lr分析器不同时，分析表也不同，分析表又可分为动作（action）表和状态转换(goto)表两个部分，他们都可用二维数组表示。（3）分析栈，包括文法符号栈和相应的状态栈。5分析器的动作由栈顶状态和当前输入符号所决定（lr(0)分析器不需向前查看输入符号）5将和初始状态0入栈读入一个字符“w”查action状态栈，w表项出错是否是acc是 分析正确结束转换如果表项是sjpush(状态栈，i);push(符号栈，w)用i号产生式代替状态栈进行归约，并进行ri代表的动作图3-5 lr分析器工作过程示意图

37、6由于用slr(1)方法解决动作冲突时，对于规约项目a- ，只要当前面临输入符为follow(a)时，就采用产生式a-进行规约，但是如果栈里的符号串为规约后变为a，再移进当前符a，则栈里变为aa，而实际上aa未必为文法规范句型的活前缀。slr(1)方法虽然相对lr(0)有所改进，但仍然存在着多余规约，也说明slr(1)方法向前查看一个符号的方法仍不够确切，lr(1)方法恰好是要解决slr(1)方法在某些情况下存在的无效规约问题。57若a-b 项目集i时。则b-也i（b-为一产生式）。由此不妨考虑，把first()作为用产生式b-规约的搜索符，称为向前搜索符，作为规约时查看的符号集合用以代替sl

38、r(1)分析中的follow集，把此搜索符号的集合也放在相应项目的后面，这种处理方法即为lr(1)方法。58由于一个lr(1)项目可以看成两个部分组成，一部分和lr(0)项目相同，这部分我们称它为心，另一部分为向前搜索符集合。59lr(1)分析表的构造对搜索符的计算方法比较确切，对文法放宽了要求，也就是适应的文法类广，可以解决slr(1)方法解决不了的问题，但是，由于它的构造对某些同心集的分裂可能对状态数目引起剧烈的增长，从而导致存储容量的急剧增加，也使应用受到一定的限制，为了克服lr(1)的这种缺点，我们可以采用对lr(1)项目集规范族合并同心集的方法，若合并同心集后不产生新的冲突，则为la

39、lr(1)项目集。它的状态个数与lr(0)、slr(1)的相同。53.5.2 功能设计语法分析部分可对已输入的文法：构造ll(1)、lr分析表，其中lr分析表可有四种：lr(0)、slr(1)、lalr(1)、lr(1)若所构造的分析表满足相应文法的要求，则用相应分析表可对输入的终结符串进行分析，给出分析过程，并说明输入串是否为正确句子，同时可以保存分析结果。3.5.3 界面设计图3-6 语法分析部分界面设计图此界面为语法分析的主界面：在该界面中可导入或者输入相应的文法，通过按钮ll1分析、lr0分析、slr分析、lr1分析、lalr1分析，可分别生成该文法的相应分析表。图3-7 lr(1)分

40、析表输出界面设计图在该界面中显示相应文法的lr1项目、lr1项目集规范簇以及lr1分析表，点击分析句子按钮可以对输入的字符串进行lr1分析，点击保存结果可以保存该lr1分析表。图3-8 lr(1)句子分析结果显示设计图在该界面中输入需要分析的句子，按分析句子按钮即可在分析结果中显示该句子的分析过程及分析结果。图3-9 lalr(1)分析表输出界面设计图在该界面中显示相应文法的lalr1项目、lr1项目集规范簇以及lalr1分析表，点击分析句子按钮可以对输入的字符串进行lalr1分析，点击保存结果可以保存该lalr1分析表。图3-10 lalr(1)句子分析结果显示设计图在该界面中输入需要分析的

41、句子，按分析句子按钮即可在分析结果中显示该句子的分析过程及分析结果。3.5.4 实现中的重难点及其实现方法1向前搜索符是前面几种语法分析，如lr(0)、slr(1)所没有的，由于lr(1)语法分析有了向前搜索符，所以lr1的项目、项目集的表示形式和以前也不一样了，需要用新的数据结构来表示。在实际编程中，我用类lr1pair来表示lr(1)的项目，该类的定义如下：class lr1pair public:lr1pair(int i,int j,set s);set prevar;/用来保存向前搜索符int two; /用来保存分析过的字符的位置int one; /用来保存产生式的编号lr1pai

42、r();virtual lr1pair();bool operator =(const lr1pair &lr1pair)const;用类lr1projectset来表示lr(1)的项目集，该类的定义如下：class lr1projectset public: lr1projectset(void);lr1projectset(void);lr1projectset(const lr1projectset & set);lr1projectset(lr1pair pair);bool insert(lr1pair insert);bool delete(lr1pair del);bool fi

43、nd(const lr1pair & find) const;int findpos(const lr1pair & find) const;int add(const lr1projectset & set);int sub(const lr1projectset & set);int size() const;lr1projectset operator + (const lr1projectset & set);lr1projectset operator - (const lr1projectset & set);const lr1projectset operator = (cons

44、t lr1projectset & set);bool operator = (const lr1projectset & set);lr1pair getat(int ipos);bool isempty();int findroot(int one,int two);/找同心项目vector setcontent;/用来表示项目集的内容;2、由于lr(1)的项目和项目集与以前都不一样了，新添加了向前搜索符，所以lr(1)项目集的闭包函数与转换函数也得做相应的修改。求闭包函数的算法为：5（1）假定i是一个项目集，i的任何项目都属于closure(i)。（2）若有项目a-b，a属于closur

45、e(i)，b-是文法中的产生式，bfirst(a)，则b-，b也属于closure(i)中。（3）重复（2）直到closure(i)不再增大为止。构造转换函数的算法为：lr(1)转换函数的构造与lr(0)的相似，go(i,x)= closure(j)其中i是lr(1)的项目集，x是文法符号：j=任何形如a-x，a的项目|a-x，a i对文法的lr(1)项目集族的构造仍以-s，#为初态集的初始项目，然后对其求闭包和转换函数，直到项目集不再增大。也就是对状态i经过符号x后转向状态j，求出j的核后，对核求闭包即为closure(j)。代码实现如下所示：求闭包的代码实现：lr1projectset l

46、r1grammar:getclosure(const lr1pair & lr1pair1) int inum = lr1pair1.one;/which perception （one用来标记产生式）int ipos = lr1pair1.two;/position of the dot （two用来标记项目中点的位置）set setprevar=lr1pair1.prevar;lr1projectset temp;lr1projectset tempcmp;temp.insert(lr1pair(inum, ipos,setprevar);int icount = 0;while (ico

47、unttemp.size()inum = temp.getat(icount).one;ipos = temp.getat(icount).two;setprevar=temp.getat(icount).prevar;string strright = pinum.getright();if (ipos strright.length()if (vn.find(strrightipos)string afterstring;set nextprevar;afterstring=getstringaftervn(temp.getat(icount); nextprevar=getlr1prev

48、ar(afterstring,setprevar);for (int j = 0; j np; j+)if (pj.getleft()0 = strrightipos)temp.insert(lr1pair(j,0,nextprevar);icount+;return temp;转换函数的代码实现：lr1projectset lr1grammar:makegoset(int ii, char cchar) lr1projectset rtn;lr1projectset ps = cii; /起始状态的项目集for (int i = 0; i ps.size(); i+)lr1pair p =

49、ps.getat(i);string strright = pp.one.getright();if (p.two strright.length()if(strrightp.two = cchar)rtn.add(getclosure(lr1pair(p.one, p.two + 1,p.prevar);return rtn;3、对于lr(1)分析表的构造与lr(0)的相类似，所以可参照lr(0)得到。4、lalr(1)与lr(1)的不同仅在于它合并了lr(1)项目集中的同心集，故lalr(1)文法类继承了lr(1)文法类，并对其进行了些许的扩充，增加了一个合并同心集的函数。3.5.5 运行

50、结果演示图3-11导入或者输入文法后的界面图3-12进行lr1分析后的界面图3-13分析句子后的界面图3-14进行lalr1分析后的界面图3-15分析句子后的界面3.6 基本块划分部分的设计与实现3.6.1 基本块划分的相关原理1基本块的概念：基本块是指程序中一个顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。52对于一个给定的程序，我们可以把他划分为一系列的基本块。53划分基本块的目的是为了进行局部优化，可以对程序进行基本块范围的优化。53.6.2 功能设计对四元式形式的中间代码进行基本块的划分。3.6.3 界面设计图3-16 基本块划分

51、的界面设计左面的列表框导入需要进行划分的四元式形式的中间代码，按划分基本块按钮，在右边即可显示基本块划分结果。3.6.4 实现中的重难点及其实现方法1如何划分基本块？首先，求出四元式程序中各个基本块的入口语句；其次，对每一入口语句，构造其所属的基本块。它是由该入口语句到下一个入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句）之间的语句序列组成的。最后，凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。5在程序中，我定义了fourparts类来表示一个四元式及其相关的操作；program类来表示由四元式组成的中间代码及其相关的操作。class fourparts public:fourparts()