課程設(shè)計(jì)---編譯原理實(shí)現(xiàn)對for語句處理的功能

1、<p><b>　　課程設(shè)計(jì)說明書</b></p><p>　　課程名稱： 編譯原理 </p><p>　　實(shí)驗(yàn)名稱：實(shí)現(xiàn)對FOR語句處理的功能 </p><p>　　實(shí)驗(yàn)性質(zhì)： 綜合性實(shí)驗(yàn) </p><p>　　院 （部）： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

2、 </p><p>　　班 級： </p><p>　　姓 名： </p><p>　　學(xué) 號： </p><p>　　指導(dǎo)教師： </p><p&

3、gt;　　完成日期： 2011/11/03 </p><p><b>　　目錄</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書3</b></p><p><b>　　結(jié)構(gòu)設(shè)計(jì)說明4</b></p><p>　　一、對pl/0語言

4、的相關(guān)描述4</p><p>　　1 PlO所有子程序4</p><p>　　2 PL/0語言的語法圖4</p><p>　　3 PL/0語言編譯器5</p><p><b>　　4 代碼執(zhí)行6</b></p><p>　　5 錯誤診斷處理8</p><p>

5、　　二、對For語句的相關(guān)描述8</p><p>　　1 增加for語句8</p><p><b>　　設(shè)計(jì)思想 8</b></p><p><b>　　設(shè)計(jì)思路8</b></p><p><b>　　2 擴(kuò)充代碼9</b></p><p>&

6、lt;b>　　實(shí)驗(yàn)測試程序11</b></p><p><b>　　程序測試結(jié)果11</b></p><p>　　課程設(shè)計(jì)實(shí)驗(yàn)心得12 </p><p><b>　　參考文獻(xiàn)12</b></p><p>　　山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院</p><p

7、><b>　　課程設(shè)計(jì)任務(wù)書 </b></p><p>　　指導(dǎo)教師（簽字）： 教研室主任（簽字）：</p><p><b>　　結(jié)構(gòu)設(shè)計(jì)說明：</b></p><p>　　一、對pl/0語言的相關(guān)描述：</p><p>　　1、PlO所有子程序如下：&l

8、t;/p><p>　　2、PL/0語言的語法圖：</p><p><b>　　程序</b></p><p><b>　　程序體</b></p><p>　　3.PL/0語言編譯器</p><p>　　本書所提供的PL/0語言編譯器的基本工作流程如下圖所示：</p>

9、<p>　　編譯器又包括：詞法分析，語法分析，語義分析和代碼生成，這里不再詳述。</p><p><b>　　代碼執(zhí)行</b></p><p>　　為了簡單起見，我們假設(shè)有一個PL/0處理機(jī)，它能夠解釋執(zhí)行PL/0編譯程序所生成的目標(biāo)代碼。這個PL/0處理機(jī)有兩類存貯、一個指令寄存器和三個地址寄存器組成。程序（目標(biāo)代碼）存貯稱為code，由編譯程序裝入，在目

10、標(biāo)代碼執(zhí)行過程中保持不變，因此它可被看成是“只讀”存貯器。數(shù)據(jù)存貯S組織成為一個棧，所有的算術(shù)運(yùn)算均對棧頂元和次棧頂元進(jìn)行（一元運(yùn)算僅作用于棧頂元），并用結(jié)果值代替原來的運(yùn)算對象。棧頂元的地址（下標(biāo)）記在棧頂寄存器T中，指令寄存器I包含著當(dāng)前正在解釋執(zhí)行的指令，程序地址寄存器P指向下一條將取出的指令。</p><p>　　PL/0的每一個過程可能包含著局部變量，因?yàn)檫@些過程可以被遞歸地調(diào)用，故在實(shí)際調(diào)用前，無法為

11、這些局部變量分配存貯地址。各個過程的數(shù)據(jù)區(qū)在存貯棧S內(nèi)順序疊起來，每個過程，除用戶定義的變量外，還應(yīng)當(dāng)有它自己的內(nèi)部信息，即調(diào)用它的程序段地址（返回地址）和它的調(diào)用者的數(shù)據(jù)區(qū)地址。在過程終止后，為了恢復(fù)原來程序的執(zhí)行，這兩個地址都是必須的。我們可將這兩個內(nèi)部值作為位于該過程數(shù)據(jù)區(qū)的內(nèi)部式隱式局部變量。我們把它們分別稱為返回地址（return address）RA和動態(tài)鏈（dynamic link）DL。動態(tài)鏈的頭，即最新分配的數(shù)據(jù)區(qū)的地

