【实验2】-LL(1)文法分析器

《编译原理》课程实验实验2第-1-页实验2LL(1)文法分析实验题目：编写LL(1)文法分析器实验目的：加深对文法分析基本理论的理解，锻炼实现LL(1)文法分析器程序的实践能力。要求：实现基本LL(1)文法的功能。输入文法，能够求出FIRST集、FOLLOW集、预测分析表，同时，输入一串字符，输出分析过程。《编译原理》课程实验实验2第-2-页一.需求分析1．问题的提出：语法分析是编译过程的核心部分，其任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给出一串符号时，如何知道它是不是该文法的一个句子，这是本设计所要解决的一个问题。2．问题解决：其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发，推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。3．解决步骤：在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是，首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含三个部分：总控程序，预测分析表函数，先进先出的语法分析栈。二.概要设计1．设计原理：所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序采用C++语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。《编译原理》课程实验实验2第-3-页（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。2．构造LL(1)分析表考查文法G[E]：E→E+T|TT→T*F|FF→(E)|i|x|y我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法来消除它使方法满足要求，即：对形如：U→Ux|y的产生式（其中x,yV+，y不以U开头），引入一个新的非终结符U’后，可以等价地改写成为：U→yU’U’→xU’|ε显然改写后，U和U’都不是左递归的非终结符。因此文法G［E］按上述方法消去左递归后可等价地写成：E→TPP→+TP|εT→FQQ→*FQ|εF→(E)|i|x|y在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。①FIRST集合的构造算法：（1）若X∈VT，则FIRST（X）={X}。《编译原理》课程实验实验2第-4-页（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集合的构造算法：（1）对于文法的开始符号S，置#于FOLLOW(S)中；（2）若A→αBβ是一个产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。根据以上描述的算法，可以构造文法G［E］的FIRST和FOLLOW集合如下：FIRST(E)={(,i，x，y}FOLLOW(E)={),#}FIRST(P)={+,ε}FOLLOW(P)={),#}FIRST(T)={(,i，x，y}FOLLOW(T)={+,),#}FIRST(Q)={*,ε}FOLLOW(Q)={+,),#}FIRST(F)={(,i，x，y}FOLLOW(F)={*,+,),#}现在来构造G［E］的LL（1）预测分析表。预测分析表M[A,a]是如下形式的一个矩阵。A为非终结符，a是终结符或‘#’。矩阵元素M[A,a]中存放这一条关于A的产生式，指出当A面临输入符号a是所应采用的规则。M[A,a]也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。文法G［E］的LL(1)预测分析表如下：i+xy*()#EE→TPERRORE→TPE→TPERRORE→TPERRORERRORPERRORE→+TPERRORERRORERRORERRORP→εP→εTT→FQERRORT→FQT→FQERRORT→FQERRORERRORQERRORQ→εERRORERRORQ→*FQERRORQ→εQ→εFF→iERRORF→xF→yERRORF→（E）ERRORERROR其中，E、P、T、Q、F为方法G［E］的非终结符，i、+、x、y、*、(、)，为方法G［E］的终结符，值得注意的是，“＃”不管有没有ε产生式，我们在构造分析表时都不能省去。《编译原理》课程实验实验2第-5-页3.利用分析表进行预测分析的步骤对于这个文法，假设输入串为i*i+i，利用分析表进行预测分析的步骤为：步骤符号栈输入串所用产生式0#Ei*i+i#1#PTi*i+i#E→TP2#PQFi*i+i#T→FQ3#PQii*i+i#F→i4#PQ*i+i#5#PQF**i+i#Q→*FQ6#PQFi+i#7#PQii+i#F→i8#PQ+i#9#P+i#Q→ε10#PT++i#P→+TP11#PTi#12#PQFi#T→FQ13#PQii#F→i14#PQ#15#P#Q→ε16##P→ε