一、实验目的 首先能让用户输入一个文法，然后让计算机自动判断是否是一个 LL(1)文法，通过实验教学， 加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通 过实践达到对所学的知识进行验证。
二、实验环境 供 Windows 系统的PC 机，可用C++/C#/Java 等编程工具编写 三、实验内容 1、让计算机接受一个文法，示例如：
G[S] 为: S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 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 ，都要满足下面条件：
SELECT(A )∩SELECT(A )=
（2）、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。
它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串， 一是 null。若用 M 表示 LL(1)分析表，则 M 可表示如下：
M: VN×VTP∪{Error} M(A, t) = Aα ，当 t select(Aα ) ，否则 M(A, t) = Error 其中 P 表示所有产生式的集合。
（3）、语法分析程序构造
LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号， #为句子括号即输入串的括号。分析表用一个二位数组 M 表示，数组元素 M[A，a]中的下标 A 表示非终结符，a 为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式， 表明当非终结符 A 向下推导时，面临输入符 a 时，所采用的候选产生式，当元素内容无产生 式时，则表明用 A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理 的信息。
LL(1)分析过程主要包括以下四个动作：
替换：当 X VN时选相应产生式的右部 去替换 X。此时 X 出栈， 逆序入栈。
匹配：当 X VT时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则符号栈 中将 X 退栈并将输入流指针向前移动一位，否则报错。
接受：当格局为（#，空#）时报告分析成功。
报错：出错后，停止分析。并给出相应的错误提示信息。
五、详细设计 【流程图】
1. 总体思路分析及流程图
给定一个正规文法 G，在 LL(1)预测分析中，必须先求出 First 集和 Follow 集，然后求 出 Select 集，通过Select 集判断是否是 LL1 文法，如果是的话，构造预测分析表。求出预 测分析表之后，再输入一个字符串，依据LL1 分析表单步输出字符串的分析过程。
读取正规文法 求文法的First集 求文法的Follow集 求文法的Select集 键盘输入字符串 字符串分析 功能模块分解图
（1）主程序流程图 开始 输入文法 判断文法是否为 LL(1)文法 Y
N 构造预测分析
表 输入要分析的 符号串 出错处理
出错处理 N
判断该符号串是否可被 该文法识别 Y 提示i*i+i#为 可接受的字符
串 结束 （2）核心算法流程图 1.计算非终结符的 First集的算法及流程：
First集合的构造算法：
（1）若 X∈VT，则 First（X）={X}。
（2）若 X∈VN，且有产生式 X→a……，则把 a 加入到 First (X)中；若 X→ε 也是一条 产生式，则把ε 也加到 First (X)中。
（3）若 X→Y……是一个产生式且 Y∈VN，则把 First (Y)中的所有非ε -元素都加到 First (X)中；若 X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任 何 j，1≤j≤i-1，First (Yj)都含有ε （即 Y1…Yi-1* ε ），则把 First (Yj)中的所有非 ε -元素都加到 First (X)中；特别是，若所有的 First (Yj)均含有ε ，j=1,2,…，k，则把 ε 加到 First (X)中。
连续使用上面的规则，直至每个集合 First不再增大为止。
开始 读取一个非终 结符V 遍历所有产生 式，查找左部
是V的产生式
添加一个删除 空的标志为 true
取出得到的一
条产生式
V*是不是有推导规 则V*->空
产生式右部第一个符 号V*是终结符？ 将该终结符V* 加入V的First集 中 空标志为真 删除空，得到 V的First集 剩有非终结符？ 结束 2.计算非终结符的 Follow 集：
Follow 集合的具体构造算法如下：
（1）对于文法的开始符号 S，置#于 Follow(S)中； （2）若 A→α Bβ 是一个产生式，则把 First(β )|{ε }加至 Follow(B)中；
（3）若 A→α B 是一个产生式，或 A→α Bβ 是一个产生式而β ε（即ε ∈First(β )）， 则把 Follow(A)加至 Follow(B)中。
连续使用上面的规则，直至每个集合 Follow 不再增大为止。
开始 取得一个非终结符 V 查找产生式的右部 含有V的产生式 Y
V是不是最后一个字符 N
V后一个字符V*是 否为终结符 Y
Y
添加#到V的Follow 集中 Y N
是否遍历完所有右 部含有V的产生式
添加V*到V的Follow中 Y 将V*的First集加入到V的
Follow集中
是否有未求解过的 非终结符
N 完成
六、结果分析 七、 实验感想
本次实验用 C 语言操作判断 LL1 型文法，判断 LL1 型文法实验最主要的地方 在于需要依次计算 FIRST 集、FOLLOW 集和 SELLECT 集,然后判断是否为 LL(1)文 法,最后再进行句子分析。由于代码的精确性造成了前几次操作结果的误差，不 过在分析之后，对代码内的冗余进行了删除，纠正了实验结果。本次实验收货颇 多。