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

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

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

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

5、驗(yàn)的重要性，必須通過上機(jī)實(shí)踐才能真正掌握所學(xué)的知識(shí)和技能，所以要特別強(qiáng)調(diào)實(shí)驗(yàn)也將作為考核成績(jī)的依據(jù)。實(shí)驗(yàn)成績(jī)占平時(shí)成績(jī)的20%。每次必須完成規(guī)定的實(shí)驗(yàn)內(nèi)容，并及時(shí)寫出實(shí)驗(yàn)報(bào)告。七、實(shí)驗(yàn)報(bào)告內(nèi)容：1實(shí)驗(yàn)題目、班級(jí)、學(xué)號(hào)、姓名、完成日期。2寫出數(shù)據(jù)結(jié)構(gòu)及生成的算法描述。3畫出算法流程圖。4打印出源程序代碼和給出測(cè)試的結(jié)果。5實(shí)驗(yàn)的評(píng)價(jià)、收獲與體會(huì)。寫出在調(diào)試過程中出現(xiàn)的問題和解決的措施；分析討論對(duì)策成功或失敗的原因。目錄TOC o 1-5 h z前言2目錄5 HYPERLINK l bookmark4 o Current Document 實(shí)驗(yàn)一:詞法分析設(shè)計(jì)6 HYPERLINK l bookm

6、ark30 o Current Document 實(shí)驗(yàn)二：LL(1)分析法13 HYPERLINK l bookmark66 o Current Document 實(shí)驗(yàn)三：逆波蘭式的產(chǎn)生及計(jì)算16 HYPERLINK l bookmark82 o Current Document 實(shí)驗(yàn)四：LR(1)分析法21 HYPERLINK l bookmark116 o Current Document 實(shí)驗(yàn)五：應(yīng)用DAG進(jìn)行局部?jī)?yōu)化26實(shí)驗(yàn)一詞法分析設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)：4實(shí)驗(yàn)類型：綜合實(shí)驗(yàn)要求：必修一、實(shí)驗(yàn)?zāi)康耐ㄟ^本實(shí)驗(yàn)的編程實(shí)踐，使學(xué)生了解詞法分析的任務(wù)，掌握詞法分析程序設(shè)計(jì)的原理和構(gòu)造方法，使學(xué)生對(duì)編譯

7、的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運(yùn)用。二、實(shí)驗(yàn)內(nèi)容用VC+/VB/JAVA語(yǔ)言實(shí)現(xiàn)對(duì)C語(yǔ)言子集的源程序進(jìn)行詞法分析。通過輸入源程序從左到右對(duì)字符串進(jìn)行掃描和分解，依次輸出各個(gè)單詞的內(nèi)部編碼及單詞符號(hào)自身值；若遇到錯(cuò)誤則顯示“Error”然后跳過錯(cuò)誤部分繼續(xù)顯示；同時(shí)進(jìn)行標(biāo)識(shí)符登記符號(hào)表的管理。以下是實(shí)現(xiàn)詞法分析設(shè)計(jì)的主要工作：1）從源程序文件中讀入字符。2）統(tǒng)計(jì)行數(shù)和列數(shù)用于錯(cuò)誤單詞的定位。3）刪除空格類字符，包括回車、制表符空格。（4）按拼寫單詞，并用（內(nèi)碼，屬性）二元式表示。（屬性值token的機(jī)內(nèi)（5）如果發(fā)現(xiàn)錯(cuò)誤則報(bào)告出錯(cuò)（6）根據(jù)需要是否填寫標(biāo)識(shí)符表供以

