語義與代碼生成

1、第七章 語義分析與代碼生成7.1 語法制導翻譯編譯程序的實質(zhì)性工作是翻譯，即為源程序生成目標代碼。為此，我們必須知道程序的含義是什么（語義分析）？應該翻譯成什么（代碼生成）？在三、四章，我們主要討論了源程序的識別，即判定一個源程序是否符合源語言的文法。在討論語法分析時曾說過，上下文無關文法不足以描述編程語言的全部語法特征。為了說明這一點，讓我們來看一個例子：VARi:integer;BEGINj:=i*iEND;如果j沒有在外層塊中說明，那么賦值語句中出現(xiàn)的j就是非法的。這是一種上下文敏感的成分。為了清楚地說明這一點，假定j是在自頂向下分析過程中由非終極符<變量>導出的，在這次推導

2、之前的句型為VARj:integer;<變量>其中,為符號串。推導后的句型為VARj:integer;j為了保證變量在使用前必須說明，需要有如下形式的規(guī)則：VAR j:integer;<變量>VAR j:integer;j而不是<變量>j即<變量>只有在一定的上下文中才可以展開成j。上下文敏感成分的分析實質(zhì)上是語法分析的內(nèi)容。但是，因為我們的語法分析是以上下文無關文法為基礎的，沒有考慮上下文敏感成分的處理，所以必須在語義分析時加以考慮。這相當于把語言的敏感成分劃歸為語言的語義范疇（盡管在概念上并非如此）。比如說在處理說明VAR j:integer

3、時，語義分析應該將這個說明所提供的信息填入符號表，即完成對符號表的插入操作；當然也需要完成其它的語義分析工作，而后在確定是否可用規(guī)則<變量>j進行推導時，就可通過對符號表的檢索操作來完成。如果符號表中有標識符j，而且j又是個變量標識符，就可以用此規(guī)則進行推導。除了敏感成分的處理之外，為了生成目標代碼，所需要完成的一切操作都屬于語義分析的范疇?？紤]如下條件語句：IF E THEN S1 ELSE S2為它生成的目標代碼應具有圖7.1的結(jié)構(gòu)（稱為它的目標結(jié)構(gòu)），其中，計算E的目標指令、S1和S2的目標指令是在處理表達式和語句時生成的，處理條件語句時所生成的指令就是“jumpf l0”和

4、“jump l1”。前者的含義為表達式E的值為false時，程序轉(zhuǎn)向l0的指令繼續(xù)執(zhí)行，后者為無條件轉(zhuǎn)到l1的指令執(zhí)行。問題在于編譯程序在處理條件語句時是從左向右進行的。因此，當要生成jumpf指令時，不知道l0的值，因為S1的目標這時尚未生成，不知道它究竟有多少條指令。在生成jump這條指令時也有同樣問題。為了解決這個問題，在生成jumpf和jump指令時，應先記錄這兩條指令本身的位置，等以后再回填它們的轉(zhuǎn)向目標。假設當前要生成的指令位置為lc，條件語句的處理算法如下：IF sy=ifsyTHENinsymbol;expression;處理表達式IF表達式類型< >boolsTH

5、ENerror (n)ENDIF;lc1:=lc;生成jumpf指令；lc:=lc+1;IF sy=thensy THENinsymbol;statement;處理語句IF sy=elsesy THENlc2:=lc;生成jump指令；lc:=lc+1;回填jumpf指令的轉(zhuǎn)向目標；insymbol; 圖7.1statement;處理語句回填jump指令的轉(zhuǎn)向目標；ELSE回填jumpf指令的轉(zhuǎn)向目標ENDIFENDIFENDIF；可以看出，除了檢查表達式類型外（敏感成分的處理），語義分析工作還包括轉(zhuǎn)向目標的回填等操作。與第四章給出的條件語句的語法分析算法相比，上述算法只是增加了如下幾個操作：

6、<op1>:IF表達式類型< >bools THENerror(n);ENDIF;lc1:=lc;生成jumpf指令；lc:=lc+1;<op2>:lc2:=lc;生成jump指令；lc:=lc+1;回填jumpf指令的轉(zhuǎn)向目標；<op3>:回填jump指令的轉(zhuǎn)向目標；<op4>:回填jumpf指令的轉(zhuǎn)向目標；這相當于說上面的處理算法是根據(jù)如下文法規(guī)則寫成的：<IF語句>IF<表達式><op1>THEN<語句>ELSE<op2><語句><op3><

