編譯原理實驗指導(dǎo)書.

1、編譯原理實驗指導(dǎo)書別小川于楓編寫適用專業(yè)：計算機科學(xué)與應(yīng)用江蘇科技大學(xué)電子信息學(xué)院2005年 2月1前言編譯原理是計算機專業(yè)的一門核心課程，在計算機本科教學(xué)中占有十分重要的地位。由于編譯原理課程兼有很強的理論性和實踐性，并且編譯程序構(gòu)造的算法比較復(fù)雜， 因而讓學(xué)生在學(xué)習(xí)時普遍感到內(nèi)容抽象、不易理解，難易掌握。但是掌握編譯原理的基本理論和設(shè)計思想是非常重要的，尤其是將本課程的理論知識與計算機應(yīng)用中的許多領(lǐng)域緊密聯(lián)系與廣泛應(yīng)用結(jié)合。將有利于學(xué)生提高專業(yè)素質(zhì)和適應(yīng)社會多方面需要的能力。因此，通過理論授課和上機實踐，使學(xué)生對編譯的基本概念、 原理和方法有完整的和清楚的理解，并能正確地、 熟練地加以運用

2、。通過實驗逐步提高學(xué)生的編程能力和調(diào)試程序的能力以及解決實際問題的能力。使學(xué)生培養(yǎng)出扎實的軟件開發(fā)基本技能，并養(yǎng)成良好的編程風(fēng)格，為進一步學(xué)習(xí)后續(xù)課程和將來從事應(yīng)用軟件開發(fā)奠定良好的基礎(chǔ)。2實驗課時具體內(nèi)容安排如下：序號實驗名稱課時必（選）做實驗一詞法分析設(shè)計4必做實驗二LL(1) 預(yù)測分析3必作實驗三逆波蘭表達式的產(chǎn)生及計算3必作實驗四SLR(1)語法分析設(shè)計4必做實驗五應(yīng)用 DAG進行局部優(yōu)化4選做一、實驗課的性質(zhì)和目的（ 1）深刻理解程序語言編譯系統(tǒng)的結(jié)構(gòu)及各部分的功能。（ 2）熟練掌握設(shè)計和構(gòu)造程序語言編譯系統(tǒng)的基本原理和技術(shù)。（ 3）能獨立編寫清晰、工整、結(jié)論正確的編譯原理的源程序。

3、（ 4）能學(xué)會上機進行正確調(diào)試，并進行程序修改。即培養(yǎng)發(fā)現(xiàn)程序錯誤，排除錯誤的能力和經(jīng)驗。二、實驗課的基本要求：（1）掌握編譯程序的功能和結(jié)構(gòu)。3（2）掌握詞法分析器的設(shè)計方法與實現(xiàn)步驟加深對講授內(nèi)容的理解，尤其是一些語法給定，通過上機實驗幫助掌握。（3）掌握語法分析器的設(shè)計方法與實現(xiàn)步驟。（4）掌握符號表和存儲空間的組織。（5）掌握代碼優(yōu)化的作用與實現(xiàn)方法（6）掌握錯誤的診斷和校正方法。三、主要實驗教學(xué)方法實驗前，由任課教師落實實驗任務(wù)， 每個學(xué)生必須事先獨立完成好程序的設(shè)計的源程序編寫工作。 實驗課上對疑難點作集中輔導(dǎo)。 實驗過程中隨時針對不同的情況作個別啟發(fā)式輔導(dǎo)。實驗后，學(xué)生撰寫并提交

4、實驗報告。最后，由實驗教師根據(jù)每個學(xué)生的編程、 上機調(diào)試能力、 編程能力和實驗結(jié)果及實驗報告綜合評定學(xué)生的實驗成績。四、實驗的重點與難點：對詞法分析設(shè)計、 語法分析設(shè)計和中間代碼的產(chǎn)生、 代碼優(yōu)化等是本課程實踐性環(huán)節(jié)的重點和難點。五、實驗教學(xué)手段通過本課程的課內(nèi)實驗， 使學(xué)生上機編程、 調(diào)試來驗證和鞏固所學(xué)的編譯原理理論及概念， 逐步掌握詞法分析的設(shè)計方法及實現(xiàn)技術(shù)。 軟件實驗室為為每個學(xué)生提供了一臺具有 WINDOWS 98/XP/NT/2000操作系統(tǒng)的計算機和 VC+/VB/JAVA/TC 等軟件環(huán)境。六、實驗考核成績編譯原理是一門實踐性很強的課程,要求在教學(xué)過程中必須十分重視實踐性環(huán)節(jié)

