推断 LL1 型文法实验报告 A 版 一、实验目的首先能让用户输入一个文法，然后让计算机自动推断是否是一个 LL (1)文法，通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。 二、实验环境供 Windows 系统的 C 机，可用 C+/C#/Java 等编程工具编写 三、实验内容 1、让计算机接受一个文法，示例如：GS 为:SABSbCAAbBBaDCADCbDaSDc 1.2、编程实现对上述文法是否是 LL (1)文法的推断，是则给出肯定回答，否则给出否定回答。2.判别是否是 LL (1)文法实验流程图如下：以链表或数组等数据结构保存文法.求出能推出的非终结符.计算 FIRST 集,FOLLOW 集和 SELECT 集是 SELECT(A)S 输出肯定 ELECT(A)=?回答否输出否定回答 四、概要设计 (1)、LL (1)文法的定义 LL (1)分析法属于确定的自顶向下分析方法。LL (1)的含义是：第一个 L 表明自顶向下分析是从左向右扫描输入串，第 2 个 L 表明分析过程中将使用最左推导，1 表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL (1)文法的判别需要依次计算 FIRST 集、FOLLOW 集和 SELLECT 集,然后推断是否为 LL (1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在 LL (1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，推断其与剩余输入串的第一个字符是否匹配，假如匹配，则继续分析，否则报错。LL (1)分析方法要求文法满足如下条件：对于任一非终极符 A 的两个不同产生式 A,A，都要满足它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是 null。若用 M 表示 LL (1) 分 析 表 ， 则 M 可 表 示 如 下 ： M:VNVTErrorM(A,t)=A ， 当 tselect(A) ， 否 则M(A,t)=Error 其中表示所有产生式的集合。 (3)、语法分析程序构造 LL (1)分析中_为符号栈栈顶元素，a 为输入流当前字符，E 为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组 M 表示，数组元素 MA，a 中的下标 A 表示非终结符，a 为终结符或句子括号#，二维数组中存放的是一条关于 A 的产生式，表明当非终结符 A 向下推导时，面临输入符 a 时，所采纳的候选产生式，当元素内容无产生式时，则表明用 A...