7、;IF語句>IF<表達式><op1>THEN<語句><op4>即在文法規(guī)則中嵌入了相應的語義加工操作。于是，語義分析及代碼生成可以隨著語法分析的進行，通過嵌入相應的語義加工操作來完成。這種方法稱為語法制導翻譯，因為語言的文法規(guī)則確定了相應的語義分析類型及生成代碼的性質(zhì)，而且分析算法的主體控制是相應的文法規(guī)則。本章后面將結(jié)合實例討論各種典型的語言結(jié)構(gòu)的語義分析及代碼生成。7.2 目標機為了完成代碼生成工作，必須有一個提供運行環(huán)境的目標機。最直接的方法是，在哪個機器上運行的編譯程序就生成那個機器的目標代碼，或生成那個機器的匯編語言程序，然后經(jīng)過

8、匯編程序匯編成可以執(zhí)行的機器語言程序。匯編后產(chǎn)生的目標代碼可以具有絕對地址，從而可以裝到內(nèi)存的固定區(qū)域去執(zhí)行；也可以具有浮動的（相應的）地址，再由裝入程序（或者是連接裝配程序）來為地址代真（即轉(zhuǎn)換成絕對地址），即可用于執(zhí)行。無論是哪一種情況，都需要知道機器的硬件，諸如有多少個累加器、特殊寄存器、地址空間的大小等。但事實上，代碼生成也可先脫離特定的硬件環(huán)境。一種逐漸流行的方法是為一個抽象機生成代碼，然后，在特定的機器上寫一個解釋程序來解釋抽象機的指令。下面我們將介紹一個抽象機，它是專為PASCAL-S設計的，與任何特定的計算機無關，不妨稱為PASCAL-S處理機。盡管PASCAL-S處理機在硬件

9、上并不存在，但它的指令不難落實到任何特定的計算機上。PASCAL-S處理機上有如下一些寄存器和一個存貯區(qū)：ps：程序狀態(tài)字ir：指令寄存器pc：指令計數(shù)器t：棧頂寄存器b：基地址寄存器display：地址寄存器組存貯區(qū)分為程序存貯區(qū)、表格區(qū)和棧區(qū)，如圖7.2所示。程序存貯區(qū)CODE用于存放目標代碼，這部分存貯區(qū)在目標代碼的執(zhí)行期間保持不變，可看作只讀存貯（ROM）。表格區(qū)用來存放程序的靜態(tài)信息。棧區(qū)用作程序執(zhí)行的數(shù)據(jù)空間。棧區(qū)由一系列數(shù)據(jù)段組成，每個數(shù)據(jù)段包括如下內(nèi)容：圖7.2（1）標記部分。（2）參數(shù)部分（可能為空）。（3）局部量。（4）處理語句時所需要的臨時工作空間。對應PASCAL-S中

10、過程或函數(shù)的數(shù)據(jù)區(qū)，標記部分用來存放（1）函數(shù)的返回結(jié)果。（2）過程或函數(shù)的返回地址。（3）靜態(tài)鏈。（4）動態(tài)鏈。（5）過程或函數(shù)標識符在tab中的位置。其中靜態(tài)鏈與動態(tài)鏈指向棧區(qū)S的其它單元，返回地址指向代碼區(qū)CODE中的單元，第（5）項則指向表格區(qū)中的單元。PASCAL-S處理機是一個棧式的機器，它沒有傳統(tǒng)的累加器，所有對數(shù)據(jù)的操作均在棧頂進行。例如，加法指令是把棧頂兩個單元的內(nèi)容相加，并把結(jié)果留在棧頂；條件轉(zhuǎn)向指令根據(jù)棧頂單元的內(nèi)容決定是否轉(zhuǎn)向，等等。下面我們來介紹PASCAL-S機的指令系統(tǒng)。因為這個指令系統(tǒng)是根據(jù)源語言PASCAL-S的特點而設計的，所以為了深刻理解各指令的意義，需要

11、與后面將討論的目標結(jié)構(gòu)結(jié)合起來學習。每條指令的格式為操作碼操作數(shù)1操作數(shù)2當然，有些指令只有一個操作數(shù)，還有的指令沒有操作數(shù)。1.雙操作指令（4條）LODA:0xy將x（層號）和y（位移量）所確定的地址裝到棧頂。LODV:1xy根據(jù)x（層號）和y（位移量）確定單元地址，把單元的內(nèi)容裝到棧頂。LOD*：2xy根據(jù)x（層號）和y（位移量）確定存放地址的單元，把那個地址所指單元的內(nèi)容裝到棧頂。UPD：3xyx,y均為層號，根據(jù)靜態(tài)鏈更新display從第x+1層到第y層的內(nèi)容。 2.單操作指令（23條）STAD：8y調(diào)用y所確定的標準函數(shù)，自變量的值在棧頂，調(diào)用后的函數(shù)值取代原來的棧頂。表7.1中給

