编译原理课程设计--SLR（1）文法与算符优先文法程序实现

《编译原理课程设计--SLR（1）文法与算符优先文法程序实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、编译原理课程设计学院课程设计任务书题目SLR(1)文法与算符优先文法程序实现专业、班级学号姓名主要内容Ø构造SLR(1)分析表，并用程序实现S->Sb

2、bAaA->aSc

3、aSb

4、aØ算符优先文法处理算术表达式基本要求Ø构造SLR(1)分析表，并用程序实现，测试某表达式是否该文法的句子。Ø根据算符优先分析法并用程序实现，将表达式进行语法分析，判断一个表达式是否正确。主要参考资料：[1]吕映芝，张素琴等.编译原理.清华大学出版社,1998[2]胡伦俊，徐兰芳，骆婷.编译原理(第2版).电子工业出版社,2002[3]严蔚敏，吴伟民.数据结构(C语言版).清华大学出版社,199

5、7完成期限：一周指导教师签名：课程负责人签名：2011年6月24日编译原理课程设计本科编译原理课程设计总结报告设计题目：SLR(1)文法与算符优先文法程序实现学生姓名：系别：专业：计算机科学与技术班级：08级2班学号：指导教师：2011年6月24日编译原理课程设计目录一、设计题目1二、运行环境1三、算法设计思想11、LR算法思想12、算符优先算法思想2四、算法流程图31、SLR（1）流程图32、算符优先流程图4五、算法设计分析51、SLR（1）分析设计52、算符优先文法分析与设计7六、运行结果分析81、SLR（1）运行结果82、算符优先运行结果8七、收获及体会10附录：程

6、序清单11编译原理课程设计一、设计题目SLR(1)文法与算符优先文法程序实现二、运行环境操作系统：MicrosoftWindowsXP可视化环境：MicrosoftVisualC++6.0三、算法设计思想1、LR算法思想LR分析方法在规范规约的过程中，一方面记住已移进和规约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。LR分析器实质上是一个带先

7、进后出存储器（栈）的确定有限状态自动机，每一步工作是由栈顶状态和现行输入符号所唯一决定的。LR分析器的核心部分是一张分析表。这张分析表包括两个部分，一是“动作”（ACTION）表，另一是“状态转换”（GOTO）表。他们都是二维数组。ACTION(s,a)规定了当状态s面临输入符号a时应采取什么动作。GOTO（s，X）规定了状态s面对文法符号X（终结符或非终结符）时下一状态是什么。显然，GOTO(s，X)定义了一个以文法符号为字母表的DFA。每项ACTION(s，a)所规定的动作不外是下述四种可能之一：（1）移进：把（s，a）的下一个状态s’=GOTO(s，X)和输入符号a

8、推进栈,下一输入符号变成现行输入符号。（2）规约：指用某一产生式A→β进行规约。假若β的长度为r，规约的动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r，A）的下一状态s’=GOTO(Sm-r,A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着β（=Xm-r+1…Xm19/22编译原理课程设计）已呈现于栈顶而且是一个相对于A的句柄。（3）接受：宣布分析成功，停止分析器的工作。（4）报错：发现源程序含有错误，调用出错处理程序。输入输出栈图2LR分析器的模型actiongoto…a1ai…an$smXmsm-1Xm-1s0……SLR

9、(1)分析程序1、算符优先算法思想算符优先分析方法是根据算符之间的优先关系而设计的一种自下而上的分析方法。算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。算符优先分析过程是自下而上的归约过程，所谓的算符优先分析就是定义算符之间（确切地说，终结符之间）的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。该文法必须满足以下条件：文法它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下产生式右部：…QR…；首先求出该文法的优先关系表，在程序中用2维数组表示，-1表示小于或者等于，大于为1，其它为0表示错误。在输入一串字符

10、串以后进行按照文法一步一步的进行规约，我所进行的是直接规约到文法的符号而不是规约到N。数据结构使用的是链表，用一个STRUCT来表示一个元素，其中包含符号和下一个符号的指针。算符优先分析法的关键是比较两个相继出现的终结符号的优先级而决定应采取的动作。要完成算符间的优先级比较，就要先定义各种可能出相继出现的运算符的优先级，并将其表示成矩阵形式，在分析过程中通过查询矩阵元素而得算符间的优先关系。19/22编译原理课程设计三、算法流程图1、SLR（1）流程图19/22编译原理课程设计1、算符优先流程图19/22编译原理课程设计三、算