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

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

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

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

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

5、　　二、對(duì)For語(yǔ)句的相關(guān)描述8</p><p>　　1 增加for語(yǔ)句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)測(cè)試程序11</b></p><p><b>　　程序測(cè)試結(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ù)書(shū) </b></p><p>　　指導(dǎo)教師（簽字）： 教研室主任（簽字）：</p><p><b>　　結(jié)構(gòu)設(shè)計(jì)說(shuō)明：</b></p><p>　　一、對(duì)pl/0語(yǔ)言的相關(guān)描述：</p><p>　　1、PlO所有子程序如下：&l

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

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

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

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

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

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

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

15、 SL</p><p>　　有了以上認(rèn)識(shí)，我們就不難明白PL/0源程序的目標(biāo)代碼是如何被解釋執(zhí)行的。以語(yǔ)句X ：= Y op Z為例，（該語(yǔ)句的目標(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)過(guò)程：base()，interpret()。其中base()的功能是根據(jù)層次差并從當(dāng)前數(shù)據(jù)區(qū)沿著靜態(tài)鏈查找，以便獲取變量實(shí)際所在的

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

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

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

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

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

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

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

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

28、;　　1）在頭文件pl0.h中增加所要求增加的符號(hào)：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 語(yǔ)句的實(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ù)或過(guò)程 如 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)//如果是變量的話(huà)，把變量入棧</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)//如果下一個(gè)讀入“=”號(hào)，則為變量初始附值</p><p><b>　　{</b></p><p>　　getsym();//第一個(gè)表達(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)//輸入第二個(gè)表達(dá)式為數(shù)字</p><p><b>　　{</b></p><p>　　cx1=cx;//cx1記錄當(dāng)前代碼段作為開(kāi)始循環(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)在要附給變量，通過(guò)偏移地址</p><p>　　gen(LOD,level - mk->

37、level, mk->address);//將此變量放入棧頂，以便與第二個(gè)表達(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);//讀取第二個(gè)表達(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);//無(wú)條件跳轉(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)測(cè)試程序：</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>　　程序測(cè)試結(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ǔ)言版) 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社</p>