8、后各階段使用。單詞的基本分類：關(guān)鍵字：由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也稱為保留字例如if、for、while、printf；單詞種別碼為1。標(biāo)識(shí)符：用以表示各種名字，如變量名、數(shù)組名、函數(shù)名；常數(shù)：任何數(shù)值常數(shù)。如125,1,0.5,3.1416；運(yùn)算符：+、-、*、/；關(guān)系運(yùn)算符：、=、=、=、；分界符：；、，、（、）、；三、詞法分析實(shí)驗(yàn)設(shè)計(jì)思想及算法1、主程序設(shè)計(jì)考慮：程序的說明部分為各種表格和變量安排空間。在具體實(shí)現(xiàn)時(shí)，將各類單詞設(shè)計(jì)成結(jié)構(gòu)和長(zhǎng)度均相同的形式，較短的關(guān)鍵字后面補(bǔ)空。k數(shù)組關(guān)鍵字表，每個(gè)數(shù)組元素存放一個(gè)關(guān)鍵字（事先構(gòu)造好關(guān)鍵字表）。s數(shù)組存放分界符表（可事先構(gòu)造好分

9、界符表）。為了簡(jiǎn)單起見，分界符、算術(shù)運(yùn)算符和關(guān)系運(yùn)算符都放在s表中（編程時(shí)，應(yīng)建立算術(shù)運(yùn)算符表和關(guān)系運(yùn)算符表，并且各有類號(hào)），合并成一類。id和ci數(shù)組分別存放標(biāo)識(shí)符和常數(shù)。instring數(shù)組為輸入源程序的單詞緩存。outtoken記錄為輸出內(nèi)部表示緩存。還有一些為造表填表設(shè)置的變量。主程序開始后，先以人工方式輸入關(guān)鍵字，造k表；再輸入分界符等造p表。主程序的工作部分設(shè)計(jì)成便于調(diào)試的循環(huán)結(jié)構(gòu)。每個(gè)循環(huán)處理一個(gè)單詞；接收鍵盤上送來的一個(gè)單詞；調(diào)用詞法分析過程；輸出每個(gè)單詞的內(nèi)部碼。例如，把每一單詞設(shè)計(jì)成如下形式:(type,pointer)其中type指明單詞的種類，例如：Pointer指向本

10、單詞存放處的開始位置。還有一些為造表填表設(shè)置的變量。主程序開始后，先以人工方式輸入關(guān)鍵字，造k表；再輸入分界符等造p表。主程序的工作部分設(shè)計(jì)成便于調(diào)試的循環(huán)結(jié)構(gòu)。每個(gè)循環(huán)處理一個(gè)單詞；接收鍵盤上送來的一個(gè)單詞；調(diào)用詞法分析過程；輸出每個(gè)單詞的內(nèi)部碼。例如，把每一單詞設(shè)計(jì)成如下形式:(type,pointer)其中type指明單詞的種類，例如：Pointer指向本單詞存放處的開始位置。仝白開姐字母或數(shù)字非字母與數(shù)字返回（記，記在苻號(hào)表中的枝迓）或返回1探宙字-）數(shù)字矣它矣它幷它返回iium,num在常數(shù)未中的菽盤）返回（+）退回（一）返回如亠）亡返回（relop,lE返回（relop,RT退回（

11、relop,EQ返回（一）返回心二非法字苻曙2、詞法分析過程考慮根據(jù)輸入單詞的第一個(gè)字符（有時(shí)還需讀第二個(gè)字符），判斷單詞類，產(chǎn)生類號(hào)：以字符k表示關(guān)鍵字；id表示標(biāo)識(shí)符；ci表示常數(shù)；s表示分界符。對(duì)于標(biāo)識(shí)符和常數(shù)，需分別與標(biāo)識(shí)符表和常數(shù)表中已登記的元素相比較，如表中已有該元素，則記錄其在表中的位置，如未出現(xiàn)過，將標(biāo)識(shí)符按順序填入數(shù)組id中，將常數(shù)變?yōu)槎M(jìn)制形式存入數(shù)組中ci中，并記錄其在表中的位置。lexical過程中嵌有兩個(gè)小過程：一個(gè)名為getchar,其功能為從instring中按順序取出一個(gè)字符，并將其指針pint加1；另一個(gè)名為error，當(dāng)出現(xiàn)錯(cuò)誤時(shí),調(diào)用這個(gè)過程，輸出錯(cuò)誤編號(hào)

