1、 课 程 设 计 LR(0)分析器自动构造程序的实现 2009 年 12 月 课程设计任务书 设 计 题 目 LR(0)分析表及分析器的构造 成绩成绩 主 要 内 容 1. 对任意给定的文法，完成识别文法活前缀的、的状态转化矩阵及项目集 规范族的构造； 2. 判断该文法是否为文法，实现分析表的构造，并输出到指定文件中； 3. 实现分析器总控程序，对输入的表达式进行文法分析。 指 导 教 师 意 见 该生能按时完成课程设计任务书所规定的程序设计，综合运用 所学 知识独立分 析和解决问 题的能力 。程序设 计方 案 。论文论述 ，文理 ，格式 。程 序运行结果 。程序验收时回答问题 。 签名：签名
2、： 目目 录录 第一章第一章 概概 述述 4 4 第二章第二章 设计的基本原理设计的基本原理 5 5 2.1 识别文法的 LR(0)项目集规范族的构造 . 5 2.2 LR(0)分析表的构造 5 2.3 LR(0)分析器总控程序构造 6 第三章第三章 程序设计程序设计 7 7 3.1 程序总体构架 . 7 3.2 程序存储结构 . 8 3.2.1 符号表存储结构 . 8 3.2.2 产生式表存储结构 . 8 3.2.3 项目集规范族表存储结构 . 9 3.2.4 LR(0)分析表存储结构 9 3.3 程序算法 10 3.3.1 项目集规范族的构造 10 3.3.2 LR(0)分析表构造 . 1
3、1 第四章第四章 程序测试程序测试 1212 4.1 符号表测试 12 4.2 产生式表测试 13 4.3 项目集规范族表测试 13 4.4 LR(0)分析表测试 . 14 4.5 LR(0)分析器测试 . 14 第五章第五章 总结和展望总结和展望 1515 参考文献参考文献 1616 附录附录 1717 第一章第一章 概概 述述 本课程设计完成了以下内容： 1. 实现了对任意给定的文法，识别文法活前缀的、的状态转化矩阵及项目集规 范族的构造； 2. 判断该文法是否为文法，实现了分析表的构造，并输出到指定文件中； 3. 实现了分析器总控程序，对输入的表达式进行文法分析。 第二章第二章 设计的基
4、本原理设计的基本原理 本课程设计的核心算法 1主要有三点：1. 识别文法活前缀的、的状态转化矩阵 及项目集规范族的构造；2.分析表的构造；3.分析器总控程序的构造。 2.12.1 识别文法识别文法的的 LR(0)LR(0)项目集规范族的构造项目集规范族的构造 采用（闭包）的构造一个文法的项目规范簇。 假定是文法的任一项目集，定义和构造的闭包的算法： （1）的任何项目都属于； （2）若属于，那么，对任何关于的产生式，项目也属于； （3）重复执行上述两个步骤直至不再增大。 其中初始，为对文法进行拓广构造而引进的不出现在中的非终结符。 定义状态转换函数，的第一个变元是一个项目集，第二个变元是一个文法
5、符号。 函数值定义为。 其中 = 任何形如的项目|属于 2.22.2 LR(0)LR(0)分析表的构造分析表的构造 假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集 合的下标为分析器的初态。分析表的子表和子表可按如下方法构造： （1）若项目属于且，为终结符，则置为“把移近栈” ，简记为“” 。 （2）若项目属于，那么对于任何终结符（或结束符#） ，置为“用产生式进行规 约” ，简记为“” （假定产生式是文法的第 j 个产生式） （3）若项目属于，则置为“接受” ，简记为“acc” 。 （4）若，则置。 （5）分析表中凡不能用规则 14 填入信息的空白处均置上“报错标志” 。
6、如果 分析表中任何一项被重复填入，则说明分析表的入口不是唯一的， 项目集中存在冲突 项目，该文法不是文法。 2.32.3 LRLR(0)(0)分析器总控程序构造分析器总控程序构造 分析表包括量部分， “动作”表和“状态转换”表。规定了当状态面临输入符号 时应采取什么动作。规定了状态面对文法符号时下一状态是什么。 每一项所规定的动作不外乎是下述四种可能之一。 （1）移进 把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。 （2）归约 指用某一产生式进行规约。假若的长度为,规约的动作是，去除栈顶 的个项，使状态变成栈顶状态，然后把的下一状态推进栈。规约动作不改变现行输入 符号。规约动作不改变现行输入符号。 （3）接受 宣布分析成功，停止分析器工作 （4）报错 发现源程序含有错误，调用出错处理程序。 第三章第三章 程序设计程序设计 3.13.1 程序总体构架程序总体构架 本课程设计开发的程序主要由 4 张表组成，分别为：符号
