编译原理课程设计

1、姓名：课程设计名称课程设计(论文)任务书 软 件 学 院 学院 专业 班 一、课程设计(论文)题目 二、课程设计(论文)工作自 2015 年 6 月 16 日起至 2013 年 6 月 19 日止。三、课程设计(论文) 地点: 软 件 学 院 实 训 中 心 四、课程设计(论文)内容要求：1本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识, 熟悉使用开发工具VC /JAVA/C#/.NET 。2课程设计的任务及要求

2、1）课程设计任务：根据自己所选择的题目填写内容2）创新要求：在基本要求达到后，可进行创新设计3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路-工作原理、功能规划（3）详细设计-数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论-给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结-设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，要求装订平整，否则要求返工；（7）课设报告的装订顺序如下：封面-任务书-中文摘要-目录-正文-附录(代码及相关图片)（8）严禁抄袭，如有发

3、现，按不及格处理。4）课程设计评分标准： （1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。5）参考文献：（1）张素琴，吕映芝. 编译原理M., 清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）M，西安：西北工业大学出版社6）课程设计进度安排1准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料2程序模块设计分析阶段（4学时）：程序总体设计、详细设计3代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名： 2015 年 6

4、月 19 日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）； 评阅人： 职称： 讲师 2015 年 6 月 19 日中文摘要1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技术。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根

5、据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。LR分析是当前最一般的分析方法。这是因为它对文法的限制最少，现今能用上下文无关文法描述的程序设计语言一般均可用LR方法进行有效的分析，而且在分析的效率上也不比诸如不带回溯的自顶向下分析、一般的“移进归约”以及算符优先等分析方法逊色。此外，LR分析器在工作过程中，还能准确及时地发现输入符号串的语法错误。凡此种种，就使LR分析方法在国际上受到了广泛的重视。顾名思义，LR(0)分析就是LR