12、。要求：所有識(shí)別出的單詞都用兩個(gè)字節(jié)的等長(zhǎng)表示，稱為內(nèi)部碼。第一個(gè)字節(jié)為t，第二個(gè)字節(jié)為i。t為單詞的種類。關(guān)鍵字的t=1；分界符的t=2；算術(shù)運(yùn)算符的t=3；關(guān)系運(yùn)算符的t=4；無符號(hào)數(shù)的t=5；標(biāo)識(shí)符的t=6oi為該單詞在各自表中的指針或內(nèi)部碼值。表1為關(guān)鍵字表；表2為分界符表；表3為算術(shù)運(yùn)算符的i值；表4為關(guān)系運(yùn)算符的i值。羲1關(guān)鍵字表楹分報(bào)表喪3：算栩蝮殺秦1興駆算制指針關(guān)鍵字0do1end2for3if456then7while指針分界符0t12345i值算術(shù)運(yùn)算符10H+11H20H*21H/i值關(guān)系運(yùn)算符OOH04H=OSH四、實(shí)驗(yàn)要求1、編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使

13、用、縮進(jìn)的使用等2、將標(biāo)識(shí)符填寫的相應(yīng)符號(hào)表須提供給編譯程序的以后各階段使用3、根據(jù)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試。測(cè)試實(shí)例應(yīng)包括以下三個(gè)部分:全部合法的輸入。各種組合的非法輸入。由記號(hào)組成的句子。4、詞法分析程序設(shè)計(jì)要求輸出形式:例：輸入VC+語(yǔ)言的實(shí)例程序：Ifi=0thenn+;a=3b%）;輸出形式為：?jiǎn)卧~二元序列類型位置（行，列）（單詞種別，單詞屬性）for(1,for)關(guān)鍵字（1，1）i(6,i)標(biāo)識(shí)符（1，2）=(4，=)關(guān)系運(yùn)算符（1，3）0(5，0)常數(shù)（1，4）then(1，then)關(guān)鍵字（1，5）n(6,n)標(biāo)識(shí)符（1，6）+ErrorError（1，7）9(2,;)分界符（1，8）

14、a(6,a)標(biāo)識(shí)符（2，1）=(4,TGG-+TG|TG(3)G-T-FSS-*FS|/FSS-F-(E)F-i輸出的格式如下：I剰余輸入串I所用產(chǎn)生式動(dòng)飛初始化E-TGF0巧PUSH(GT)T-FSPDF*FUSXCSF)F-XPOP,PUSH(i)H*i#GETWESTQ)+i*i#S-tFOF+i*i#G-NTGFOF,FUSM(GT+)GETHEKTa)i*i#T-FSPOP,FUSMCSF)F-iFDF*PUSK(i)GETHEKia)S-*F5FOF.FUSMCSF*):i#GETNEXTa)1#FOF,FUSMG)#GETNESTCD#S-eFOP二I2006-6-23五、實(shí)驗(yàn)步

15、驟1、根據(jù)流程圖編寫出各個(gè)模塊的源程序代碼上機(jī)調(diào)試。2、編制好源程序后，設(shè)計(jì)若干用例對(duì)系統(tǒng)進(jìn)行全面的上機(jī)測(cè)試，并通過所設(shè)計(jì)的LL(1)分析程序；直至能夠得到完全滿意的結(jié)果。3、書寫實(shí)驗(yàn)報(bào)告；實(shí)驗(yàn)報(bào)告正文的內(nèi)容：寫出LL(1)分析法的思想及寫出符合LL(1)分析法的文法。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細(xì)的算法描述(程序執(zhí)行流程圖)。給出軟件的測(cè)試方法和測(cè)試結(jié)果。實(shí)驗(yàn)總結(jié)(設(shè)計(jì)的特點(diǎn)、不足、收獲與體會(huì))。實(shí)驗(yàn)三逆波蘭表達(dá)式的產(chǎn)生及計(jì)算實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)類型：驗(yàn)證實(shí)驗(yàn)要求：必修一、實(shí)驗(yàn)?zāi)康姆呛缶Y式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)