12、址，保存在某地址寄存器B內(nèi)。</p><p>　　因?yàn)閷?shí)際的存貯分配是運(yùn)行（解釋）時進(jìn)行的，編譯程序不能為其生成的代碼提供絕對地址，它只能確定變量在數(shù)據(jù)區(qū)內(nèi)的位置，因此它只能提供相對地址。為了正確地存取數(shù)據(jù)，解釋程序需將某個修正量加到相應(yīng)的數(shù)據(jù)區(qū)的基地址上去。若變量是局部于當(dāng)前正在解釋的過程，則此基地址由寄存器B給出，否則，就需要順著數(shù)據(jù)區(qū)的鏈逐層上去找。然而遺憾的是，編譯程序只能知道存取路線的表的長度，同時動態(tài)

13、鏈保存的則是過程活動的動態(tài)歷史，而這兩條存取路線并不總是一樣。</p><p>　　例如，假定有過程A，B，C，其中過程C的說明局部于過程B，而過程B的說明局部于過程A，程序運(yùn)行時，過程A調(diào)用過程B，過程B則調(diào)用過程C，過程C又調(diào)用過程B，如下圖所示：</p><p>　　從靜態(tài)的角度我們可以說A是在第一層說明的，B是在第二層說明的，C則是在第三層說明的。若在B中存取A中說明的變量a，由于

14、編譯程序只知道A，B間的靜態(tài)層差為1，如果這時沿著動態(tài)鏈下降一步，將導(dǎo)致對C的局部變量的操作。為防止這種情況發(fā)生，有必要設(shè)置第二條鏈，它以編譯程序能明了的方式將各個數(shù)據(jù)區(qū)連接起來。我們稱之為靜態(tài)鏈（static link）SL。這樣，編譯程序所生成的代碼地址是一對數(shù)，指示著靜態(tài)層差和數(shù)據(jù)區(qū)的相對修正量。下面我們給出的是過程A、B和C運(yùn)行時刻的數(shù)據(jù)區(qū)圖示：</p><p>　　DL RA

15、 SL</p><p>　　有了以上認(rèn)識，我們就不難明白PL/0源程序的目標(biāo)代碼是如何被解釋執(zhí)行的。以語句X ：= Y op Z為例，（該語句的目標(biāo)代碼序列我們己在2.4節(jié)給出），PL/0處理機(jī)解釋該指令的“步驟”如下：</p><p><b>　　step 1,</b></p><p>　　S[++T] ← S[base(level_

16、diff_Y) + addr_Y];</p><p>　　// 將變量Y的值放在棧頂</p><p><b>　　step 2,</b></p><p>　　S[++T] ← S[base(level_diff_Z) + addr_Z];</p><p>　　// 將變量Z的值放在棧頂，此棧頂元為變量Y的值</p&

17、gt;<p><b>　　step 3,</b></p><p><b>　　T--;</b></p><p>　　// 棧頂指針指向次棧頂元，即存放結(jié)果的單元</p><p><b>　　step 4,</b></p><p>　　S[T] ← S[T] op

18、S[T + 1];</p><p>　　// 變量Y和變量Z之間進(jìn)行“op”操作</p><p><b>　　step 5,</b></p><p>　　S[base(level_diff_X) + addr_X] ← S[T];</p><p>　　// 將棧頂?shù)闹荡娣诺阶兞縓所在的單元</p><

19、p><b>　　step 6,</b></p><p><b>　　T--;</b></p><p><b>　　// 棧頂指針減一</b></p><p>　　相關(guān)過程：base()，interpret()。其中base()的功能是根據(jù)層次差并從當(dāng)前數(shù)據(jù)區(qū)沿著靜態(tài)鏈查找，以便獲取變量實(shí)際所在的

20、數(shù)據(jù)區(qū)基地址；interpret()則完成各種指令的執(zhí)行工作。</p><p><b>　　錯誤診斷處理</b></p><p>　　一個編譯程序，在多數(shù)情況下，所接受的源程序正文都是有錯誤的。發(fā)現(xiàn)錯誤，并給出合適的診斷信息且繼續(xù)編譯下去從而發(fā)現(xiàn)更多的錯誤，對于編譯程序而言是完全必要的。一個好的編譯器，其特征在于：</p><p>　　任何輸入