12、出了編號y與標準函數(shù)的對應關系。表7.1y函 數(shù)y函 數(shù)y函 數(shù)0整數(shù)abs7succ14ln1實數(shù)abs8pred15sqrt2整數(shù)sqr9round16arctan3實數(shù)sqr10trunc17eof4 odd11sin18eoln5 chr12cos6 ord13expADDL:9y將棧頂單元的內(nèi)容加y。JUMP：10y轉(zhuǎn)到y(tǒng)所指的指令繼續(xù)執(zhí)行。JUMPF:11y當棧頂單元的內(nèi)容為false時退掉棧頂單元并轉(zhuǎn)到y(tǒng)所指的指令去執(zhí)行。JUMPX:12yy為情況表的入口地址。根據(jù)棧頂單元的內(nèi)容從情況表中確定轉(zhuǎn)向目標，然后完成轉(zhuǎn)向并退掉棧頂單元。ENTRY:13yENTRY總是成對出現(xiàn)。第一條中

13、的y為情況標號的值，第二條中的y為相應的情況子句的入口地址。CASE語句的情況表由若干對ENTRY組成。FORIUP:14yFOR1UP在如下形式的循環(huán)語句中用作循環(huán)的入口條件測試。FOR i:=E1 TO E2 DOS S當執(zhí)行到FOR1UP指令時，運行時棧的狀態(tài)如圖7.3所示。圖7.3指令FOR1UP在初值小于終值時，為循環(huán)變量i賦初值，否則退掉棧頂三個單元并轉(zhuǎn)到y(tǒng)（循環(huán)出口）所指的指令繼續(xù)執(zhí)行。FOR2UP:15yFOR2UP與FOR1UP配對使用。FOR2UP用于循環(huán)的重復條件測試。如果循環(huán)變量的值小于終值，則循環(huán)變量的值加上1，并轉(zhuǎn)循環(huán)入口y；否則退掉棧頂三個單元。FOR1DOWN:

14、16yFOR2DOWN:17y這兩條指令與前兩條類似，它們用于如下形式的循環(huán)語句中：FOR i:=E1 DOWNTO E2 DO SMARK:18y這條指令為過程語句或函數(shù)調(diào)用的第一條指令，y為過程或函數(shù)標識符在符號表的位置。該指令在棧頂分配5個單元作為標記部分，并將y填入所分配的第5個單元中。CALL：19y這條指令為過程或函數(shù)調(diào)用的最后一條指令。y為btab j.psize1；由于棧頂指針t指向參數(shù)區(qū)最后一個單元，所以t-y恰為本層數(shù)據(jù)區(qū)的開始位置。在MARK與CALL之間的指令用于為形參分配存貯。CALL指令用于填寫本層display內(nèi)容（t-y）；填寫標記部分（靜態(tài)鏈，動態(tài)鏈，返回地址

15、）；為局部量分配存貯，根據(jù)標識符表中的入口地址轉(zhuǎn)過程體。INDEX1:20yINDEX:21y這兩條指令是為計算數(shù)組元素的地址而設計的，y是指向數(shù)組表的指針。它的功能是將（棧頂單元內(nèi)容數(shù)組下界）*L加到次棧頂單元的內(nèi)容上并退掉棧頂單元。在INDEX1中，L=1；在INDEX中，L=atab y.elsize。LODB：22y將一串相連單元的內(nèi)容裝到棧頂，這串單元的個數(shù)由y指定，第一個單元的地址在原來的棧頂單元中，修改棧頂指針。COPYB:23y以棧頂單元所包含的地址為開始地址，復制y個單元的內(nèi)容到次棧頂所含地址為開始的y個單元中。LODL：24y把y裝到棧頂。LODR：25yy為指向?qū)崝?shù)表的指

16、針。這條指令是將y所指向的實數(shù)裝到棧頂。FLOAT:26y將棧中從棧頂開始數(shù)的第y個單元的內(nèi)容變成浮點數(shù)。READ：27y將y所指定類型的數(shù)據(jù)讀到棧頂單元的內(nèi)容所指定的單元中，并退掉棧頂單元。WRITE0:28yy為指向串表stab的指針。這條指令是輸出從y開始的一串字符，（輸出字符的個數(shù)在棧頂單元中）并退掉棧頂單元。WRITE1:29yWRITE2:30y這兩條指令是輸出簡單變量的值，變量類型由y指定。WRITE1輸出棧頂單元的內(nèi)容并退掉棧頂單元（輸出域?qū)挒槿笔≈担?。WRITE2按棧頂單元所示域?qū)捿敵龃螚ｍ數(shù)膬?nèi)容并退掉棧頂兩個單元。 3.無操作數(shù)指令（33條）HALT：31終止目標程序執(zhí)行。