16、式，并計(jì)算用逆波蘭式來表示的算術(shù)表達(dá)式的值。二、實(shí)驗(yàn)內(nèi)容將非后綴式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)式，并計(jì)算用逆波蘭式來表示的算術(shù)表達(dá)式的值。三、逆波蘭表達(dá)式的產(chǎn)生及計(jì)算實(shí)驗(yàn)設(shè)計(jì)思想及算法逆波蘭式定義將運(yùn)算對(duì)象寫在前面，而把運(yùn)算符號(hào)寫在后面。用這種表示法表示的表達(dá)式也稱做后綴式。逆波蘭式的特點(diǎn)在于運(yùn)算對(duì)象順序不變，運(yùn)算符號(hào)位置反映運(yùn)算順序。產(chǎn)生逆波蘭式的前提中綴算術(shù)表達(dá)式逆波蘭式生成的設(shè)計(jì)思想及算法首先構(gòu)造一個(gè)運(yùn)算符棧，此運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則。讀入一個(gè)用中綴表示的簡(jiǎn)單算術(shù)表達(dá)式，為方便起見,設(shè)該簡(jiǎn)單算術(shù)表達(dá)式的右端多加上了優(yōu)先級(jí)最低的特殊符號(hào)“#?！睆淖?/p>

17、至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。如果不是數(shù)字，該字符則是運(yùn)算符，此時(shí)需比較優(yōu)先關(guān)系。做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。倘若不是的話，則將此運(yùn)算符棧頂?shù)倪\(yùn)算符從棧中彈出，將該字符入棧。重復(fù)上述操作(1)-(2)直至掃描完整個(gè)簡(jiǎn)單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡(jiǎn)單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡(jiǎn)單算術(shù)表達(dá)式。是是是是否是否頂運(yùn)算符與syrS優(yōu)癥相等？一挨頂是gym為-A?挨頂運(yùn)算符挨頂運(yùn)算符優(yōu)題于割鳴逆波半讓

18、豹產(chǎn)笙式渝程曆譽(yù)入一個(gè)中黠式表示簡(jiǎn)單運(yùn)算表達(dá)式#入挨對(duì)數(shù)字進(jìn)行處理,形威一個(gè)軟字串sym=當(dāng)菌輸入符號(hào)將挨頂運(yùn)算符彈出且輸出出錯(cuò)處理挨頂運(yùn)算符岀挨將向前看符號(hào)入找程序結(jié)運(yùn)用以上算法分析表達(dá)式(a+b*c)*d的過程如下:當(dāng)前符號(hào)輸入?yún)^(qū)符號(hào)棧輸出區(qū)(a+b*c)*da+b*c)*d(+*c)*d(abc)*d(+a*)*d(+abc*d(+*ab)*d(+*abc)*d(+abc*)d(abc*abc*+cl*abc*+*abc*+dabc*+d構(gòu)造一個(gè)棧，存放運(yùn)算對(duì)象。讀入一個(gè)用逆波蘭式表示的簡(jiǎn)單算術(shù)表達(dá)式自左至右掃描該簡(jiǎn)單算術(shù)表達(dá)式并判斷該字符，如果該字符是運(yùn)算對(duì)象，則將該字符入棧。若是運(yùn)算