21、序列都不會引起編譯程序的崩潰。</p><p>　　一切按語言定義為非法的結(jié)構(gòu)，都能被發(fā)現(xiàn)和標(biāo)志出來。</p><p>　　經(jīng)常出現(xiàn)的錯誤，程序員的粗心或誤解造成的錯誤能被正確地診斷出來，而不致引起進(jìn)一步的株連錯誤。</p><p>　　根據(jù)這樣的要求，我們?yōu)镻L/0編譯程序制定了以下兩條規(guī)則：</p><p>　　關(guān)鍵字規(guī)則；程序員在寫程序

22、時，可能會因?yàn)榇中亩┑粽Z句的分隔符——“;”，但他決不會漏掉算術(shù)運(yùn)算符“+”，對于編譯程序而言，不論是分隔符號類的符號還是關(guān)鍵字符號類的符號，它們都具有同等重要的地位?；谶@樣的特點(diǎn)，我們可以采用不易出錯的部分來作為恢復(fù)正常步調(diào)的標(biāo)記。每當(dāng)遇到錯誤時，分析程序跳過后面的某些部分，直到出現(xiàn)所期望的符號為止。對于程序設(shè)計(jì)語言來說，這種符號（稱為同步符號）的最好選擇就是關(guān)鍵字。PL/0的每一種構(gòu)造語句以begin、if或while開頭；每種

23、說明則以var、const或procedure開頭。每遇到錯誤時，編譯程序便可跳過一段程序，直到遇到這類符號為止，而繼續(xù)編譯。</p><p>　　鎮(zhèn)定規(guī)則；自頂向下分析的特點(diǎn)在于目標(biāo)被分成一些子目標(biāo)，分程序則用別的分析程序來處理其子目標(biāo)。鎮(zhèn)定規(guī)則是說一個分析程序發(fā)現(xiàn)了錯誤，它不應(yīng)該消極地停止前進(jìn)，僅僅向調(diào)用它的程序報(bào)告發(fā)生的錯誤；而應(yīng)該自己繼續(xù)向前掃描，找到似乎可以使正常的分析得以恢復(fù)的地方。這一規(guī)則在程序設(shè)計(jì)

24、上的含義就是任一分析程序除了正常終止外，沒有其它出口。</p><p>　　二、對For語句的相關(guān)描述：</p><p><b>　　1.增加for語句</b></p><p><b>　　設(shè)計(jì)思想：</b></p><p>　　For語句的語法分析：</p><p>　　&

25、lt;for語句>::=for(賦值語句；關(guān)系表達(dá)式) do <語句></p><p><b>　　設(shè)計(jì)思路：</b></p><p>　　主要分為兩部分模塊：一，for和；之間的賦值語句處理；二，條件語句處理和最后的語句處理。</p><p>　　首先獲取賦值號左邊的標(biāo)識符，從符號表中找到它的信息，并確認(rèn)這個標(biāo)識符確為變量名

26、。然后通過調(diào)用表達(dá)式處理過程算得賦值號右部的表達(dá)式的值并生成相應(yīng)的指令保證這個值放在運(yùn)行期的數(shù)據(jù)棧頂。最后通過前面查到的左部變量的位置信息，生成相應(yīng)的STO指令，把棧頂值存入指定的變量的空間，實(shí)現(xiàn)了賦值操作。返回函數(shù)值也是用賦值語句進(jìn)行返回值的儲存。</p><p>　　首先調(diào)用condition函數(shù)處理?xiàng)l件語句，并且把當(dāng)前condition處理生成的判斷條件操作代碼的的地址cx保存到cx1。每個循環(huán)體中，在循環(huán)

27、體結(jié)束前，設(shè)置跳回判斷操作判斷當(dāng)前條件是否跳出循環(huán)。都把本循環(huán)體結(jié)束的下一個位置保存到cx2生成跳轉(zhuǎn)，并在循環(huán)結(jié)束時用cx2更新為目前循環(huán)結(jié)束跳轉(zhuǎn)地址。</p><p>　　難點(diǎn)分析：本模塊，主要難點(diǎn)是處理循環(huán)體的跳轉(zhuǎn)，解決方法參照上點(diǎn)。不過可以參照if語句和while語句。</p><p><b>　　2 .擴(kuò)充代碼：</b></p><p>

28、;　　1）在頭文件pl0.h中增加所要求增加的符號：enum symtype中加入SYM_FOR//實(shí)現(xiàn)for循環(huán)；char* word中加入"for"關(guān)鍵字。</p><p><b>　　2）源代碼：</b></p><p>　　else if (sym == SYM_FOR)</p><p>　　{//for 語句的實(shí)現(xiàn)

