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

淮阴工学院编译原理课程设计报告选题名称:算符优先分析法系（院）:计算机工程学院专业:计算机科学与技术班级:计算机1075姓名:学号:指导教师:学年学期:2009~2010学年第2学期2010年5月17日设计任务书课题名称算符优先分析法设计目的通过一周的课程设计，对算符优先分析法进行分析，编程实现算符优先分析器，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统VisualC++6.0以上编译环境任务要求任务：整理算符优先分析法方面的资料；根据已知文法编写程序代码，实现算符优先分析法；撰写课程设计报告；参加答辩。工作进度计划序号起止日期工作内容12010.05.17~2010.05.18理论辅导，搜集资料22010.05.18~2008.06.20编写代码，上机调试32008.06.20~2008.06.21答辩42008.06.21~2008.06.21撰写课程设计报告指导教师（签章）：年月日摘要：编译原理是计算机系统的基本组成部分之一，而且多数据计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。算符优先分析法是一种简单直观、广为使用的自下而上分析法。这种方法特别有利于表达式分析，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓算符优先分析就是定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。关键词：编译原理；归约；算法；算符优先；编译目录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参考文献.....................................................................................................................17《编译原理课程设计报告》11需求分析本次课程设计的题目是算符优先分析法。算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约。它是一种不规范归约法。根据已知文法：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)输入测试字符串，输出测试结果给出关键类类图、整个应用程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在windows运行的可以根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确，输入测试字符串，输出测试结果的完整应用程序。2概要设计2.1算符优先分析法的思想及其原理算符优先分析算法算法原理：（1）初始化栈：k=1;S[k]=‘#’；（2）依次从输入串中读入符号a：①当前单词若为标识符，则a值为i，若为常数则a值为d；其它a直接取单词值。②若a大于等于栈顶第一个终结符的优先级，则a进栈；③若a小于栈顶第一个终结符的优先级，则重复做：《编译原理课程设计报告》2i)找出最左子串S[j]⋖S[j+1]=…=S[k]⋗a；ii)把S[j+1]…S[k]归约为某个N；iii)将归约后的非终结符N入栈；④出错处理。若输入串扫描完毕，且栈中呈现#S，且a为#，则符合语法要求，否则就不符合语法要求。2.1.1算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。2.1.2优先关系的定义设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系、、定义如下：①ab当且仅当G中含有形如A→…ab…或A→…aBb…的产生式②ab当且仅当G中含有形如A→…aB…的产生式，且Bb…或BCb…③ab当且仅当G中含有形如A→…Bb…的产生式，且B…a或B…aC以上三种关系也可由下列语法树来说明：①ab则存在语法子树如图2.1(a)其中δ为ε或为B，这样a,b在同一句柄中同时归约所以优先级相同。②ab则存在语法子树如图2.1(b)其中δ为ε或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。《编译原理课程设计报告》3③ab则存在语法子树如图2.1(c)。图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)若有产生式P-…a或P-…aQ，则a属于LastVT集。(2)若a属于LastVT（Q），且有产生式P-〉…Q，则a属于LastVT集。构造FirstVT集的算法：BeginFor每个非终结符P和终结符aDoF[P，a]=FALSE；For每个形如P-〉a…或P-〉Qa…的产生式……（1）DOinsert（P，a）WhileStack非空DoBegin把Stack的顶项，记为（Q，a），上托出去；A…aδb…A…aB…A…bB…Pδb…P…aδ(a)ab(b)ab(c)ab《编译原理课程设计报告》4For每条形如P-〉Q…的产生式DO…….（2）Insert（P，a）Endofwhile；END2.2算符优先分析算法2.2.1算符优先分析句型的性质如果aNb(或ab)出现在句型r中，则a和b之间有且只有一种优先关系,即：若ab则在r中必含有b而不含a的短语存在。若ab则在r中必含有a而不含b的短语存在。若ab则在r中含有a的短语必含有b，反之亦然。2.2.2最左素短语设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例如,若表达式文法G[E]为：E→E+T|TT→T*F|FF→P↑F|PP→(E)|i图2.2句型T+T*F+i的语法树若有句型#T+T*F+i#，它的语法树如图2.2。其短语有：T+T*F+i相对于非终结符E的短语T+T*F相对于非终结符E的短语ET+ET+ETT*FFPi《编译原理课程设计报告》5T相对于非终结符E的短语T*F相对于非终结符T的短语i相对于非终结符P,F,T的短语由以上内容知i和T*F为素短语，T*F为最左素短语。也为算符优先分析的可归约串。由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条件：ai-1aiai+1...ajaj+1上述句型#T+T*F+i#写成算符分析过程的形式为：#N1a1N2a2N3a3a4