编译原理课程设计.doc

编译原理课程设计任务书1、本课题的目的及意义课程设计实践对学生巩固所学基础专业课程知识、进行编译系统基本技能训练、培养实践动手能力，从而掌握编译系统的基本工作原理、基本方法和基本开发技术，最终达到具有一定的编译系统的实际开发能力有重要意义。通过课程设计，主要达到以下目的：1.帮助学生深入理解编译原理的有关理论和巩固编译原理相关知识。2. 巩固学生学习的编译原理、程序设计语言、数据结构等课程的基础知识，训练学生分析和解决编译系统的相关问题的能力，提高学生的综合素质。3. 从软件工程的角度来看，编译原理课程设计是一个很好的实例，可以训练学生软件设计的能力以及编码调试能力。2、本课题任务的主要内容本课程设计主要内容包括以下几点:1、根据选定的题目，查阅资料，熟悉相关理论、方法；（1）掌握文献检索方法，以获得编译系统开发技术等相关资料；（2）学习并熟练使用一种4GL开发平台（如VC+、Java、Dephi、PB、VB等）；2、分析问题，确定系统逻辑结构；3、确定系统所需模块及模块结构，并用流程图描述各模块；4、编码及调试程序；5、撰写课程设计说明书。3、提交的成果1、一份符合课程设计说明书撰写规范的课程设计说明书。2、一套系统原型。3、所有的文档及代码存放在同一个文件夹同意提交。目录前言4摘 要4ABSTRACT4第1章 概述5第2章 设计目的6第3章 设计的内容和要求73.1 设计内容73.2 设计要求73.3 设计任务的组织与分工7第4章 需求分析94.1编写目的94.2运行环境94.3编译环境简介94.4数据流图（DFD）94.5数据字典104.6 E-R图12第5章 总体设计135.1 总体功能模块图135.2 流程简介135.3 算符优先分析思想135.4 本模块简介135.5本模块功能模块图145.6 相关概念定义145.7 相关数据结构15第6章 详细设计186.1 FirstVT集的构造，算法描述186.2LastVT集的构造，算法描述186.3 算符优先关系表算法描述196.4算符优先分析流程图216.5算法描述21计数子项数量函数21TEMP_VT_ITEM_REF构造函数22将内部所有的终结符复制到Target中22计数子项数量函数23TEMP_VT_ITEM_REF构造函数24所有的终结符复制到Target中25小结26致谢26参考文献27前言随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，当前已成为计算机科学的理论基础。本文主要研究自动机在编译方面的应用，并将讨论的重点放在算符优先算法分析上，并用此理论完成算术表达式的正确与否的判断。 根据算符优先分析算法，编写一个语法分析程序，程序具有通用性，即所有编制的语法分析程序能够适用于不同文法以及各种输入单词串，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的字符，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期的准备，算符优先分析法的核心算法书本已给出，因此所要做的事就是对其进一步分析细化并将其编程实现。 本课程设计的前面几章是对题目的介绍，理解，以及对组员的具体分工，后面的详细设计及其算法描述对自己的任务做了详细的描述， 在整个设计中有很多不足的地方望老师细心指导，让我们在以后的学习中取得更大的进步。摘 要算符优先分析是自底向上优先分析（移进-归约分析）思想基础上的一种重要的算法，算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先分析法是仿效算数四则运算而建立起来的。做四则运算时，为了保证计算结果和过程的唯一性，规定了一个统一的四则运算法则，规定了运算符之间的优先关系。算符优先分析法仿效四则运算过程，它预先规定了相邻终结符之间的优先关系，然后利用这种优先关系来确定句型的“句柄”，并进行归约。关键字自底向上分析法 算符优先关系表 句子 移进-归约Priority Structure Analyzer Operator Analog DesignAbstractAnalysis of operator priority is the analysis of bottom-up priority (Moved into - Reduction Analysis)thinking on the basis of an important algorithm, Operator priority analysis is a simple and intuitive, especially to facilitate analysis of the expression, easy to hand-type methods to achieve analysis of operator priority is to follow four counts and set up operations . When done four operations , in order to ensure the calculated results and the uniqueness of the process, Provides a unified algorithm 4, Operator provides the relationship between the priority. Priority analysis operator follow the course of four operations, which pre-established at the end of the neighboring relations between the priorities, and then use this relationship to determine the priority of the sentence handle, and reduction.KeywordBottom-up analysis Moved into reduction TableSentence operator precedence relations 第1章 概述算符优先分析文法是一类广为使用的自底而上分析的文法。自底而上分析也称移进-归约分析，粗略的说它的实现思想是输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串时，就用该产生式的左部非终结符代替相应的右部文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时，则为分析成功。采用自底而上分析技术要解决两个基本问题：如何找出直接归约的简单短语？ 把找出的简单段誉直接归约到哪一个非终结符号？算符优先文法的基本思想是只考虑算符之间的优先关系，也就是只考虑终结符之间的优先关系，由于算符优先分析不考虑非终结符之间的关系，在归约过程中可归约的串就归约，并不考虑归约到那个非终结符名，因而算符优先归约不是规范归约。算符优先分析文法虽然有不规范问题，但是他分析速度快，特别适用于表达式的分析，因此在实际应用中常常采取适当措施克服此缺点。 第2章 设计目的一、通过本次课程设计，加深了我对编译原理这门课程的理解和掌握，是我明白了分析器的原理、构造及其实现方法。基本掌握了算符优先关系分析的原理和使用方法。本次课程设计主要任务是根据算符优先分析表,求句子的优先分析表过程，实现编译器的构造。此次设计需使用电子文档的格式，为加深即将迎来的毕业设计做准备，使我们提前熟悉写毕业设计的基本格式、流程和方法。二、课程设计实践的主要是为巩固我们所学基础专业课程知识、进行编译系统基本技能训练、培养实践动手能力，从而掌握编译系统的基本工作原理、基本方法和基本开发技术，最终达到具有一定的编译系统的实际开发能力有重要意义。概括来说课程设计主要为实现一下目的：1.帮助我们深入理解编译原理的有关理论和巩固编译原理相关知识。全面系统的了解编译原理程序构造的一般原理和全面实现方法，尤其是对自底而上的优先分析法的认识和理解。2. 巩固我们学习的编译原理、程序设计语言、数据结构等课程的基础知识，训练学生分析和解决编译系统的相关问题的能力，提高学生的综合素质。3. 从软件工程的角度来看，编译原理课程设计是一个很好的实例，可以训练我们软件设计的能力以及编码调试能力。4提高对编译程序工作基本过程及其各阶段基本任务的分析技能。第3章 设计的内容和要求3.1 设计内容本课程设计主要内容包括以下几点:1、根据选定的题目，查阅资料，熟悉相关理论、方法；（1）掌握文献检索方法，以获得编译系统开发技术等相关资料；（2）学习并熟练使用一种4GL开发平台（如VC+、Java、Dephi、PB、VB等）；2、分析问题，确定系统逻辑结构；3、确定系统所需模块及模块结构，并用流程图描述各模块；4、编码及调试程序；5、撰写课程设计说明书。3.2 设计要求1、提交一份课程设计电子文档；2、通过该课程设计要学会用消除左递归的方法来使文法满足进行确定自顶向下分析的条件。3、学会用C/C+高级程序设计语言来设计一个算符优先分析分析法的语法分析器；4、通过该课程设计，加深对语法分析理论的理解，培养动手实践的能力。3.3 设计实现的功能本次课程设计主要实现算符优先分析表的构造，该分析器能够分析产生式到语法树。3.3 设计任务的组织与分工本组包含十一个同学，本小组的主要任务是对算符优先关系表的判断。针对本组同学掌握的程度不同，和各自的特长，本小组的十一个同学经过在一起讨论确定分工。本组成员列表如下：刘启明琚汪慧鲍光耀褚诗运曹兴戴许文丽周学萍杨波邓晓凤尹家庆吴长梅本小组分工明细，本次我的任务模块是将用于保存当前非终结符的FIRSTVT或LASTVT对其他非终结符的FIRSTVT或LASTVT的引用，通过分析，查找资料，基本完成了模块分解的任务，在本次的课程设计中将会作详细的介绍。相关理论知识介绍确定G的VT之间的优先关系的规则设有文法G和G的非终结符P的LASTVT(P)、FIRSTVT(P)，则有：若有文法规则P ab或PaQb，则有ab； 若有文法规则QPb，对所有aLASTVT()，有ab； 若有文法规则aP，对所有bFIRSTVT(P) ，有ab；第4章 需求分析4.1编写目的算符优先分析发是一种广为使用的自底而上分析的文法。自底而上分析也称移进-归约分析，粗略的说它的实现思想是输入符号串自左向右进行扫描，并将输入符逐个一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串时，就用该产生式的左部非终结符代替相应的右部文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时，则为分析成功。4.2运行环境操作系统：Microsoft Windows XP支持环境：IIS 5.0可视化环境：Microsoft Visual C+6.04.3编译环境简介Microsoft Visual C+6.0是Microsoft公司开发的基于CC+的集成开发工具，它是Microsoft Visual Studio中功能最为强大、代码效率最高的开发工具。 Microsoft Visual C+6.0与以前的版本相比有了多方面的改进。它的编译器、调试器、连接器、编辑器、资源编辑器都有所加强，在编辑器中还提供了自动语句生成功能，编辑器会像Microsoft Visual Basic一样自动提示函数的参数、对象的成员。另外，Microsoft Visual C+6.0还提供了很多向导。MFC提供了一些新的类，提供了更强大的数据访问功能。4.4数据流图（DFD）0层数据流图文法判定句子分析一层数据流图4.5数据字典数据项数据项名：终结符别名：VT数据类型：CHAR长度：40取值范围：T001-T040数据项名：非终结符别名：VN数据类型：CHAR长度：30取值范围：T001-T030数据项名：句子别名：字符串数据类型：CHAR长度：60取值范围：T001-T030数据结构数据结构名：文法产生式说明：用来生成项目集组成：左部，右部数据结构名：文法说明：用来提供文法的信息组成：终结符，非终结符，开始符，左部，右部数据流数据流名：Gs产生式数据流来源：文法Gs数据流去向：OG文法判定与改造数据结构：产生式的左部，产生式的右部数据流名：改造后的文法Gs数据流来源：OG文法判定与改造数据流去向：生成FirstVT集和LastVT集数据结构：产生式的左部，产生式的右部数据流名：Gs的Vt之间的优先关系数据流来源：生成算符优先关系表数据流去向：OPG文法判定数据流名：算符优先关系表数据流来源：OPG文法判定数据流去向：句子移进-归约数据流名：句子数据流来源：输入数据流去向：句子移进-归约数据流名：移进-归约过程表数据流来源：句子移进-归约数据流去向：输出处理过程处理过程名：OG文法判定与改造输入：Gs产生式；输出：改造后的文法Gs处理：该处理过程主要是用来生成项目集规范族表，以及将文法产生式转化成项目产生式；处理过程名：生成FirstVT集和LastVT集输入：改造后的文法Gs输出：Gs的FirstVT集和LastVT集处理：该处理过程主要用来判断当前项目产生式的下个动作是移进还是归约处理过程名：生成算符优先关系表输入：Gs的FirstVT集和LastVT集输出：算符优先关系表 处理：该处理过程用来查找移进的下个产生式的序号处理过程名：句子移进-归约 输入： 算符优先关系表，句子输出：移进-归约过程表处理：最终生成分析表4.6 E-R图第5章 总体设计5.1 总体功能模块图5.2 流程简介输入一个文法，判断该文法是否为OG文法，如果是OG文法则不需要改造，若不是OG文法则改造它。然后，生成FirstVT集与LastVT集，其中FirstVT集与LastVT集可通过布尔数组与关系图法计算求出。利用一个不含产生式的算符文法G，如果对任意两个终结符对a,b之间之多只有和=这三种关系的一种成立，判断G是一个OPG文法。从而构造出算符优先关系表，最后根据算符优先关系表构造出算符优先分析器，其中算符优先分析器的构造可利用基于算符优先关系表、基于优先函数表，构造句子语法树的方法得出。5.3 算符优先分析思想算符优先文法的基本思想是只考虑算符之间的优先关系，也就是只考虑终结符之间的优先关系。或者说，算符优先文法在归约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需要知道把当前句柄归约为某一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的归约，因为若只有一个非终结符时无法与句型中该非终结符的左部及右部的串比较优先关系。也就无法确定该非终结符为句柄。5.4 本模块简介算符优先分析表可以描述程序设计语言的大部分语法现象，但不是全部。程序语言中某些普遍性的约束，如要算符必须是终结符，就不能由非终结符描述。因此，语法分析程序后面的编译阶段还必须对语法分析的输出作出进一步的分析。对输入进行语法分析的过程基本上是为其建立分析树或建立最左（最右）推导的过程。一般每种分析方法只能处理某种形式的文法。因此，虽然语言的设计者给出了定义程序设计语言的文法，为了适应所选择的分析方法，还需常常改写初始文法。如适合于表达式的文法常常用结合律和优先级的信息来构造。5.5本模块功能模块图优先分析表的构造优先关系的判断Lsatvt集的生成Firstvt集的生成关系构造关系构造关系构造5.6 相关概念定义句柄：一个句型的最左直接短语称为该句型的句柄。OG文法：设有一文法G，如果G中没有形如ABC的产生式，其中B和C为非结符则称G为算符文法。OG文法性质1）在算符文法中忍和句型都不包含两个相邻的非终极符。2） 如果Ab（或bA）出现在算符文法的句型中，其中A属于非终结符，b属于终结符，则此句型中任何含有b的短语必含有A。OG文法：设一个不含产生式的算符文法，如果对任意两个终结符对和之间至多只有、和三种关系的一种成立，则称是一个算符优先文法。5.7 相关数据结构 （1）/文法class Gprivate:/非终结符Vn的集合WCHAR *Vns1024;/非终结符Vn的数量int Vn_Length;/终结符Vt的集合WCHAR Vts4069;/终结符Vt的数量int Vt_Length;public:/产生式的集合P Ps2048;/产生式的数量int P_Length;public:/构造函数G(WCHAR *FileName);/查找指定的产生式P* Search_P(WCHAR *vn);void AddVn(WCHAR *Vn);private:/编译操作void Compile(WCHAR *fstr);/扫描非终结符void ScanVn(WCHAR *fstr);（2）/产生式class Ppublic:/左边的非终结符WCHAR *Vn;/右边的产生式链表V *Vs;/是否已扫描过的标志bool Flag;public:/构造函数P(void);/出队函数V* PopQueue();/非终结符入队void AddVn(WCHAR *Vn);/终结符入队void AddVt(WCHAR *Vt);（3）/字符类型enum V_TYPETYPE_VN,TYPE_VT,;/终结符和非终结符的基类class Vpublic:/链表下一级指针V *next;public:/构造V(void);/获取存储的类型virtual V_TYPE GetType()=0;/存储非终结符class VN:public Vpublic:/非终结符字符串WCHAR *Vn;public:/构造VN(void);/返回非终结符类型virtual V_TYPE GetType()return TYPE_VN;/存储终结符class VT:public Vpublic:WCHAR *Vt;public:VT(void);/返回终结符类型virtual V_TYPE GetType()return TYPE_VT;（4）/FIRSTVT和LASTVT的基类class X_VTpublic:/对应的非终结符WCHAR *Vn;/终结符的链表VT *Vts;public:/构造函数X_VT(void);/添加一个终结符到VT集合中void Add(WCHAR *vt);/绘图函数virtual void Paint()=0;/FIRSTVTclass FIRSTVT: public X_VTpublic:/绘图函数virtual void Paint();/LASTVTclass LASTVT: public X_VTpublic:/绘图函数virtual void Paint();第6章 详细设计6.1 FirstVT集的构造，算法描述：若有产生式A-a或A-Ba，则a属于FirstVT（A），其中A、B为非终结符，a为终结符。 ：若a属于FirstVT（B）且有产生式A-B则有a属于FirstVT（A）。为了计算方便，建立一个布尔数组Fm,n（m为非终结字符的个数，n为终结字符的个数）和一个后进先出栈STACK。将所有的非终结符排序，用iA表示非终结符A的序号，再将所有的终结符排序，用ia表示终结符a的序号。算法的目的是要使数组的一个元素最终取值满足：FiA,ja的值为真，当且仅当a属于FirstVT（A）。至此，显然所有的非终结符的FirstVT集已完全确定。步骤如下：首先按规则对每个数组元素附初值。观察这些初值，若FiA,ia的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此处理完。然后对栈做如下运算。将栈顶项弹出，则令其变为真，且将（A，a）推进栈，如此重复直到栈弹空为止。若表达式文法为：（0） E# E #（1） EE + T（2） ET（3） TT*F（4） TF（5） FPF | P（6） P(E)（7） Pi计算每个非终结符的FirstVT集和LastVT集得到如下结果：FIRSTVT(E) = # FIRSTVT(E) = +，*，（，iFIRSTVT(T) = *，（，iFIRSTVT(F) = ，（，iFIRSTVT(P)=（，i6.2LastVT集的构造，算法描述用于构建输入文法的LastVT集若有规则U:=a或U:=aV,则a属于LastVT（U）若有规则U:=V,且a属于LastVT（V）则a属于LastVT（U）设一个栈STACK，和一个布尔数组BProcedureInsert（U，a） IF NOT BU,a THEN BEGIN BU,a:=TRUE;把（U，a）推进STACK栈； END；BEGIN FOR 每个非终结符号U和终结符号a DO BU,a:=FALSE; FOR 每个形如U:=a或U:=aV的规则 DO INSERT(U,a); WHILE STACK栈非空 DO BEGIN 把STACK栈的栈顶弹出，记为（V,a）; FOR 没条形如U:=V的规则 DO INSERT(U,a); END OF WHILE;END; 具体算法如下： Begin For每个终结符P和终结符 a Do FP,a=FALSE; For 每个形如P-a或P-aQ的产生式， Do insert （P，a） While Stack 非空 Do Begin 把Stack 的顶端，记为（Q，a），上托出去； For每条形如P-Q的产生式 Insert（P，a） End of while； END针对上述算法可得到每个非终结符的LastVT集如下：LASTVT(E) = # LASTVT(E) +，*，），iLASTVT(T) *，），iLASTVT(F) ，），iLAVSTVT(P)），i6.3 算符优先关系表算法描述FOR 每条规则U:=x1 x2xn DOFOR i:=1 TO n-1 DO BEGIN IF xi和xi+1均为终结符，THEN 置 xi=xi+1 IF i=n-2.且xi和xi+2都为终结符号但xi+1为非终结符号 THEN 置xi=xi+2 IF xi为终结符号xi+1为非终结符号 THEN FOR FIRSTVT(xi+1)中的每个b DO 置xixi+1END 从而可以构造优先关系矩阵为表一。+*i()#+*i()#表一 表达式文法算符优先关系表6.4算符优先分析流程图6.5算法描述计数子项数量函数TEMP_VT_ITEM_REF:GetCount()/当前锁定标志为真，输出存在无法消除的环if(this-Flag) throw 存在无法消除的环;/再将标志记录为锁定状态this-Flag=true;/定义非终结符的指针函数refvt-GetCount()int Count=refvt-GetCount();/将标志解除锁定返回计数数值this-Flag=false;return Count;TEMP_VT_ITEM_REF构造函数TEMP_VT_ITEM_REF:TEMP_VT_ITEM_REF(void)/构造函数初始化this-Flag=false;this-refvt=0;将内部所有的终结符复制到Target中int TEMP_VT_ITEM_REF:CopyTo(WCHAR *Target,int Count)/判断锁定标志if(this-Flag) throw 存在无法消除的环;this-Flag=true;/将now-CopyTo(Target,Count+RCount)所有终结符依次存放到RCountint RCount=0;for(TEMP_VT_ITEM *now=refvt-items;now;now=now-next)RCount+=now-CopyTo(Target,Count+RCount);/返回值this-Flag=false;return RCount;6.6算法流程图计数子项数量函数TEMP_VT_ITEM_REF构造函数所有的终结符复制到Target中小结为期一星期的课程设计终于结束了，这段时间是我们小组在大学期间不可多得的美好记忆。给了我们很多的感受和经验，让我们在饱受酸甜苦辣的同时也体会到集体的力量和成功的喜悦。在我们以后的人生中，这些感受和经验将会充实我们的生活，美化我们的人生。在这个过程，我受到了好多帮助，一句温暖的话语，一杯热热的白开水，让人有无比的动力和解决问题的决心。其实这次的课程设计我的最大的感受不是知识的获得，而是人格的磨练和交际的能力。和大家想的一样我们也会产生一些小矛盾，当然这是不可避免的。在产生小矛盾的时候，我们没有逃避。重要的是我们如何