19、符，如果此運(yùn)算符是二目運(yùn)算符，則將對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果入棧，并且將執(zhí)行該運(yùn)算的兩個(gè)運(yùn)算對(duì)象從棧頂彈出。如果該字符是一目運(yùn)算符，則對(duì)棧頂部的元素實(shí)施該運(yùn)算，將該棧頂部的元素彈出，將運(yùn)算結(jié)果入棧。重復(fù)上述操作直至掃描完整個(gè)簡(jiǎn)單算術(shù)表達(dá)式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡(jiǎn)單算術(shù)表達(dá)式的值。逆波蘭式計(jì)算的設(shè)計(jì)思想及算法四、實(shí)驗(yàn)要求1、編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等2、如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息。3、程序輸入/輸出實(shí)例：輸入以#結(jié)束的中綴表達(dá)式(包括+-*/()數(shù)字#)。例：(1)(a+b)(2)(a+b*c)(3)

20、B+(-(A)*C輸出逆波蘭表達(dá)式的格式如下：(a+b)；fab+)(a+b*c)fabc*+)(B+(-A(A)*CBA)(-)(C*+輸入中綴表達(dá)式并計(jì)算結(jié)果：a*(b+c)+(-d)#；輸出逆波蘭式:abc+*d+輸入：a=3；b=1；c=2；d=5；計(jì)算結(jié)果為:4284614B一L22=42422艮五、實(shí)驗(yàn)步驟1、根據(jù)流程圖編寫出各個(gè)模塊的源程序代碼上機(jī)調(diào)試。2、編制好源程序后，設(shè)計(jì)若干用例對(duì)系統(tǒng)進(jìn)行全面的上機(jī)測(cè)試，并通過所設(shè)計(jì)的逆波蘭式的產(chǎn)生及計(jì)算程序；直至能夠得到完全滿意的結(jié)果。3、書寫實(shí)驗(yàn)報(bào)告；實(shí)驗(yàn)報(bào)告正文的內(nèi)容：描述逆波蘭式的產(chǎn)生及計(jì)算程序的設(shè)計(jì)思想。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式

21、、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細(xì)的算法描述（程序執(zhí)行流程圖）。給出軟件的測(cè)試方法和測(cè)試結(jié)果。實(shí)驗(yàn)總結(jié)（設(shè)計(jì)的特點(diǎn)、不足、收獲與體會(huì)）。實(shí)驗(yàn)四LR(1)分析法實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)類型：驗(yàn)證實(shí)驗(yàn)要求：必修一、實(shí)驗(yàn)?zāi)康臉?gòu)造LR分析程序，利用它進(jìn)行語(yǔ)法分析，判斷給出的符號(hào)串是否為該文法識(shí)別的句子，了解LR(K)分析方法是嚴(yán)格的從左向右掃描，和自底向上的語(yǔ)法分析方法。二、實(shí)驗(yàn)內(nèi)容對(duì)下列文法，用LR(1)分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析：(1)E-E+T(2)E-ETT-T*FT-T/FF-(E)F-i三、LR(1)分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR

22、分析器總控程序都是相同的。分析表或分析函數(shù)，不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表將不同，分析表又可以分為動(dòng)作表(ACTION)和狀態(tài)轉(zhuǎn)換(GOTO)表兩個(gè)部分，它們都可用二維數(shù)組表示。分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動(dòng)作就是由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。LR分析器由三個(gè)部分組成：轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。ACTIONi,a規(guī)定了棧頂狀態(tài)為i時(shí)遇到輸入符號(hào)a應(yīng)執(zhí)行。動(dòng)作有四種可能：(1)移進(jìn)：actioni,a=Sj：狀態(tài)j移入到狀態(tài)棧，把a(bǔ)移入到文法符號(hào)棧，其中i,j表示狀態(tài)號(hào)。(2)歸約：actioni,a=rk:當(dāng)在棧

23、頂形成句柄時(shí)，則歸約為相應(yīng)的非終結(jié)符A,即文法中有A-B的產(chǎn)生式，若B的長(zhǎng)度為R(即IBI=R)，則從狀態(tài)棧和文法符號(hào)棧中自頂向下去掉R個(gè)符號(hào)，即棧指針SP減去R,并把A移入文法符號(hào)棧內(nèi)，j=GOTOi,A移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。接受acc:當(dāng)歸約到文法符號(hào)棧中只剩文法的開始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。報(bào)錯(cuò):當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入端不是該文法能接受的符號(hào)串。四、實(shí)驗(yàn)要求1、編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。2、如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息。3、程序輸入/輸出實(shí)例

