提高型实验参考格式汇编.doc

黄冈师范学院 提高型实验报告 课程名称： 编译原理 设计题目： LL(1)语法分析器 专 业： 计算机科学与技术 班 级： 201301班 小组成员： 姓 名：胡 璇 学号：2013261040105 姓 名：黄美玲 学号：2013261040106 姓 名：李昭容 学号：2013261040108 日 期: 2015-2016 第一学期 指导教师: 张瑞红 成 绩： 一、实验目的和要求 1.目的： （1）通过设计，编写和调试构造LL(1)分析表（也称预测分析表）的程序，了解构造LL(1)分析表的步骤，对文法的要求，能够从文法G出发自动生成LL(1)分析表。 （2）通过设计、编写和调试预测分析程序，了解一般预测分析器的组成结构及对文法的要求，掌握构造通用的总控制程序实现预测分析的方法。 2.要求： 通过实验能够提高的自己程序设计能力，同时掌握编译原理中重要的组成部分——语法分析的思想。 二、实验条件 装有C++语言工具环境的计算机一台。 三、实验原理分析 语法分析器是编译过程的核心部分，语法分析的核心任务就是识别词法分析程序输出的单词序列是否为给定方法的正确句子，并确定其语法结构。 LL（1）分析表 1. 对文法要求 LL(1)分析法属于自顶向下分析方法，因此需要预测匹配的产生式。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A，其任意两个产生式A((,A((，都要满足下面条件：Predict(A(()∩predict(A(()=( 2. 分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的编号，一是错误编号。若用T表示LL(1)分析表，则T可表示如下： T: VN×VT(P∪{Error} T(A, t) = A(α，当t(predict(A(α) T(A, t) = Error，否则 其中P表示所有产生式的集合。显然，一个文法G是LL(1)文法，当且仅当T的元素包含唯一的一个产生式或Error。 LL（1）分析程序 自上而下的分析方法就是规约的方法，也就是从方法的开始符出发，试图向下构造待分析符号串的语法树，若语法的叶节点可以构成该符号串，则表示这个符号串是该方法的句子。自上而下的分析方法又分为：带回溯的自上而下分析方法和不带回溯的自上而下分析方法。预测分析属于自上而下不带回溯的语法分析方法，这种分析方法要求文法是LL(1)的，语法分析程序的输入是终结符号串（即单词符号串，一一个“#”结尾），如果输入串是句子，则输出YES，否则输出NO和错误信息。 四、实验方案或步骤 1、概要设计（算法和数据结构、流程图） （1）算法和数据结构 构造LL(1)分析表的算法： 对于文法G的每个符号X，构造FIRST(X)集合。 构造FIRST(X)集合又分为几种情况： 若X-a….(a为终结符)，则FIRST(X)={a}。 若X-#（为空），则FIRST(X)={#}。 若X-Y1Y2Y3……则先求出Y1的FIRST集，将Y1的FIRST集加入到X的FIRST集中，直到FIRST集不再扩大为止。 将所有的非终结符的FIRST(X)集合用一个二维布尔矩阵F[m][n]表示，其中m 的大小表示非终结符的个数，n的大小表示终结符的个数+1，若n对应的终结符属于m对应的非终结符的FIRST集，则F[m][n]=1，否则为0。 对于文法G的每个非终结符符号X，构造FOLLOW(X)集合. 构造FOLLOW(X)集合又分为以下几种情况： a．若A-aBβ(a可以为空)，则将FIRST（β）\{ε}加入到FOLLOW（B）中。 b．若A—aB或A—aBβ,且β=ε(即ε?FIRST（β）)，则把FOLLOW（A）加到FOLLOW（B）中。 构造分析表M。 a、对文法G（S）的每个产生式A—a执行以下步。 b、对每个终结符a?FIRST (A)，把A—a加入到M[A,a]中，其中a为含有首字符a的候选式或为惟一的候选式。 c、若ε?FIRST（A），