編譯原理課程實驗報告(詞法分析器及語法分析器)

1、編譯原理實驗報告班級：軟件0501班學號：姓名：詞法分析器與語法分析器I.問題描述設計、編制并調試一個詞法分析子程序，完成識別語言單詞的任務；設計、編制、調試一個語法分析程序，并用它對詞法分析程序所提供的單詞序列進行語法檢查和結構分析。ii.設計簡要描述界面需求：為了更加形象的模擬過程，此實驗使用圖形界面。要求從圖形界面上輸入輸入串，點擊詞法分析，可以將詞法分析后識別的單詞符號顯示，點擊語法分析，可以將語法分析的堆棧過程顯示，并且顯示結果（是否是符合文法的句子），清空則可以將所有置空。功能分析：1、由用戶輸入輸入串；2、用戶點擊“詞法分析”，可以將詞法分析后識別的單詞符號顯示。3、用戶點擊語法

2、分析，可以將語法分析的堆棧過程顯示，并且顯示結果（是否是符合文法的句子）4、用戶點擊清空，則將界面所有組件置為空思路描述：一、設計構想：本實驗決定編寫一個簡易C語言的詞法分析器和語法分析器。使其能夠識別while，if等關鍵字，可以判斷賦值語句、條件語句、循環(huán)語句。二、文法分析1、需要識別的關鍵字及其識別碼有關鍵字識別碼關鍵字識別碼關鍵字識別碼main0-11；22int1*1223char2/13=25else4)15=26for516=27while617!=28ID718ERROR-1NUM819=920+10:212、文法程序main()語句塊語句塊語句串語句串語句；語句串|語句；語句

3、賦值語句|條件語句|循環(huán)語句賦值語句ID=表達式;條件語句if條件語句塊循環(huán)語句while條件語句塊條件(表達式關系符表達式)表達式表達式運算符表達式|(表達式)|ID|NUM運算符+|-|*|/關系符V|=|=|!轉化為符號表示：Smain()K|空KCCY；C|空YF|T|XFID=BTifJKXwhileJKJ(BGB)BBZB|(B)|IDNUMZ+|-|*|/G|=|=|!表示含義：S:程序K:語句塊C:語句串Y:語句F：賦值語句T:條件語句X:循環(huán)語句J:條件B:表達式I:項Z:運算符G:關系符3、LL(1)分析表(1)，求出first集及follow集:FIRST(S)=mian

