您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 编译原理语法分析器实验报告
西安邮电大学编译原理实验报告学院名称:计算机学院学生姓名:高宏伟实验名称:语法分析器的设计与实现班级:计科1405班学号:04141152时间:2017年5月12日一.实验目的1.熟悉语法分析的过程2.理解相关文法分析的步骤3.熟悉First集和Follow集的生成二.实验要求对于给定的文法,试编写调试一个语法分析程序:要求和提示:1)可选择一种你感兴趣的语法分析方法(LL(1)、算符优先、递归下降、SLR(1)等)作为编制语法分析程序的依据。2)对于所选定的分析方法,如有需要,应选择一种合适的数据结构,以构造所给文法的机内表示。3)能进行分析过程模拟。如输入一个句子,能输出与句子对应的语法树,能对语法树生成过程进行模拟;能够输出分析过程每一步符号栈的变化情况。设计一个由给定文法生成First集和Follow集并进行简化的算法动态模拟三.实验内容1.文法:E-TE’E’-+TE’|εT-FT’T’-*FT’|εF-(E)|i:2.程序描述(LL(1)文法)本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析,判断输入的字符串是否属于该文法的句子。基本实现思想:接收用户输入的字符串(字符串以“#”表示结束)后,对用做分析栈的一维数组和存放分析表的二维数组进行初始化。然后取出分析栈的栈顶字符,判断是否为终结符,若为终结符则判断是否为“#”且与当前输入符号一样,若是则语法分析结束,输入的字符串为文法的一个句子,否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈,当前输入符号从输入字符串中除去,进入下一个字符的分析。若不为“#”且不与当前输入符号一样,则出错。3.判断是否LL(1)文法要判断是否为LL(1)文法,需要输入的文法G有如下要求:具有相同左部的规则的SELECT集两两不相交,即:SELECT(A→?)∩SELECT(A→?)=?如果输入的文法都符合以上的要求,则该文法可以用LL(1)方法分析。算法描述如下:把第一条产生式的SELECT(0)集放到一个临时数组temp[]中for(i=1;i=产生式总数-1;i++)求temp的长度lengthifi指向的当前产生式的左部等于上一条产生式的左部then把SELECT(i)并入到temp数组中Iftemp的长度小于length加上SELECT(i)的长度返回0else把temp清空把SELECT(i)存放到temp中结果返回1;4.构建好的预测分析表5.语法分析流程图四.实验结果正确运行结果:错误运行结果:五.设计技巧和心得体会这次实验编写了一个语法分析方法的程序,但是在LL(1)分析器的编写中我只达到了最低要求,就是自己手动输入的select集,first集,follow集然后通过程序将预测分析表构造出来,然后自己编写总控程序根据分析表进行分析。通过本次试验,我能够设计一个简单的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。还能选择最有代表性的语法分析方法,如LL(1)语法分析程序、算符优先分析程序和LR分析分析程序。六.源代码packagecom.LL1;importjava.util.ArrayDeque;importjava.util.Deque;/***LL1文法分析器,已经构建好预测分析表,采用Deque实现*CreatedbyHongWeiPCon2017/5/12.*/publicclassLL1_Deque{//预测分析表privateString[][]analysisTable=newString[][]{{TE',,,TE',,},{,+TE',,,ε,ε},{FT',,,FT',,},{,ε,*FT',,ε,ε},{i,,,(E),,}};//终结符privateString[]VT=newString[]{i,+,*,(,),#};//非终结符privateString[]VN=newString[]{E,E',T,T',F};//输入串strTokenprivateStringBuilderstrToken=newStringBuilder(i*i+i);//分析栈stackprivateDequeStringstack=newArrayDeque();//shuru1保存从输入串中读取的一个输入符号,当前符号privateStringshuru1=null;//X中保存stack栈顶符号privateStringX=null;//flag标志预测分析是否成功privatebooleanflag=true;//记录输入串中当前字符的位置privateintcur=0;//记录步数privateintcount=0;publicstaticvoidmain(String[]args){LL1_Dequell1=newLL1_Deque();ll1.init();ll1.totalControlProgram();ll1.printf();}//初始化privatevoidinit(){strToken.append(#);stack.push(#);System.out.printf(%-8s%-18s%-17s%s\n,步骤,符号栈,输入串,所用产生式);stack.push(E);curCharacter();System.out.printf(%-10d%-20s%-20s\n,count,stack.toString(),strToken.substring(cur,strToken.length()));}//读取当前栈顶符号privatevoidstackPeek(){X=stack.peekFirst();}//返回输入串中当前位置的字母privateStringcurCharacter(){shuru1=String.valueOf(strToken.charAt(cur));returnshuru1;}//判断X是否是终结符privatebooleanXisVT(){for(inti=0;i(VT.length-1);i++){if(VT[i].equals(X)){returntrue;}}returnfalse;}//查找X在非终结符中分析表中的横坐标privateStringVNTI(){intNi=0,Tj=0;for(inti=0;iVN.length;i++){if(VN[i].equals(X)){Ni=i;}}for(intj=0;jVT.length;j++){if(VT[j].equals(shuru1)){Tj=j;}}returnanalysisTable[Ni][Tj];}//判断M[A,a]={X-X1X2...Xk}//把X1X2...Xk推进栈//X1X2...Xk=ε,不推什么进栈privatebooleanproductionType(){returnVNTI()!=;}//推进stack栈privatevoidpushStack(){stack.pop();StringM=VNTI();Stringch;//处理TE'FT'*FT'特殊情况switch(M){caseTE':stack.push(E');stack.push(T);break;caseFT':stack.push(T');stack.push(F);break;case*FT':stack.push(T');stack.push(F);stack.push(*);break;case+TE':stack.push(E');stack.push(T);stack.push(+);break;default:for(inti=(M.length()-1);i=0;i--){ch=String.valueOf(M.charAt(i));stack.push(ch);}break;}System.out.printf(%-10d%-20s%-20s%s-%s\n,(++count),stack.toString(),strToken.substring(cur,strToken.length()),X,M);}//总控程序privatevoidtotalControlProgram(){while(flag){stackPeek();//读取当前栈顶符号令X=栈顶符号if(XisVT()){if(X.equals(shuru1)){cur++;shuru1=curCharacter();stack.pop();System.out.printf(%-10d%-20s%-20s\n,(++count),stack.toString(),strToken.substring(cur,strToken.length()));}else{ERROR();}}elseif(X.equals(#)){if(X.equals(shuru1)){flag=false;}else{ERROR();}}elseif(productionType()){if(VNTI().equals()){ERROR();}elseif(VNTI().equals(ε)){stack.pop();System.out.printf(%-10d%-20s%-20s%s-%s\n,(++count),stack.toString(),strToken.substring(cur,strToken.length()),X,VNTI());}else{pushStack();}}else{ERROR();}}}//出现错误privatevoidERROR(){System.out.println(输入串出现错误,无法进行分析);System.exit(0);}//打印存储分析表privatevoidprintf(){if(!flag){System.out.println(****分析成功啦!****);}else{System.out.println(****分析失败了****);}}}
本文标题:编译原理语法分析器实验报告
链接地址:https://www.777doc.com/doc-5172593 .html