1、集美大學計算機工程學院實驗報告指導教師：付永鋼實驗成績:實驗名稱：LL(1)語法分析器的構造姓名：學號上機實踐時間：6學時一、實驗目的1、掌握LL(1)分析法的基本原理；2、掌握LL(1)分析表的構造方法；3、掌握LL(1)驅動程序的構造方法。二、實驗環境Ubuntu三、實驗原理1、對文法要求LL(1)分析法屬于自頂向下分析方法，因此需要預測匹配的產生式。即在LL(1)分析法中，每當在符號棧的棧頂出現非終結符時，要預測用哪個產生式的右部去替換該非終 結符。LL(1)分析方法要求文法滿足如下條件：對于任一非終結符A，其任意兩個產生式A :,A一 都要滿足下面條件：First(A：)First (

2、A -)=.2、分析表構造LL(1)分析表的作用是對當前非終結符和輸入符號確定應該選擇用哪個產生式進行推 導。它的行對應文法的非終結符，列對應終結符，表中的值有兩種：一是產生式的編 號，一是錯誤編號。若用T表示LL(1)分析表，則T可表示如下：T: VNWTPUErrorT(A, t) = Aa當tFirst(AaT(A, t) = Error，否則其中P表示所有產生式的集合。顯然，一個文法G是LL(1)文法，當且僅當T的元素包含唯一的一個產生式或Error。3、驅動程序構造LL(1)分析主要包括以下四個動作，其中X為符號棧棧頂元素，a為輸入流當前字 符。替換：當X VN時選相應產生式的右部1

3、去替換X。匹配：當XVT時它與a進行匹配，其結果可能成功，也可能失敗，如果成功則 符號棧中將X退棧并將輸入流指針向前移動一位，否則報錯。成功：當格局為(空，空)時報告分析成功。報錯：出錯后，停止分析。四、實驗內容已知文法GE:EE+T|TTT*F|FF(E)|i說明：終結符號i為用戶定義的簡單變量，即標識符的定義。課程名稱：編譯原理 實驗編號：實驗三 班級：計算14上機實踐日期：2017.61消除文法的左遞歸，構造對應文法的預測分析表；2、 根據構造的預測分析表，實現LL(1)分析中控制程序(表驅動程序)， 并完成整 個的LL(1)分析程序的界面設計、運行；3、P104中，3.36寫一個Yac

4、c程序，把輸入的算術表達式翻譯成對應的后綴表達式 輸出。要求轉換正確，同時對于簡單錯誤能夠識別。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)存在

5、左遞歸。 用直接改寫法消除 左遞歸，得到如下文法：GE:ETEE+TE|&TFTT*FTF(E)|i(2) 對于以上改進的文法，可以得到：FIRST(E)=FIRST(+TEUFIRST(-TE )U=+，FIRST(T)=FIRST(*FT)FIRST(/FT) U&=*，FIRST(E)= FIRST( T ) = FIRST( F )=FIRST(E)UFIRST(i)=(，i 由此得到各非終結符的FOLLOW集合：FOLLOW(E)= )，$FOLLOW(E)=FOLLOW(E)=)，$FOLLOW(T)=FIRST(E)UFOLLOW(E )= +，)，$FOLLOW

6、(T )=FOLLOW(T)= +，)，$FOLLOW(F)=FIRST1構造LL(1)分析表采用手工操作構造LL(1)分析表。LL(1)分析表用一個二維矩陣表示，其中每個非終 結符對應一行，每個終結符對應一列，一個非終結符和一個終結符可以確定矩陣中的一 個元素，元素的值表示該非終結符和該終結符對應的產生式。每個矩陣元素都是一個符 號串，所有元素初始化為”；構造LL(1)表時，根據文法和各個產生式的First集，填寫LL(1)分析表的內容。 各產生式只要降右端填入到對應的表項中即可， 用空串表示Error。 在根據LL(1)分析表選擇產生式進行推導時，若查到的產生式為空串表示無相應 的產生式可

7、選，不匹配錯誤；否則根據符號串得到相應的產生式進行推導，即進行壓棧 操作。步驟分析棧(棧頂符號，當前輸入 符)剩余串所用產生式1$E(E, i)查表i+i*i$E-TEX2$EXT（T，i）查表i+i*i$T-FTX3$EXF（F，i）查表i+i*i$F-i4$EXTxi（i，i）i匹配i+i*i$5$EX（，+）查表+i*i$- &6$EX（Ex，+）查表+i*i$Ex-+T Ex7$EXT+（+，+）+匹配+i*i$8廠$EXT（T，i）查表i*i$T-FJ9$EXTXF（F，i）查表i*i$F-i10$EXi（i，i）i匹配i*i$11$EX（，*）查表*i$- *F T/12$

