合肥工业大学编译原理实验

宣城校区实验报告课程名称编译原理专业班级计算机0001班学生姓名及学号赵保飞2015216768指导教师李芒宏计算机中心楼第四机房2017～2018学年第一学期《编译原理》课程实验报告实验名称词法分析设计姓名赵保飞系院专业计算机科学与技术班级计算机01班学号2015216768实验日期2017.10.18指导教师李芒宏成绩一、实验目的和要求通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。四、实验评价、收获与体会纸上得来终觉浅，虽然词法分析器是理论上实行最简单的，但是编写程序实现时却也遇到了不少的问题。使用JAVA来写是因为这学期正在开这门课，数据的读入还是自己提前看才实现的，读入的一条源代码看似简单，首先要储存，储存后要清楚空格直到读到字符为止，还是以C++的思维来写java程序，其中很多细节均是通过函数来实现。这也许自己没有深刻理解java设计思维的原因。希望以后能改进。《编译原理》课程实验报告实验名称LL（1）分析法姓名赵保飞系院专业计算机科学与技术班级计算机01班学号2015216768实验日期10.25指导教师李芒宏成绩一、实验目的和要求复变函数。。编译原理实验和预习。。java作业和实验。。操作系统复习。。通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二、实验原理文法为（1）E->TG（2）G->+TG|-TG（3）G->ε（4）T->FS（5）S->*FS|/FS（6）S->ε（7）F->(E)（8）F->i（1）实验数据结构说明 Char数组-Vn数组--非终结符表；char数组-Vt数组--终结符；String数组-Gr数组--文法；Boolean型FIRST[][]二维数组对应每个非终结符的first集，初始化均为false；Boolean型FOLLOW[][]二维数组对应每个非终结符的Follow集，初始化均为false;String型M[][]二维数组对应预测分析表（2）实验算法描述算法总的来讲不是很复杂，但是细节上可能有点复杂。总的是依据本实验的数据结构FIRST[][]和FOLLOW[][]集，这两个数据结构虽然浪费了不少空间但是确实让程序的实现变得更简单。First()总的来求所有的非终结符的first集，first1()分工为具体求某一个具体非终结符的first集；first2()则是求某一个集体的产生式的first集。通过这三个函数的逐级分工来实现求所有的非终结符的first集。Follow集来说相对难求一点，但把它放到first集后面求来说相对简单一点。通过上面的分布设计就可以实现了。（3）算法流程图三、源程序代码和测试结果packageexp3;importjavax.swing.*;importjava.awt.*;importjava.awt.GridLayout.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;classWinGridextendsJFrame{ GridLayoutgrid; JPanelchessboard; JTextFieldtext;JTextAreatextShow;JButtonbutton;ReaderListenlistener; WinGrid(){ init(); setVisible(true);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } voidinit(){ setLayout(newFlowLayout()); text=newJTextField(10); setBounds(466,166,500,400); button=newJButton("读取"); textShow=newJTextArea(9,30); listener=newReaderListen(); listener.setJTextField(text); listener.setJTextArea(textShow); text.addActionListener(listener); button.addActionListener(listener); add(text); add(button); add(newJScrollPane(textShow)); }}classReaderListenimplementsActionListener{JTextFieldtext;JTextAreatextShow;LLone=newLL();Strings; Stringtemp1[][]=newString[18][6];publicvoidsetJTextField(JTextFieldtext){this.text=text;}publicvoidsetJTextArea(JTextAreatextShow){this.textShow=textShow;}publicStringS(){ Stringt=text.getText(); returnt;}@OverridepublicvoidactionPerformed(ActionEvente){try{ Strings=text.getText()+"#";textShow.append(s+"\n");textShow.append("步骤"+"\t"+"分析栈"+"\t"+"剩余输入串"+"\t"+"所用产生式"+"\t"+"动作"+"\n");one.right(s,temp1); for(inti=0;i<18;i++){ for(intk=0;k<5;k++){ textShow.append(temp1[i][k]+"\t"); } textShow.append("\n"); }}catch(Exceptione2){e2.printStackTrace();}}}publicclassexp3{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub newWinGrid(); }}packageexp3;importjava.util.*;importjava.io.*;publicclassLL{ charVn[]={'E','T','G','F','S'};//非终结符 charVt[]={'+','-','*','/','(',')','i','#','ε'};//终结符 booleanFIRST[][]=newboolean[Vn.length][Vt.length+1];//bool型数组，初始化均为flasebooleanFOLLOW[][]=newboolean[Vn.length][Vt.length+1];//bool型StringM[][]=newString[Vn.length][Vt.length-1];//预测分析表 StringGr[]={"E->TG","G->+TG|-TG","G->ε","T->FS","S->*FS|/FS","S->ε","F->(E)","F->i"};//文法 LL(){ first();//求first集 follow();//求follow集 buildM();//求预测分析表 }intor(inti,Strings){//返回该文法第i符号离他最近的在其右边一个“|”位置 for(i=i+1;i<s.length();i++){ if(s.charAt(i)=='|') returni;//存在，就返回位置 } return-1;//返回-1表示没有“|”在其右边}intvnNum(charc){//返回c在非终结符表中的位置 inti; for(i=0;i<Vn.length;i++){ if(c==Vn[i]) returni;//在表中，就返回位置 } return-1;//返回-1表示不在表中}intvtNum(charc){//返回c在终结符表中的位置 inti; for(i=0;i<Vt.length;i++){ if(c==Vt[i]) returni; } return-1;}voidfirst2(Strings,intj){//求关于某一个产生式s,关于第j个字符的的first集 intv=vnNum(s.charAt(0));//v是产生式左边的非终结符所在序号 inti; if(vtNum(s.charAt(j))!=-1){//若产生式右边第一个为终结符 FIRST[v][vtNum(s.charAt(j))]=true;//就把s.charAt(j)加入s.charAt(0)的first集 } else{//产生式右边第一个为非终结符 if(!FIRST[vnNum(s.charAt(j))][Vt.length]){ first1(s.charAt(j)); } for(i=0;i<Vt.length;i++){ if(FIRST[vnNum(s.charAt(j))][i]&&Vt[i]!='ε'){ FIRST[v][i]=true; } } if(vtNum('ε')!=-1){//终结符中有ε if(FIRST[vnNum(s.charAt(j))][vtNum('ε')]){ if(j==s.length()-1){ FIRST[v][vtNum('ε')]=true; return; } if(s.charAt(j+1)!='|'){ j++; first2(s,j); } else{ FIRST[v][vtNum('ε')]=true; } } } }}voidfirst1(charv){//求非终结符v关于该文法的first集 inti,j; Strings; for(i=0;i<Gr.length;i++){ s=Gr[i]; if(s.charAt(0)==v){ j=3; first2(s,j); while(or(j,s)!=-1&&j<s.length()){ j=or(j,s); first2(s,j+1); } } } FIRST[vnNum(v)][Vt.length]=true;//将fi[vn(v)][Vt.length]设为true，表示已求v的first集}voidfirst(){//求所有非终结符的first集 inti,j; for(i=0;i<Vn.length;i++){//遍历非终结符表求各自first集 if(!FIRST[i][Vt.length]){ first1(Vn[i]); } }}voidfollow2(Strings,intj){//求关于某一个产生式的follow集 inti; if(j==s.length()-1||(j<s.length()-1&&s.charAt(j+1)=='|')){ if(s.charAt(0)!=s.charAt(j)){//考察字符与产生式左边的非终结符不同时 if(!FOLLOW[vnNum(s.charAt(0))][Vt.length]){ follow1(s.charAt(0)); } for(i=0;i<Vt.length;i++){//产生式左边的非终结符的follow集加到考察字符的follow集中 if(FOLLOW[vnNum(s.charAt(0))][i]){ FOLLOW[vnNum(s.charAt(j))][i]=true; } } } } if(j<s.length()-1&&s.charAt(j+1)!='|'){ if(vtNum(s.charAt(j+1))!=-1){//该字符为终结符 if(Vt[vtNum(s.charAt(j+1))]!='ε') FOLLOW[vnNum(s.charAt(j))][vtNum(s.charAt(j+1))]=true; } else{ for(i=0;i<Vt.length;i++){//该字符的first集中除ε的非终结符加入考察字符的follow集中 if(FIRST[vnNum(s.charAt(j+1))][i]&&Vt[i]!='ε'){ FOLLOW[vnNum(s.charAt(j))][i]=true; } } if(vtNum('ε')!=-1){//非终结符中有ε if(s.charAt(0)==s.charAt(j)) return; booleanm=true;//当考察字符右边的字符串的first集中有'ε'，m为真，没有时，m为假 for(i=j+1;i<s.length();i++){ if(vtNum(s.charAt(i))!=-1){ m=false; break; } if(s.charAt(i)=='|'){ break; } if(!FIRST[vnNum(s.charAt(i))][vtNum('ε')]){//当考察字符右边的字符串中的有一非终结符的first集中不含ε，m为假 m=false; } } if(m){ if(!FOLLOW[vnNum(s.charAt(0))][Vt.length]){ follow1(s.charAt(0)); } for(i=0;i<Vt.length;i++){//产生式左边的非终结符的follow集加到考察字符的follow集中 if(FOLLOW[vnNum(s.charAt(0))][i]){ FOLLOW[vnNum(s.charAt(j))][i]=true; } } } } } }}voidfollow1(charv){//求非终结符v关于该文法的follow集 if(v=='E'){//v为开始符号时 FOLLOW[vnNum(v)][vtNum('#')]=true; } inti,j; Strings; for(i=0;i<Gr.length;i++){ s=Gr[i]; for(j=3;j<s.length();j++){ if(s.charAt(j)==v){//产生式右边有考察字符 follow2(s,j);//求关于该产生式的follow集 } } } FOLLOW[vnNum(v)][Vt.length]=true;}voidfollow(){//求所有非终结符的follow集 inti,j; for(i=0;i<Vn.length;i++){//非终结符的follow集未求时 if(!FOLLOW[i][Vt.length]){ follow1(Vn[i]); } }}voidMM(intj,inti,Strings,intm){//将某一个产生式填入预测分析表中 charu=Gr[i].charAt(0); intk; if(vtNum(Gr[i].charAt(j))!=-1){//为终结符 if(Gr[i].charAt(j)!='ε'){//Gr[i].charAt(j)不为ε时将s加到M[vn(u)][vt(Gr[i].charAt(j))]中 M[vnNum(u)][vtNum(Gr[i].charAt(j))]=s; } else{//是ε for(k=0;k<Vt.length-1;k++){//Gr[i].charAt(j)为ε，将属于u的follow集的元素b的位置用s加到M[vn(u)][vt(b)]中 if(FOLLOW[vnNum(u)][k]){ M[vnNum(u)][k]=s; } } } } else{//Gr[i].charAt(j)为非终结符 for(k=0;k<Vt.length-1;k++){//对于终结符a属于Gr[i].charAt(j)的first集时，将s加到M[vn(u)][vt(a)]中 if(FIRST[vnNum(Gr[i].charAt(j))][k]){ M[vnNum(u)][k]=s; } } if(FIRST[vnNum(Gr[i].charAt(j))][vtNum('ε')]){//当ε属于Gr[i].charAt(j)的first集时，将属于u的follow集的b将s加到M[vn(u)][vt(b)]中 if(j==m-1){ for(k=0;k<Vt.length-1;k++){ if(FOLLOW[vnNum(u)][k])M[vnNum(u)][k]=s; } } else{ j=j+1; MM(j,i,s,m); } } }}voidbuildM(){//构造预测分析表 inti,j,m; Strings; for(i=0;i<Gr.length;i++){ j=3; while(j<Gr[i].length()){ m=or(j,Gr[i]); if(m==-1){ m=Gr[i].length(); } s=Gr[i].substring(j,m);//将j到m-1赋值到s截取一段字符（从索引出发） MM(j,i,s,m); j=m+1; } } }voidright(Strings,String[][]t){//分析一个字符串是否符合该文法 Stack<Character>temp=newStack<Character>();//分析栈 Stringtempp[][]=t;//保存输出临时数组 Stringz; temp.setSize(20); temp.push(newCharacter('#'));//初始化将#入栈 temp.push(newCharacter('E'));//初始化将E入栈 charu,v; inti=0,j,k=0; Stringm,action="初始化",rule=""; while(i<s.length()){ tempp[k][0]=String.valueOf(k);//整数型变量赋值给字符串数组使用函数String.valueOF() u=s.charAt(i); Stringtemp0_string=""; for(j=0;j<temp.size();j++){ if(temp.get(j)!=null) temp0_string=temp0_string.concat(temp.get(j).toString()); } tempp[k][1]=temp0_string; tempp[k][2]=s.substring(i); tempp[k][3]=rule; tempp[k][4]=action.toString(); v=temp.pop(); action="pop"; if(vnNum(v)!=-1){//栈顶元素为非终结符时 if(M[vnNum(v)][vtNum(u)]!=null){//分析表中有产生式 m=M[vnNum(v)][vtNum(u)]; rule=v+"->"+m; if(!m.equals("ε")){//产生式m不是ε action=action+",push("; for(j=m.length()-1;j>-1;j--){//将产生式反序入栈 action=action+m.charAt(j); temp.push(newCharacter(m.charAt(j))); } action=action+")"; } } else{//分析表中没有产生式，提示错误 rule=""; tempp[k+1][1]="错误"; //StringO=String.valueOf(u); //StringP=String.valueOf(v); StringQ=u+"\t不在"+v+"对应的分析表中"; tempp[k+1][2]=Q; return; } } else{//栈顶元素为终结符时 rule=""; if(v==u){//栈顶元素与输入符匹配 if(v=='#'){//栈顶元素为#时，成功 tempp[k+1][1]="成功"; return; } else{ i++; action="getnext(I)"; } } else{//栈顶元素与输入符不匹配，提示错误 tempp[k+1][1]="错误"; StringQ=u+"\t不在"+v+"不等"; tempp[k+1][2]=Q; return; } } k++; } return;}}四、实验评价、收获与体会从第一个实验越到第二个实验，难度着实陡增，时间有非常短，匆匆忙忙的结果是现在这一份结果。试验中的FIRST集FOLLOW集的自动化求是非常困难的，实现这一结果要密切结合初始的数据结构，所以一开始就要有系统的考虑，数据结构的设计与后面的程序功能的实现有无帮助，最好是能简化后面的功能实现。所以程序设计要先有一个总体布局，然后开动才能事半功倍。《编译原理》课程实验报告实验名称LR（1）分析表姓名赵保飞系院专业计算机科学与技术班级计算机01班学号2015216768实验日期2017.11.1指导教师李芒宏成绩一、实验目的和要求构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验原理文法：（1）E->E+T（2）E->T（3）T->T*F（4）T->F（5）F->(E)（6）F->i（1）实验数据结构说明 （2）实验算法描述(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。（3）算法流程图三、源程序代码和测试结果#include"stdafx.h"#include<iostream>#include<string>#pragmawarning(disable:4996)//strcpy()函数usingnamespacestd;typedefstructGe//存储文法{ charsleft;//文法左部 charsright[4];//文法右部}sentence;typedefstructA{ intmove[6];//移进 intchange[6];//规约}action_grid;typedefstructG{ charhead[3]; intgt[3];}goto_grid;intstatus[20];//状态栈intsta_Index;charsymbol[20];//符号栈intsym_Index;/*|instr_indexinpustring[20]:i+i*i#|instr_top*/charinputstring[20];//输入串intinstr_index;//指向inputstring最后一位#intinstr_top;//指向inputstring最前一位，即输入串栈顶intstep;intIsAccept=0;sentences_have[7];action_gridaction[12];goto_gridgo[12];voidchange_goto(intsta,charsymb);/*对各种表进行初始化*/voidInitlize(void){ /*存储六条文法*/ s_have[1].sleft='E'; strcpy(s_have[1].sright,"E+T");//E->E+T s_have[2].sleft='E'; strcpy(s_have[2].sright,"T");//E->T s_have[3].sleft='T'; strcpy(s_have[3].sright,"T*F");//T->T*F s_have[4].sleft='T'; strcpy(s_have[4].sright,"F");//T->F s_have[5].sleft='F'; strcpy(s_have[5].sright,"(E)");//F->(E) s_have[6].sleft='F'; strcpy(s_have[6].sright,"i");//F->i /*存储ACTION表中的move移进change规约*/ action[0].move[0]=5; action[0].move[3]=4; action[1].move[1]=6; action[2].change[1]=2; action[2].move[2]=7; action[2].change[4]=2; action[2].change[5]=2; action[3].change[1]=4; action[3].change[2]=4; action[3].change[4]=4; action[3].change[5]=4; action[4].move[1]=5; action[4].move[3]=4; action[5].change[1]=6; action[5].change[2]=6; action[5].change[4]=6; action[5].change[5]=6; action[6].move[0]=5; action[6].move[3]=4; action[7].move[0]=5; action[7].move[3]=4; action[8].change[1]=6; action[8].change[4]=11; action[9].change[1]=1; action[9].move[2]=7; action[9].change[4]=1; action[9].change[5]=1; action[10].change[1]=3; action[10].change[2]=3; action[10].change[4]=3; action[10].change[5]=3; action[11].change[1]=5; action[11].change[2]=5; action[11].change[4]=5; action[11].change[5]=5; /*存储GOTO表*/ go[0].head[0]='E';//符号栈栈顶非终结符 go[0].head[1]='T'; go[0].head[2]='F'; go[0].gt[0]=1;//要使用的文法 go[0].gt[1]=2; go[0].gt[2]=3; go[4].head[0]='E'; go[4].head[1]='T'; go[4].head[2]='F'; go[4].gt[0]=8; go[4].gt[1]=2; go[4].gt[2]=3; go[6].head[1]='T'; go[6].head[2]='F'; go[6].gt[1]=9; go[6].gt[2]=3; go[7].head[2]='F'; go[7].gt[2]=10; //其它初始化 sta_Index=0; status[sta_Index]=0; step=1; sym_Index=0; symbol[sym_Index]='#'; IsAccept=0; instr_top=0;}/*功能：利用状态和字符来查找action和goto参数：当前状态，剩余输入串栈顶符号，剩余输入串栈顶符号是第几个*/voidfind_table(intsta,charsymb,intcol){ if(sta==1&&col==5) { cout<<"Acc:分析成功\n)"; IsAccept=1; return; } /*查找移进*/ if(action[sta].move[col]!=0) { cout<<"ACTION["<<sta<<","<<symb<<"]="<<"S"<<action[sta].move[col] <<",PUSH"<<action[sta].move[col]<<endl; status[++sta_Index]=action[sta].move[col];//更新状态栈 symbol[++sym_Index]=symb;//更新符号串 instr_top++;//剩余输入串向后缩1 } /*查找规约*/ elseif(action[sta].change[col]!=0) { cout<<"r"<<action[sta].change[col]<<":"<<s_have[action[sta].change[col]].sleft<<"->" <<s_have[action[sta].change[col]].sright<<"规约,GOTO("<<status[sta_Index-strlen(s_have[action[sta].change[col]].sright)]<<"," <<s_have[action[sta].change[col]].sleft<<")="; inti=0; for(i=0;i<strlen(s_have[action[sta].change[col]].sright);i++)//规约：将符号栈中的文法右部去除 symbol[sym_Index--]='\0'; symbol[++sym_Index]=s_have[action[sta].change[col]].sleft;//规约：在符号栈中加入文法左部 for(i=0;i<strlen(s_have[action[sta].change[col]].sright);i++)//去除状态栈中对应的状态 status[sta_Index-i]='\0'; sta_Index-=i;//指向状态栈数组最后一位的标记减小 change_goto(status[sta_Index],symbol[sym_