本文格式為Word版，下載可任意編輯——編譯原理試驗三LL(1)語法分析器的構造集美大學計算機工程學院試驗報告

課程名稱：編譯原理試驗編號：試驗三班級：計算12

上機實踐日期：2023.12一、試驗目的

1、把握LL(1)分析法的基本原理；2、把握LL(1)分析表的構造方法；3、把握LL(1)驅動程序的構造方法。二、試驗環境

Windows7x64、VC6.0三、試驗原理

1、對文法要求

LL(1)分析法屬于自頂向下分析方法，因此需要預計匹配的產生式。即在LL(1)分析法中，每當在符號棧的棧頂出現非終結符時，要預計用哪個產生式的右部去替換該非終結符。LL(1)分析方法要求文法滿足如下條件：對于任一非終結符A，其任意兩個產生式A??,A??，都要滿足下面條件：First(A??)∩First(A??)=?

2、分析表構造

LL(1)分析表的作用是對當前非終結符和輸入符號確定應選中擇用哪個產生式進行推導。它的行對應文法的非終結符，列對應終結符，表中的值有兩種：一是產生式的編號，一是錯誤編號。若用T表示LL(1)分析表，則T可表示如下：T:VN×VT?P∪{Error}T(A,t)=A?α，當t?First(A?α)T(A,t)=Error，否則

其中P表示所有產生式的集合。顯然，一個文法G是LL(1)文法，當且僅當T的元素包含唯一的一個產生式或Error。

3、驅動程序構造

LL(1)分析主要包括以下四個動作，其中X為符號棧棧頂元素，a為輸入流當前字符。

?替換：當X?VN時選相應產生式的右部?去替換X。

?匹配：當X?VT時它與a進行匹配，其結果可能成功，也可能失敗，假使成功則符號棧中將X退棧并將輸入流指針向前移動一位，否則報錯。?成功：當格局為（空，空）時報告分析成功。?報錯：出錯后，中止分析。四、試驗內容

已知文法G[E]:E→E+T|TT→T*F|FF→(E)|i

說明：終結符號i為用戶定義的簡單變量,即標識符的定義。

指導教師：付永鋼姓名：

上機實踐時間：6學時

試驗成績：學號：

試驗名稱：LL(1)語法分析器的構造

1、消除文法的左遞歸，構造對應文法的預計分析表；

2、根據構造的預計分析表，實現LL(1)分析中控制程序（表驅動程序），并完成整個的LL(1)分析程序的界面設計、運行；

3、P104中，3.36寫一個Yacc程序，把輸入的算術表達式翻譯成對應的后綴表達式輸出。要求轉換正確，同時對于簡單錯誤能夠識別。

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)存在左遞歸。用直接改寫法消除左遞歸，得到如下文法：G[E]:

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i

（2）對于以上改進的文法，可以得到：

FIRST(E’)=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，ε}FIRST(T’)=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，ε}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST((E))∪FIRST(i)={(，i}由此得到各非終結符的FOLLOW集合：FOLLOW(E)={)，$}

FOLLOW(E’)=FOLLOW(E)={)，$}

FOLLOW(T)=FIRST(E’)∪FOLLOW(E’)={+，)，$}FOLLOW(T’)=FOLLOW(T)={+，)，$}FOLLOW(F)=FIRST1、構造LL(1)分析表

采用手工操作構造LL(1)分析表。LL(1)分析表用一個二維矩陣表示，其中每個非終結符對應一行，每個終結符對應一列，一個非終結符和一個終結符可以確定矩陣中的一個元素，元素的值表示該非終結符和該終結符對應的產生式。每個矩陣元素都是一個符號串，所有元素初始化為〞〞；構造LL(1)表時，根據文法和各個產生式的First集，填寫LL(1)分析表的內容。各產生式只要降右端填入到對應的表項中即可，用空串表示

Error。在根據LL(1)分析表選擇產生式進行推導時，若查到的產生式為空串表示無相應的產生式可選，不匹配錯誤；否則根據符號串得到相應的產生式進行推導，即進行壓棧操作。步驟分析棧（棧頂符號，當前輸入剩余串所用產生式符）1$E（E，i）查表i+i*i$E->TEˊ234567891011121314151617

$EˊT（T，i）查表$EˊTˊF（F，i）查表$EˊTˊi（i，i）i匹配$EˊTˊ（Tˊ，+）查表$Eˊ（Eˊ，+）查表$EˊT+（+，+）+匹配$EˊT（T，i）查表$EˊTˊF（F，i）查表$EˊTˊi（i，i）i匹配$EˊTˊ（Tˊ，*）查表$EˊTˊF*（*，*）*匹配$EˊTˊF（F，i）查表$EˊTˊi（i，i）i匹配$EˊTˊ（Tˊ，$）查表$Eˊ(Eˊ,$)查表$$i+i*i$i+i*i$i+i*i$+i*i$+i*i$+i*i$i*i$i*i$i*i$*i$*i$i$i$$$$T->FTˊF->iTˊ->εEˊ->+TEˊT->FTˊF->iTˊ->*FTˊF->iTˊ->εEˊ->ε2．數據結構

LL(1)語法分析程序共用到個棧，分別稱為：符號棧，語法樹棧，操作符棧和操作數棧。其中，符號棧用于進行LL(1)語法分析；其它的棧是為了在語法分析的過程中同時生成與源程序結構對應的語法樹而設。語法樹棧用于生成聲明部分和語句部分的語法樹；操作符棧和操作數棧用于生成表達式部分的語法樹。

3.構造驅動程序

構造LL(1)驅動程序的算法：(1).分析開始時，首先將標志符號#和文法開始符號S依次壓入符號棧；輸入流指針指向第一個輸入符號，即由符號棧和輸入流構成的初始格局為：(#S,a1a2...an#)然后，反復執行第2步所列的工作。(2).設在分析的某一步，符號棧及剩余的輸入流處于如下的格局(#X1X2...Xm-1Xm,aiai+1...an#)

其中，X1X2...Xm-1Xm為分析過程中所得的文法符號，此時，可視棧頂符號Xm的不可憐況，分別作如下動作：

?若Xm?VN，則以Xm及ai組成的符號對(Xm，ai)查分析表T。設T(Xm，ai)為一產生式，假設是Xm?UVW，此時將Xm從分析棧中退出，并將UVW壓入棧中，從而得到新的格局(#X1X2...Xm-1WVU,aiai+1...an#)但若T(Xm，ai)=Error，則調用出錯處理程序進行處理；

?若Xm=ai?#，則說明棧頂符號已經與當前掃描的輸入符號得到匹配，此時應將Xm（即ai）從棧中退出，并將輸入流指針向前移動一個位置。

?若Xm=ai=#，則說明輸入串已經完全得到匹配，此時即可宣告分析成功而終止分析。

其它情形，轉錯誤處理程序。程序見附錄

七、試驗結果

六、試驗小結

1、在本次試驗中，通過設計、編制、調試一個遞歸下降語法分析程序，實現對詞法分析程序所提供的單詞序列進行語法檢查和結構分析，把握LL(1)分析法的基本原理、把握LL(1)分析表的構造方法、把握LL(1)驅動程序的構造方法；

2、通過本次試驗，對LL(1)遞歸下降分析程序的構造和設計有了更為全面的認識，對LL(1)文法分析程序的實現有了進一步了解；

3、試驗輸入串以‘$’終止，才用棧的形式，依次彈出進行處理；

附錄：程序代碼：

importjava.io.IOException;importjava.util.Scanner;importjava.util.Stack;

publicclasstest3{

staticchar[]a=newchar[20];stat