4、FIRST(K)=FIRST(C)=FIRST(Y)=ID,if,while，空；FIRST(Y)=FIRST(F)+FIRST(T)+FIRST(X)=ID,if,while;FIRST(F)=ID;FIRST(T)=if;FIRST(X)=while;FIRST(J)=FIRST(B)=;FIRST(B)=(,ID,NUM；FIRST(Z)=+，-，*，/FIRST(G)=,=,=,!=;FOLLOW(S)=#；FOLLOW(K)=；FOLLOW(C)=；FOLLOW(Y)=；FOLLOW(F)=；;FOLLOW(T)=；;FOLLOW(X)=；;FOLLOW(J)=，；FOLLOW(B)

5、=+,-,*,/,),V,V=,=,=,!=,；FOLLOW(B=+,-,*,/,),V,V=,=,=,!=,;；FOLLOW(Z)=(,ID,NUM;FOLLOW(G)=(,ID,NUM;2）消除左遞歸,拆分文法關系并編號0、St空1、Stmain()K2、KtC3、CtY；C4、Ct空5、YtF6、YtT7、YtX8、FtID=B9、TtifJK10、XtwhileJK11、Jt(BGB)12、Bt(B)B13、BtIDB14、BtNUMB15、BtBZBB16、Bt空17、Zt+18、Zt-19、Zt*20、Zt/21、Gt22、Gt24、Gt=25、Gt=26、Gt!=(3)構造LL(

6、1)分析表(注：在表中用上一步的編號表示所需要的產生式)main空()；=ifwhileIDnum+-*/=!=#S10K2C44333Y675F8T9X10J11B121314B!16151616151516161616161616161616Z17181920G212223242526iii詳細設計描述項目構架：aa二n-Jo-1Iaavll.WQwos*00皿郵礎-E-.0.E-.0E-4-.-二一-十-:H-JL.JL.Tu-H.-kt-t-a-H-m此AJAJsi-sc55b1flsenmBB咧EE1、word.wordList包(存儲了關鍵字)：word:此類是定義了存儲關鍵字的結

7、構：包括String型的關鍵字，和int型的識別符。wordList:此類存儲了29個關鍵字，在構造函數(shù)中初始化。2、word包(進行詞法分析)中：basicFunction:此類定義了做詞法分析的基本函數(shù)：GetChar()將下一輸入字符讀到ch中，搜索知識器前移一個字符位置GetBC()；檢查ch中的字符是否為空白。若是，貝V調用GetChar直至不是字符為止Concat()；將ch中的字符連接到strToken之后IsLetter()；判斷ch中的字符是否為字母IsDigit()；判斷ch中的字符是否為數(shù)字Reserve。；對strToken中的字符創(chuàng)查找保留字表，若是則返回它的編碼，否

8、貝返回0Retract()；將搜索指示器回調一個字符位置RetractStr()；將strToken置空lexAnalysis:此類是用來進行詞法分析，將分析后的單詞存入word數(shù)組中,(注：在詞法分析中，若是一串字母，則認為是ID,若是數(shù)字，則認為是NUM。存儲的時候識別符分別存ID與NUM的識別符，但是內容仍然是自己的內容)其中的wordAnalysis函數(shù)就是詞法分析函數(shù)(具體實現(xiàn)請看后面的重要函數(shù)分析)3、stack包(定義棧)中：棧是通過鏈表來定義的，因此StringListElement:次類定義了鏈表的每一個節(jié)點StringStrack：此類定義了棧，其中有長度屬性，有函數(shù)：To

9、p();用來取得棧頂Push()；壓棧Pop()；出棧4、sentence包(語法分析)中：juzi:定義了文法的句子的結構：key(左邊部分)content(右邊推出的部分)lo(長度)grammar：存儲了文法的27個關系式AnalysisFB：定義了分析表的存儲結構AnalysisF：存儲分析表SentenceAnalysis：語法分析JuProduction(wordw)：此函數(shù)是用來判斷在當前棧與輸入串的情況下，用哪一個產生式，返回產生式在數(shù)組中的下標若輸入串的第一個字符與棧頂字符相同則表示可以規(guī)約，則返回-1；若不能過用產生式，則返回-2；AnalysisBasic(wordw):

10、此函數(shù)是分布進行語法分析，對棧操作根據(jù)所需要的產生式對符號棧進行操作返回0表示規(guī)約；返回1表示移進；否則表示輸入串不是文法的句子5.Main包(主界面)中Main：此類定義了圖形界面重要函數(shù)分析：一、詞法分析函數(shù)：當搜索指示器小于輸入串長度是，就循環(huán)執(zhí)行如下操作：得到當前char，如果是字母，判斷下一個，如是數(shù)字或字母，繼續(xù)直至不是字母或者是數(shù)字，將此時的單詞與關鍵字比較，獲得識別符，存入word數(shù)組中如果是數(shù)字，循環(huán)看下一個是否為數(shù)字，繼續(xù)直至不是數(shù)字為止，將單詞存入數(shù)組中如果是+、-、*、/、（、）、，、：、；與關鍵字比較，直接存入數(shù)組中如果是、=、!時，要判斷下一個，是否構成了=、=、=

11、、!=。然后在存入數(shù)組中如果下一個字符是空，換行，則跳過去下一個字符。在做詞法分析的時候，注意每一次判斷結束之后要將strToken清空，而且要注意回退，即當輸入串下一個不滿足要求的時候，要回退一格。二、語法分析函數(shù)利用詞法分析已經分析出來的單詞數(shù)組，循環(huán)進行每一步的語法分析，每當歸并一個單詞之后，index指示器加一，直至index等于單詞數(shù)組長度，循環(huán)結束。在每一次循環(huán)中，根據(jù)當前指示器指示的單詞及堆棧的棧頂判斷：若相同，則表示要歸并，將index+；棧頂彈出若不相同，在分析表中查找所需要的產生式，并將棧頂彈出，將產生式逆向堆棧。在查詢的過程中，如果不能夠移進也不能夠歸并，表示輸入串不符合

12、文法，在提示欄中提示。如果循環(huán)結束，直至棧中是由#，輸入串中只剩#，表示分析完畢，輸入串是符合文法的句子。iv.結果分析（原始圖示）圖形界面：輸入句子：main()空的main函數(shù)，運行結果1、點擊詞法分析之后，在右側的詞法分析結果中顯示分析后的單詞:2、點擊語法分析之后，在中間的表中顯示堆棧過程:3、語法分析結束，該語句是符合文法的句子，因此在提示欄中顯示“該句子是符合文法的語句！輸入復雜一點的句子：main()If(zhj=zhj)Zhj=good;；則結果是:J耐去啊Hi：1.rrijin；rf(zh|=zhj)Ztij-QHld；夕豁on;.i;-T#K.r：.B-lD氐活U輔Ifi境

13、說程磁字昂T顯工彳琉：上品的和二個?INJ耐去啊Hi：1.rrijin；rf(zh|=zhj)Ztij-QHld；夕豁on;.i;-T#K.r：.B-lD氐活U輔Ifi境說程磁字昂T顯工彳琉：上品的和二個?IN袴gum工帶丄陶和.B=朋HJJBP?|C.!一Me:*dhi$03Oij;l卓bhi二ggiQiJ；泮-；：-寸flC.-CFE14.0!：15.：-1_陰,Ui.inZ；Q32i軟去是符色文陡的偃駅C-Y;CYFF-4CcB7頂WH.“.躋.m：臨廠.n.A則他輸出的單詞是：(l,main)(14,()(15,)(18,)(4,if)(14,()(7,zhj)(27,=)(7,zhj

14、)(15,)(18,)(7,zhj)(9,=)(7,good)(22,；)(19,)(22,；)(19,)語法分析經過了從0到37的38步，分析結束：（在下圖中將語法分析的全過程拼合）分析結束后的輸出結果是:F圖為此次語法分析的堆棧全過程:語法分柝堆旌過程連：輸入字荷黑兄顯示待輸入髓的前三咋捋號桂輸入串所用產生武0#smainOfif(zhj=zhj)(zhj=good;.1i40(rnatnmainQfif(zhj=zhjXzhj-good;S-mainQK2#K)(0if(zhj=hj)znj=good；,#3)if(zhj=zrj)zhj=good;#4ood；;#5*Cirtni-Zi

15、ij.iZh：-juOd1；：#“伯6ncif(zhj=zlij)ztij=good;#7W；Yih=zhj)曲戶good;#C、Y；CS機;Tiftzhj=zhjXztij=good;#Y-T9#C；KJifif(zhj=zhj)ztij=good;#T-ifJK10*C；KJ(2tij=zhj)zhj=goodj;i#11C；kjBOE(zhj=zhj)zhj=good;#12#C；K)BGBzhj2hXzhj=good；l#13*C;K)B3B1Dzhj=zhj)(zhj=good;#14枇;加酮-=zfiiXzhi=qood;l#15=zlij)zlij=good1j;#B-*15#C

16、；K)B=G-=17C；KJBzh)zhj=good;#18刊GKJB1Dzhi)zhi=QoodJ/i#19#C；K)SXzhj=good;)：)#20hgood;g|#0d-21#C：kzhj=good.;)#22#肉鳳zhi-good;K如C#17-1r4pnrhiTizilt1-#29#C；)C;B1D30#CJC；B;#.31濟：32l#C；)C腫33帕j腫034腓3536*C-J37#-*輸出更加復雜的句子：Main()While(lsq=zhj)If(zhj=zhj)Zhj=good;則結果是:右側的單詞符號序列為:語法分析過程為:吿騾輸扎串斫甲立生衣0main0whilm(l陰

