算符优先分析法课程设计报告

1、淮阴工学院编译原理课程设计报告选题名称: 算符优先分析法 系（院）: 计算机工程学院 专 业: 计算机科学与技术班 级: 计算机1075 姓 名: 学 号: 指导教师: 学年学期: 2009 2010 学年 第 2 学期2010年 5 月 17 日设计任务书课题名称算符优先分析法设计目的通过一周的课程设计，对算符优先分析法进行分析，编程实现算符优先分析器，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境windows2000以上操作系统visual c+6.0以上编译环境任务要求任务：整理算符优先分析法方面的资料；根据已知文法编写程序代码，实现算符优先分析法；撰写课程设计报告；

2、参加答辩。工作进度计划序号起止日期工 作 内 容12010.05.172010.05.18理论辅导，搜集资料22010.05.182008.06.20编写代码，上机调试32008.06.202008.06.21答辩42008.06.212008.06.21撰写课程设计报告指导教师（签章）： 年 月 日 摘要：编译原理是计算机系统的基本组成部分之一，而且多数据计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。算符优先分析法是一种简单直观、广为使用的自下而上分析法。这种方法特别有利于表达式分析，宜于手工实现。算

3、符优先分析过程是自下而上的归约过程，但这种归约未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓算符优先分析就是定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。关键词：编译原理；归约；算法；算符优先；编译目 录1需求分析12 概要设计12.1算符优先分析法的思想及其原理12.2算符优先分析算法42.3 构建算符优先关系表62.4 出错处理73 详细设计73.1 程序流程图73.2 构建算符优先关系表83.3 进栈优先函数83.4 算符优先规约函数103.5 弹出窗体124 程序运行、调试及操作说明12总 结15致 谢16参考

4、文献171需求分析本次课程设计的题目是算符优先分析法。算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约。它是一种不规范归约法。根据已知文法：e-e+t|e-t|tt-t*f|t/f|ff-(e)|i(e)|i|d（其中d表示0-9的数字，i表示字母，大小写均包括）根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确(1)可以使用任何语言来完成，例如：java、c+。(2)构造此文法的分析过程(3)输入测试字符串，输出测试结果给出关键类类图、整个应用

5、程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在windows运行的可以根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确，输入测试字符串，输出测试结果的完整应用程序。2 概要设计2.1算符优先分析法的思想及其原理算符优先分析算法算法原理：（1）初始化栈：k=1; sk=#；（2）依次从输入串中读入符号a： 当前单词若为标识符，则a值为i，若为常数则a值为d； 其它a直接取单词值。 若a大于等于栈顶第一个终结符的优先级，则a进栈； 若a小于栈顶第一个终结

6、符的优先级，则重复做： i)找出最左子串sjsj+1=ska； ii)把sj+1sk归约为某个n； iii)将归约后的非终结符n入栈； 出错处理。若输入串扫描完毕，且栈中呈现#s，且a 为#，则符合语法要求，否则就不符合语法要求。2.1.1算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中

7、的符号和剩余的输入符号构成句型的最左素短语。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

8、b 则存在语法子树如图2.1(c) 。a a b a a b a b b p b p a (a)ab(b)ab(c)ab图2.1 由语法树结构决定优先性2.1.3算符优先文法的定义那么定义firstvt(p)=a|p-a、或p-qa、，a属于终结字符集，而q属于非终结字符集 lastvt（p）=a|p-.a或p-.aq，a属于终结字符集，而q属于非终结字符集 由以下两条规则来构造firstvt集： (1)若有产生式p-a、或p-qa，则a属于firstvt（p）； (2)若有a属于firstvt（q），且有产生式p-q，则a属于firstvt(p); 类似的有构造lastvt集的规则： (1)

9、若有产生式p-a或p-aq，则a属于lastvt集。 (2)若a属于lastvt（q），且有产生式p-q，则a属于lastvt集。 构造firstvt集的算法： 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； end2.2算符优先分析算法2.2.1算符优先分析句型的性质如果anb(或ab)出现在句型