5、，包括平時練習(xí)作業(yè)、記分作業(yè)、上機實驗等。尤其是要注重上機實驗的重要性，必須通過上機實踐才能真正掌握所學(xué)的知識和技能，所以要特別強調(diào)實驗也將作為考核成績的依據(jù)。 實驗成績占平時成績的20%。每次必須完成規(guī)定的實驗內(nèi)容，并及時寫出實驗報告。4七、實驗報告內(nèi)容：1實驗題目、班級、學(xué)號、姓名、完成日期。2寫出數(shù)據(jù)結(jié)構(gòu)及生成的算法描述。3畫出算法流程圖。4打印出源程序代碼和給出測試的結(jié)果。5實驗的評價、收獲與體會。寫出在調(diào)試過程中出現(xiàn)的問題和解決的措施；分析討論對策成功或失敗的原因。目錄前言2目錄5實驗一 : 詞法分析設(shè)計6實驗二： LL(1) 分析法13實驗三：逆波蘭式的產(chǎn)生及計算16實驗四： LR

6、(1)分析法 .21實驗五：應(yīng)用 DAG 進行局部優(yōu)化265實驗一詞法分析設(shè)計實驗學(xué)時： 4實驗類型：綜合實驗要求：必修一、實驗?zāi)康耐ㄟ^本實驗的編程實踐， 使學(xué)生了解詞法分析的任務(wù)， 掌握詞法分析程序設(shè)計的原理和構(gòu)造方法， 使學(xué)生對編譯的基本概念、 原理和方法有完整的和清楚的理解，并能正確地、熟練地運用。二、實驗內(nèi)容用 VC+/VB/JA VA 語言實現(xiàn)對 C 語言子集的源程序進行詞法分析。通過輸入源程序從左到右對字符串進行掃描和分解， 依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值；若遇到錯誤則顯示 “Error，”然后跳過錯誤部分繼續(xù)顯示 ；同時進行標識符登記符號表的管理。以下是實現(xiàn)詞法分析設(shè)

7、計的主要工作：6（ 1）從源程序文件中讀入字符。（ 2）統(tǒng)計行數(shù)和列數(shù)用于錯誤單詞的定位。（ 3）刪除空格類字符，包括回車、制表符空格。（ 4）按拼寫單詞，并用（內(nèi)碼，屬性）二元式表示。 (屬性值 token 的機內(nèi)表示 )（ 5）如果發(fā)現(xiàn)錯誤則報告出錯（ 6）根據(jù)需要是否填寫標識符表供以后各階段使用 。單詞的基本分類：關(guān)鍵字：由程序語言定義的具有固定意義的標識符。也稱為保留字例如if 、for、while 、printf；單詞種別碼為 1。標識符：用以表示各種名字，如變量名、數(shù)組名、函數(shù)名；常數(shù)：任何數(shù)值常數(shù)。如125, 1,0.5,3.1416；運算符： +、-、* 、/；關(guān)系運算符：&l

8、t;、<=、= 、>、>=、<>；分界符：；、，、（、）、 、 ；三、詞法分析實驗設(shè)計思想及算法1、主程序設(shè)計考慮：程序的說明部分為各種表格和變量安排空間。在具體實現(xiàn)時， 將各類單詞設(shè)計成結(jié)構(gòu)和長度均相同的形式， 較短的關(guān)鍵字后面補空。k 數(shù)組 - 關(guān)鍵字表，每個數(shù)組元素存放一個關(guān)鍵字（事先構(gòu)造好關(guān)鍵字表）。s 數(shù)組 - 存放分界符表（可事先構(gòu)造好分界符表）。為了簡單起見，分界符、算術(shù)運算符和關(guān)系運算符都放在 s 表中（編程時， 應(yīng)建立算術(shù)運算符表和關(guān)系運算符表，并且各有類號） ，合并成一類。id 和 ci 數(shù)組分別存放標識符和常數(shù)。7instring 數(shù)組為輸入