17、八zh()irG!hj=-ziij)fzliJ=goDd,!#1#K)(mairiinQ(v*hiEe=zh)iffthj=zhi)maimQK20Yvhi舊(l$q=41jX?hJ)(;hgDfld;用_3Hwhile(lsq*=zhj)(iftzhi=znjX2HJ=good,#4杯ielsq=ih)4fC!hj=zhj)jzhj=gaod;i*Mi帕牡碉=ihj)if(lhj-zh)(zlij-good;)*K-C#C:wrtilB(is(j=znjXiffznj=zhi)zhFgooq肘|7#1C;Ywhil80$q*=ztijXiffzhj=-zhD(zh(=good;)#O忤8wn

18、Heysn=z?iJxif(zriJ=:hp)zhFyooc,j缶7-X9#C；KJwhile砧ile(isq=ztijXigj=z帥血尸gdoJ;#幣詢iiej瓦10(1sq-zhj)tf(zhj=zhj)zhjgood;甘序11#JC.LOBGB(1sq=zhi)r(zhF=znjXzhi=good,#121?q匸zhji伽j=Nhj)hKOQd;)|?i3JC.KJBGBTD蹴帚頑ik茁但hi二m葩（LHl*辛：C：KIE13F=南)：i他hi=zin甬血i=nocri：Hl#輸入串是符合文法的句子，因此，正常結束輸入一個不符合文法的句子：Main()zhanghuijuanisagoo

