《编译原理--LR(0)分析表及分析器的构造课程设计报告-20072575-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《编译原理--LR(0)分析表及分析器的构造课程设计报告-20072575-公开DOC·毕业论文（47页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计设计题目LR(0)分析器自动构造程序的实现学生姓名号 学 号指导教师专业班级 20072588计算机科学与技术 07-4 2009 年 12 月 47合肥工业大学课程设计任务书设 计题 目LR(0)分析表及分析器的构造成绩主要内容1. 对任意给定的文法，完成识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 判断该文法是否为文法，实现分析表的构造，并输出到指定文件中；3. 实现分析器总控程序，对输入的表达式进行文法分析。指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力 。程序设计方案 。论文论述 ，文理 ，格式 。程序运行
2、结果 。程序验收时回答问题 。 签名： 目 录第一章 概 述4第二章 设计的基本原理52.1 识别文法的LR(0)项目集规范族的构造52.2 LR(0)分析表的构造52.3 LR(0)分析器总控程序构造6第三章 程序设计73.1 程序总体构架73.2 程序存储结构83.2.1 符号表存储结构83.2.2 产生式表存储结构83.2.3 项目集规范族表存储结构93.2.4 LR(0)分析表存储结构93.3 程序算法103.3.1 项目集规范族的构造103.3.2 LR(0)分析表构造11第四章 程序测试124.1 符号表测试124.2 产生式表测试134.3 项目集规范族表测试134.4 LR(0
3、)分析表测试144.5 LR(0)分析器测试14第五章 总结和展望15参考文献16附录17第一章 概 述本课程设计完成了以下内容：1. 实现了对任意给定的文法，识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 判断该文法是否为文法，实现了分析表的构造，并输出到指定文件中；3. 实现了分析器总控程序，对输入的表达式进行文法分析。第二章 设计的基本原理本课程设计的核心算法1主要有三点：1. 识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 分析表的构造；3. 分析器总控程序的构造。2.1 识别文法的LR(0)项目集规范族的构造采用（闭包）的构造一个文法的项目规范簇。假定是文法的
4、任一项目集，定义和构造的闭包的算法：（1）的任何项目都属于；（2）若属于，那么，对任何关于的产生式，项目也属于；（3）重复执行上述两个步骤直至不再增大。其中初始 ，为对文法进行拓广构造而引进的不出现在中的非终结符。定义状态转换函数，的第一个变元是一个项目集，第二个变元是一个文法符号。函数值定义为。其中 = 任何形如的项目| 属于2.2 LR(0)分析表的构造 假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集合的下标为分析器的初态。分析表的子表和子表可按如下方法构造： （1）若项目属于且，为终结符，则置为“把移近栈”，简记为“”。 （2）若项目属于，那么对于任何终结符（或结束
5、符#），置为“用产生式进行规约”，简记为“”（假定产生式是文法的第j个产生式） （3）若项目属于，则置为“接受”，简记为“acc”。 （4）若，则置。 （5）分析表中凡不能用规则14填入信息的空白处均置上“报错标志”。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是文法。2.3 LR(0)分析器总控程序构造分析表包括量部分，“动作”表和“状态转换”表。规定了当状态面临输入符号时应采取什么动作。规定了状态面对文法符号时下一状态是什么。每一项所规定的动作不外乎是下述四种可能之一。（1）移进 把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。（
6、2）归约 指用某一产生式进行规约。假若的长度为,规约的动作是，去除栈顶的个项，使状态变成栈顶状态，然后把的下一状态推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。（3）接受 宣布分析成功，停止分析器工作（4）报错 发现源程序含有错误，调用出错处理程序。第三章 程序设计3.1 程序总体构架 本课程设计开发的程序主要由4张表组成，分别为：符号表、产生式表、表和项目集规范簇表。同时，项目集规范簇表包含一个分析栈作为分析器总控程序。产生式表包含符号表作为子表，项目集规范簇表包含产生式表、表作为子表。 程序工作流程：1. 读取含有文法规则的文件，为该文法中的每一个不同的文法符号（终结符和
7、非终结符分配一个编号），记录文法符号的属性（终结符/非终结符），存储于一张符号表中；2. 再次读取文件，将产生式存储于产生式表中；3. 根据产生式构建项目集规范族，存储于表中；4. 根据构建的项目集规范族构建分析表，填写分析表同时检查该文法是否为文法；5. 对于输入的表达式，分析器根据构建的分析表进行文法分析，给出分析结果。3.2 程序存储结构3.2.1 符号表存储结构动态数组下标，同时作为符号的编号标识符是否为非终结符3.2.2 产生式表存储结构产生式标号非终结符标号 （与中的一致）指示当前非终结符的产生式当前非终结符产生式的长度，用于帮助区分一个产生式的不同项目，即项目个数等于指示下一个非
8、终结符一个产生式中的标识符名（与中的一致）一个产生式中的下一个标识符3.2.3 项目集规范族表存储结构 1）定义二元组 ： ：产生式标号，与 中的一致 ：一个产生式的第个项目，可由 中的帮助确定 如：产生式 ： ， 2）结构：当前状态编号 指示下一状态 指示闭包中的项目 闭包中的项目名当前项目的产生的新状态的编号，即状态转移的目的地状态编号闭包中的下一个项目待构造的项目的闭包的待构造的项目的闭包待构造状态的待构造状态的项目3.2.4 LR(0)分析表存储结构指示表头的孩子结点指示表头的后继结点指示该表项的操作指示该表项的操作数指示该表项是否被填写过,用于判断文法是否为文法3.3 程序算法3.3
9、.1 项目集规范族的构造1. （初始化）将初始条件作为该状态头结点的第一个孩子结点，并构造该孩子结点的闭包，连接其后，指向第一个状态头结点，指向第一个状态头结点的第一个孩子结点；2. 查看，若为空，停止；若不为空，转3；3. 查看，若为空，转4；若不为空，构造的，检查该状态与之前构造的状态有无重复，若重复，则停止构造，的填写重复的已存在的状态的编号；若不重复，则作为一个新状态，连接于，并构造其闭包连接其后，指向。转2；4. 指向下一状态，若下一状态为空，则结束，否则，指向下一状态头结点的第一个孩子结点，转3。具体细节：设所指项目为，因为要对其构造闭包，该项目一定不是终态，所以区分项目的圆点符号
10、位于第个标识符的左侧。现在构造的闭包，分两个步骤实现：1. 构造的 ： 查看中编号为的产生式，取得该产生式的长度属性1） 若，则停止构造当前闭包（已是终态），此时 的项填；2） 否则，将作为该闭包的第一个项目，此时 的项填该新状态的状态编号。2. 构造该孩子结点的闭包 ：查看中编号为的产生式的第个标识符，取得该标识符的，查看中该标识符的类别属性3） 若为1（非终结符），则查看非终结符的所有产生 式，记这些产生式的编号为，将所有的加入闭包4） 否则，结束3. 检查该状态与之前构造的状态有无重复 :断言：任意两个状态，只要不同，则即为不同状态。3.3.2 LR(0)分析表构造对于编号为的状态，现依
11、据其项目填写分析表：1. 如果该项目形如，查看该项目的属性，1）若为终结符，则在表的状态对应行，对应列，填写，表示将把 移进栈2）若为非终结符，则在表的状态对应行，对应列，填写，表示状态转移至状态2. 如果该项目形如1）若为起始符号，则置在表的状态对应行，对应列，填写，表示接受。2）否则，对任何终结符或结束符，则在表的状态对应行，对应列，填写，表示用产生式进行规约。第四章 程序测试以文法G为例：程序模块输入：含上述文法的文件，下面展示个模块的输出结果4.1 符号表测试图6 符号表测试输出结果为 与预期结果相同图7 产生式表测试4.2 产生式表测试输出结果与读入的文件中的产生式相同，且产生式中符
12、号的编号正确4.3 项目集规范族表测试图8 产生式表测试输出结果为 ：与预期结果相同4.4 LR(0)分析表测试图9 分析表测试输出结果为分析表，与预期结果相同4.5 LR(0)分析器测试以输入字符串和为例图10 分析器测试表达式的分析结果正确第五章 总结和展望完成了编译原理课程设计之后，我感到十分的疲惫，但是那一份富有成就感的欣喜却胜过了那十分的疲惫。由于本次选题匆忙，选了一道比较有难度的题目，在做课程设计的过程中，我翻阅了很多相关资料，对课本中点到即止的知识进行了更加深入的学习，有了更加深入的理解。做课程设计的过程是痛苦的，我在这一个星期内多次熬夜战斗，有时甚至顾不上吃饭，只为了揪出程序中
13、的错误，只为了精益求精的完成这个课程设计。就在我写这份总结的时候，我发现自己我一点也不累了，反而很兴奋，很有成就感。通过本次课程设计，我发现实践是检验学习深度、学习成果的唯一途径，课本上的知识点都是浓缩的精华，在理论阐述上不可能做到面面俱到，学到的知识当然也不可能直接运用到实际情况上。在实践的过程中，我们需要将我们学习到的知识进行一定程度的扩充，本次课程设计涉及到算法，LR分析器自动构造程序的机制原理以及C+语言。在用C+语言实现本次课程设计的过程中，我更加熟悉了C+语言的语法机制，语言规范；在实现LR分析器自动构造程序的过程中，我更加熟悉了其构造程序的原理以及与之相关的算法。由于时间匆忙，我完