29、</p><p>　　//cx1 = cx;</p><p><b>　　getsym();</b></p><p>　　i=position(id);//詞法分析中讀取的字符串名字 i</p><p><b>　　if(i==0)</b></p><p><b>

30、;　　{</b></p><p>　　error(29);</p><p><b>　　}</b></p><p>　　else//變量不能為常數(shù)或過程 如 for i=5 </p><p><b>　　{</b></p><p>　　if(table[i].ki

31、nd==SYM_CONST||table[i].kind==SYM_PROCEDURE)</p><p>　　error(30);</p><p>　　if(table[i].kind==SYM_VAR)//如果是變量的話，把變量入棧</p><p><b>　　{</b></p><p><b>　　mask

32、* mk;</b></p><p>　　mk = (mask*) &table[i];</p><p>　　gen(LOD, level - mk->level, mk->address);</p><p><b>　　}</b></p><p><b>　　getsym();&

33、lt;/b></p><p>　　if(sym==SYM_EQU)//如果下一個讀入“=”號，則為變量初始附值</p><p><b>　　{</b></p><p>　　getsym();//第一個表達(dá)式</p><p>　　set1 = createset(SYM_TO,SYM_DO, SYM_NULL);&l

34、t;/p><p>　　set = uniteset(set1, fsys);</p><p>　　expression(set);</p><p>　　destroyset(set1);</p><p>　　destroyset(set);</p><p><b>　　}</b></p>

35、<p>　　if(sym==SYM_TO)//輸入第二個表達(dá)式為數(shù)字</p><p><b>　　{</b></p><p>　　cx1=cx;//cx1記錄當(dāng)前代碼段作為開始循環(huán)位置</p><p><b>　　//將數(shù)存進(jìn)變量中</b></p><p><b>　　mask

36、* mk;</b></p><p>　　mk = (mask*) &table[i];</p><p>　　gen(STO, level - mk->level, mk->address);//棧頂?shù)膬?nèi)容給變量 如i=1，剛才的數(shù)存在棧頂，現(xiàn)在要附給變量，通過偏移地址</p><p>　　gen(LOD,level - mk->

37、level, mk->address);//將此變量放入棧頂，以便與第二個表達(dá)式進(jìn)行比較運(yùn)算</p><p><b>　　getsym();</b></p><p>　　set1 = createset(SYM_DO, SYM_NULL);</p><p>　　set = uniteset(set1, fsys);</p>

38、<p>　　expression(set);//讀取第二個表達(dá)式</p><p>　　destroyset(set1);</p><p>　　destroyset(set);</p><p>　　gen(OPR,0,9);//棧頂與次棧頂?shù)膬?nèi)容進(jìn)行運(yùn)算，結(jié)果放次棧頂,如i<10</p><p>　　cx2=cx; //cx2

39、記錄當(dāng)前代碼段，用于JPC的跳轉(zhuǎn)地址回填</p><p>　　gen(JPC,0,0);</p><p><b>　　}</b></p><p>　　if(sym==SYM_DO)</p><p><b>　　{</b></p><p><b>　　getsym()

40、;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　error(18);</p><p><b>　　}</b>&

41、lt;/p><p>　　statement(fsys);</p><p><b>　　mask* mk;</b></p><p>　　mk = (mask*) &table[i];</p><p>　　gen(LOD, level - mk->level, mk->address);//讀取變量，放入棧頂

42、，將與1相加</p><p>　　gen(LIT,0,1);//1入棧</p><p>　　gen(OPR,0,OPR_ADD);//執(zhí)行加法運(yùn)算，結(jié)果放次棧頂</p><p>　　gen(JMP,0,cx1);//無條件跳轉(zhuǎn)到cx1記錄的地址段</p><p>　　code[cx2].a=cx; //回填JPC的跳轉(zhuǎn)地址</p>

43、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　test(fsys, phi, 19);</p><p>　　} // statement</p><p>　　三 .實(shí)驗(yàn)測試程序：</p><p>　　var inte

44、ger i,d;</p><p><b>　　begin</b></p><p><b>　　d:=0;</b></p><p>　　for i=1 to 3 do</p><p><b>　　d:=d+2;</b></p><p><b>　

45、　end.</b></p><p><b>　　程序測試結(jié)果截圖：</b></p><p>　　四、課程設(shè)計(jì)實(shí)驗(yàn)心得：</p><p><b>　　參考文獻(xiàn)</b></p><p>　　1數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社</p>