19、dstudent;/zhanghuijuanisagoodstudent語句即不是賦值，條件，也不是循環(huán)，因此不符合文法輸出結果是：輸入一個不符合文法的句子：Main()zhanghuijuanisagoodstudent;/zhanghuijuanisagoodstudent語句即不是賦值，條件，也不是循環(huán)，因此不符合文法輸出結果是：詞法分析仍然可以進行，但是語法分析中發(fā)現(xiàn)進行不下去了，因此輸出錯誤提示:“此輸入串不是一個語句，不符合文法！”iiv調試報告:程序在編寫的過程中有很多小的地方并沒有注意，在不斷的調試的過程當中逐漸發(fā)現(xiàn)：1、在文法中有A-空的情況，在文法產生式的存儲過程中就用空格

20、代替了空，但是當需要用這樣的產生式移進的時候，如果跟其他的產生式一樣處理,則會在堆棧中將空格壓棧，因此使語法分析不能繼續(xù)進行下去。因此，我們在壓棧之前要先進行判斷，若是這種情況，則只是彈出棧頂，而不對其進行壓棧。2、由于在此程序中應用了多個數(shù)組，因此很容易出現(xiàn)數(shù)組越界的情況，所以這里就要多加注意才行。3、在堆棧過程輸出的時候，要輸出當前棧中的元素，以及剩余的輸入串，一定要注意要將輸入串的輸出放在index的增加之后，否則就是輸出上一次的執(zhí)行時的輸入串了附：程序原代碼*packageword.wordList;*/fileword.java/publicclasswordStringvalue;

21、intID;publicintgetID()returnID;publicvoidsetID(intid)ID=id;publicStringgetValue()returnvalue;publicvoidsetValue(Stringvalue)this.value=value;/fileword.java/publicclassWordList/此類定義了語言單詞符號種別碼wordw=newword30;publicWordList()w0=newword();w0.setID(1);w0.setValue(main);w1=newword();w1.setID(2);w1.setValu

22、e(int);w2=newword();w2.setID(3);w2.setValue(char);/省略w27=newword();w27.setID(28);w27.setValue(!=);w28=newword();w28.setID(29);w28.setValue(ERROR);publicintReserve(Stringvalue)for(inti=0;i=a&ch=A&ch=0&ch1)strToken=strToken.substring(0,l-1);index-;/將strToken置空publicvoidRetractStr()strToken=;/file:lexA

23、nalysis.java;/importword.wordList.word;publicclasslexAnalysisStringinput;publicwordword=newword1000;publicStringgetInput()returninput;publicvoidsetInput(Stringinput)this.input=input;publicintwordAnalysis()inti=0;basicFunctionbf=newbasicFunction(input);intlo=input.length();while(bf.indexlo)wordi=neww

