LL(1)文法分析程序实验报告

LL（1）文法分析程序实验报告学院：计算机科学与信息学院班级：××××学号：1109×××××姓名：×××指导老师：孙老师专业：计算机科学与技术计算机科学与技术系1、概述当我们需选用自顶向下分析技术来分析文法时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。2、LL(1)的判定步骤2.1、求出能推出ε的非终结符

首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出ε。其值有三种情况："未定"、"是"、"否"。①将数组X[]中对应每一非终结符的标记置初值为"未定"。②扫描文法中的产生式。

(a)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出ε。

(b)若某一非终结符的某一产生式右部为ε，则将数组中对应该非终结符的标志置为"是"，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。③扫描产生式右部的每一符号。

(a)若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。

(b)若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"

④重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。2.2、计算FIRST集

(a)若X∈VN，且有产生式X→a…，a∈VT，则a∈FIRST(X)。

(b)若X∈VN，X→ε,则ε∈FIRST(X)。

(c)若X∈VN；Y1，Y2，…，Yi∈VN，且有产生式X→Y1Y2…Yn；当Y1Y2…Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)的所有非{ε}元素和FIRST(Yi)都包含在FIRST(X)中。(d)当(d)中所有Yiε,(i=1,2,…n)，则

FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}，反复使用上述(a)～(d)步直到每个符号的FIRST集合不再增大为止。2.3、计算FOLLOW集

对文法中每一A∈VN计算FOLLOW(A)

(a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里"#"为句子括号)。

(b)若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(B)中。

如果βε则把FOLLOW(A)也加入FOLLOW(B)中。

(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。2.4、计算SELECT集对文法中每一A->a,A∈VN,a属于V*,若a不能推出空，则SELECT(A->a)=FIRST(a)。否则SELECT(A->a)={FIRST(a)-{ε}UFOLLOW(A)。2.5、判定对于每个非终结符的两个不同产生式，A->a,A->b,满足SELECT(A->a)ΠSELECT(A->b)=ф。其中a,b不能同时推出ε。3、预测分析3.1、构建文法的预测分析表分析表又可用一个矩阵M(或称二维数组)表示。矩阵的元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号"#"，矩阵元素M[A,a]中的内容为存放着一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所应采取的候选产生式，当元素内容无产生式时，则表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理的信息。3.2、预测分析程序框图4、文法分析实现5、实验心得本次实验利用自上而下的分析方法对任给的文法进行判断，基本完成了实验要求，但仅仅局限于LL（1）文法才能用，具有一