8、EXF*（*，*）*匹配*i$13$EXTXF（F，i）查表i$F-i14$EXTxi（i，i）i匹配i$15$EX（，$）查表$- &16$EX(E/,$)查表$Ex-&17$2數據結構LL（1）語法分析程序共用到個棧，分別稱為： 符號棧，語法樹棧，操作符棧和操作數棧。其中，符號棧用于進行LL（1）語法分析；其它的棧是為了在語法分析的過程中同 時生成與源程序結構對應的語法樹而設。語法樹棧用于生成聲明部分和語句部分的語法 樹；操作符棧和操作數棧用于生成表達式部分的語法樹。3.構造驅動程序構造LL（1）驅動程序的算法：（1）.分析開始時，首先將標志符號#和文法開始符號S依次壓入符

9、號棧；輸入流 指針指向第一個輸入符號，即由符號棧和輸入流構成的初始格局為：（#S,aia2sn#）然后，反復執行第2步所列的工作。（2） .設在分析的某一步，符號棧及剩余的輸入流處于如下的格局（#XlX2Xm-iXm,aiai+i.a#）其中，XiX2.Xm-lXm為分析過程中所得的文法符號，此時，可視棧頂符號Xm的不同情況，分別作如下動作：若XmWN,則以Xm及ai組成的符號對（Xm，a）查分析表T。設T（Xm，Si）為一產 生式，假設是XmUVW，此時將Xm從分析棧中退出，并將UVW壓入棧中，從而 得到新的格局（#XiX2.Xm-iWVU, aiai+i.an#）但若T（Xm，a）=Err

10、or，則調用出錯處理程序進行處理；若Xm=a*貝憔明棧頂符號已經與當前掃描的輸入符號得到匹配，此時應將Xm（即ai）從棧中退出，并將輸入流指針向前移動一個位置。若Xm=ai=#，則表明輸入串已經完全得到匹配，此時即可宣告分析成功而結束分 析。其它情形，轉錯誤處理程序。程序見附錄 TEfji*i+i$IT - FTfIi*i+i$IF - iI|*i+-i$| i Matching|I*1+1$IT1- *FT*I|i+i$| * Matching| F - 1|+i$ji Matching|+1$| T* - |+1$| E1- +TE*j|+1$j + Matching|+ jError|-

11、 +- +七、實驗結果正確的語法：InputT$SEtablepression:i *1+i EHX1, T X1J YTXft*Y X1, X1, *V x1, Y X1, YrFS I F*j*$*錯誤的語法:TXJxs*TS x1,T1 Xff*Y,X*,*FHInput | Action| | -TE1| 1*1+1$ | T - FT1I|F- i| *i +1$ | i Match-ing *i+1$ Tf- *FT1+1$ | * Matching|5+1$ F1|+i$ | i Matching|+1$ | Tf- I+1$IE1- +TE|1$ | + MatchingIi$

12、 | TFT1I| F-iI$ jiMatchingI$|I$ | E - 六、實驗小結1、在本次實驗中，通過設計、編制、調試一個遞歸下降語法分析程序，實現對詞 法分析程序所提供的單詞序列進行語法檢查和結構分析，掌握LL(1)分析法的基本原 理、掌握LL(1)分析表的構造方法、掌握LL(1)驅動程序的構造方法；2、通過本次實驗， 對LL(1)遞歸下降分析程序的構造和設計有了更為全面的認 識， 對LL(1)文法分析程序的實現有了進一步了解；3、 實驗輸入串以$結束，才用棧的形式，依次彈出進行處理；附錄：程序代碼：#coding:utf-8from prettytable import Prett

13、yTabledef LL1():global c,flag if(c=E): if(ak=i or ak=(): table.add_row(ak:, E - TE)stack.append(X) stack.append(T) print stack c=stack.pop()else:error()flag=1elif(c=X): if(ak=+): table.add_row(ak:, E - +TE) stack.append(X)stack.append(T) stack.append(+) print stack c=stack.pop()elif(ak=) or ak=$): t

14、able.add_row(ak:, E -)print stack c=stack.pop()error()flag=1elif(c=T):if(ak=iorak=():table.add_row(ak:,T-FT)stack.append(Y) stack.append(F) print stack c=stack.pop()else:error()flag=1elif(c=Y):if(ak=*):table.add_row(ak:,T-*FT)stack.append(Y)stack.append(F) stack.append(*) print stack c=stack.pop()el

15、if(ak=+ or ak=) or ak=$):table.add_row(ak:, T -)print stack c=stack.pop()else:else:error()flag=1elif(c=F):if(ak=i):table.add_row(ak:, F - i) stack.append(i) print stackc=stack.pop()elif(ak=(): table.add_row(ak:, F - (E) stack.append()stack.append(E) stack.append() print stack c=stack.pop()error()fla

16、g=1def error(): global k table.add_row(ak, Error) print stack k+=1if _name_ = _main_: a=raw_input(Input Etablepression:) a=a+$ fortemp in a:if(temp!=i and temp!=+ and temp!=* and temp!=( and temp!=) andtemp!=$):print You input is wrong! exit(0)table = PrettyTable(Input, Action) table.padding_width = 1table.alignInput = r table.alignAction = l stack= k=0 flag=0stack.append($) stack.append(E) table.add_row(ak:, ) print stackc=