9、源程序的單詞緩存。outtoken 記錄為輸出內(nèi)部表示緩存。還有一些為造表填表設(shè)置的變量。主程序開始后， 先以人工方式輸入關(guān)鍵字，造 k 表；再輸入分界符等造p表。主程序的工作部分設(shè)計成便于調(diào)試的循環(huán)結(jié)構(gòu)。每個循環(huán)處理一個單詞；接收鍵盤上送來的一個單詞；調(diào)用詞法分析過程；輸出每個單詞的內(nèi)部碼。例如，把每一單詞設(shè)計成如下形式 : (type,pointer)其中 type 指明單詞的種類，例如：Pointer 指向本單詞存放處的開始位置。還有一些為造表填表設(shè)置的變量。主程序開始后， 先以人工方式輸入關(guān)鍵字，造 k 表；再輸入分界符等造p表。主程序的工作部分設(shè)計成便于調(diào)試的循環(huán)結(jié)構(gòu)。每個循環(huán)處理一

10、個單詞；接收鍵盤上送來的一個單詞；調(diào)用詞法分析過程；輸出每個單詞的內(nèi)部碼。例如，把每一單詞設(shè)計成如下形式:(type,pointer)其中 type 指明單詞的種類，例如：Pointer 指向本單詞存放處的開始位置。89詞法分析設(shè)計流程圖2、詞法分析過程考慮根據(jù)輸入單詞的第一個字符（有時還需讀第二個字符），判斷單詞類，產(chǎn)生類號：以字符k 表示關(guān)鍵字； id 表示標識符；ci 表示常數(shù)； s 表示分界符。對于標識符和常數(shù)，需分別與標識符表和常數(shù)表中已登記的元素相比較，如表中已有該元素， 則記錄其在表中的位置， 如未出現(xiàn)過， 將標識符按順序填入數(shù)組 id 中，將常數(shù)變?yōu)槎M制形式存入數(shù)組中ci 中

11、，并記錄其在表中的位置。lexical 過程中嵌有兩個小過程：一個名為getchar，其功能為從instring 中按順序取出一個字符， 并將其指針pint 加 1 ；另一個名為error ，當出現(xiàn)錯誤時，調(diào)用這個過程，輸出錯誤編號。要求：所有識別出的單詞都用兩個字節(jié)的等長表示，稱為內(nèi)部碼。第一個字節(jié)為t ，第二個字節(jié)為i 。 t 為單詞的種類。關(guān)鍵字的t=；分界符的 t=；算術(shù)運算符的 t=；關(guān)系運算符的 t=；無符號數(shù)的 t=；標識符的 t=。i 為該單詞在各自表中的指針或內(nèi)部碼值。 表 1 為關(guān)鍵字表； 表 2 為10分界符表；表3 為算術(shù)運算符的i 值；表4 為關(guān)系運算符的i 值。11

12、取字符和統(tǒng)計字符行列位置子程序四、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使用等。2、將標識符填寫的相應(yīng)符號表須提供給編譯程序的以后各階段使用。3、根據(jù)測試數(shù)據(jù)進行測試。測試實例應(yīng)包括以下三個部分:全部合法的輸入。各種組合的非法輸入。由記號組成的句子。4、詞法分析程序設(shè)計要求輸出形式:例：輸入 VC+ 語言的實例程序：If i=0 thenn+;a= 3b %);輸出形式為：單詞二元序列類 型位置（行，列）（單詞種別，單詞屬性）for(1,for )i( 6,i )=(4，=)關(guān)鍵字標識符關(guān)系運算符（ 1，1）（1，2）（ 1，3）120(5，0)常數(shù)（1，4）then(

13、 1，then)關(guān)鍵字（1，5）n(6,n )標識符（1，6）+ErrorError（1， 7）；(2,;)分界符（1，8）a(6,a )標識符（2，1） =(4,<= )關(guān)系運算符（2，2）3bErrorError（2，4）%ErrorError（2，4）)(2,)分界符（2，5）；(2,;)分界符（2，6）五、實驗步驟1、根據(jù)流程圖編寫出各個模塊的源程序代碼上機調(diào)試。2、 編制好源程序后， 設(shè)計若干用例對系統(tǒng)進行全面的上機測試，并通過所設(shè)計的詞法分析程序；直至能夠得到完全滿意的結(jié)果。3、書寫實驗報告；實驗報告正文的內(nèi)容：功能描述：該程序具有什么功能？程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含