24、：輸入一以#結(jié)束的符號(hào)串(包括+*/()i#)：在此位置輸入符號(hào)串輸出過程如下：步驟狀態(tài)棧符號(hào)棧剩余輸入串動(dòng)作10#i+i*i#移進(jìn)i+i*i的LR分析過程步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作說明10#i+i*i#ACTION0,i=S5,狀態(tài)5入棧205#i+i*i#r6：Ffi歸約,GOTO(0,F)=3入棧303#F+i*i#r4：TfF歸約,GOTO(0,T)=3入棧402#T+i*i#r2:EfT歸約,GOTO(0,E)=1入棧501#E+i*i#ACTION1,+=S6，狀態(tài)6入棧6016#E+i*i#ACTION6,i=S5,狀態(tài)5入棧70165#E+i*i#r6:Ffi歸約,GOTO(6

25、,F)=3入棧80163#E+F*i#r4:TfF歸約,GOTO(6,T)=9入棧90169#E+T*i#ACTION9,*=S7，狀態(tài)7入棧1001697#E+T*i#ACTION7,i=S5,狀態(tài)5入棧11016975#E+T*i#r6:Ffi歸約,GOTO(7,F)=10入棧1201697匹#E+T*F#r3:TfT*F歸約,GOTO(6,T)=9入棧130169#E+T#r1:EfE+T,GOTO(0,E)=1入棧1401#E#Acc:分析成功4、輸入符號(hào)串為非法符號(hào)串（或者為合法符號(hào)串）1、根據(jù)流程圖編寫出各個(gè)模塊的源程序代碼上機(jī)調(diào)試。2、編制好源程序后，設(shè)計(jì)若干用例對(duì)系統(tǒng)進(jìn)行全面的

26、上機(jī)測(cè)試，并通過所設(shè)計(jì)的LR(1)語(yǔ)法分析程序；直至能夠得到完全滿意的結(jié)果。3、書寫實(shí)驗(yàn)報(bào)告；實(shí)驗(yàn)報(bào)告正文的內(nèi)容：描述LR(1)語(yǔ)法分析程序的設(shè)計(jì)思想。程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的調(diào)用關(guān)系圖。詳細(xì)的算法描述(程序執(zhí)行流程圖)。給出軟件的測(cè)試方法和測(cè)試結(jié)果。實(shí)驗(yàn)總結(jié)(設(shè)計(jì)的特點(diǎn)、不足、收獲與體會(huì))。實(shí)驗(yàn)五應(yīng)用DGA進(jìn)行局部?jī)?yōu)化實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)類型：設(shè)計(jì)實(shí)驗(yàn)要求：必修一、實(shí)驗(yàn)?zāi)康氖箤W(xué)生通過本次實(shí)驗(yàn)，能夠?qū)Τ绦騼?yōu)化技術(shù)有一定的了解，掌握利于DGA進(jìn)行局部?jī)?yōu)化的方法。二、實(shí)驗(yàn)內(nèi)容對(duì)給定的四元式序列：1）：T1=A*B2）：T2=3/23）：T3=T1-T24）：X=T35）：C=56）：T4=A*B7）：C=28）：T5=18+C9）：T6=T4*T610)：Y=T6要求：構(gòu)造其相應(yīng)的DGA,并利于DGA進(jìn)行了刪除無用賦值、消除公共子表達(dá)式、合并已知量等到局部?jī)?yōu)化技術(shù)進(jìn)行優(yōu)化；再?gòu)乃玫降腄GA重建四元式序列。三、LR（1）分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法由基本塊構(gòu)造DGA的算法描述如下：for（i=0;iQli