6、(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。做这次课设采用的是C+语言进行编写的LR(0)分析器，使用的编译器是ClodeBlocks,电脑系统是win 8.1内存为4G目录一、课程设计任务及要求1二、需求分析1三、设计思路13.1 识别文法的LR(0)项目集规范族的构造13.2 LR(0)分析表的构造23.3 LR(0)分析器总控程序构造3四、详细设计44.1 程序总体构架44.2 程序存储结构54.2.1 符号表存储结构54.2.2 产生式表存储结构54.2.

7、3 项目集规范族表存储结构64.2.4 LR(0)分析表存储结构74.3 程序算法74.3.1 项目集规范族的构造74.3.2 LR(0)分析表构造9五、运行调试与分析讨论104.1 符号表测试104.2 产生式表测试114.3 项目集规范族表测试114.4 LR(0)分析表测试124.5 LR(0)分析器测试12六、设计体会与小结13七、参考文献14-第 3 页 -一、课程设计任务及要求. 本课程设计完成了以下内容：1. 实现了对任意给定的文法，识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 判断该文法是否为文法，实现了分析表的构造，并输出到指定文件中；3. 实现了分析器总控程序

8、，对输入的表达式进行文法分析。二、需求分析本课程设计的核心算法Error! Reference source not found.主要有三点：1. 识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 分析表的构造；3. 分析器总控程序的构造。三、设计思路3.1 识别文法的LR(0)项目集规范族的构造采用（闭包）的构造一个文法的项目规范簇。假定是文法的任一项目集，定义和构造的闭包的算法：（1）的任何项目都属于；（2）若属于，那么，对任何关于的产生式，项目也属于；（3）重复执行上述两个步骤直至不再增大。其中初始 ，为对文法进行拓广构造而引进的不出现在中的非终结符。定义状态转换函数，的第一个

9、变元是一个项目集，第二个变元是一个文法符号。函数值定义为。其中 = 任何形如的项目| 属于3.2 LR(0)分析表的构造 假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集合的下标为分析器的初态。分析表的子表和子表可按如下方法构造： （1）若项目属于且，为终结符，则置为“把移近栈”，简记为“”。 （2）若项目属于，那么对于任何终结符（或结束符#），置为“用产生式进行规约”，简记为“”（假定产生式是文法的第j个产生式） （3）若项目属于，则置为“接受”，简记为“acc”。 （4）若，则置。 （5）分析表中凡不能用规则14填入信息的空白处均置上“报错标志”。如果分析表中任何一项被

10、重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是文法。3.3 LR(0)分析器总控程序构造分析表包括量部分，“动作”表和“状态转换”表。规定了当状态面临输入符号时应采取什么动作。规定了状态面对文法符号时下一状态是什么。每一项所规定的动作不外乎是下述四种可能之一。（1）移进 把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。（2）归约 指用某一产生式进行规约。假若的长度为,规约的动作是，去除栈顶的个项，使状态变成栈顶状态，然后把的下一状态推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。（3）接受 宣布分析成功，停止分析器工作（4）报错 发现源程序

11、含有错误，调用出错处理程序。四、详细设计4.1 程序总体构架本课程设计开发的程序主要由4张表组成，分别为：符号表、产生式表、表和项目集规范簇表。同时，项目集规范簇表包含一个分析栈作为分析器总控程序。产生式表包含符号表作为子表，项目集规范簇表包含产生式表、表作为子表。 程序工作流程：1. 读取含有文法规则的文件，为该文法中的每一个不同的文法符号（终结符和非终结符分配一个编号），记录文法符号的属性（终结符/非终结符），存储于一张符号表中；2. 再次读取文件，将产生式存储于产生式表中；3. 根据产生式构建项目集规范族，存储于表中；4. 根据构建的项目集规范族构建分析表，填写分析表同时检查该文法是否为

12、文法；5. 对于输入的表达式，分析器根据构建的分析表进行文法分析，给出分析结果。4.2 程序存储结构4.2.1 符号表存储结构动态数组下标，同时作为符号的编号标识符是否为非终结符4.2.2 产生式表存储结构产生式标号非终结符标号 （与中的一致）指示当前非终结符的产生式当前非终结符产生式的长度，用于帮助区分一个产生式的不同项目，即项目个数等于指示下一个非终结符一个产生式中的标识符名（与中的一致）一个产生式中的下一个标识符4.2.3 项目集规范族表存储结构 1）定义二元组 ： ：产生式标号，与 中的一致 ：一个产生式的第个项目，可由 中的帮助确定 如：产生式 ： ， 2）结构：当前状态编号 指示下

13、一状态 指示闭包中的项目 闭包中的项目名当前项目的产生的新状态的编号，即状态转移的目的地状态编号闭包中的下一个项目待构造的项目的闭包的待构造的项目的闭包待构造状态的待构造状态的项目4.2.4 LR(0)分析表存储结构指示表头的孩子结点指示表头的后继结点指示该表项的操作指示该表项的操作数指示该表项是否被填写过,用于判断文法是否为文法4.3 程序算法4.3.1 项目集规范族的构造1. （初始化）将初始条件作为该状态头结点的第一个孩子结点，并构造该孩子结点的闭包，连接其后，指向第一个状态头结点，指向第一个状态头结点的第一个孩子结点；2. 查看，若为空，停止；若不为空，转3；3. 查看，若为空，转4；

14、若不为空，构造的，检查该状态与之前构造的状态有无重复，若重复，则停止构造，的填写重复的已存在的状态的编号；若不重复，则作为一个新状态，连接于，并构造其闭包连接其后，指向。转2；4. 指向下一状态，若下一状态为空，则结束，否则，指向下一状态头结点的第一个孩子结点，转3。具体细节：设所指项目为，因为要对其构造闭包，该项目一定不是终态，所以区分项目的圆点符号位于第个标识符的左侧。现在构造的闭包，分两个步骤实现：1. 构造的 ： 查看中编号为的产生式，取得该产生式的长度属性1） 若，则停止构造当前闭包（已是终态），此时 的项填；2） 否则，将作为该闭包的第一个项目，此时 的项填该新状态的状态编号。2.

15、 构造该孩子结点的闭包 ：查看中编号为的产生式的第个标识符，取得该标识符的，查看中该标识符的类别属性3） 若为1（非终结符），则查看非终结符的所有产生式，记这些产生式的编号为，将所有的加入闭包4） 否则，结束3. 检查该状态与之前构造的状态有无重复 :断言：任意两个状态，只要不同，则即为不同状态。4.3.2 LR(0)分析表构造对于编号为的状态，现依据其项目填写分析表：1. 如果该项目形如，查看该项目的属性，1）若为终结符，则在表的状态对应行，对应列，填写，表示将把 移进栈2）若为非终结符，则在表的状态对应行，对应列，填写，表示状态转移至状态2. 如果该项目形如1）若为起始符号，则置在表的状态

16、对应行，对应列，填写，表示接受。2）否则，对任何终结符或结束符，则在表的状态对应行，对应列，填写，表示用产生式进行规约。五、运行调试与分析讨论以文法G为例：程序模块输入：含上述文法的文件，下面展示个模块的输出结果4.1 符号表测试图6 符号表测试输出结果为 <符号编号，符号，是否为终结符>与预期结果相同图7 产生式表测试4.2 产生式表测试输出结果与读入的文件中的产生式相同，且产生式中符号的编号正确4.3 项目集规范族表测试图8 产生式表测试输出结果为 <状态编号> ：<产生式编号，产生式项目编号，项目转移的目标状态>与预期结果相同4.4 LR(0)分析表测试图9 分析表测试输出结果为分析表，与预期结果相同4.5 LR(0)分析器测试以输入字符串和为例图10 分析器测试表达式的分析结果正确第 11 页 六、设计体会与小结经过半年的编译原理的学习，我渐渐明白编译器的工作原理，通过这次实验对该理论在实践中的应用有深刻的理解， 通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。 作系统的认识是模糊的，概念上的，现在通过自己动手