14、義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細的算法描述（程序總體執(zhí)行流程圖）。給出軟件的測試方法和測試結(jié)果。實驗總結(jié)（設(shè)計的特點、不足、收獲與體會） 。13實驗二LL(1) 分析法實驗學(xué)時： 2實驗類型：綜合實驗要求：必修一、實驗?zāi)康耐ㄟ^完成預(yù)測分析法的語法分析程序，了解預(yù)測分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學(xué)生了解語法分析的功能， 掌握語法分析程序設(shè)計的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的基本方法。有利于提高學(xué)生的專業(yè)素質(zhì)，為培養(yǎng)適應(yīng)社會多方面需要的能力。二、實驗內(nèi)容根據(jù)某一文法編制調(diào)試LL （ 1 ）分析程序，以便對任意輸入的符號串進行分析。構(gòu)造預(yù)測分析表，并利用分析表和一

15、個棧來實現(xiàn)對上述程序設(shè)計語言的分析程序。分析法的功能是利用LL （1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號以及 LL （1）分析表，對輸入符號串自上而下的分析過程。三、 LL （1）分析法實驗設(shè)計思想及算法模塊結(jié)構(gòu)：（ 1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（ 2）初始化：設(shè)立 LL(1) 分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）；（ 3）控制部分：從鍵盤輸入一個表達式符號串；（ 4）利用 LL(1) 分析算法進行表達式處理：根據(jù)LL(1) 分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。14四、實驗要求1、編程時注意編程風(fēng)格：空行

16、的使用、注釋的使用、縮進的使用等。2、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。3、對下列文法，用LL （ 1）分析法對任意輸入的符號串進行分析：（ 1） E->TG（ 2） G->+TG| TG（ 3） G->（ 4） T->FS（ 5） S->*FS|/FS（ 6） S->（ 7） F->(E)（ 8） F->i輸出的格式如下：15五、實驗步驟1、根據(jù)流程圖編寫出各個模塊的源程序代碼上機調(diào)試。2、 編制好源程序后， 設(shè)計若干用例對系統(tǒng)進行全面的上機測試，并通過所設(shè)計的 LL(1) 分析程序；直至能夠得到完全滿意的結(jié)果。3、書寫實驗報告；實驗報

17、告正文的內(nèi)容：寫出 LL （1）分析法的思想及寫出符合LL （ 1）分析法的文法。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細的算法描述（程序執(zhí)行流程圖） 。給出軟件的測試方法和測試結(jié)果。實驗總結(jié)（設(shè)計的特點、不足、收獲與體會） 。16實驗三逆波蘭表達式的產(chǎn)生及計算實驗學(xué)時： 2實驗類型：驗證實驗要求：必修一、實驗?zāi)康姆呛缶Y式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表達式的值。二、實驗內(nèi)容將非后綴式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表達式的值。三、逆波蘭表達式

18、的產(chǎn)生及計算實驗設(shè)計思想及算法逆波蘭式定義將運算對象寫在前面， 而把運算符號寫在后面。 用這種表示法表示的表達式也稱做后綴式。 逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。產(chǎn)生逆波蘭式的前提中綴算術(shù)表達式逆波蘭式生成的設(shè)計思想及算法(1)首先構(gòu)造一個運算符棧，此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。(2)讀入一個用中綴表示的簡單算術(shù)表達式，為方便起見,設(shè)該簡單算術(shù)表達式的右端多加上了優(yōu)先級最低的特殊符號“#?！?3)從左至右掃描該算術(shù)表達式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。(4)如果不是數(shù)字，該字符則是運算符，此時需比較