24、ord();bf.GetChar();bf.Concat();if(bf.IsLetter()intf=0;if(bf.indexlo)bf.GetChar();bf.Concat();while(bf.IsLetter()|bf.IsDigit()if(bf.indexlo)bf.GetChar();bf.Concat();elsebf.ch=;f=1;if(f!=1)bf.Retract();intm=bf.Reserve();if(m=0)wordi.setValue(bf.strToken);wordi.setID(7);elsewordi.setValue(bf.strToken);

25、wordi.setID(m);i+;bf.RetractStr();elseif(bf.IsDigit()intf=0;if(bf.indexlo)bf.GetChar();bf.Concat();while(bf.IsDigit()if(bf.index|bf.ch=|bf.ch=|bf.ch=!)intf=0;if(bf.indexlo)bf.GetChar();bf.Concat();elsebf.index+;bf.ch=;f=1;if(bf.ch!=&f!=1)bf.Retract();intm=bf.Reserve();if(m=0)wordi.setValue(bf.strTok

26、en);elsewordi.setValue(bf.strToken);wordi.setID(m);i+;bf.RetractStr();elseif(bf.ch=|bf.ch=n|bf.ch=r)bf.RetractStr();returni;1J1平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平不/file:StringListElement.java;/publicclassStringListElementpublicStringdata;publicStringListElementnext=null;StringListElement(Stringvalue)dat

27、a=value;StringListElement(Stringvalue,StringListElementnext)data=value;this.next=next;/file:StringStack.java;/publicclassStringStackpublicStringListElementtop=newStringListElement();publicintlo=0;publicStringtop()if(top!=null)returntop.data;elsereturnERROR!;publicStringpop()Stringresult=top();if(top

28、!=null)top=top.next;lo-;returnresult;publicvoidpush(Stringvalue)if(top=null)top=newStringListElement(value);lo+;elseStringListElementtemp=newStringListElement(value);temp.next=top;top=temp;lo+;1J平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平,廠.平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平/file:juzi.java;/publicclassjuzipublicStr

29、ingkey;publicintlo;publicStringcontent=,;/file:grammar.java;/publicclassgrammarpublicjuzigram=newjuzi27;publicgrammar()gram0=newjuzi();gram0.key=S;gram0.lo=1;gram0.content0=;gram1=newjuzi();gram1.key=S;gram1.lo=4;gram1.content0=main;gram1.content1=(;gram1.content2=);gram1.content3=K;省略gram26=newjuzi

30、();gram26.key=G;gram26.lo=1;gram26.content0=!=;publicstaticvoidmain(Stringargs)grammarg=newgrammar();System.out.println(g.gram0.key);/file:AnalysisFB.java;/publicclassAnalysisFB/此類定義了分析表中的每一個單元的數(shù)據(jù)結構publicStringkey;publicStringinput;publicintindex;/file:AnalysisF.java;/publicclassAnalysisFpublicAnaly

31、sisFBA=newAnalysisFB43;publicAnalysisF()A0=newAnalysisFB();A0.key=S;A0.input=#;A0.index=0;A1=newAnalysisFB();A1.key=S;A1.input=main;A1.index=1;A2=newAnalysisFB();A2.key=K;A2.input=;A2.index=2;/省略A42=newAnalysisFB();A42.key=G;A42.input=!=;A42.index=26;/file:SentenceAnalysis.java;/importstack.StringSt

32、ack;importword.wordList.word;/*此類中是用于語法分析*/publicclassSentenceAnalysispublicStringStackss=newStringStack();此堆棧是符號棧publicgrammargg=newgrammar();publicAnalysisFaf=newAnalysisF();/初始化堆棧publicSentenceAnalysis()ss.push(#);ss.push(S);/*此函數(shù)是用來判斷在當前棧與輸入串的情況下，用哪一個產生式,返回產生式在數(shù)組中的下標*若輸入串的第一個字符與棧頂字符相同則表示可以規(guī)約，則返回

33、-1；*若不能過用產生式，則返回-2；*/publicintJuProduction(wordw)intf=-2;Stringtop=ss.top();System.out.println(+ss.top();Stringinput=;if(w.getID()=7)input=ID;elseif(w.getID()=8)input=NUM;elseinput=w.getValue();if(top.equals(input)f=-1;for(inti=0;i=0&pro=0;j-)ss.push(gg.grampro.contentj);f=1;returnf;平平平平平平平平平平平平平平平平

34、平平平平平平平平平平平平平平平平,w-xqIOTVVO1f*l?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*?*此圖形界面代碼不再黏貼了，只是將詞法分析的函數(shù)及語法分析的函數(shù)黏貼privateJButtongetJButton()if(jButton=null)jButton=newJButton();jButton.setBounds(newjava.awt.Rectangle(599,80,89,41);jButton.setText(”詞法分析)；jButton.addActionListener(newActionListener(

35、)publicvoidactionPerformed(ActionEventarg0)Stringinput=getJTextArea().getText().toString().trim()；System.out.print(input)；TableModelmodel=getJTable().getModel()；DefaultTableModeltablemodel=(DefaultTableModel)model；intcounts=tablemodel.getRowCount()；for(intk=counts-1；k=0；k-)tablemodel.removeRow(k)；lexAnalysisle