合肥工业大学编译原理LL(1)自上而下文法分析.docx

学 号: 学 号: 69 学 号: 学 号: 69 合肥工业大学计算机与信息学院 计算机系2013级 编译原理课程设计报告 姓 名： 马骏 专业年级： 信息安全13-1 提交时间： 2016年07月 、实验题目 自上而下的 LL(1) 文法分析 二、实验目的 了解掌握自上而下的 LL( 1)文法分析过程。 二、实验内容与要求 从语法分析树构造句型所有的推导的程序实现，接受用户任意输入的一个句型的语法分析 树(其表示存于指定文件中) ，生成该语法分析树中包含的该句型的所有推导(显示输出) 。 构造一程序，实现教材的FIRST(X)集合的构造算法。对任一给定的文法G,程序输出所有 非终结符P的FIRST(P)。构造一程序，实现教材的 FIRST(X)集合的构造算法。对任一给定 的文法G,程序输出所有非终结符 P的FIRST(P)。在此基础上，构造一程序，实现教材的 FOLLOW(A集合的构造算法。对任一给定的文法 G,程序输出所有非终结符 A的FOLLOWA)。 对于给定的一个 LL(1)文法，假定所有非终结符号 P的集合FIRST(P)和集合FOLLOW(P都已 知，构造其预测分析表(实现教材给出的预测分析表构造算法) 。对教材给出的例构造出预 测分析表。程序显示输出预测分析表或输出到指定文件中。 首先实现集合FIRST(X)构造算法和集合FOLLOW(A构造算法，再实现教材给出的预测分析 表构造算法。程序显示输出预测分析表或输出到指定文件中。 对文法按教材表构造出 G的预测分析程序，程序显示输出如那样的匹配过程。 三、实验环境与工具 操作系统： Windows 7 开发语言： C++ 四、开发过程 1） 字符要求： 2） 你的程序必须能够根据以下字符来处理语法： 3） -终端字符：字母，数字，符号例如“ +”, “ 一 ”，…； 4） - 非终端字母表中的大写字母。 5） 符号“ =”，和“ #” （替换“￡”，因为它更容易输入到文本文件）被保留用于语 法的描述中，因此不能被用作终端。 6） 初始状态 您的程序通过读取一个文件中的“文本”格式开始。 这个文件的结构可以随意构建，不做要求，但建议做成简单的 simple 。 例如，程序描述以下语句： E = E + T |T T = T * F |F F =（E） | 0 |1 在这种情况，我们可以很容易确定 E, T和F是非终端，而符号“（”，“）”，“ *”和“ +” 和数字“ 0”和“ 1”是在终端。 第一个非终端（第一衍生物）被认为是语法的公理。 结果必须存储在内存中， 是一个您所选择的数据结构。 然后，使用一个函数再取出数据, 存储在内存中并屏幕上显示（以你选择的格式）O显示在屏幕rru ar cd：［U2a _i txLE-E+T|T T^T*F|F F=(EHO|1 存储在内存中并屏幕上显示（以你选择的格式） O 显示在屏幕 rru ar cd：［U2a _i txL E-E+T|T T^T*F|F F=(EHO|1 E E+T T T T+F F Gramtnaire initialF (E) Gramtnaire initial 0 在上面的图中，并在下文中，右列显示的程序的执行的过程， 并左栏表示中使用的数据结构。 这些都是明显的例子。你可以使用任何你想要的格式。 3）消除传递 为了产生一个分析器，你现在必须计算，每个分支, “第一个”和“其后”的集合?。 为了产生一个分析器，你现在必须计算，每个分支, “第一个”和“其后”的集合?。 为了产生一个分析器，你现在必须计算，每个分支, “第一个”和“其后”的集合?。 为了产生一个分析器，你现在必须计算，每个分支, “第一个”和“其后”的集合?。 3 3）计算“ first 集”和“ follow 集”的集合 Cr^mmaire non recursive ① 判断你的程序是否包含一个传递关系或没有。如果包含，递归应该被消除。 指向自己的判断： 遍历语句 您可以创建一个新的数据结构语句来表示其中传递关系已被删除， 这有利于进- 步加工。 没有传递关系的语句 在这种情况下，如果语法不包含判定递归的语句，程序当然必须使用第二数据结 构的副本。 结果被存储在数据结构，再次“你的选择。 然后，这些集合被显示在屏幕上 ② Calcul des ensembles ? premiers u et ^uivantso Enscmb cs P / S Affichage des ensembles 图注释：Calcul des ensembles ? premiers ? et ? suivants ? 计算“第一个”和“其 后”的集合 Affichage des ensembles 显示集合 premiers 第一个