19、優(yōu)先關(guān)系。做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。 倘若不是的話， 則將此運算符棧頂?shù)倪\算符從棧中彈出，將該字符入棧。17(5)重復(fù)上述操作 (1)-(2) 直至掃描完整個簡單算術(shù)表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達式。運用以上算法分析表達式 (a+b*c)*d 的過程如下：當前符號輸入?yún)^(qū)符號棧輸出區(qū)（a+b*c)*da+b*c)*d(+*c)*d(abc)*d(+a*)*d(+abc*d(+*ab)*d(+*abc)*d(+abc*)d(abc*

20、abc*+18d*abc*+*abc*+dabc*+d(1)構(gòu)造一個棧，存放運算對象。(2)讀入一個用逆波蘭式表示的簡單算術(shù)表達式。(3)自左至右掃描該簡單算術(shù)表達式并判斷該字符，如果該字符是運算對象，則將該字符入棧。 若是運算符， 如果此運算符是二目運算符， 則將對棧頂部的兩個運算對象進行該運算， 將運算結(jié)果入棧， 并且將執(zhí)行該運算的兩個運算對象從棧頂彈出。如果該字符是一目運算符， 則對棧頂部的元素實施該運算， 將該棧頂部的元素彈出，將運算結(jié)果入棧。(4)重復(fù)上述操作直至掃描完整個簡單算術(shù)表達式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術(shù)表達式的值。逆波蘭式計算的設(shè)計思想

21、及算法四、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使用等。192、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。3、程序輸入 /輸出實例：輸入以 #結(jié)束的中綴表達式 (包括 + - */ （）數(shù)字 #)。例： (1)（ a+b）(2)(a+b*c)(3) B+(-(A)*C輸出逆波蘭表達式的格式如下：(1) (a+b) ;ab+)(2)(a+b*c) abc*+)(3)B+(-A(A) *C BA)(-)(C*+輸入中綴表達式并計算結(jié)果：a* (b+c)+(-d)# ；輸出逆波蘭式 :abc+*d+輸入： a=3; b=1;c=2;d=5;計算結(jié)果為 :4五、實驗步驟201、

22、根據(jù)流程圖編寫出各個模塊的源程序代碼上機調(diào)試。2、 編制好源程序后， 設(shè)計若干用例對系統(tǒng)進行全面的上機測試，并通過所設(shè)計的逆波蘭式的產(chǎn)生及計算程序；直至能夠得到完全滿意的結(jié)果。3、書寫實驗報告；實驗報告正文的內(nèi)容：描述逆波蘭式的產(chǎn)生及計算程序的設(shè)計思想。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細的算法描述（程序執(zhí)行流程圖） 。給出軟件的測試方法和測試結(jié)果。實驗總結(jié)（設(shè)計的特點、不足、收獲與體會） 。21實驗四LR(1) 分析法實驗學(xué)時： 2實驗類型：驗證實驗要求：必修一、實驗?zāi)康臉?gòu)造 LR(1) 分析程序，利用它進行語法分析，判斷給出的符號串是否為該

23、文法識別的句子，了解LR （K ）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。二、實驗內(nèi)容對下列文法，用LR（ 1）分析法對任意輸入的符號串進行分析：（ 1） E- E+T（ 2）E- ET（ 3） T- T*F（ 4） T- T/F（ 5） F- (E)（ 6） F- i三、 LR （1）分析法實驗設(shè)計思想及算法(1)總控程序，也可以稱為驅(qū)動程序。對所有的LR 分析器總控程序都是相同的。(2)分析表或分析函數(shù)， 不同的文法分析表將不同， 同一個文法采用的LR 分析器不同時，分析表將不同，分析表又可以分為動作表 （ ACTION ）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)

24、組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。LR 分析器由三個部分組成：22其中 :SP 為棧指針， Si 為狀態(tài)棧， Xi 為文法符號棧。狀態(tài)轉(zhuǎn)換表用 GOTOi ，X=j 表示，規(guī)定當棧頂狀態(tài)為 i ，遇到當前文法符號為 X 時應(yīng)轉(zhuǎn)向狀態(tài) j，X 為終結(jié)符或非終結(jié)符。ACTIONi ，a規(guī)定了棧頂狀態(tài)為i 時遇到輸入符號a 應(yīng)執(zhí)行。動作有四種可能：(1)移進：actioni ，a= Sj：狀態(tài) j 移入到狀態(tài)棧，把a 移入到文法符號棧，其中i,j 表示狀態(tài)號。(2)歸約：actioni ，a=rk：當在棧頂形成句柄

