编译原理课程设计报告
选题名称: 算符优先分析法 系（院）: 专 业:
计算机工程学院
计算机科学与技术
班 级: 计算机1083班 姓 名: 毛金花 学 号: 1081301315 指导教师: 杨荣根 陈剑洪
学年学期: 2010 ~ 2011 学年 第 1 学期
2011年 01 月 07 日
设计任务书
课题 名称 算符优先分析法 通过一周的课程设计，对算符优先分析法有深刻的理解，达到巩固理论设计 目的 知识、锻炼实践能力、构建合理知识结构的目的。 实验环境 任务要求 Windows2000以上操作系统，Visual C++6.0编译环境 1.判断文法是否为算符优先文法，对相应文法字符串进行算符优先分析； 2.编写代码，实现算符优先文法判断和相应文法字符串的算符优先分析； 3.撰写课程设计报告； 4.参加答辩。 工作进度计划 序号 1 2 3 4 起止日期 2011.01.03 2011.01.04～2011.01.05 2011.01.06 2011.01.07 工 作 内 容 理论辅导，搜集资料 编写代码，上机调试 撰写课程设计报告 答辩
指导教师（签章）：
年 月 日
摘要：
编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析，并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的规范归约。而在整个归约过程中，起决定作用的是相继连个终结符之间的优先关系。因此，所谓算符优先分析法就是定义算符之间的某种优先关系，并借助这种关系寻找句型的最左素短语进行归约。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。
关键字： 编译原理；算符优先分析；最左素短语
目 录
1 课题综述 .................................................................................................................................... 1
1.1 课题来源 ................................................................................................................................ 1 1.2 课题意义 ................................................................................................................................ 1 1.3 预期目标 ................................................................................................................................ 1 1.4 面对的问题 ............................................................................................................................ 1
2 系统分析 .................................................................................................................................... 2
2.1 基础知识 ................................................................................................................................ 2 2.2 解决问题的基本思路 ............................................................................................................ 5 2.3 总体方案 ................................................................................................................................ 5
3 系统设计 .................................................................................................................................... 6
3.1 算法实现 ................................................................................................................................ 6 3.2 流程图 .................................................................................................................................... 7
4 代码编写 .................................................................................................................................... 8 5 程序调试 .................................................................................................................................. 10 6 运行与测试 ............................................................................................................................. 11 总 结 .......................................................................................................................................... 13 致 谢 .......................................................................................................................................... 14 参 考 文 献 ............................................................................................................................... 15
1 课题综述
1.1 课题来源
算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都只满足>，=，<的关系的一种，则称G是一个算符优先文法。
1.2 课题意义
算符优先文法在规约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需知道把当前句柄规约为某一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的规约，因为若只有一个非终结符时无法与句型中该非终结符的左部及右部的串比较优先关系。也就无法确定该非终结符为句柄。
1.3 预期目标
编写程序，实现文法的算符优先判断，并对输入的符合算符优先文法的字符串进行算符优先分析。首先对输入的表达式求FIRSTVT集和LASTVT集，然后根据优先级关系构造算符优先关系表，最后进行算符优先分析的过程。过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索知识的习惯。
1.4 面对的问题
如何通过自底向上的方法分析表达式，构造文法的优先矩阵，以及如何运用该优先矩阵完成移入和归约的过程，从而完成整个文法的分析。
1.5 需解决的关键技术
本次课程设计中的关键是：扫描和语法分析函数，它使用一个用于存放文法符号的先进后出栈，并利用有限关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和带输入符号之间优先关系是<或=则表示栈顶符号串未形成最左素短语，此时分析器将移进输入符号。如果当前栈顶的终结符号和待输入符号之间的优先关系是>，则表示已找到最左素短语的尾，在从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误。以
1
及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。
2 系统分析
2.1 基础知识
2.1.1 算符优先分析法的基本思想
仿照算术表达式的四则运算过程
算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。
2.1.2算符优先关系的定义
设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系 ① a ② aCb… ③ a…aC
以上三种关系也可由下列语法树来说明： ① a
b 则存在语法子树如图2.1(a)
b当且仅当G中含有形如A→…Bb …的产生式，且B…a 或B
、
、
定义如下 ：
b 当且仅当G中含有形如A→…ab…或A→…aBb…的产生式 b 当且仅当G中含有形如A→…aB …的产生式，且B
b… 或B
其中δ为ε或为B，这样a, b在同一句柄中同时归约所以优先级相同。 ② a
b 则存在语法子树如图2.1(b)
其中δ为ε或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。 ③ a
b 则存在语法子树如图2.1(c) 。
2
图2.1 由语法树结构决定优先性
2.1.3算符优先文法的定义
设有一文法G，如果G中没有形如A→…BC…的 产生式，其中B和C为非终结符，则称G为算符文法(Operater Grammar)也称OG文法。 例如：表达式文法E→E+E|E*E|(E)|i
其中任何一个产生式中都不包含两个非终结符相邻的情况，因此该文法是算符文法。
设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有
、
和
三种关系中的一种成立，则称G是一个算符优先文法。
(Operator Precedence Grammar)即OPG文法。
由以上内容我们可计算出给定的算符文法中任何两个终结符对(a,b)之间的优先关系，其算法如下：
首先定义如下两个集合： FIRSTVT(B)={b|BLASTVT(B)={a|B
b… 或 B…a 或 B
Cb…} …aC}
三种优先关系的计算为 a)
关系:
可直接查看产生式的右部，对如下形式的产生式 A→…ab… , A→…aBb… 有a b)
b 成 立。 关系:
3
求出每个非终结符B的FIRSTVT(B)，在如下形式的产生式 A→…aB… 中，对每一 b∈FIRSTVT(B),有ac)
关系:
b成立。
计算每个非终结符B的LASTVT(B)，在如下形式的产生式 A→…Bb… 中，对每一a∈LASTVT(B)，有a2.1.4 最左素短语的定义
设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。
例如,若表达式文法G[E]为： E→E+T|T T→T*F|F F→P↑F|P P→(E)|i
b成立。
图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为最左素短语。也为算符优先分析的可归约串。由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条
4
件：
ai-1
ai
ai+1
...
aj
aj+1
上述句型#T+T*F+i#写成算符分析过程的形式为： #N1a1N2a2N3a3a4#其中a1 = +, a2 = *, a3 = +, a4 = i a1 a2
a2 (因+ a3 (因*
*) +)
由此 N2a2N3 即T*F为可归约串，也就是前面分析的最左素短语。
2.2 解决问题的基本思路
根据课程设计的要求，程序应具有如下功能：对输入的文法进行分析并判断是否为算符优先文法。如果是算符优先分析文法则再进一步输入符合该算符优先 文法的字符串，并对该字符串进行算符优先分析，同时输出算符优先分析的过程。
2.3 总体方案
启动VC++，新建源程序并进行编程，程序的功能模块图如图2-1所示。 图2-1系统功能结构图
函数功能：
Main()函数：调用主函数，运行程序； FIRSTVT()函数：构造FIRSTVT表； LASTVT()函数：构造LASTVT表； OpPrioTable()函数：构造算符优先关系表；
InputAnalyse()函数：分析输入串是否为文法中的句子，并给出规约过程。
5
主函数mainFirstVt函数LastVt函数OpPrioTable函数InputAnalyse函数3 系统设计
3.1 算法实现
算符优先分析法的具体过程如下：
1、首先先输入文件的路径，在readfile(char sen[][col])函数中，将需要分析的文法通过输入流文件打开函数open()复制到sen[row][col]中。
2、然后利用FIRSTVT( )构造产生式sen[row][col]的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 ]>a，将S[ j -1]到栈顶S[ k ]规约，若S[ j ]= a ，如果S[ j ]=#，则接受，如果S[ j ]！=#，则移进。直到接受或者出错，算符优先分析结束。
6
3.2 流程图
读入.txt文件初始化存放产生式的数组判断是否为算符文法打印文法不是算符文法初始化操作栈操作栈是否为空N弹出栈顶填入FIRSTVT表Y反转构造LASTVT表构造算符优先关系表头产生式全扫描完？输入串分析当前输入符给a初始化分析栈SK=1，S[K]=#YN扫描产生式相邻符号构造算符优先关系表NOpTable[i][j]=’\\0’找离栈顶最近的终结符S[j]YS[j] 7 4 代码编写 在这次课程设计过程中，我主要负责的是文件导入及主函数的实现的构造部分，代码如下。 //读文件函数 int readfile(char sen[][col]) { } //主函数部分 void main() { char char choice='y'; while(choice=='y') { system(\"cls\"); char addr[50]; cout<<\"请输入要读文件的地址（\\\\用\\\\\\\\表示）：\"< for(int i=0;!fin.eof();i++) { } return i; fin>>sen[i]; cout< sen[row][col]={'\\0'},first[row][col]={'\\0'},last[row][col]={'\\0'},opTable[row][col]={'\\0'}; char string[col]; if(PrioGramJud(sen,p)==true) { ItemInit(sen,first,last,p,q); //j记录FIRSTVT和LASTVT表的长度 p=readfile(sen); int i,k,p,q; FirstVt(sen,first,p,q); cout<<\"\各非终结符FIRSTVT集\"< { cout<<\"\优先关系表：\"< } } } } for(i=0;i InputAnalyse(opTable,string,k); //k是opTable表的长度 cout< 5 程序调试 程序中调用了许多函数，编写代码时会出现调用的错误，使在程序运行时无法正确判断以致程序运行出错。在创建函数时会出现错误而无法得知，致使在程序运行时出错，需要很细心的去编写代码。编程的时候一定要细心，对出现的错误要认真调整，反复修改，使函数前后相对应。 10 6 运行与测试 运行界面如下： 图6-1 运行结果图1 图6-3 运行结果图3 11 图6-1 运行结果图2 图6-4 运行结果图4 12 总 结 通过本周的课程设计,加深了对于编译原理中算符优先分析算法的理解,通过自己编写一个程序去实现这个算法,增强了对于编译原理的理解和应用能力,从另一个方面,提高了理论与实践相结合的能力,锻炼了使用VC6等编程环境将课上所学习的各种理论知识转换为可执行的应用程序并使用其解决问题的能力,为进一步深入学习编译原理打下了良好的基础,加深了动手能力的锻炼。 我们设计的这个系统的目标是编写程序，实现文法的算符优先判断，并对输入的符合算符优先文法的字符串进行算符优先分析。首先对输入的表达式求FIRSTVT集和LASTVT集，然后根据优先级关系构造算符优先关系表，最后进行算符优先分析的过程。 在这次课程设计中需解决的问题有：扫描和语法分析函数，它使用一个用于存放文法符号的先进后出栈，并利用有限关系可以确定最左素短语是否已形成来决定分析器的动作。如果当前栈顶的终结符号和带输入符号之间优先关系是<或=则表示栈顶符号串未形成最左素短语，此时分析器将移进输入符号。如果当前栈顶的终结符号和待输入符号之间的优先关系是>，则表示已找到最左素短语的尾，在从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后分析器将归约最左素短语。如果出现两个终结符号之间不存在优先关系，则表示存在语法错误。调试代码的过程中遇到问题，就赶紧利用网络资源搜集正确的解决方法，或者去图书馆查找资料，再与同学讨论终于得出正确的解决方案，我了解一个问题有许多种解决方法，但要找到自己认为最简单有效的方法。 回想刚刚过去的忙碌的一周，感触颇多，收获颇丰。通过翻阅各种参考文献，对编译原理课程设计的知识有了初步的了解，收获最大的地方就是锻炼了自己的独立思考能力和解决问题的能力。 13 致 谢 本次实验历时一周,与其他几位同组的同学一起,以编译原理课上所学知识为基础,通过编程实现一个能够实现算符优先算法的程序。在此过程中遇到了许许多多的问题,在各位老师的不倦指导和其他同学的热心帮助下,充分利用了网络搜索引擎的强大功能和学校图书馆的大量相关书籍,最终解决了所遇到的各种各样的问题,完成了预定的任务。在此特别感谢淮阴工学院计算机工程学院提供时间机会,感谢系部提供优良的实验环境,感谢各位老师的辛勤指导,以及各位同学不遗余力的团结互助,使得最后能够解决理论基础知识以及编程上的各种问题,最终得以完成任务。要特别感谢给我们指导的杨荣根、王文豪、陈剑洪老师，是你们悉心指导我们怎样去解决实践中遇到的问题，使问题得以顺利解决，使我们的课程设计更加顺利地进行，老师们勤勤恳恳的工作精神是值得我们永远学习的，在此谨向所有的课程设计指导老师致以由衷的感谢和崇高的敬意！当然，还要感谢帮助过我的所有同学，在本次课程设计的选题、研究与实验过程中，他们提供了我许多信息，让我对课程设计的步骤有了相当的了解，是他们鼓励了我让我有自己尝试的勇气，还有他们给我所提的建议以及他们给予我的帮助对于我能顺利完成此次课程设计也是必不可少的，在此表示衷心的感谢!总之，是因为大家的帮助，我才能顺利地完成本次课程设计，在这里衷心地向他们道声感谢，谢谢你们！ 在此，再次深深感谢淮阴工学院、计算机工程系提供的实践机会，实验室人员提供的实验环境，指导教师的辛勤指导，同组同学的互帮互助，参考文献的原作者，以及所有给我提供过帮助的所有人员和机构。 14 参 考 文 献 1 编译原理及实践教程/黄贤英, 王柯柯编著 北京:清华大学出版社,2008 2 编译原理及实现/孙悦红编著 北京:清华大学出版社,2005 3 编译原理学习辅导/张伟编著 北京:清华大学出版社,2005 4 编译原理课程设计/王雷，刘志成著 北京：机械工业出版社,2005 5 编译原理和技术/丁文魁, 杜淑敏编著 15 北京:电子工业出版社,2008 指导教师评语 学号 1081301315 选题 算符优先分析法 名称 序号 1 姓名 毛金花 班级 计1083 评价内容 考勤记录、学习态度、工作作风与表现。 权重（%） 5 得分 2 3 自学情况： 上网检索机时数、文献阅读情况（笔记）。 论文选题是否先进，是否具有前沿性或前瞻性。 成果验收： 10 5 4 是否完成设计任务；能否运行、可操作性如何等。 报告的格式规范程度、是否图文并茂、语言规20 5 范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。 30 6 文献引用是否合理、充分、真实。 答辩情况： 5 7 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。 25 合计 指导教师（签章）： 年 月 日 因篇幅问题不能全部显示，请点此查看更多更全内容