合肥工業(yè)大學編譯原理實驗

宣城校區(qū)實驗報告課程名稱編譯原理專業(yè)班級計算機0001班學生姓名及學號趙保飛2015216768指導教師李芒宏計算機中心樓第四機房2017～2018學年第一學期《編譯原理》課程實驗報告實驗名稱詞法分析設計姓名趙保飛系院專業(yè)計算機科學與技術班級計算機01班學號2015216768實驗日期2017.10.18指導教師李芒宏成績一、實驗目的和要求通過本實驗的編程實踐，使學生了解詞法分析的任務，掌握詞法分析程序設計的原理和構造方法，使學生對編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運用。四、實驗評價、收獲與體會紙上得來終覺淺，雖然詞法分析器是理論上實行最簡單的，但是編寫程序實現(xiàn)時卻也遇到了不少的問題。使用JAVA來寫是因為這學期正在開這門課，數(shù)據(jù)的讀入還是自己提前看才實現(xiàn)的，讀入的一條源代碼看似簡單，首先要儲存，儲存后要清楚空格直到讀到字符為止，還是以C++的思維來寫java程序，其中很多細節(jié)均是通過函數(shù)來實現(xiàn)。這也許自己沒有深刻理解java設計思維的原因。希望以后能改進?！毒幾g原理》課程實驗報告實驗名稱LL（1）分析法姓名趙保飛系院專業(yè)計算機科學與技術班級計算機01班學號2015216768實驗日期10.25指導教師李芒宏成績一、實驗目的和要求復變函數(shù)。。編譯原理實驗和預習。。java作業(yè)和實驗。。操作系統(tǒng)復習。。通過完成預測分析法的語法分析程序，了解預測分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學生了解語法分析的功能，掌握語法分析程序設計的原理和構造方法，訓練學生掌握開發(fā)應用程序的基本方法。有利于提高學生的專業(yè)素質，為培養(yǎng)適應社會多方面需要的能力。二、實驗原理文法為（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）實驗數(shù)據(jù)結構說明 Char數(shù)組-Vn數(shù)組--非終結符表；char數(shù)組-Vt數(shù)組--終結符；String數(shù)組-Gr數(shù)組--文法；Boolean型FIRST[][]二維數(shù)組對應每個非終結符的first集，初始化均為false；Boolean型FOLLOW[][]二維數(shù)組對應每個非終結符的Follow集，初始化均為false;String型M[][]二維數(shù)組對應預測分析表（2）實驗算法描述算法總的來講不是很復雜，但是細節(jié)上可能有點復雜?？偟氖且罁?jù)本實驗的數(shù)據(jù)結構FIRST[][]和FOLLOW[][]集，這兩個數(shù)據(jù)結構雖然浪費了不少空間但是確實讓程序的實現(xiàn)變得更簡單。First()總的來求所有的非終結符的first集，first1()分工為具體求某一個具體非終結符的first集；first2()則是求某一個集體的產(chǎn)生式的first集。通過這三個函數(shù)的逐級分工來實現(xiàn)求所有的非終結符的first集。Follow集來說相對難求一點，但把它放到first集后面求來說相對簡單一點。通過上面的分布設計就可以實現(xiàn)了。（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"+"所用產(chǎn)生式"+"\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型數(shù)組，初始化均為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){//求關于某一個產(chǎn)生式s,關于第j個字符的的first集 intv=vnNum(s.charAt(0));//v是產(chǎn)生式左邊的非終結符所在序號 inti; if(vtNum(s.charAt(j))!=-1){//若產(chǎn)生式右邊第一個為終結符 FIRST[v][vtNum(s.charAt(j))]=true;//就把s.charAt(j)加入s.charAt(0)的first集 } else{//產(chǎn)生式右邊第一個為非終結符 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){//求關于某一個產(chǎn)生式的follow集 inti; if(j==s.length()-1||(j<s.length()-1&&s.charAt(j+1)=='|')){ if(s.charAt(0)!=s.charAt(j)){//考察字符與產(chǎn)生式左邊的非終結符不同時 if(!FOLLOW[vnNum(s.charAt(0))][Vt.length]){ follow1(s.charAt(0)); } for(i=0;i<Vt.length;i++){//產(chǎn)生式左邊的非終結符的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++){//產(chǎn)生式左邊的非終結符的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){//產(chǎn)生式右邊有考察字符 follow2(s,j);//求關于該產(chǎn)生式的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){//將某一個產(chǎn)生式填入預測分析表中 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截取一段字符（從索引出發(fā)） MM(j,i,s,m); j=m+1; } } }voidright(Strings,String[][]t){//分析一個字符串是否符合該文法 Stack<Character>temp=newStack<Character>();//分析棧 Stringtempp[][]=t;//保存輸出臨時數(shù)組 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);//整數(shù)型變量賦值給字符串數(shù)組使用函數(shù)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){//分析表中有產(chǎn)生式 m=M[vnNum(v)][vtNum(u)]; rule=v+"->"+m; if(!m.equals("ε")){//產(chǎn)生式m不是ε action=action+",push("; for(j=m.length()-1;j>-1;j--){//將產(chǎn)生式反序入棧 action=action+m.charAt(j); temp.push(newCharacter(m.charAt(j))); } action=action+")"; } } else{//分析表中沒有產(chǎn)生式，提示錯誤 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;}}四、實驗評價、收獲與體會從第一個實驗越到第二個實驗，難度著實陡增，時間有非常短，匆匆忙忙的結果是現(xiàn)在這一份結果。試驗中的FIRST集FOLLOW集的自動化求是非常困難的，實現(xiàn)這一結果要密切結合初始的數(shù)據(jù)結構，所以一開始就要有系統(tǒng)的考慮，數(shù)據(jù)結構的設計與后面的程序功能的實現(xiàn)有無幫助，最好是能簡化后面的功能實現(xiàn)。所以程序設計要先有一個總體布局，然后開動才能事半功倍。《編譯原理》課程實驗報告實驗名稱LR（1）分析表姓名趙保飛系院專業(yè)計算機科學與技術班級計算機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）實驗數(shù)據(jù)結構說明 （2）實驗算法描述(1)總控程序，也可以稱為驅動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。（3）算法流程圖三、源程序代碼和測試結果#include"stdafx.h"#include<iostream>#include<string>#pragmawarning(disable:4996)//strcpy()函數(shù)usingnamespacestd;typedefstructGe//存儲文法{ charsleft;//文法左部 charsright[4];//文法右部}sentence;typedefstructA{ intmove[6];//移進 intchange[6];//規(guī)約}action_grid;typedefstructG{ charhead[3]; intgt[3];}goto_grid;intstatus[20];//狀態(tài)棧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規(guī)約*/ 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;}/*功能：利用狀態(tài)和字符來查找action和goto參數(shù)：當前狀態(tài)，剩余輸入串棧頂符號，剩余輸入串棧頂符號是第幾個*/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];//更新狀態(tài)棧 symbol[++sym_Index]=symb;//更新符號串 instr_top++;//剩余輸入串向后縮1 } /*查找規(guī)約*/ 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<<"規(guī)約,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++)//規(guī)約：將符號棧中的文法右部去除 symbol[sym_Index--]='\0'; symbol[++sym_Index]=s_have[action[sta].change[col]].sleft;//規(guī)約：在符號棧中加入文法左部 for(i=0;i<strlen(s_have[action[sta].change[col]].sright);i++)//去除狀態(tài)棧中對應的狀態(tài) status[sta_Index-i]='\0'; sta_Index-=i;//指向狀態(tài)棧數(shù)組最后一位的標記減小 change_goto(status[sta_Index],symbol[sym_