17、EXITP:32這條指令是從過程返回的指令，它將棧頂指針恢復到執(zhí)行MARK前的值；根據(jù)動態(tài)鏈恢復基地址寄存器的內(nèi)容；按返回地址完成返回。EXITF:33這條指令是從函數(shù)返回的指令，它將棧頂指針恢復到執(zhí)行MARK前的值加1（棧頂為函數(shù)結(jié)果）；根據(jù)動態(tài)鏈恢復基地址寄存器的內(nèi)容；按返回地址返回。FETCH:34以棧頂單元的內(nèi)容作地址，取這個地址所指單元的內(nèi)容回送到棧頂。NOT：35將棧頂單元的內(nèi)容求反（棧頂單元的內(nèi)容為布爾值）。NEGATE:36將棧頂單元的內(nèi)容乘上-1。WRITER:37這條指令的意義是用如下語句打印實數(shù)x：write (x:y:z)；其中z在棧頂單元中，y在次棧頂單元中，而x在棧

18、頂?shù)谌齻€單元中。STORE:38將棧頂單元的內(nèi)容存到次棧頂單元所指示的單元中。READLN:62WRITELN:63這兩條指令分別等價于PASCAL語言中的readln與writeln語句。以下指令均是在棧頂兩個單元間進行的數(shù)據(jù)操作，功能是 <次棧頂><次棧頂><運算><棧頂>并退掉棧頂單元。表7.2給出了各種運算所對應的操作碼及助記符。表7.2運 算助記符操作碼運 算助記符操作碼實數(shù)相等EQR39邏輯加OR51實數(shù)不等NEQR40邏輯與AND56實數(shù)小于LTR41實數(shù)小等LER42整數(shù)加ADDI52實數(shù)大于GTR43整數(shù)減SUBI53實數(shù)大等G

19、ER44實數(shù)加ADDR54整數(shù)相等EQI45實數(shù)減SUBR55整數(shù)不等NEQI46整數(shù)乘MULI57整數(shù)小于LTI47整數(shù)除DIVI58整數(shù)小等LEI48求余數(shù)MODI59整數(shù)大于GTI49實數(shù)乘MULR60整數(shù)大等GEI50實數(shù)除DIVR61我們之所以這樣設計目標機，一方面是因為可以避免考慮特定計算機的具體細節(jié)，另一方面是因為可以簡化編譯程序的代碼生成。然而，由于這個目標機在實際上并不存在，因此，為了使目標程序可以真正執(zhí)行，必須設法實現(xiàn)這個目標機。我們的辦法是用PASCAL語言寫一個解釋程序來執(zhí)行這個目標機的指令。目標機的各寄存器及存貯區(qū)可以用PASCAL的各種變量來模擬，比如：CONSTm

20、axlevel=7;tabsize=100;atabsize=30;btabsize=20;rconstsize=20;stabsize=600;codesize=800;stacksize=1450;TYPEobject=(konstant,vvariable,typel,prozedure,funktion);types=(notyp,ints,reals,bools,chars,arrays,records);order=PACKEDRECORDf:0.63;x:0.maxlevel;y:integerEND;VARps: (run,finish,error);程序狀態(tài)字ir : ord

21、er;指令寄存器pc: integer;指令計數(shù)器t: integer;棧頂寄存器b: integer;基地址寄存器display: ARRAY 0.maxlevel OF integer;地址寄存器組code: ARRAY 0.codesize OF order;代碼區(qū)tab: ARRAY 0.tabsize OFPACKED RECORDname:PACKED ARRAY 1.10 OF char;link:0.tabsize;obj:object;typ:types;ref:integer;normal:boolean;lev:0.maxlevel;adr:integerEND;atab

22、: ARRAY 1.atabsize OF PACKED RECORDinxtyp:types;eltyp:types;elref:integer;low:integer;hig:integer;elsize:integer;size:integerEND;btab:ARRAY 1.btabsize OF PACKED RECORDlast,lastpar:0.tabsize;psize,vsize:integerEND;rconst:ARRAY 1.rconstsize OF real;stab:PACKED ARRAY 0.stabsize OF char;s:ARRAY 1.stacks

23、ize OF 棧區(qū)RECORDCASE cn:types OFints: (I:integer);reals: (r:real);bools: (b:boolean);chars: (c:char)END;目標程序的執(zhí)行則可以用如下語句模擬：各寄存器及棧區(qū)初始化；REPEATir:=code pc;pc:=pc+1;CASE ir.f OFLODA:t:=t+1;st.i:=display ir.x+ir.y;LODV:t:=t+1;st.i:=sdisplayir.x+ir.y;LOD*:t:=t+1;st:=ssdisplayir.x+ir.y.i;UPD:h1:=ir.y; h2:=ir

