编译原理课程设计LL(1)文法分析

编译原理课程设计——LL(1)语法分析

课题综述算法介绍人员分工程序流程目录课题综述

语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定的文法的正确句子。目前语法分析常用的方法右自顶向下分析和自底向上分析两大类。

确定的自顶向下方法，是从文法的开始符号，考虑如何根据当前的输入符号（单词）唯一的确定选用哪个产生式替换相应非终结符往下推导。LL(1)文法是一种确定的自顶向下的分析方法。

LL(1)的含义是：第一个L表明自顶向下分析从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导即选择哪个产生式（即规则）进行推导。

算法介绍1、在对输入序列进行LL(1)文法分析之前，首先要对文法进行判别，看文法是不是LL(1)文法。这个文法应该满足无二义性，无左递归，无公因子。具体的判别过程是，求出能推出ε的非终结符，求出FIRST集，求出FOLLOW集，求出SELLECT集，看相同左部的产生式的SELLECT集是否有交集，有就不是LL（1）文法。2、如果输入文法不是LL(1)文法，可以进行转换，转换一般有两种方法：提取左公因子法和消除左递归法。3、构造预测分析表，设二维矩阵M。4、预测分析。人员分工负责MFC界面制作，程序总控，各个非终结符能否推出ε的计算,判断是否LL(1),以及人员分工。消除左递归的实现提取公因子的实现求FIRST集求FOLLOW集求SELLECT集构造预测分析表，分析输入的句子程序流程程序开始InitAndConvertPt();//读入文法、消除左递归、提取公因子InitArray();//初始化N[]数组VnRefresh(Pt);//构造非终结符集VtRefresh(Pt);//构造终结符集Create_N_Table();//判断哪些非终结符可以推出空,存入N[]FirstVt();//求FIRST集FollowVt();//求Follow集SelectVt();//求Select集是不是LL(1)输出不是LL（1）文法NOyes构造预测分析表分析表达式界面输出提取公因子

使产生式右部没有公共因子。若产生式右部有左公因子，则反复提取，直到引进的新非终结符的有关的产生式再无左公共因子为止。

消除左递归左递归分为直接左递归和间接左递归。（1）直接左递归的处理

我们利用引入新非终结符的方法来消除左递归：

如：

U→Ux|y（其中x,yV+，y不以U开头），引入一个新的非终结符U’后，可以等价地改写成为：

U→yU’

U’→x

U’|ε

（2）间接左递归的处理对于间接左递归的消除需要通过产生式非终结符置换，将间接左递归变为直接左递归，然后按直接左递归消除。终结符推出ε的计算分为三步：1、将数组N中对应每一非终结符的标记置初值为“未定”2、扫描文法中的产生式。1）删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出ε。2）若某一非终结符的某一产生式右部为ε，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。3、扫描产生式右部的每一个符号。1）若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。2）若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。4、重复3，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。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不再增大为止。FOLLOW集的计算FOLLOW集合的构造算法：（1）对于文法的开始符号S，置#于FOLLOW(S)中；（2）若A→αBβ是一个产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。

SELLECT集的计算对某一产生式Ａ－＞ＢＣ，若产生式右部可以推出ε，则ＳＥＬＬＥＣＴ（Ａ）＝｛ＦＩＲＳＴ（ＢＣ）－｛ε｝｝ＵＦＯＬＬＯＷ（Ａ）若产生式右部推不出ε，则ＳＥＬＬＥＣＴ（Ａ）＝ＦＩＲＳＴ（ＢＣ）判断是否LL(1)文法对当前的产生式左部，查找后面的具有相同左部的其他产生式，并比较SELLECT集，若有重合，则不是LL(1)文法。构造预测分析表在确定的自顶向下分析方法中，又有递归子程序法和预测分析方法，我们采用的是预测分析的方法。一个预测分析器由三部分组成：（1）预测分析程序（2）先进后出栈（3）预测分析表其中，只有预测分析表与文法有关。分析表可用矩阵M表示。M（A，a）中的下标A表示非终结符，a为终结符或括号，矩阵元素M（A，a）中的内容是一条关于A的产生式，表明当用非终结符A往下推导时，面临输入符A时，所应采取的候选产生式，元素内容无产生式时，则表明出错。为便于辨认，我们令M数组为

Analyze数组。预测分析过程#为文法的括号；