编译原理 实验三 LL(1)语法分析器的构造

集美大学计算机工程学院实验报告课程名称：编译原理指导教师：付永钢实验成绩：实验编号：实验三实验名称：LL(1)语法分析器的构造班级：计算12姓名：学号：上机实践日期：2014.12上机实践时间：6学时一、实验目的1、掌握LL(1)分析法的基本原理；2、掌握LL(1)分析表的构造方法；3、掌握LL(1)驱动程序的构造方法。二、实验环境Windows7x64、VC6.0三、实验原理1、对文法要求LL(1)分析法属于自顶向下分析方法，因此需要预测匹配的产生式。即在LL(1)分析法中，每当在符号栈的栈顶出现非终结符时，要预测用哪个产生式的右部去替换该非终结符。LL(1)分析方法要求文法满足如下条件：对于任一非终结符A，其任意两个产生式A,A，都要满足下面条件：First(A)∩First(A)=2、分析表构造LL(1)分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终结符，列对应终结符，表中的值有两种：一是产生式的编号，一是错误编号。若用T表示LL(1)分析表，则T可表示如下：T:VN×VTP∪{Error}T(A,t)=Aα，当tFirst(Aα)T(A,t)=Error，否则其中P表示所有产生式的集合。显然，一个文法G是LL(1)文法，当且仅当T的元素包含唯一的一个产生式或Error。3、驱动程序构造LL(1)分析主要包括以下四个动作，其中X为符号栈栈顶元素，a为输入流当前字符。替换：当XVN时选相应产生式的右部去替换X。匹配：当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。成功：当格局为（空，空）时报告分析成功。报错：出错后，停止分析。四、实验内容已知文法G[E]:E→E+T|TT→T*F|FF→(E)|i说明：终结符号i为用户定义的简单变量,即标识符的定义。1、消除文法的左递归，构造对应文法的预测分析表；2、根据构造的预测分析表，实现LL(1)分析中控制程序（表驱动程序），并完成整个的LL(1)分析程序的界面设计、运行；3、P104中，3.36写一个Yacc程序，把输入的算术表达式翻译成对应的后缀表达式输出。要求转换正确，同时对于简单错误能够识别。4、P104中，3.37，写一个Yacc“台式计算器”程序，它计算布尔表达式，其中的词法分析器用Lex写。要求转换正确，同时对于简单错误能够识别。五、实验要求1、输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。2、LL(1)分析过程应能发现输入串中的错误。3、设计至少两个测试用例（尽可能完备，正确和出错），并给出测试结果。六、实验步骤、1、分析文法（1）E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归。用直接改写法消除左递归，得到如下文法：G[E]:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i（2）对于以上改进的文法，可以得到：FIRST(E’)=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，ε}FIRST(T’)=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，ε}FIRST(E)=FIRST(T)=FIRST(F)=FIRST((E))∪FIRST(i)={(，i}由此得到各非终结符的FOLLOW集合：FOLLOW(E)={)，$}FOLLOW(E’)=FOLLOW(E)={)，$}FOLLOW(T)=FIRST(E’)∪FOLLOW(E’)={+，)，$}FOLLOW(T’)=FOLLOW(T)={+，)，$}FOLLOW(F)=FIRST1、构造LL(1)分析表采用手工操作构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示，其中每个非终结符对应一行，每个终结符对应一列，一个非终结符和一个终结符可以确定矩阵中的一个元素，元素的值表示该非终结符和该终结符对应的产生式。每个矩阵元素都是一个符号串，所有元素初始化为””；构造LL(1)表时，根据文法和各个产生式的First集，填写LL(1)分析表的内容。各产生式只要降右端填入到对应的表项中即可，用空串表示Error。在根据LL(1)分析表选择产生式进行推导时，若查到的产生式为空串表示无相应的产生式可选，不匹配错误；否则根据符号串得到相应的产生式进行推导，即进行压栈操作。步骤分析栈（栈顶符号，当前输入符）剩余串所用产生式1$E（E，i）查表i+i*i$E-TEˊ2$EˊT（T，i）查表i+i*i$T-FTˊ3$EˊTˊF（F，i）查表i+i*i$F-i4$EˊTˊi（i，i）i匹配i+i*i$5$EˊTˊ（Tˊ，+）查表+i*i$Tˊ-ε6$Eˊ（Eˊ，+）查表+i*i$Eˊ-+TEˊ7$EˊT+（+，+）+匹配+i*i$8$EˊT（T，i）查表i*i$T-FTˊ9$EˊTˊF（F，i）查表i*i$F-i10$EˊTˊi（i，i）i匹配i*i$11$EˊTˊ（Tˊ，*）查表*i$Tˊ-*FTˊ12$EˊTˊF*（*，*）*匹配*i$13$EˊTˊF（F，i）查表i$F-i14$EˊTˊi（i，i）i匹配i$15$EˊTˊ（Tˊ，$）查表$Tˊ-ε16$Eˊ(Eˊ,$)查表$Eˊ-ε17$$$2．数据结构LL(1)语法分析程序共用到个栈，分别称为：符号栈，语法树栈，操作符栈和操作数栈。其中，符号栈用于进行LL(1)语法分析；其它的栈是为了在语法分析的过程中同时生成与源程序结构对应的语法树而设。语法树栈用于生成声明部分和语句部分的语法树；操作符栈和操作数栈用于生成表达式部分的语法树。3.构造驱动程序构造LL(1)驱动程序的算法：(1).分析开始时，首先将标志符号#和文法开始符号S依次压入符号栈；输入流指针指向第一个输入符号，即由符号栈和输入流构成的初始格局为：(#S,a1a2...an#)然后，反复执行第2步所列的工作。(2).设在分析的某一步，符号栈及剩余的输入流处于如下的格局(#X1X2...Xm-1Xm,aiai+1...an#)其中，X1X2...Xm-1Xm为分析过程中所得的文法符号，此时，可视栈顶符号Xm的不同情况，分别作如下动作：若XmVN，则以Xm及ai组成的符号对(Xm，ai)查分析表T。设T(Xm，ai)为一产生式，假设是XmUVW，此时将Xm从分析栈中退出，并将UVW压入栈中，从而得到新的格局(#X1X2...Xm-1WVU,aiai+1...an#)但若T(Xm，ai)=Error，则调用出错处理程序进行处理；若Xm=ai#，则表明栈顶符号已经与当前扫描的输入符号得到匹配，此时应将Xm（即ai）从栈中退出，并将输入流指针向前移动一个位置。若Xm=ai=#，则表明输入串已经完全得到匹配，此时即可宣告分析成功而结束分析。其它情形，转错误处理程序。程序见附录七、实验结果六、实验小结1、在本次实验中，通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握LL(1)分析法的基本原理、掌握LL(1)分析表的构造方法、掌握LL(1)驱动程序的构造方法；2、通过本次实验，对LL(1)递归下降分析程序的构造和设计有了更为全面的认识，对LL(1)文法分析程序的实现有了进一步了解；3、实验输入串以‘$’结束，才用栈的形式，依次弹出进行处理；附录：程序代码：importjava.io.IOException;importjava.util.Scanner;importjava.util.Stack;publicclasstest3{staticchar[]a=newchar[20];staticintn=0,i=0;staticcharc;staticStrings;staticStackCharactersk=newStackCharacter();publicstaticvoidmain(String[]args){System.out.println(input:);Scannerin=newScanner(System.in);charz=0;try{z=(char)System.in.read();}catch(IOExceptione){e.printStackTrace();}while(z!='$'){a[n]=z;try{z=(char)System.in.read();}catch(IOExceptione){e.printStackTrace();}n++;a[n]='$';}sk.push('$');sk.push('E');c=sk.pop();do{if(c==a[i]){i++;c=sk.pop();}elseif(a[i]=='$')break;elsell1();}while(c!='$');}privatestaticvoidll1(){if(c=='E'){if(a[i]=='i'||a[i]=='('){System.out.println(E-TE');sk.push('e');sk.push('T');c=sk.pop();}elseerror();}elseif(c=='e'){if(a[i]=='+'){System.out.println(E'-+TE');sk.push('e');sk.push('T');sk.push('+');c=sk.pop();}elseif(a[i]==')'||a[i]=='$'){System.out.println(E'-&);c=sk.pop();}elseerror();}elseif(c=='T'){if(a[i]=='i'||a[i]=='('){System.out.println(T-FT');sk.push('t');sk.push('F');c=sk.pop();}elseerror();}elseif(c=='t'){if(a[i]=='+'||a[i]==')'||a[i]=='$'){System.out.println(T'-&);c=sk.pop();}elseif(a[i]=='*'){System.out.println(T'-*FT');sk.push('t');sk.push('F');sk.push('*');c=sk.pop();}elseerror();}elseif(c=='F'){if(a[i]=='i'){System.out.println(F-i);sk.push('i');c=sk.pop();}elseif(a[i]=='('){System.out.println(F-(E));sk.push(')');sk.push('E');sk.push('(');c=sk.pop();}elseerror();}}privatestaticvoiderror(){System.out.println((i+1)+:+a[i]+error!);i++;}}