编译原理课程设计报告-预测分析程序的设计.doc

课程设计任务书课程设计任务书 学生姓名：学生姓名： 专业班级：专业班级： 指导教师：指导教师： 工作单位：工作单位： 题题 目目: : 预测分析程序的设计预测分析程序的设计 初始条件：初始条件： 程序设计语言:主要使用 c 语言的开发工具，或者采用 lex、yacc 等工具，也可 利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设 计。 要求完成的主要任务要求完成的主要任务: : （包括课程设计工作量及其技术要求，说明书撰写等 具体要求） 1. 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书 的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资 料解决具体问题的方法。严格要求自己，要独立思考，按时、独立按时、独立完成课程设计任 务。 2. 课设任务：对教材 p94 中的上下文无关文法，实现它的预测分析程序，给出符号 串 i+i*i 的分析过程。 （参考教材 p9396） 3. 主要功能：对于这个给的 ll（1）文法，假设所有非终结符号 p 的 first 集合和 follow 集合都是已知的，构造其预测分析表，程序显示输出预测分析表，同时用这 个预测分析程序对输入串进行分析，并给出了栈的变化过程。 4. 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试， 合理使用出错处理程序。 5. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于 0.3 万字。 包含内容： 课程设计的题目。 目录。 正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法 分析方法及中间代码形式的描述、文法和属性文法的设计） ，数据结构与模块说明 （功能与流程图） 、详细的算法设计、软件调试、软件的测试方法和结果、有关技术 的讨论、收获与体会等。 结束语。 参考文献。 附录：软件清单（或者附盘） 。 时间安排：时间安排： 消化资料、系统调查、形式描述1 天 系统分析、总体设计、实施计划3 天 撰写课程设计报告书1 天 指导教师签名：指导教师签名： 20102010 年年 6 6 月月 1111 日日 编译原理编译原理课程设计说明书课程设计说明书 3 系主任（或责任教师）签名：系主任（或责任教师）签名： 20102010 年年 6 6 月月 1111 日日 目目 录录 1 1引言引言 4 4 2 2需求分析需求分析 5 5 2.1 问题的提出 5 2.2 问题的解决 5 2.3 解决步骤 5 3 3总体设计总体设计 6 6 3.1 概要设计 6 3.1.1 设计原理 .6 3.1.2 构造 ll（1）分析表 7 3.2 详细设计 .10 3.2.1 程序流程图 10 3.2.2 设计要求 12 3.2.3 设计原理 12 3.2.3.1 first(x)(xvnvt)的构造12 3.2.3.2 函数 getfirst() (=x1x2x3xn)的构造 12 3.2.3.3 follow(a) (avn)的构造 .13 3.2.3.4 分析表 m【a,a】的构造 .13 3.2.3.5 匹配过程的实现13 编译原理编译原理课程设计说明书课程设计说明书 4 3.3 程序设计 .14 3.3.1 总体方案设计 14 3.3.2 各模块的实现 14 4 4开发工具的选择开发工具的选择 2323 5 5程序测试程序测试 2323 6 6有关技术的讨论有关技术的讨论 2525 7 7收获与体会收获与体会 2626 8 8参考文献参考文献 2626 编译原理编译原理课程设计说明书课程设计说明书 5 1 1 引言引言 一个编译程序在对某个源程序完成了词法分析工作之后，就进入了语法分 析阶段，分析检查源程序是否语法上正确的程序，并生成相应的内部中间表供 下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查 时语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子语法树 建立的方式，有自顶向下与自底向上两大类分析技术。本课程讨论自顶向下的 情况。 本次课程设计所做的工作是对已知 first 集合和 follow 集合的 ll(1)文 法构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对 输入串进行分析，并给出了栈的变化过程。 2 2 需求分析需求分析 2.1 问题的提出问题的提出 语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串 的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构 是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产 生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是， 如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。 2.2 问题的解决问题的解决 其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的 开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的 编译原理编译原理课程设计说明书课程设计说明书 6 分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图 用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法 树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过 程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。 2.3 解决步骤解决步骤 在自上而下的分析法中，主要是研究 ll(1)分析法。它的解决步骤是首先 接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到 ll(1)文 法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件 后，再分别构造文法每个非终结符的 first 和 follow 集合，然后根据 first 和 follow 集合构造 ll（1）分析表，最后利用分析表，根据 ll(1) 语法分析构造一个分析器。当然本课设只是针对 first 和 follow 集合都以 知的任意输入的 ll（1）文法。ll（1）的语法分析程序包含了三个部分，总 控程序，预测分析表函数，先进先出的语法分析栈。 3 3 总体设计总体设计 3.1 概要设计概要设计 3.1.1 设计原理设计原理 所谓 ll（1）分析法，就是指从左到右扫描输入串（源程序） ，同时采用最 左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选 择的规则。实现 ll（1）分析的程序又称为 ll（1）分析程序或 ll1（1）分 析器。 我们知道一个文法要能进行 ll（1）分析，那么这个文法应该满足：无二义 性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结 符的 first 和 follow 集合，然后根据 first 和 follow 集合构造 编译原理编译原理课程设计说明书课程设计说明书 7 ll（1）分析表，最后利用分析表，根据 ll(1)语法分析构造一个分析器。 ll（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进 先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，也是采用了 c+语言来编写。 ll（1）预测分析程序的总控程序在任何时候都是按 stack 栈顶符号 x 和当前的输入符号 a 做哪种过程的。对于任何（x，a），总控程序每次都执行 下述三种可能的动作之一： （）若 x = a =#，则宣布分析成功，停止分析过程。 （）若 x = a #，则把 x 从 stack 栈顶弹出，让 a 指向下一个输入 符号。 （）若 x 是一个非终结符，则查看预测分析表 m。若 ma，a中存放着 关于 x 的一个产生式，那么，首先把 x 弹出 stack 栈顶，然后，把产生式的 右部符号串按反序一一弹出 stack 栈（若右部符号为 ，则不推什么东西进 stack 栈）。若 ma，a中存放着“出错标志”，则调用出错诊断程序 error。 事实上，ll（1）的分析是根据文法构造的，它反映了相应文法所定义的 语言的固定特征，因此在 ll（1）分析器中，实际上是以 ll（1）分析表代替 相应方法来进行分析的。 3.1.2 构造构造 ll（1）分析表分析表 在构造 ll(1)预测分析表之前，首先要构造该文法的每个非终结符的 first 和 follow 集合，按照下面描述的算法来构造这两个集合。 first 集合的构造算法： （1）若 xvt，则 first（x）=x。 编译原理编译原理课程设计说明书课程设计说明书 8 （2）若 xvn，且有产生式 xa，则把 a 加入到 first(x)中；若 x 也是一条产生式，则把 也加到 first(x)中。 （3）若 xy是一个产生式且 yvn，则把 first(y)中的所有非 -元 素都加到 first(x)中；若 xy1y2yk 是一个产生式，y1，yi-1 都是 非终结符，而且，对于任何 j，1ji-1，first(yj)都含有 （即 y1yi-1* ），则把 first(yj)中的所有非 -元素都加到 first(x)中；特别是，若所 有的 first(yj)均含有 ，j=1,2,，k，则把 加到 first(x)中。 连续使用上面的规则，直至每个集合 first 不再增大为止。 follow 集合的构造算法： （1）对于文法的开始符号 s，置#于 follow(s)中； （2）若 ab 是一个产生式，则把 first()| 加至 follow(b) 中； （3）若 ab 是一个产生式，或 ab 是一个产生式而 （即 first()），则把 follow(a)加至 follow(b)中。 连续使用上面的规则，直至每个集合 follow 不再增大为止。 根据以上描述的算法，可以构造文法 ga的 first 和 follow 集合 如下： 非终结符 a first(a)follow(a) a (，i ), # b +, ), # c (，i +, ), # d * , +, ), # 编译原理编译原理课程设计说明书课程设计说明书 9 e (，i *, +, ), # 构造预测分析表，设计预测分析表的存储结构（构造算法） 。 i+*()# a acbacb b b+cbbb c cedced d dd*eddd e eie(a) 总体的框图： 编译原理编译原理课程设计说明书课程设计说明书 10 句子分析过程的框图： 编译原理编译原理课程设计说明书课程设计说明书 11 3.2 详细设计详细设计 3.2.1 程序流程图程序流程图 在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分析过 程中更好的对各个模块之间的联系进行了解。 程序的流程图如下： 编译原理编译原理课程设计说明书课程设计说明书 12 开始 输入文法 相关信息 ll（1）文 法 构造 first 集 构造 follow 集 构造预测分析表 输入产生式 判断句型 continue=“y“ 构造句子的预测分析过程 是 y 结束 编译原理编译原理课程设计说明书课程设计说明书 13 3.2.2 设计要求设计要求 1. 实现 first(x) (xvnvt)； 2. 根据 first(x) (xvnvt)，实现 getfirst() (=x1x2x3xn)； 3. 实现 follow(a) (avn)； 4. 根据 getfirst()以及 follow(a)构造 ll(1)分析表 m【a,a】 ； 5. 根据分析表 m【a,a】 ，对任一输入字符串进行匹配，判断是否合法，并 且显示其匹配过程。 3.2.3 设计原理设计原理 3.2.3.13.2.3.1first(x)(xfirst(x)(xvnvnvt)vt)的构造的构造 连续使用下面的规则，直至每个集合 first 不再增大为止： (1). 若 xvt，则 first(x)=x; (2). 若 xvn，且有产生式 xa，则把 a 加入到 first(x)中；若 x $(表示空字符串)也是一条产生式，则把$也加到 first(x)中。 (3)若 xy是一个产生式且 yvn，则把 first(y)中的所有非$元素都加 到 first(x)中；若 xy1y2yk 是一个产生式，y1,yi-1 都是非终结符， 而且，对于任何 j,1$)，则把 first(yj)中的所有非$元素都加到 first(x)中；特别是，若所有的 first(yj) 均含有$,j=1,2,k,则把$加到 first(x)中。 如上可得到 first(x) (xvnvt)。 3.2.3.23.2.3.2函数函数 getfirst(getfirst() ) ( (=x1x2x3xn)=x1x2x3xn)的构造的构造 之前已经实现了 first(x) (xvnvt)，现在我们能够对文法 g 的任何符 号串=x1x2xn 构造集合 first(a)。 首先，置 first()=first(x1)$;若对任 1b是一个产生式，则把 first()$加至 follow(b)中； (3). 若 ab 是一个产生式，或 ab是一个产生式而=$(即 $first(),则把 follow(a)加至 follow(b)。 如上可得到 follow(a) (avn)的构造。 3.2.3.4 分析表分析表 m【a,a】m【a,a】的构造的构造 在对文法 g 的每个终结符 a 及其任意候选 a 都构造出 first(a)(2.2 节的 getfirst(a),和 follow(a)(2.3 节的 follow(a)之后,我们现在可以用它们来 构造 g 的分析表 m【a,a】 。 构造分析表 m 的算法是： (1). 对文法 g 的每个产生式 a执行第 2 步和第 3 步； (2). 对每个终结符 afirst(),把 a加至 m【a,a】中； (3). 若$first(),则对任何 afollow(a)把 a加至 m【a,a】中； (4). 把所有无定义的 m【a,a】标上“出错标志“。 如上可得到 m【a,a】 。 3.2.3.5 匹配过程的实现匹配过程的实现 对于任何(a,a),总控程序每次都执行下述三种可能的动作之一： (1). 若 x=a=#,则宣布分析成功，停止分析过程。 编译原理编译原理课程设计说明书课程设计说明书 15 (2). 若 x=a!=#,则把 x 从 stack 栈顶逐出，让 a 指向下一个输入符号。 (3). 若 x 是一个非终结符，则查看分析表 m。若 m【a,a】中存放着关于 x 的一个产生式，那么把 x 逐出 stack 栈顶，然后，把产生式的右部符号串按反 序一一推进 stack 栈(若右部符号为$,则意味不推什么东西进栈)。若 m【a,a】 中存放着“出错标志“，则中断匹配，显示出错信息。 3.3程序设计程序设计 3.3.1 总体方案设计总体方案设计 (1). main()调用 input(),读入文法 g 的有关内容：g(vt,vn,s, (2). main()调用 createfirst(),实现 first(x),(xvtvn); (3). 内部程序中通过调用 getfirst(string)得到字符串的 first 终结符； (4). main()调用 createfollow(),实现 follow(a),(avn); (5). main()调用 createtable(),创建 ll(1)分析表 m【a,a】 ； (6). main()调用 match (string)对任一输入的字符串进行匹配，判断其是否合 法，并且显示匹配过程； 3.3.2 各模块的实现各模块的实现 (1). void input() vt,vn 都是以字符存储的，numvt 表示 vt 的数目，numvn 表示 vn 的 数目。vt 标号 0numvt-1，vn 标号 numvtnumvt+numvn-1。函数 findv(char)和 v(int)分别实现字符索引和索引字符间的转换($用 nunvt+numvn 索引)。 产生式 numvt=top; coutcc numvn=top-numvt; vtop=$; coutstart; coutss (2). void createfirst() 用布尔数组 firstij(0 getfirst(string str) 对于字符串 str，该函数返回 str 的开始终结符数组。 可根据 3.2.2 2 的规则实现，对字符串的字符依次分析，将得到的开始 终结字符存储到临时 vector数组 tmp 中，函数结束返回 tmp 数组。 vector getfirst(string str)代码如下： vector getfirst(string str) /返回str的开始终结符数组 vector tmp; if(str.size()=0) return tmp; if(str=“$“) tmp.push_back($); return tmp; int i,j,no; bool sign; for(i=0;i=numvt if(t tmp=getfirst(ttij.substr(t+1,ttij.size()-t-1); for(tt=0;tt=numvt if(t tmp=getfirst(ttij.substr(t+1,ttij.size()-t- 1); for(tt=0;tt first=getfirst(tmp); bool sign=0; for(t=0;t“+ttij; if(sign) int iter; for(iter=0;iter“+ttij; (6). bool match (string str) 用栈来实现匹配算法： 栈 stack 用来存放文法符号。分析开始时，栈底先存放一个#,然后放入文法 编译原理编译原理课程设计说明书课程设计说明书 22 开始符号。同时，假定输入串之后也总有一个#,标志输入串结束。 预测分析程序的总控程序在任何时候都是按 stack 栈顶符号 x 和当前的输入 符号 a 行事的。对具体情况根据规则 3.2.2 5 的 3 种处理方式之一进行处理。 处理完后，函数结束返回。 bool match (string str)代码如下： bool match(string str) /用栈来实现匹配算法 str=str+“#“; cout=3;j-) stacktop+=tmpj; else return false; stacktop=0; cout0) coutstr; if(match(str) couts; while(s=y); if (s=n) system(“pause“); return 0; 4 4 开发工具的选择开发工具的选择 visual studio2008 5 5 程序测试程序测试 程序的调试结果如下： 程序的运行结果如下： 编译原理编译原理课程设计说明书课程设计说明书 25 编译原理编译原理课程设计说明书课程设计说明书 26 6 6 有关技术的讨论有关技术的讨论 本次课程设计主要实现了以下功能：实现对 ll(1)文法预测分析表的构造， 使得该文法变的一目了然，从而为判断输入符号串是否是该文法的句型做铺垫。 编译原理编译原理课程设计说明书课程设计说明书 27 总的来说本次课设基本上实现了相应的功能，但仍存在一定的问题，需要 进一步的思考，由于时间限制和本人能力这方面，做的不是很完美，没有实现 程序自