25、時，則歸約為相應(yīng)的非終結(jié)符 A ，即文法中有 A- B 的產(chǎn)生式，若 B 的長度為 R(即 |B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉 R 個符號，即棧指針 SP 減去 R，并把 A 移入文法符號棧內(nèi)， j=GOTOi,A 移進狀態(tài)棧，其中 i 為修改指針后的棧頂狀態(tài)。(3)接受 acc:當歸約到文法符號棧中只剩文法的開始符號S 時，并且輸入符號串已結(jié)束即當前輸入符是 '#'，則為分析成功。(4)報錯 :當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。23四、實驗要求1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進的使

26、用等。2、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。3、程序輸入 /輸出實例：輸入一以 #結(jié)束的符號串 (包括 +*/ （） i#)：在此位置輸入符號串輸出過程如下：步驟狀態(tài)棧符號棧剩余輸入串動 作10#i+i*i#移進i+i*i 的 LR 分析過程步驟狀態(tài)棧符號棧輸入串動作說明10#i+i*i#ACTION0,i=S 5,狀態(tài) 5 入棧205#i+i*i#r6: Fi 歸約 ,GOTO(0,F)=3 入棧303#F+i*i#r4: TF 歸約 ,GOTO(0,T)=3 入棧402#T+i*i#r2: ET 歸約 ,GOTO(0,E)=1 入棧24501#E+i*i#ACTION1,+=S 6

27、,狀態(tài) 6 入棧6016#E+i*i#ACTION6,i=S5,狀態(tài) 5 入棧70165#E+i*i#r6: Fi 歸約 ,GOTO(6,F)=3 入棧80163#E+F*i#r4: TF 歸約 ,GOTO(6,T)=9 入棧90169#E+T*i#ACTION9,*=S 7,狀態(tài) 7 入棧1001697#E+T*i#ACTION7,i=S 5,狀態(tài) 5 入棧11016975#E+T*i#r :F i 歸約 ,GOTO(7,F)=10 入棧6120169710#E+T*F#3T*F歸約,GOTO(6,T)=9入棧r : T130169#E+T#1E+T,GOTO(0,E)=1入棧r :E140

28、1#E#Acc ：分析成功4、輸入符號串為非法符號串(或者為合法符號串 )算術(shù)表達式文法的LR 分析表狀A(yù)CTIONGOTO態(tài)i+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108SS6119r1S7r1r110r3r3r3r311r5r5r5r5五、實驗步驟1、根據(jù)流程圖編寫出各個模塊的源程序代碼上機調(diào)試。252、編制好源程序后，設(shè)計若干用例對系統(tǒng)進行全面的上機測試，并通過所設(shè)計的 LR(1) 語法分析程序；直至能夠得到完全滿意的結(jié)果。3、書寫實驗報告；實驗報告正文的內(nèi)容：描述 LR(1) 語法分析程

29、序的設(shè)計思想。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細的算法描述（程序執(zhí)行流程圖） 。給出軟件的測試方法和測試結(jié)果。實驗總結(jié)（設(shè)計的特點、不足、收獲與體會） 。26實驗五應(yīng)用 DGA 進行局部優(yōu)化實驗學(xué)時： 2實驗類型：設(shè)計實驗要求：必修一、實驗?zāi)康氖箤W(xué)生通過本次實驗， 能夠?qū)Τ绦騼?yōu)化技術(shù)有一定的了解，掌握利于 DGA進行局部優(yōu)化的方法。二、實驗內(nèi)容對給定的四元式序列：（1）：T1=A*B（2）：T2=3/2（3）：T3=T1-T2（4）：X=T3（5）：C=5（6）：T4=A*B（7）：C=2（8）：T5=18+C（9）：T6=T4*T6（10）： Y=T6要求：構(gòu)造其相應(yīng)的 DGA ，并利于 DGA 進行了刪除無用賦值、 消除公共子表達式、合并已知量等到局部優(yōu)化技術(shù)進行優(yōu)化；再從所得到的 DGA 重建四元式序列。三、 LR （1）分析法實驗設(shè)計思想及算法由基本塊構(gòu)造 DGA 的算法描述如下：for (i=0; i<QlistLength; i+)27取出第