10、r中，则a和b之间有且只有一种优先关系,即：若a b则在r中必含有b而不含a的短语存在。若a b则在r中必含有a而不含b的短语存在。若a b则在r中含有a的短语必含有b，反之亦然。2.2.2最左素短语设有文法gs,其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例如,若表达式文法ge为：ee+t|ttt*f|ffpf|pp(e)|iet+et+ett*ffpi图2.2 句型t+t*f+i的语法树若有句型#t+t*f+i#，它的语法树如图2.2。其短语有：t+t*f+i 相对于非终结符e的短语t+t*f 相对于非终结符e的短语t 相对于非终

11、结符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.3 算符优先分析归约过程的算法自底向上的算符优先分析法，也为自左

12、向右归约，我们已经知道它不是规范归约。规范归约的关键问题是如何寻找当前句型的句柄，而算符优先分析归约的关键是如何找最左素短语。最左素短语 niaini+1ai+1 ajnj+1 应满足：ai-1 aiai ai+1 ajaj aj+1在文法的产生式中存在右部符号串的符号个数与该素短语的符号个数相等，非终结符号对应 nk,(k=i，j+1)不管其符号名是什么。终结符对应ai，aj，其符号名要与ai，aj的 实际名相一致，相应位置也一致，才有可能形成素短语。由此，我们在分析过程中可以设置一个符号栈s，用以寄存归约或待形成最左素短语的符号串，用一个工作 单元a存放当前读入的终结符号，归约成功的标志是

13、当读到句子结束符#时，s栈中只剩#n，即只剩句子最左括号#和一非终结符n。下面给出分析过程的示 意图如图2.3。最初值k:=1,sk:=#当前输入符读入askvr？j:=kj:=k-1sj asj a?q:=sjs(j-1)vr?j:=j-1j:=j-2sj qsj+1sk归纳为nk:=j+1 sk:=nsj a?sj #出错k:=k+1sk:=a检查是否正常结束结束出错ynyynynnynnnnyyy图 2.3 算符优先分析归约过程框图在归约时要检查是否有对应产生式的右部与sj+1sk相符，若有才可归约，否则出错。在这个分析过程中把#也放在终结符集中。sj+1sk为s栈中符号串，sk为栈顶符

14、号。所谓检查是否有对应产生式的右部与sj+1sk相符，是指符号个数是否相等，对应的终结符名是否相同。不管非终结符名字。规范归约时句柄为某一产生式的右部，归约结果为从符号栈中去掉与句柄相同的产生式右部符号串，并把左部非终结符放入栈中，代替归约前的句柄。2.3 构建算符优先关系表假定g是一个不含e-产生式的算符文法。对于任何一对终结符a、b，我们说：1. ab当且仅当文法g中含有形如pab或paqb的产生式；2. ab当且仅当g中含有形如par的产生式，而rb或rqb；3. ab当且仅当g中含有形如prb的产生式，而ra或raq。如果一个算符文法g中的任何终结符对（a，b）至多只满足下述三关系之一

15、： ab，ab， ab 则称g是一个算符优先文法。 现在来研究从算符优先文法g构造优先关系表的算法。通过检查g的每个产生式的每个候选式，可找出所有满足ab的终结符对。为了找出所有满足关系和的终结符对，我们首先需要对g的每个非终结符p构造两个集合firstvt（p）和lastvt（p）：firstvt（p）a | pa或pqa，avt而qvn lastvt（p）a | pa或paq，avt而qvn2.4 出错处理使用算符优先分析法时，可在两种情况下，发现语法错误： 1. 若在栈顶终结符号与下一输入符号之间不存在任何优先关系； 2. 若找到某一“句柄”（此处“句柄”指素短语），但不存在任一产生式，

16、其右部为此“句柄”。 针对上述情况，处理错误的子程序也可分成几类。首先，我们考虑处理类似第2种情况错误的子程序。当发现这种情况时，就应该打印错误信息。子程序要 确定该“句柄”与哪个产生式的右部最相似。例如，假定从栈中确定的“句柄”是abc，可是，没有一个产生式，其右部包含a,b,c在一起。此时，可考虑是 否删除a,b,c中的一个。例如，假若有一产生式，其右部为aacb，则可给出错误信息：“非法b”；若另有一产生式，其右部为abdc，则可给出错误信 息：“缺少d”。3 详细设计3.1 程序流程图开始初值i=1; strstack = #strcode.getlength() 0存在非法字符fla