24、.x; h3:=b; REPEAT displayh1:=h3; h1:=h1-1; h3:=sh3+2.i UNTIL h1=h2;STAD:CASE ir.y OF 0:st.i:=abs(st.i); 1:st.r:=abs(st.r); 16:st.r:=atan(st.r); 17:st.b:=eof(prd); 18:st.b:=eoln(prd)ENDCASE;ADDL:st.i:=st.i+ir.y;JUMP:pc:=ir.y;JUMPF:IF NOT st.b THEN pc:=ir.y ENDIF; t:=t-1;JUMPX:h1:=st.i;t:=t-1;h2:=ir.y

25、;h3:=0;REPEATIF codeh2.f<>ENTRY THENh3:=1;ps:=caschk情況語句出錯ELSEIF codeh2.y=h1 THENh3:=1;pc:=codeh2+1.yELSEh2:=h2+2ENDIFENDIFUNTIL h3<>0;FOR1UP:h1:=St-1.i;IF h1<=st.i THEN sst-2.i.i:=h1ELSE t:=t-3; pc:=ir.yENDIFFOR2UP:h2:=st-2.i; h1:=sh2.i+1; IF h1<=st.i THEN sh2.i:=h1; pc:=ir.yELSE

26、t:=t-3ENDIF;FOR1DOWN:h1:=st-1.i;IF h1>=st.i THEN sst-2.i.i:=h1ELSE pc:=ir.y; t:=t-3ENDIF;FOR2DOWN:h2:=st-2.i; h1:=sh2.i-1IF h1>=st.i THEN sh2.i:=h1; pc:=ir.yELSE t:=t-3ENDIF;MARK:h1:=btabtabir.y.re.vsize;t:=t+5;st-1.i:=h1-1;st.i:=ir.y;CALL:h1:=t-ir.y; h2:=sh1+4.i h3:=tabh2.lev; displayh3+1:=h1

27、; h4:=sh1+3.i+h1 sh1+1.i:=pc; sh1+2.i:=displayh3; sh1+3.i:=b;FOR h3:=t+1 TO h4 DO sh3.i:=0ENDFOR;b:=h1;t:=h4;pc:=tabh2.adr;INDEX1:h1:=ir.y; h2:=atabh1.low; h3:=st.i;IF h3<h2 THEN ps:=inxchk 下標越界錯ELSE IF h3>atabh1.high THEN ps:=inxchk ELSE t:=t-1; st.i:=st.i+(h3-h2) ENDIFENDIF;INDEX:h1:=ir.y; h

28、2:=atabh1.low; h3:=st.i;IF h3<h2 THEN ps:=inxchkELSE IF h3>atabh1.high THEN ps:=inxchk ELSE t:=t-1; st.i:=st.i+(h3-h2)*atabh1.elsize ENDIFENDIF;LODB:h1:=st.i;t:=t-1;h2:=ir.y+t;WHILE t<h2 DO BEGIN t:=t+1; st:=sh1 h1:=h1+1 END;COPYB:h1:=st-1.i; h2:=st.i; h3:=h1+ir.y; WHILE h1<h3 DO BEGIN s

29、h1:=sh2; h1:=h1+1; h2:=h2+1 END; t:=t-2;LODL:t:=t+1;st.i:=ir.y; LODR :t:=t+1; st.r:=rconstir.y;FLOAT:h1:=t-ir.y; sh1.r:=sh1.i;READ:IF eof(prd) THEN ps:=redchk 讀錯ELSE CASE ir.y OF ints:read(prd,sst.i.i); reals:read(prd,sst.i.r); chars:read(prd,sst.i.c); ENDCASE;t:=t-1;WRITE0:h1:=st.i; h2:=ir.y; t:=t-

