lr分析表及分析器的构造课程设计

《lr分析表及分析器的构造课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计LR(0)分析器自动构造程序的实现2009年12月课程设计任务书设计题目LR(0)分析表及分析器的构造成绩主要内容1.对任意给定的文法，完成识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2.判断该文法是否为文法，实现分析表的构造，并输出到指定文件中；3.实现分析器总控程序，对输入的表达式进行文法分析。指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力。程序设计方案。论文论述，文理，格式。程序运行结果。程序验收时回答问题。签名：目录第一章概述4第二章设计的基本原理52.1识别文法的LR(

2、0)项目集规范族的构造52.2LR(0)分析表的构造52.3LR(0)分析器总控程序构造6第三章程序设计73.1程序总体构架73.2程序存储结构83.2.1符号表存储结构83.2.2产生式表存储结构83.2.3项目集规范族表存储结构93.2.4LR(0)分析表存储结构93.3程序算法103.3.1项目集规范族的构造103.3.2LR(0)分析表构造11第四章程序测试124.1符号表测试124.2产生式表测试134.3项目集规范族表测试134.4LR(0)分析表测试144.5LR(0)分析器测试14第五章总结和展望15参考文献16附录17第一章概述本

3、课程设计完成了以下内容：1.实现了对任意给定的文法，识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2.判断该文法是否为文法，实现了分析表的构造，并输出到指定文件中；3.实现了分析器总控程序，对输入的表达式进行文法分析。第二章设计的基本原理本课程设计的核心算法[1]主要有三点：1.识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2.分析表的构造；3.分析器总控程序的构造。2.1识别文法的LR(0)项目集规范族的构造采用（闭包）的构造一个文法的项目规范簇。假定是文法的任一项目集，定义和构造的闭包的算法：（1）的任何项目都属于；（2）若属于

4、，那么，对任何关于的产生式，项目也属于；（3）重复执行上述两个步骤直至不再增大。其中初始，为对文法进行拓广构造而引进的不出现在中的非终结符。定义状态转换函数，的第一个变元是一个项目集，第二个变元是一个文法符号。函数值定义为。其中={任何形如的项目

5、属于}2.2LR(0)分析表的构造假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集合的下标为分析器的初态。分析表的子表和子表可按如下方法构造：（1）若项目属于且，为终结符，则置为“把移近栈”，简记为“”。（2）若项目属于，那么对于任何终结符（或结束符#），置为“用产生式进行规约”，简记

6、为“”（假定产生式是文法的第j个产生式）（3）若项目属于，则置为“接受”，简记为“acc”。（4）若，则置。（5）分析表中凡不能用规则1~4填入信息的空白处均置上“报错标志”。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是文法。2.3LR(0)分析器总控程序构造分析表包括量部分，“动作”表和“状态转换”表。规定了当状态面临输入符号时应采取什么动作。规定了状态面对文法符号时下一状态是什么。每一项所规定的动作不外乎是下述四种可能之一。（1）移进把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。（

7、2）归约指用某一产生式进行规约。假若的长度为,规约的动作是，去除栈顶的个项，使状态变成栈顶状态，然后把的下一状态推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。（3）接受宣布分析成功，停止分析器工作（4）报错发现源程序含有错误，调用出错处理程序。第三章程序设计3.1程序总体构架本课程设计开发的程序主要由4张表组成，分别为：符号表、产生式表、表和项目集规范簇表。同时，项目集规范簇表包含一个分析栈作为分析器总控程序。产生式表包含符号表作为子表，项目集规范簇表包含产生式表、表作为子表。程序工作流程：1.读取含有文法规则的文件，为该文法中的

8、每一个不同的文法符号（终结符和非终结符分配一个编号），记录文法符号的属性（终结符/非终结符），存储于一张符号表中；2.再次读取文件，将产生式存储于产生式表中；3.根据产生式构建项目集规范族，存储于表中；4.根据构建的项目集规范族构建分析表，填写分析表同时检查该文法是否为文法；5.对于输入的表达式，分析器根据构建的分析表进行文法分析，给出分析结果。3.2程序存储结构3.2.1符号表存储结构动态数组下标，同时作为符号的编号标识符是否为非终结符3.2.2产生式表存储结构产生式标号非终结符标号（与中的一致）指示当前非终结符的产生式当前非终结符产生式的长度，

9、用于帮助区分一个产生式的不同项目，即项目个数等于指示下一个非终结符一个产生式中的标识符名（与中的一致）一个产生式中的下一个