17、ge符值可否规约规约进栈是否是是否结束出错检测是否正常结束否出错图3.1 程序流程图3.2 构建算符优先关系表通常在算术表达式求值过程中， 运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优级， 乘除为同一优先级但运算符在前边的先做，这称为左结合，同样加减运算也是如此， 这也说明了运算的次序只与运算符有关，而与运算对象无关， 因而直观算符优先分析法的关键是对一个给定文法g，人为地规定其算符的优先顺序，即给出优先级别和同一级别中的结合性质，算符间的优先关系表示与前面介绍的优先关系的表示类似，其规定如下：ab表示a的优先性低于b。ab表示a的优先性等于b，即与b相同。ab表示a的优先

18、性高于b。但必须注意，这三个关系和数学中的是不同的，它们是有序的，也就是若有ab，不一定有ba，ab成立不一定有ba，例如：通常表达式中运算符的优先关系有+-，但没有-+成立，（）成立但没有）（成立。下面给出一个表达式的文法为ge: ee+e|e-e|e*e|e/e|ee|（e）|i我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：（1）优先级最高，遵循右结合。相当。例如：232=29=512。 也就是同类运算符在归约时为从右向左归约。即i1i2i3为i2i3先归约。（2）*，/优先级其次， 服从左结合。相当*、*/、/、/*。（3）+，-优先级最低，服从左结合。 相当+、+-、

19、-+、-。（4）对（，）规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。对于句子括号#号规定与它相邻的任何运算的优先性都比它大。此外，对运算对象的终结符i其优先级最高。综上所述，我们可对表达式运算符的优先关系构造如表3-1:表3-1 算符优先关系表+-*/()i#+_*/()i#3.3 进栈优先函数在实际上，实现算符优先分析法时，一般不用文法的优先关系矩阵，而是用两个优先函数f和g。前面用算符优先分析法时，对算符之间的优先关系，我们用优先矩阵表示，这样需占用大量的内存空间，当文法有n个非终结符时，就需要有（n+1）2个内存单元（终结符和#号），因而，在实际应用

20、中往往用优先函数来代替优先矩阵表示优先关系。它对具有n个终结符的文法，只需2(n+1)个单元存放优先函数，这样可节省大量的存储空间。缺点是原先不存在优先关系的，由于与自然数相对应，变成可比较。我们可以定义两个函数f,g满足如下条件：当ab，则令f(a)=g(b)当ab，则令f(a)g(b)对f，g我们称它为优先函数。它的值可用整数表示，下面给出其构造方法：由定义直接构造优先函数。若已知文法g终结符之间的优先关系，可按如下步骤构造其优先函数f,g。（1）对每个终结符avt（包括#号在内）令f(a)=g(a)=1，（也可是其它整数）。（2）如果ab，而f(a)g(b)则令f(a)=g(b)+1（3

21、）如果ab，而f(a)g(b)则令g(b)=f(a)+1（4）如果ab，而f(a)g(b)则令minf(a), g(b)=maxf(a), g(b)（5）重复b）d）直到过程收敛。 如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。对同一个文法的优先关系矩阵对应的优先函数不唯一，然而也有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数，例如下面优先关系矩阵：不存在优先函数f,g的对应关系。由于若存在优先函数f,g，则必定满足下列条件：由矩阵的第一行应有f(a)=g(a), f(a)g(b)由矩阵的第二行应有f(b)=g(a), f(b)=g(b)这样导致有f(a)=

