编译原理课程设计报告书

淮阴工学院编译原理课程设计报告选题名称: 算符优先分析法 系（院）: 计算机工程学院 专 业: 计算机科学与技术 班 级: 计算机1083班 姓 名: 学 号: 指导教师: 学年学期: 2010 2011 学年 第 1 学期2011年 01 月 07 日设计任务书课题 名称算符优先分析法设计目的通过一周的课程设计，对算符优先分析法有深刻的理解，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统，Visual C+6.0编译环境任务要求1.判断文法是否为算符优先文法，对相应文法字符串进行算符优先分析；2.编写代码，实现算符优先文法判断和相应文法字符串的算符优先分析；3.撰写课程设计报告；4.参加答辩。工作进度计划序号起止日期工 作 内 容12011.01.03理论辅导，搜集资料22011.01.042011.01.05编写代码，上机调试32011.01.06撰写课程设计报告42011.01.07答辩指导教师（签章）： 年 月 日摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析，并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。而在整个归约过程中，起决定作用的是相继连个终结符之间的优先关系。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。关键字： 编译原理；算符优先分析；最左素短语目 录1 课题综述11.1 课题来源11.2 课题意义11.3 预期目标11.4 面对的问题11.5 需解决的关键技术12 系统分析22.1 基础知识22.1.1 算符优先分析法的基本思想22.1.2算符优先关系的定义22.1.3算符优先文法的定义32.1.4 最左素短语的定义42.2 解决问题的基本思路52.3 总体方案53 系统设计63.1 算法实现63.2 流程图74 代码编写85 程序调试126 运行与测试12总 结14致 谢15参考文献16编译原理课程设计报告书1 课题综述 1.1 课题来源算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都只满足，=，的关系的一种，则称G是一个算符优先文法。1.2 课题意义算符优先文法在规约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需知道把当前句柄规约为某一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的规约，因为若只有一个非终结符时无法与句型中该非终结符的左部及右部的串比较优先关系。也就无法确定该非终结符为句柄。1.3 预期目标编写程序，实现文法的算符优先判断，并对输入的符合算符优先文法的字符串进行算符优先分析。首先对输入的表达式求FIRSTVT集和LASTVT集，然后根据优先级关系构造算符优先关系表，最后进行算符优先分析的过程。过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索知识的习惯。1.4 面对的问题如何通过自底向上的方法分析表达式，构造文法的优先矩阵，以及如何运用该优先矩阵完成移入和归约的过程，从而完成整个文法的分析。1.5 需解决的关键技术本次课程设计中的关键是：扫描和语法分析函数，它使用一个用于存放文法符号的先进后出栈，并利用有限关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和带输入符号之间优先关系是，则表示已找到最左素短语的尾，在从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误。以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。 2 系统分析2.1 基础知识2.1.1 算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。2.1.2算符优先关系的定义设G是一个不含产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系、定义如下 ： ab 当且仅当G中含有形如Aab或AaBb的产生式 ab 当且仅当G中含有形如AaB 的产生式，且Bb 或BCb ab当且仅当G中含有形如ABb 的产生式，且Ba 或BaC以上三种关系也可由下列语法树来说明： a b 则存在语法子树如图2.1(a)其中为或为B，这样a, b在同一句柄中同时归约所以优先级相同。 a b 则存在语法子树如图2.1(b) 其中为或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。 a b 则存在语法子树如图2.1(c) 。图2.1 由语法树结构决定优先性2.1.3算符优先文法的定义设有一文法G，如果G中没有形如ABC的 产生式，其中B和C为非终结符，则称G为算符文法(Operater Grammar)也称OG文法。例如：表达式文法EE+E|E*E|(E)|i其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。设有一不含产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有 、 和 三种关系中的一种成立，则称G是一个算符优先文法。(Operator Precedence Grammar)即OPG文法。由以上内容我们可计算出给定的算符文法中任何两个终结符对(a,b)之间的优先关系，其算法如下：首先定义如下两个集合：FIRSTVT(B)=b|B b 或 B CbLASTVT(B)=a|Ba 或 B aC三种优先关系的计算为a) 关系: 可直接查看产生式的右部，对如下形式的产生式Aab , AaBb有a b 成 立。b) 关系:求出每个非终结符B的FIRSTVT(B)，在如下形式的产生式AaB 中，对每一 bFIRSTVT(B),有ab成立。c) 关系:计算每个非终结符B的LASTVT(B)，在如下形式的产生式ABb 中，对每一aLASTVT(B)，有ab成立。2.1.4 最左素短语的定义设有文法GS,其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例如,若表达式文法GE为：EE+T|TTT*F|FFPF|PP(E)|i图2.2 句型T+T*F+i的语法树若有句型#T+T*F+i#，它的语法树如图2.2。其短语有：T+T*F+i 相对于非终结符E的短语T+T*F 相对于非终结符E的短语T 相对于非终结符E的短语T*F 相对于非终结符T的短语i 相对于非终结符P,F,T的短语由以上内容知i和T*F为素短语，T*F为最左素短语。也为算符优先分析的可归约串。由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条件：ai-1 ai ai+1 . aj aj+1上述句型#T+T*F+i#写成算符分析过程的形式为：#N1a1N2a2N3a3a4#其中a1 = +, a2 = *, a3 = +, a4 = ia1 a2 (因+ *)a2 a3 (因* +)由此 N2a2N3 即T*F为可归约串，也就是前面分析的最左素短语。2.2 解决问题的基本思路根据课程设计的要求，程序应具有如下功能：对输入的文法进行分析并判断是否为算符优先文法。如果是算符优先分析文法则再进一步输入符合该算符优先文法的字符串，并对该字符串进行算符优先分析，同时输出算符优先分析的过程。2.3 总体方案启动VC+，新建源程序并进行编程，程序的功能模块图如图2-1所示。图2-1系统功能结构图函数功能：Main()函数：调用主函数，运行程序；FIRSTVT()函数：构造FIRSTVT表；LASTVT()函数：构造LASTVT表；OpPrioTable()函数：构造算符优先关系表；InputAnalyse()函数：分析输入串是否为文法中的句子，并给出规约过程。3 系统设计3.1 算法实现算符优先分析法的具体过程如下：1、首先输入文件的路径，在readfile(char sencol)函数中，将需要分析的文法通过输入流文件打开函数open()复制到senrowcol中。2、然后利用FIRSTVT( )构造产生式senrowcol的FIRSTVT表。先找出形如A-a（a为第一个终结符）的产生式，把（A,a）压入Operator栈中。从Operator栈顶抛出项（A，a），填入first表相应位置。在找出形如B-A的产生式，把（B,a）压入Operator栈中。循环直到Operator栈为空，此时FIRSTVT表构造完毕。3、然后把产生式右部翻转，调用FIRSTVT函数求出LASTVT表。4、接着调用OpPriotable（）构造算符优先关系表opTable。先把产生式中所有终结符填入opTable表第一行和第一列，然后利用产生式和FIRSTVT表LASTVT表分别找出满足=关系、关系的算符填表。若相应位已有关系，说明两个终结符之间至少有两种优先关系，该文法不是算符优先文法。5、最后调用InputAnalyse（）对输入串进行分析。初始化分析栈S，依次判断当前输入符a和分析栈中离栈顶最近的终结符S j 的关系，若S j a ，则a移近，若S j a，将S j -1到栈顶S k 规约，若S j = a ，如果S j =#，则接受，如果S j ！=#，则移进。直到接受或者出错，算符优先分析结束。3.2 流程图图3-1 程序流程图4 代码编写在这次课程设计过程中，我主要负责的是算符优先分析过程的部分，代码如下。void InputAnalyse(char opTablecol,char stringcol,int opTable_len) /opTable_len是opTable表的长度char a,Q,SSIZE=0; /S是分析栈 char cho1,cho2;int i,j,relation;int k=0;Sk=#;cho2=y;couttttt分析过程如下：endl;cout-endl;/cout 栈t当前字符t优先关系t移进或规约endl;/cout分析过程如下：endl;cout.width(10);cout栈;cout.width(15);cout当前字符;cout.width(20);cout剩余符号串;cout.width(15);cout优先关系;cout.width(15);cout移进或规约a/cout St att;cout.setf(ios:left);cout.width(10);coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout;do Q=Sj; if(TerminalJud(Sj-1)=true) j=j-1; else j=j-2;while(RelationshipJud(Sj,Q,opTable,opTable_len)!=1);/cout Sj归约endl;cout.width(11);coutSj;cout.width(4);cout归约endl;k=j+1; Sk=N;for(int l=k+1;lSIZE;l+)Sl=0; else if(relation=1) /Sja cho1=y; /cout St att tt 移进endl; cout.setf(ios:left);cout.width(10); coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout;cout.width(15);cout移进endl;k=k+1; Sk=a; else if(relation=2) /Sj=a cho1=y; /cout St att =tt;cout.setf(ios:left);cout.width(10); coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout=;cout.width(15); if(RelationshipJud(Sj,#,opTable,opTable_len)=2) cout 接受endl;cout分析成功！endl; break; else cout 移进endl;k=k+1; Sk=a; elsecho1=y; /cout Statt出错endl;coutS a 出错endl;cout对不起！字符串有错！endl;cho2=n; break;/while/for/5 程序调试程序中调用了许多函数，编写代码时会出现调用的错误，使在程序运行时无法正确判断以致程序运行出错。在创建函数时会出现错误而无法得知，致使在程序运行时出错，需要很细心的去编写代码。编程的时候一定要细心，对出现的错误要认真调整，反复修改，使函数前后相对应。 6 运行与测试运行界面如下： 图6-1 运行结果图1 图6-1 运行结果图2图6-3 运行结果图3输入一个字符串，使得该字符串是该文法的一个句子。则输入字符串i+i*i/(i+i)#时运行结果为：图6-4 运行结果图4总 结在经过了一个星期的编译原理课程设计，我获益匪浅。本次课程设计是我们将所学理论知识形成系统的一个锻炼的好机会，也是学校和老师检验我们学习成果的一个方法。经过一周的设计，实现算符优先分析法。其功能能够分析判断一个文法是否为算符优先分析文法，还可以对符合算符优先文法的字符串进行算符优先分析。 这次的课程设计已经结束了，通过编程实现了预期的目标，管如此，VC+不断地探索和研究，在程序实现的过程中出现过许多没有想到的功能，原本设计的思路和方法，到真正的程序中运行的时候就达不到预想的效果。因此，我感觉编程序实际操作是非常重要的，不亲自实践就不会发现问题，我们只有不断的发现问题，不断的解决问题，才能使一个程序尽可能的完善。由于经验不足，时间有限，虽然在一周的时间里顺利的完成了系统的分析、设计和调试的工作，但是仍然有许多不足之处，我会在将来的学习过程中引以为戒。在做课程设计期间，有目的的去学习一些将要用到的东西，仔细的考虑工作流程的规律和步骤，充分的利用手中的开发工具，使自己的开发在代码上实现少而精确，能够尽量简单的进行操作。当我即将完成这个设计的时候我终于认清楚了以前老师经常提起的一个问题，那就是：一个程序开发中编码不是最重要的，重要的是对分析系统以及系统模型的建立。有了一个好的系统模型之后，我们再将其划分成几个模块，那样做起来就会容易得多。通过这个课程设计让我有了深刻的了解，增长了自己的动手能力，而且我认识到团队合作也十分重要。通过这次课程设计不仅锻炼了我学习能力，在团队合作上也有很大提高。致 谢在这次的课程设计中，让我深深地体现到编程不是一件简单的事情，它需要设计者具有全面的专业知识、缜密的思维、严谨的工作态度以及较高的分析问题、解决问题的能力，而我在很多方面还有欠缺。首先我要感谢淮阴工学院、计算机工程系提供的实践机会，实验室人员提供的实验环境，以及指导老师的悉心教导。因为课程设计不仅是学校和老师对我学习成果的一个统筹检测的方法，也是我将所学理论知识形成系统的一个锻炼的好机会。经过一个星期的时间，我不仅对操作环境有了更新的了解，更是掌握了程序设计的基本步骤，同时也对Visual C+有了更深的了解和掌握。其次我要感谢同学们的帮助，以及其他提供过帮助的所有人。在课程设计的过程中，我查阅了大量的资料，也上网搜索了许多资料。但还是有不会做的地方，于是我去请教同学，他们都很热情的讲给我听并且还帮我上机调试，我真的很感谢他们。最后，我要向给予我悉心指导和帮助的各位老师表示衷心的感谢和诚挚的敬意。因为在本次课程设计中，我从几位老师身上学到了很多东西，他们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我受益匪浅。他们无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高。这对于我以后的工作和学习都有一种巨大的帮助，感谢他们耐心的辅导。同时也感谢其他老师对我技术上的指导，由于经验不足，时间有限，虽然在近一个星期时间里顺利的完成了程序的调研、分析、设计和调试的工作，但是仍然有许多不足之处，我会在将来的软件设计过程中引以为戒。参考文献1 编译原理（第2版）/张素琴，吕映芝，蒋维杜，戴桂兰编著 北京：清华大学出版社，20082 编译原理及实践教程/黄贤英, 王柯柯编著 北京:清华大学出版社,20083 编译原理学习辅导/张伟编著 北京:清华大学出版社,20054 编译原理/主编胡延忠, 刘建舟, 林姗 武汉:华中科技大学出版社,20075 编译原理和技术/丁文魁, 杜淑敏编著 北京:电子工业出版社,2008指导教师评语学号1081301332姓名智庆芳班级计算机1083选题名称算符优先分析法序号评价内容权重（%）得分1考勤记录、学习态度、工作作风与表现。52自学情况：上网检索机时数、文献阅读情况（笔记）。103论文选题是否先进，是否具有前沿性或前瞻性。54成果验收：是否完成设计任务；能否运行、可操作性如何等。205报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况： 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）： 年 月 日