算符优先文法分析算术表达式是否正确.doc

课程设计任务书本课程设计的目的和意义： 1、提高对已学高级程序设计语言的掌握与应用。 2、可以设计某种高级程序设计语言的语法分析程序。 3、对中间件的开发有实际应用和借鉴。主要内容：一般要求同学们均应独立、自主地协同工作，解决本人分担到的具体子任务，顺利完成本次课程设计任务。每个人应根据所分配的任务进行：1、进行需求分析形成系统数据流图及其数据字典设计（数据内外部存储结构及其上的数据约束与关系集）2、进行总体设计形成系统功能层次结构图及其上的接口与调用关系；合理分配数据工作期与作用域。3、进行模块内详细设计，形成各模块算法流程图及其数据结构与界面设计。4、进行编码与调试方案设计并实验。5、总结、汇总、规范各类分析、设计文档形成论文。集成各模块形成软件并上报 指导教师 (签名)_ 年 月 日前 言随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前已成为计算机科学的理论基础。本文主要研究自动机在编译方面的应用，并将讨论的重点放在算符优先算法分上，并用此理论完成算术表达式的正确与否的判断。 根据算符优先分析算法，编写一个语法分析程序，程序具有通用性，即所编制的语法分析程序能够适用于不同文法以及各种输入单词串。基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的字符，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。算符优先分析法的核心算法教材上已给出，因此所要做的事只是将其编程实现。 本课程设计第一、二、三章主要是对题目的介绍分析及具体分工，第四章为详细的过程设计及算法描述等，第五章是运行结果记录，第六章得出结论，后附有小结、参考文献和核心代码。整个课程设计功能完成比较成功。其中还存在许多不足，望老师查阅细心指导，让我们在今后的学习中取得更大进步。 编者 2008.06目 录第0章 开发工具介绍 4第1章 设计目的 6第2章 设计的内容和要求 7 2.1 设计内容 7 2.2设计要求 7第3章 设计任务的组织和分工 83.1 小组任务分工 8 3.2本人的主要工作 8第4章 系统设计 10 4.1 总体设计 10 4.2 详细设计 10 4.2.1 FIRSTVT集的构造，算法描述 10 4.2.2 LASTVT集的构造，算法描述 12 4.2.3 构造算符优先关系表及规约流程图 13第5章 运行与测试结果 15第6章 结论 16课程设计心得 16参考文献 16附录 17第0章 开发工具介绍面向对象的程序设计语言C+ C+类中包含私有、公有和保护成员 C+类中可定义三种不同访控制权限的成员。一种是私有(Private)成员，只有在类中说明的函数才能访问该类的私有成员，而在该类外的函数不可以访问私有成员；另一种是公有(Public)成员，类外面也可访问公有成员，成为该类的接口；还有一种是保护(Protected)成员，这种成员只有该类的派生类可以访问，其余的在这个类外不能访问。 C+中通过发关消息来处理对象 C+中是通过向对象发关消息来处理对象的，每个对象根据所接收到的消息的性质来决定需要采取的行动，以响应这个消息。响应这些消息是一系列的方法，方法是在类定义中使用函数来定义的，使用一种类似于函数调用的机制把消息发送到一个对象上。 C+支持继承性 C+中可以允许单继承和多继承。一个类可以根据需要生成派生类。派生类继承了基类的所有方法，另外派生类自身还可以定义所需要的不包含在父类中的新方法。一个子类的每个对象包含有从父类那里继承来的数据成员以及自己所特有的数据成员。 Visual C+特性MFC的本质就是一个包含了许多已经定义好的对象的类库，虽然我们要编写的程序在功能上是千差万别的，但从本质上来讲，都可以化归为用户界面的设计，对文件的操作，多媒体的使用，数据库的访问等等一些最主要的方面。在这个类库中包含了一百多个程序开发过程中最常用到的对象。在进行程序设计的时候，如果类库中的某个对象能完成所需要的功能，这时我们只要简单地调用已有对象的方法就可以了。我们还可以利用面向对象技术中很重要的“继承”方法从类库中的已有对象派生出我们自己的对象，这时派生出来的对象除了具有类库中的对象的特性和功能之外，还可以由我们自己根据需要加上所需的特性和方法，产生一个更专门的，功能更为强大的对象。更可以在程序中创建全新的对象，并根据需要不断完善对象的功能。正是由于Visual C+充分利用了面向对象技术的优点，它使得我们编程时极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大为减少，有力地保证了程序的良好的可调试性。Visual C+主要的开发工具：ClassWizardClassWizard（类向导）是Visual C+提供的强大的类处理工具。其中的Message Map(消息映射)选项卡可以让我们添加或删除要处理的Windows消息处理器；Member Variable(成员变量)选项卡为应用程序中的类创建成员变量，并和控件联系在一起；Class Info（类信息）选项卡显示了应用程序中所包含类的一般信息，包括定义的头文件和源文件类名，以及与之相关联的基类。并且Add Class 按钮提供了在工程中创建新类的方法。组件库组件库允许向工程中插入与定义的类，我们可以通过组件库中的预制组件来增强应用程序的功能。他们可以是对话框中的简单控件，以可以是ActiveX中的复杂控件。调试器Visual C+ 中提供的调试器功能非常强大，其中最好的例子是能够提供在线帮助。在程序调试过程中，常用的有调试器工作栏、指针观察窗口、数据观察窗口等。第1章 设计目的本次课程设计课题为“算符优先文法分析算术表达式是否正确”，算符优先算法是自底而上分析方法的一种。所谓自底向上分析，也称移进规约分析，粗略地说他的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串是，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。重复这一过程直到规约到栈中只剩文法的开始符号是则为分析成功，也就确认输入串是文法的句子。而算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。本课程设计的主要目的：1、通过本次课程设计，全面系统的了解了编译原理程序构造的一般原理和基本实现方法，尤其是对自底向上的优先分析方法的认识和理解；2、提高了对编译程序工作基本过程及其各阶段基本任务的分析技能；3、加强了对编译程序的生成过程、构造工具及编译程序总流程框图的理解，巩固了所学的课本知识。第2章 设计的内容和要求2.1设计内容此次的课程设计的内容是给出一个算符优先分析方法的程序，根据输入的算术表达失判断此表达失是否正确。列如：输入：10# 输出： 正确输入：1+2#输出： 正确输入：(1+2)/3+4-(5+6/7)#输出： 正确输入：(1-2)/3+4# 输出： 错误输入：1+2-3+(*4/5)# 输出:： 错误2.2设计要求 按照课程设计的要求，提交一份标准的课程设计报告，一般用碳素墨水、统一论文纸书写（提倡打印）。 编程语言、运行环境不限（推荐在VC+环境下）。第3章 设计任务的组织和分工3.1 小组任务分工祝琳：撰写设计目的、内容和要求。负责详细设计中的FIRSTVT集的构造算法。徐霖：负责详细设计中的LASTVT集的构造算法。杨海燕：负责构造优先关系表，总体规约流程图。王巧云：负责后期的测试和协助查找资料。3.2 本人主要工作本人的主要工作是撰写设计目的、内容和要求。负责详细设计中的FIRSTVT集的构造算法。现把成果罗列如下：设一个栈S和一个二维布尔数组FFU,b=TRUE iff bFIRSTVT(U) PROCEDVRE INSERT(U,b) IF NOT FU,b THEN BEGIN FU,b:=TRUE 把(U,b)推进S栈 /* bFIRSTVT(U) */ END BEGIN main FOR 每个非终结符号U和终结符b DO FU,b:=FALSE /*赋值符*/ FOR 每个形如U:=b或U:=Vb 的规则 DO INSERT(U,b) WHILE S栈非空 DO BEIGN 把S栈的顶项弹出,记为 (V,b)/* bFIRSTVT(U)*/ FOR 每条形如U:=V的规则 DO INSTER(U,b); /* bFIRSTVT(U)*/ END OF WHILE END上述算法的工作结果是得到一个二维的布尔数组F,从F 可以得到任何非终结符号U的FIRSTVT ：FIRSTVT(U)=b|FU,b=TRUE 具体算法如下：Begin For 每个非终结符P和终结符a Do FP，a=FALSE；For 每个形如P-a或P-Qa的产生式（1） DO insert（P，a）While Stack 非空 Do Begin 把Stack 的顶项，记为（Q，a），上托出去； For每条形如P-Q的产生式DO .（2） Insert（P，a）End of while；END第4章 系统设计4.1 总体设计1、FIRSTVT集的构造2、LASTVT集的构造3、构造算符优先关系表4.2 详细设计首先介绍算符优先文法的几个重要性质：性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如果Aa（或者bA）出现在算符文法的句型X中，其中AVN，bVT，则X中任何含此b的短语必含有A。4.2.1 FIRSTVT集的构造，算法描述用于构建输入文法的FIRSTVT集设一个栈S和一个二维布尔数组FFU,b=TRUE iff bFIRSTVT(U) PROCEDVRE INSERT(U,b) IF NOT FU,b THEN BEGIN FU,b:=TRUE 把(U,b)推进S栈 /* bFIRSTVT(U) */ END BEGIN main FOR 每个非终结符号U和终结符b DO FU,b:=FALSE /*赋值符*/ FOR 每个形如U:=b或U:=Vb 的规则 DO INSERT(U,b) WHILE S栈非空 DO BEIGN 把S栈的顶项弹出,记为 (V,b)/* bFIRSTVT(U)*/ FOR 每条形如U:=V的规则 DO INSTER(U,b); /* bFIRSTVT(U)*/ END OF WHILE END上述算法的工作结果是得到一个二维的布尔数组F,从F 可以得到任何非终结符号U的FIRSTVT ：FIRSTVT(U)=b|FU,b=TRUE 具体算法如下：Begin For 每个非终结符P和终结符a Do FP，a=FALSE；For 每个形如P-a或P-Qa的产生式（1） DO insert（P，a）While Stack 非空 Do Begin 把Stack 的顶项，记为（Q，a），上托出去； For每条形如P-Q的产生式DO .（2） Insert（P，a）End of while；END4.2.2 LASTVT集的构造，算法描述用于构建输入文法的LASTVT集1.若有规则U:=a或U:=aV,则aLASTVT(U)2.若有规则U:=V,且aLASTVT(V)则aLASTVT(U)设一个栈ST,和一个布尔数组B PROCEDURE INSERT(U,a) IF NOT BU,a THEN BEGIN BU,a:=TRUE;把(U,a)推进ST栈; END;BEGIN FOR 每个非终结符号U和终结符号a DO BU,a:=FALSE; FOR 每个形如U:=a或U:=aV的规则 DO INSERT (U,a); WHILE ST栈非空 DO BEGIN 把ST栈的栈顶弹出,记为(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；END4.2.3 构造算符优先关系表及规约流程图1 算符优先关系表FOR 每条规则U:=x1x2xn DO FOR i:=1 TO n-1 DO BEGIN IF xi和xi+1均为终结符,THEN 置 xi=xi+1 IF in-2，且xi和xi+2都为终结符号但 xi+1为非终结符号 THEN 置 xi=xi+2 IF xi为终结符号xi+1为非终结符号 THEN FOR FIRSTVT(xi+1)中的每个b DO 置xixi+1 END 2 算符优先分析流程图图4-1 算符优先分析规约流程图第5章 运行与测试结果第一个测试表达失是：（8-3）+34 #第二个测试表达失是：2+（3+9）-6*（2+7） #第6章 结论本次课程设计主要通过算符优先文法分析算术表达失的正确性，经过多方查找资料以及组员间的相互合作，总的过程比较顺利。课程设计心得：刚拿到课程设计的题目时，真是一头雾水，不是因为别的而是当初在课堂上学习的知识不够扎实，内心有点压力：），想了一整天也没有头绪。第二第三天的时候把书本上相关的知识又从新温习了一遍，又从我们发的配套习题上做了相应的题目，感觉平时没搞明白的地方，突然彻底掌握了。但这只是理论知识，想真正完成一份完美的设计报告，这些是不够的。于是通过图书馆、网络，查找了许多相关的内容，受益非浅。等到在看这个题目是，心里也不会那么恐惧了，因为设计所用到的知识我都掌握了。剩下的内容就是和小组成员很顺利的完成了这份报告。参考文献：1编译原理及编译程序构造，秦振松编，东南大学出版社，19972程序设计语言编译原理，陈火旺编，国防工业出版社，20003编译原理（第2版），张素琴、吕映芝等编，清华大学出版社，2007附录（核心代码罗列）#include#include#include#include#define FileName TestOPG#define M 8#define N 8#define Buf 256using namespace std;typedef struct Tablechar leftOpt;char rev;char rightOpt;Table;void buildTable(Table tableN)int i = 0;Table *t = &table00;FILE *fp;if(fp=fopen(FileName,r)=NULL)cout不能打开文件n;while(ileftOpt),&(t-rev),&(t-rightOpt);t+;i+;/在算符优先矩阵中查找各算符的优先关系char find(char leftOpt,char rightOpt,Table tableN)int i,j;i = 0 ;while(iM)if(tablei0.leftOpt = leftOpt)break;i+;j = 0 ;while(jN)if(tableij.rightOpt = rightOpt)return tableij.rev ;j+;return E;void getString(char buf)printf(请输入您要验证表达式串n);scanf(%s,buf);void test(Table tableN)char bufBuf;int i = 0 ;int FLAG; /数字输入标志/输入字符串getString(buf);stack st_opt;char ch17 = #,(,),*,+,-,/,0,1,2,3,4,5,6,7,8,9;st_opt.push(#);while(bufi != 0)if(bufi9)&(bufi!=+)&(bufi!=-)&(bufi!=*)&(bufi!=/)&(bufi!=()&(bufi!=)&(bufi!=#)printf(输入错误:%sn,buf);return ;FLAG = 0 ;while(bufi = 0) & (bufi = 9)i+;/如果输入的是数字，则将数字移进FLAG = 1 ;if(FLAG