30、1; REPEAT write(prr,stabh2); h1:=h1-1; h2:=h2+1UNTIL h1=0;WRITE1:CASE ir.y OFints:write(prr,st.i:fld1);reals:write(prr,st.r:fld2);bools:IF st.b THENwrite(true)ELSEwrite(false)ENDIF;chars:write(prr,chr(st.i)ENDCASE;t:=t-1;WRITE2:CASE ir.y OFints:write(prr,st-1.i:st.i);reals:write(prr.s1.r:st.i);bools

31、:IF st THENwrite(true)ELSEwrite(false)ENDIF;chars:write(prr,chr(st-1.i:st.i)ENDCASE;t:=t-2;HALT:ps:=finish; 正常停機EXITP:t:=b-1;pc:=sb+1.i;b:=sb+3.i;EXITF:t:=b;pc:=sb+1.i;b:=sb+3.i;FETCH:st:=sst.i;NOT:st.b:=NOTst.b;NEGATE:st.i:=-st.i;WRITER:write(prr,st-2.r:st-1.i);t:=t-3;STORE:sst-1.i:=st;t:=t-2;EQR :

32、t:=t-1; st.b:=st.r=st+1.r;NEQR:t:=t-1;st.b:=st.r< >st+1.r; DIVR:t=t-1;st.r:=st.r/st+1.r;READLN:readln;WRITELN:writeln; ENDCASE;UNTIL ps< >run;IF ps< >finish THEN 運行時錯誤處理；這就是解釋執(zhí)行的過程。這個解釋程序的結(jié)構(gòu)非常簡單，幾乎就是一個情況語句。事實上，高級語言的解釋程序結(jié)構(gòu)基本都是這樣。7.3 說明部分的處理說明部分給語言帶來了一定的冗余度。有些語言（如LISP）沒有說明語句；有些語言雖然有說

33、明語句（如BASIC，F(xiàn)ORTRAN），但很少需要用；而其它語言（如PASCAL，ADA），則要求程序中所使用的每個實體都必須說明，說明的作用是把程序中的實體與某個標識符聯(lián)系起來，用標識符作為這個實體的名字。通過缺省的命名規(guī)則（如FORTRAN中以I，J，K，L，M，N開頭的名字若不特別說明則是用來標識整型變量的）或根據(jù)名字所出現(xiàn)的上下文（如在SNOBOL中，TEXT=STRINGA意味著TEXT是一個字符串的名字），說明的使用是可以避免的。然而，人們并不總是希望避免使用說明，特別是當軟件開發(fā)的主要目標是生產(chǎn)可靠的軟件產(chǎn)品時更是這樣。因為說明的作用是明確地聲明程序員打算怎樣使用所說明的實體，而

34、編譯程序根據(jù)某個實體的上下文可以推斷它的使用情況。如果后者與前者不一致，編譯程序就可以檢查出來并通知給程序員，而如果不使用說明，這類錯誤就無法檢查出來。因此，需要說明部分的語言可以編出較為可靠的程序。從語義分析及代碼生成的角度看，編譯程序在處理說明部分時的主要任務是：（1）分離出說明語句中所說明的每一個實體，并把它填到符號表中。（2）在符號表中填入盡可能多的有關實體的屬性。從而，編譯程序可以根據(jù)符號表中的信息來檢查將來對某個實體的引用是否正確，并根據(jù)有關屬性為源程序生成正確的目標代碼。下面我們將結(jié)合PASCAL-S的說明部分加以討論。7.3.1 常量說明常量說明的作用在于提高程序的可讀性與修改

35、方便。例如在上一節(jié)，我們利用常量說明定義了棧區(qū)S的大?。?stacksize=1450；由此可以很容易看出， IF t>stacksize THEN是在測試棧是否溢出。如果需要修改棧區(qū)大小，只需修改常量說明，程序中所有用到stacksize的地方（如測試棧溢出的地方）就都同時得到了修改，而無需逐一進行修改。PASCAL-S中常量說明的定義為 <常量說明>CONST<標識符><op1>=<常量><op2><標識符><op1>=<常量><op2>請注意，文法中已嵌入了語義加工操作。處理

36、完標識符后，可以知道常量的名字；處理完常量后可以知道常量的類型（整型、實型、字符型等）及其值。設id定義為 id:PACKED ARRAY1.10 OF char;用來存放所拼出的標識符，c定義為c:RECORDCASE tp:types OFints,chars,bools: (i:integer);reals: (r:real)END;用來存放常量的類型及其值（字符型及布爾型常量的值是用其序號代表的），則嵌入的語義操作為：<op1>:enter(id,konstant);<op2>: tabt.typ:=c.tp;IF c.tp=reals THEN enterre

37、al (c.r); tabt.adr:=c1ELSE tabt.adr:=c.iENDIF;這兩個操作對符號表完成了一次完整的插入（見5.2節(jié)）。相應的，常量的定義為<常量><字符常量><op1>|+|-<op2><無符號數(shù)><op3>|+|-<op2><常量標識符><op4>嵌入的語義操作如下：<op1>:c.tp:=chars;c.i:=inum;字符值的序號<op2>:sign:=1;IF sy=minus THEN sign:=-1ENDIF;<op

38、3>:IF sy=intcon THEN c.tp:=ints; c.i:=sign*inumELSE IF sy=realcon THEN c.tp:=reals; c.r:=sign*rnum ENDIFENDIF;<op4>:x:=loc<id>檢索標識符表IF (x< >0) AND (tabx.obj=konstant) THEN c.tp:=tabx.typ; IF c.tp=reals THEN c.r:=sign*rconsttabx.adr ELSE IF c.tp=ints THEN c.i:=sign*tabx.adr ENDIF

39、 ENDIFENDIF;根據(jù)這兩個嵌入語義操作的文法規(guī)則，不難寫出常量說明的處理算法。7.3.2 類型說明為數(shù)據(jù)規(guī)定類型可以更自然地描述數(shù)據(jù)，因而適于對實際問題的抽象。類型實質(zhì)上代表著一組值以及可在這組值上施加的一組操作。例如，integer表示整數(shù)類型，它與集合，-2，-1，0，1，2，+，-，*，div,:=,<,有關，即說明為integer的變量i可以取第一個集合中的值，可以參與第二個集合中的運算。當然，類型可以在定義數(shù)據(jù)對象時引入，而不是非有名字不可。但利用類型說明為類型賦以名字更能反映類型概念本身，而且用有名類型來定義數(shù)據(jù)更能反映對數(shù)據(jù)的抽象。比較下面兩個說明：1.VARr1,

40、r2,r3:RECORDname:PACKED ARRAY1.20OF char;age:integer;sex: (male,female)END;2.TYPEpersonal message=RECORDname:PACKED ARRAY1.20OF char;age:integer;sex: (male,female)END;VARr1,r2,r3:personal message;第一個說明定義了r1,r2,r3為一個記錄，它們將來可存放這種記錄的值。第二個說明先定義了personal message（個人信息）為一個記錄類型，然后定義r1,r2,r3為個人信息，它們將來可用于存放有關

41、個人的信息。顯然第二個說明更自然些。PASCAL-S中，類型說明的定義為<類型說明>TYPE<標識符><op1>=<類型><op2><標識符><op1>=<類型><op2>處理完標識符后，需要將這個標識符（類型的名字）填到標識符表中，其它一些屬性如typ,ref及adr等，則需在處理完類型后回填。但處理類型的時候，可能會對標識符表完成其它的插入操作，如對記錄類型就需要將各域標識符插入標識符表中。因此，為了在標識符表中回填屬性，需要記下類型名字在標識符表中的位置。于是，嵌入的語義操作為&l

42、t;op1>:enter(id,type1); t1:=t;<op2>:tabt1.typ:=tp; tabt1.ref:=rf; tabt1.adr:=sz;其中tp,rf,sz由處理類型的過程返回。關于類型的處理，我們將在討論變量說明時一起介紹。7.3.3 變量說明變量說明是顯式地為程序中所使用的變量命名并規(guī)定屬性。由于變量在程序運行時擁有值，編譯程序必須為變量分配存貯空間，并賦予變量一個地址，且當存貯分配是動態(tài)進行時，這個地址只能是相對地址。為變量分配存貯空間的大小取決于變量的數(shù)據(jù)類型。在PASCAL-S中，由于允許過程的遞歸調(diào)用，所以存貯分配是動態(tài)進行的，編譯時所做的

43、工作是為變量分配位移量。變量說明的語法規(guī)則如下：<變量說明>VAR<標識符><op1>,<標識符><op2>:<op3><類型><op4><標識符><op1>,<標識符><op2>:<op3><類型><op4>當處理完逗號分隔的標識符時，尚不知其類型，所以無法填類型及地址屬性，必須等處理完類型后回填。因此，需要記錄這些標識符在標識符表tab中的位置（注意，這些標識符在標識符表tab中是連續(xù)存放的）。如果dx作為位移量

44、分配的計數(shù)器（它在處理一個塊的開始時被初始化），則各語義操作如下：<op1>:t0:=t;enter(id,vvariable);<op2>:enter(id,vvariable);<op3>:t1:=t;<op4>:WHILE t0<t1 DO BEGINt0:=t0+1;WITH tabt0DOtyp:=tp;ref:=rf;normal:=true;adr:=dx;dx:=dx+szENDWITHEND;其中tp、rf、sz由處理類型的過程返回?，F(xiàn)在我們來討論類型的處理。首先考慮最簡單的情況<類型><類型標識符>

45、;<op1>此時，類型的處理算法很簡單，只需執(zhí)行對符號表的檢索操作并取出相應的屬性即可。<op1>:x:=loc(id);IF(x< >0)AND(tabx.obj=typel)THENtp:=tabx.typ;rf:=tabx.ref;sz:=tabx.adr;ENDIF;其中各屬性是在處理類型說明時填入的（或預定義的）。當引入新的數(shù)組或記錄類型時，相應的算法要復雜些，它必須將這種新類型的信息填到數(shù)組表或塊表中，而且，在處理當前的新類型時，又必須遞歸地調(diào)用它本身去處理數(shù)組的基類型或記錄域的類型。下面我們先討論記錄類型的處理。<類型>RECORD

46、<op1><標識符><op2>,<標識符><op3>:<op4><類型><op5>END<op6>處理記錄時，需要將記錄的信息填到塊表中，而記錄的各個域則需填進標識符表tab，有些屬性需要回填。由于各個域標識符是局部于它所在的記錄的，所以在處理各個域之前需要執(zhí)行符號表的進層操作，而各個域處理完后要執(zhí)行符號表的復位操作。算法如下：<op1>:enterblock;level:=level+1;displaylevel:=b;offset:=0;tp:=records;rf:=b

47、;<op2>:t0:=t;enter(id,vvariable);<op3>:enter(id,vvariable);<op4>:t1:=t;調(diào)用處理類型的過程；返回eltp,elrf,elsz<op5>:WHILE t0<t1 DO BEGINt0:=t0+1;tabt0.typ:=eltp;tabt0.ref:=elrf;tabt0.normal:=true;tabt0.adr:=offset;offset:=offset+elsz;END;<op6>:sz:=offset;btabrf.vsize:=offset;btab

48、rf.psize:=0;level:=level-1;最后，我們討論數(shù)組類型的處理。<類型>ARRAY<op1><常量><op2>.<常量><op3>,<op4><常量><op2>.<常量><op3>OF<類型><op5>它要求在數(shù)組表中建立如圖7.4的串記錄并返回rf及size，其中elsizen=elsz elsz由處理類型的過程返回elsizei=sizei+1 1<=i<nsizei=(hi-li+1)*elsizei

49、1<=i<=n可以看出，這一串記錄的建立是一個遞歸的過程，相當于把給定的多維數(shù)組看作是ARRAY l1.h1 OFARRAY l2.h2 OFARRAY ln.hn OF<類型>圖7.4這樣處理的好處是使數(shù)組元素的地址計算得到了簡化。具體算法如下：<op1>:tp:=arrays;<op2>:IF low.tp=reals THEN error(n)ENDIF;low由處理常量的過程返回<op3>:IF high.tp < > low.tp THEN error(n)ENDIF;high由處理常量的過程返回enterarr

50、ay(low.tp,low.i,high.i);rf:=a;<op4>:eltp:=ARRAY;遞歸地調(diào)用處理數(shù)組的過程；<op5>:atabrf.eltyp:=eltp;atabrf.elref:=elrf;atabrf.elsize:=elsz;atabrf.size:=(high.i-low.i+1)*elsz;sz:=atabrf.size;7.3.4 子程序說明子程序使我們能利用語言所提供的基本結(jié)構(gòu)來定義更高級的操作，從而，在編譯時可以不受語言的基本結(jié)構(gòu)的束縛，盡量使用問題本身的術語來描述它的解，就好象語言是可擴充的一樣。PASCAL-S中有兩種形式的子程序過

51、程與函數(shù)。它們都是在更高的層次上為一組操作命名，函數(shù)區(qū)別于過程的主要點是它需要返回一個值。子程序說明是用來定義子程序的，包括兩個部分：一部分定義子程序與外界的接口，或稱調(diào)用約定；這部分包括子程序名、參數(shù)的數(shù)目、類型及傳遞方式（對函數(shù)來說，返回值的類型也在這個接口中提供）。另一部分定義了子程序的操作，稱為子程序體；這部分包括一些局部量的定義以及實現(xiàn)子程序操作的一些語句。子程序定義后要在調(diào)用時執(zhí)行。為了實現(xiàn)這一點，編譯程序在處理子程序說明時必須為子程序生成目標代碼，以便在調(diào)用子程序時執(zhí)行。子程序的目標結(jié)構(gòu)為入口地址：實現(xiàn)子程序操作的各語句的目標代碼返回指令此外，為了檢查對子程序的調(diào)用是否正確，處理

52、子程序說明時還必須將有關調(diào)用約定的信息保存起來。以過程說明為例，在掃描到過程標識符時，應將它登記在標識符表中，并在塊表中建立相應記錄。但有些信息在此時是無法填入的，因此要記住標識符及塊表中相應記錄的位置，以便回填。在處理參數(shù)表時，將各參數(shù)的屬性如參數(shù)類型，傳遞方式（值參或變量參數(shù)）等插入標識符表中。參數(shù)表處理完后，需要回填塊表中相應記錄的lastpar及psize域。過程的各局部量說明及定義過程操作的語句部分要由各種說明的處理過程及語句的處理過程分別處理，結(jié)果是為各種局部量分配存貯（包括在表格區(qū)的分配及位移量分配），為過程體的語句生成代碼。在此期間，需要回填塊表中相應記錄的vsize域以及標識符表中相應記錄的adr域（過程入口地址）。當整個過程說明處理完后，要生成返回指令EXITP。注意，過程的形式參數(shù)及局部量是局部于過程的，所以在處理參數(shù)表之前要執(zhí)行對符號表的進層操作，而在過程說明處理完后要執(zhí)行復位操作。嵌入語義操作的文法規(guī)則為<過程說明>PROCEDURE<標識符><op1><形參表><op2><說明部分>；<op3><復合語句>；<op4>各語義操作為<op1>:enter(