一、实验目的
首先能让用户输入一个文法，然后让计算机自动判断是否是一个LL(1)文法，通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。
二、实验环境
供Windows系统的PC机，可用C++/C#/Java等编程工具编写
三、实验内容
1、让计算机接受一个文法，示例如：
G[S]为:
S→ABS→bCA→εA→bB→εB→aDC→AD C→bD→aS D→c
1.2、编程实现对上述文法是否是LL(1)文法的判断，是则给出肯定回答，否则给出否
定回答。
2.判别是否是LL(1)文法实验流程图如下：
以链表或数组等数据结构保存文法.
求出能推出ε的非终结符.
计算FIRST集,FOLLOW集和SELECT集
SELECT(A→α)∩SELECT(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×VT?P∪{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完成
判断LL1型文法实验报告-可复制