22、g(a)=f(b)=g(b) 与f(a) g(b)矛盾，因而优先函数不存在。3.4 算符优先规约函数在该函数中，我们我们列出了文法中提到的所有规约规则，使用while语句使程序在strcode（剩余字符串）长度大于0时进行循环操作，直到将整个字符串分析结束。在循环体内，我们先判断当前将要读入栈的字符是否为合法字符，如若不是弹出对话框提示“存在非法字符！”（如图4.6）并结束循环。if(strcode0 != e & strcode0 != t & strcode0 != f &strcode0 != + & strcode0 != - & strcode0 != * &strcode0 !=

23、/ & strcode0 != i & strcode0 != d & strcode0 != ( & strcode0 != ) & strcode0 != #)messagebox(存在非法字符！);break;其次使用if语句对各种情形进行比较最后选择一种最佳的操作方法，是将栈中最左素短语根据规约规则进行规约，还是将下一字符压入栈中。这里我们定义了一个bool变量flag用来确定是可规约还是要进栈。if(strstack.getlength() 2)if( f(strstackstrstack.getlength() - 2) e+t; 3.5 弹出窗体程序运行过程中的一些提示窗口我们是

24、调用messagebox()来实现的。运行程序并单击“帮助”按钮，将弹出“帮助”窗口。在创建窗体后，我们引入help类并使其继承domodal类以响应相应的事件。单击“帮助”按钮调用onhelp事件。代码如下：void cmydlg:onhelp() / todo: add your control notification handler code herehelp a;a.domodal(); /打开“帮助”窗口单击“清除”按钮调用onclear()事件，清除列表框的所有内容。代码如下：void cmydlg:onclear() / todo: add your control notif

25、ication handler code heresetdlgitemtext(idc_code,);m_list.deleteallitems();updatedata(true);单击“示例”按钮调用onexample()事件，将示例添加到编辑框中。代码如下：void cmydlg:onexample() setdlgitemtext(idc_code, (i+i)*(i/d)*i(e)+i);4 程序运行、调试及操作说明运行程序显示程序主界面，在主界面上可以看到编辑框、分析树骨架列表、实现文法以及“示例”按钮、“清除”按钮、“帮助”按钮、“分析”按钮、“取消”按钮。如图4.1:编辑框分析

26、列表实现文法“示例”按钮“清除”按钮“帮助”按钮“分析”按钮 “取消”按钮图4.1 程序主界面编辑框：用来输入将要分析的算式分析树骨架列表：用来显示分析过程。如图4.3实现文法：用来显示已知文法。如图4.1“示例”按钮：单击“示例”按钮编辑框中将显示一条示例算式。如图4.3“清除”按钮：单击“清除”按钮清除编辑框和列编框中的所有内容“帮助”按钮：单击“帮助”按钮将弹出帮助窗口，显示帮助信息。如图4.2：图4.2 帮助信息“分析”按钮：单击“分析”按钮执行算符优先分析法，在分析树骨架列表中显示分析的过程。如图4.3：图4.3 分析结果“取消”按钮：单击“取消”按钮，退出程序。总 结本次编译原理课

27、程设计的题目是算符优先分析法，算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约，它是一种不规范归约法。为期一周的课程设计在紧张和忙碌中度过，虽然时间不长，但还是让我学到了不少东西，对编译原理也有了相当程度的理解。从中能锻炼到不会的要问；不会的要在书中去寻找；要会运用现代的网络去寻找新知识；要对新知识不断的探索；要有勇于探索与创新的精神。在做课程设计之前要求一定要对所做的案例进行做全面的思考，只有思考比较完善，才可以不会出现大的问题。不然到了设计过程中才发现自己

28、的设计的内容不完善，那就要再花大量的时间去修改进。磨刀不误砍柴功，还是先总揽全局比较好。无论是在软件设计还是在论文撰写的过程中都使我获益非浅，我从中不仅接触到了许多新的技术和知识，而且通过亲手实践，了解了如何把书本上所学的东西应用到实践中去。总的来说,经过这次课程设计实践,不仅使我的编程能力得到了很大的锻炼,而且让我体会到了团队合作的精神,让我感觉到了团队的温暖,增强了我们的友谊,提高了团队合作意识,这对与我们以后步入社会和参加工作都会有很大的帮助。致 谢在这里，对本次课程设计中给予帮助的人表示衷心的感谢。首先，我要向指导教师高丽老师表示感谢，她负责了本次编译原理课程设计，对我们做出了辛勤的指导。同时要向高丽老师表示感谢，她负责了本学期编译原理。她不但传授我们有关知识；而且给我们提出了以后我们在程序设计中的学习的宝贵意见，给了我们在日常学习中提出了大量的意见。必须向淮阴工学院、计算机工程学院提供的课程设计机会表示感谢，就因为他们提供了这次机会，我能圆满的完成了这次课程设计。同时要向实验室人员提供的实验环境表示感谢，对他们的辛勤劳动表示感谢。本组成员间的互帮互助，对付出辛劳的本组成员表示感谢。他们积极地参与、支持此项课程设计，并在我们感到灰心时不断