編譯原理課件：Chapter-10 語(yǔ)義分析和代碼生成

1、第十章 語(yǔ)義分析和代碼生成10.1 語(yǔ)義分析的概念10.2 棧式抽象機(jī)及其匯編指令10.3 聲明的處理10.4 表達(dá)式的處理10.5 賦值語(yǔ)句的處理10.6 控制語(yǔ)句的處理10.7 過程調(diào)用和返回假定:源語(yǔ)言： 通用的過程語(yǔ)言生成代碼：棧式抽象機(jī)的（偽）匯編程序翻譯方法：自頂向下的屬性翻譯語(yǔ)法成分翻譯子程序參數(shù)設(shè)置：繼承屬性為值形參綜合屬性為變量形參語(yǔ)法成分翻譯動(dòng)作子程序參數(shù)設(shè)置：繼承屬性為值形參綜合屬性不設(shè)形參，而作為動(dòng)作子程序的返回值（由RETURN語(yǔ)句返回）5.2.3 (1) L-屬性翻譯文法（L-ATG） 這是屬性翻譯文法中較簡(jiǎn)單的一種。其輸入文法要求是LL(1)文法，可用自頂向下分析

2、構(gòu)造分析器。在分析過程中可進(jìn)行屬性求值。定義5.2: L-屬性翻譯文法是帶有下列說明的翻譯文法： 1. 文法中的終結(jié)符，非終結(jié)符及動(dòng)作符號(hào)都帶有屬性，且每個(gè)屬性都有一個(gè)值域 2. 非終結(jié)符及動(dòng)作符號(hào)的屬性可分為繼承屬性和綜合屬性 3. 開始符號(hào)的繼承屬性具有指定的初始值 4. 輸入符號(hào)（終結(jié)符號(hào)）的每個(gè)綜合屬性具有指定的初始值 5.屬性值的求值規(guī)則： （略）10.1 語(yǔ)義分析的概念1、上下文有關(guān)分析：即標(biāo)識(shí)符的作用域2、類型的一致性檢查3、語(yǔ)義處理： 聲明語(yǔ)句：其語(yǔ)義是聲明變量的類型等，并不要求做其他的操作。 語(yǔ)義分析程序的工作是填符號(hào)表，登錄名字的特征信息，分配存儲(chǔ)。 執(zhí)行語(yǔ)句：語(yǔ)義是要做某

3、種操作。 語(yǔ)義處理的任務(wù)：按某種操作的目標(biāo)結(jié)構(gòu)生成中間代碼或目標(biāo)代碼。 用上下文無關(guān)文法只能描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)，而不能描述其語(yǔ)義！例如，對(duì)于有嵌套子程序結(jié)構(gòu)的程序段：BEGIN BEGIN INT I I END I ENDBEGIN BEGIN INT I I END I END若存在文法規(guī)則：VAR := I 則BEGIN BEGIN INT I VAR END I END此時(shí)內(nèi)層子程序可歸約為 BEGIN I . END BEGIN VAR . END V*且不包含變量 I 的聲明文法規(guī)則應(yīng)改為：INT I VAR := INT I I第一次I的歸約正確第二次I的歸約錯(cuò)誤上下文相關(guān)文法然

4、而上下文有關(guān)文法不僅構(gòu)造困難，而且其分析器十分復(fù)雜，分析效率又低，顯然不實(shí)用。處理這種上下文有關(guān)問題的一般方法使用專門的語(yǔ)義動(dòng)作來補(bǔ)充上下文無關(guān)分析器的動(dòng)作，即借助語(yǔ)義分析來解決。通常我們把與語(yǔ)義相關(guān)的上下文有關(guān)信息填入符號(hào)表中，并通過查符號(hào)表中的這些信息來分析程序的語(yǔ)義是否正確。10.2 棧式抽象機(jī)及其匯編指令棧式抽象機(jī)：由三個(gè)存儲(chǔ)器、一個(gè)指令寄存器 和多個(gè)地址寄存器組成。存儲(chǔ)器： 數(shù)據(jù)存儲(chǔ)器 （存放AR的運(yùn)行棧） 操作存儲(chǔ)器 （操作數(shù)棧） 指令存儲(chǔ)器計(jì)算機(jī)的存儲(chǔ)大致情況如下：Pcode指令PC程序指令存儲(chǔ)器SPBP當(dāng)前模塊活動(dòng)記錄(數(shù)據(jù)段)棧底運(yùn)行棧堆常量區(qū)（堆底）NP程序數(shù)據(jù)存儲(chǔ)器例：

5、a := b+c;LDA (a)LOD bLOD cADDSTN指令名稱操作碼地址指令意義加載指令LODD將D的內(nèi)容棧頂立即加載LDC常量常量棧頂?shù)刂芳虞dLDA(D)變量D的地址棧頂存儲(chǔ)STOD棧頂內(nèi)容存入變量D 間接存STD將棧頂內(nèi)容D所指單元間接存STN將棧頂內(nèi)容次棧頂所指單元加ADD棧頂和次棧頂內(nèi)容相加，結(jié)果留棧頂減SUB次棧頂內(nèi)容減棧頂內(nèi)容乘MUL棧式抽象機(jī)指令代碼如下：指令名稱操作碼地址指令意義等于比較EQL不等比較NEQ大于比較GRT次棧頂內(nèi)容與棧頂內(nèi)容比較，結(jié)果（1或0）留棧頂小于比較LES大于等于GTE小于等于LSE邏輯與AND邏輯或ORL邏輯非NOT轉(zhuǎn)子JSRlab分配ALC

6、M在運(yùn)行棧頂分配大小為M的活動(dòng)記錄區(qū)10.3 聲明的處理語(yǔ)義的表示：給出語(yǔ)言結(jié)構(gòu)的屬性翻譯文法來說明其語(yǔ)義及語(yǔ)義動(dòng)作，并把這些語(yǔ)義動(dòng)作插入屬性翻譯文法產(chǎn)生式中的適當(dāng)位置。 編譯程序處理聲明語(yǔ)句要完成的主要任務(wù)為：編譯程序的任務(wù)：1) 分離出每一個(gè)被聲明的實(shí)體，并把它們的名字填入符號(hào)表中2) 把被聲明實(shí)體的有關(guān)特性信息盡可能多地填入符號(hào)表中 對(duì)于已聲明的實(shí)體，在處理對(duì)該實(shí)體的引用時(shí)要做的事情：1) 檢查對(duì)所聲明的實(shí)體引用（種類、類型等）是否正確2) 根據(jù)實(shí)體的特征信息，例如類型、所分配的目標(biāo)代碼地址（可能為數(shù)據(jù)區(qū)單元地址，或目標(biāo)程序入口地址）生成相應(yīng)的目標(biāo)代碼也就是說，處理聲明語(yǔ)句主要是做填表工

7、作（填表前先得查表，檢查是否重名）。 處理對(duì)已聲明的實(shí)體的引用時(shí)主要是做查表工作。10.3 聲明的處理語(yǔ)義的表示：給出語(yǔ)言結(jié)構(gòu)的屬性翻譯文法來說明其語(yǔ)義及語(yǔ)義動(dòng)作，并把這些語(yǔ)義動(dòng)作插入屬性翻譯文法產(chǎn)生式中的適當(dāng)位置。編譯程序的任務(wù)：聲明的兩種方式： (1) 類型說明符放在變量的前面。如C語(yǔ)言： int a; 在填表時(shí)已知類型和a的值（名字），直接填入符號(hào)表。 (2) 類型說明放符在變量的后面。如：Pascal，PL/1，Ada等，需要返填。 如PL/1聲明語(yǔ)句：DECLARE( X, Y(N), YTOTAL) FLOAT; 聲明有常量聲明，變量（包括簡(jiǎn)單變量，數(shù)組變量和記錄變量等）和過程（函

8、數(shù)）聲明等，這里主要討論常量聲明和簡(jiǎn)單變量、數(shù)組聲明的處理。該聲明語(yǔ)句的輸入文法為：DECLARE dec_onx ( ) t fix_upx, t n name_defn n| n , name_defn n tFIXED t | FLOAT t | CHAR tDECLARE () | , FIXED | FLOAT | CHAR 其屬性翻譯文法為：DECLARE( X, Y(N), YTOTAL) FLOAT;dec_onxfix_upx, t name_defn nname_defn n name_defn n是將由各實(shí)體名所得的n繼承屬性值，依次填入從x開始的符號(hào)表中。注：顯然應(yīng)有內(nèi)

9、部計(jì)數(shù)器或內(nèi)部指針，指向下一個(gè)該填的符號(hào)表項(xiàng)。fix_upx, t 是將類型信息t 和相應(yīng)的數(shù)據(jù)存儲(chǔ)區(qū)分配地址填入從 x 位置開始的符號(hào)表中。（反填）當(dāng)然，如果聲明語(yǔ)句中，類型說明符放在頭上，就無需“反填”處理了。動(dòng)作程序dec_onx 是把符號(hào)表當(dāng)前可用表項(xiàng)的入口地址（指向符號(hào)表入口的指針，或稱 表項(xiàng)下標(biāo)值）賦給屬性變量x 。DECLARE dec_onx ( ) t fix_upx, t n name_defn n| n , name_defn n tFIXED t | FLOAT t | CHAR tDECLARE( X, Y(N), YTOTAL) FLOAT;10.3.1 常量類型聲

10、明處理常量標(biāo)識(shí)符通常被看作是全局名。常量聲明的ATG如下： constant t n := c, sinsert t，n，c，s ； t real t |integer t |string t c, s c, s |c, s |c, s 由該文法產(chǎn)生的一個(gè)聲明實(shí)例為： constant integer SYMBSIZE := 1024;翻譯處理過程為： 先識(shí)別類型（integer），將它賦給屬性t；然后識(shí)別常量名字（SYMBSIZE), 將它賦給屬性n；最后識(shí)別常量表達(dá)式，并將其值賦給c，其類型賦給屬性s 。 insert 的功能是： 檢查聲明的類型t 和常量表達(dá)式的類型s 是否一致，若 不一

11、致，則輸出錯(cuò)誤信息； 把名字n，類型t 和常量表達(dá)式的值c 填入全局符號(hào)表中。 constant t n :=c, s insert t，n，c，s ；由該文法產(chǎn)生的一個(gè)聲明實(shí)例為： constant integer SYMBSIZE := 1024;10.3.2 簡(jiǎn)單變量聲明處理ATG文法： t , i n svardef t, i, n allocsvi ；t, i realt, i |integert, i |charactert (i ) | logicalt, i 簡(jiǎn)單變量聲明的例子： real x ; integer j; character (20) s ;其中 n: 變量名 t

12、: 類型值 i: 該類型變量所需 數(shù)據(jù)空間的大小allocsv 和 svardef 可以合并 t , i n svardef t, i, n allocsvi t, i real t, i |integer t, i |character t (i ) | logical t, i procedure svardef( t, i, n ); j := tableinsert ( n, t, i ); /將有關(guān)信息填入符號(hào)表 if j = 0 /填表時(shí)要檢查是否重名 then errmsg ( duplident , statementno); else if j = -1 /符號(hào)表已滿 the

13、n errmsg( tblovflow, statementno); abort; /符號(hào)表溢出，編譯失敗，終止。end svardef;procedure allocsv( i ); codeptr := codeptr + i ; /codeptr 為地址區(qū)指針end allocsv；svardef動(dòng)作符號(hào)是把n，i 和t 填入符號(hào)表中allocsvi 為簡(jiǎn)單變量分配數(shù)據(jù)空間對(duì)于變長(zhǎng)字符串（或其它大小可變的數(shù)據(jù)實(shí)體），往往需要采用動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間的辦法把可變長(zhǎng)實(shí)體存儲(chǔ)在堆中。我們可通過指向存放該實(shí)體數(shù)據(jù)區(qū)的指針來引用該實(shí)體，有時(shí)還應(yīng)得到該實(shí)體存儲(chǔ)空間的大小信息，并一起填入符號(hào)表內(nèi)。即可變長(zhǎng)

14、實(shí)體存儲(chǔ)在堆中，而其指針存放在符號(hào)表中。10.3.3 數(shù)組變量聲明的處理對(duì)于靜態(tài)數(shù)組，即數(shù)組的大小在編譯時(shí)是已知的，編譯程序在處理數(shù)組聲明時(shí)，可建立一個(gè)數(shù)組模板（又稱為數(shù)組信息向量）以便以后的程序中引用該數(shù)組元素時(shí)，可按照該模板提供的信息，計(jì)算數(shù)組元素(下標(biāo)變量）的存儲(chǔ)地址。對(duì)于動(dòng)態(tài)數(shù)組，其大小只有在運(yùn)行時(shí)才能最后確定。我們?cè)诰幾g時(shí)僅為該模板分配一個(gè)空間，而模板本身的內(nèi)容將在運(yùn)行時(shí)才能填入。 大部分程序設(shè)計(jì)語(yǔ)言，數(shù)組元素是按行（優(yōu)先）存放在存儲(chǔ)器中的，如聲明數(shù)組 array B ( N, -2: 1 )char ;B:* FORTRAN 例外！它按列（優(yōu)先）存放數(shù)組元素實(shí)際數(shù)組B各元素的存儲(chǔ)次

15、序?yàn)椋篖OC是數(shù)組首地址(該數(shù)組第一個(gè)元素的地址）LOCarray B ( N, -2: 1 ) char ;a）n維數(shù)組的地址計(jì)算公式 設(shè)數(shù)組的維數(shù)為n， 各維的下界和上界為L(zhǎng)(i)和U(i) 例如， 上例二維數(shù)組B L(1) = 1 (隱含值）, U(1) = N L(2) = -2 , U(2) = 1 還假定n維數(shù)組元素的下標(biāo)為V(1), V(2), V(n）則該數(shù)組元素的地址計(jì)算公式為：其中P(i) = 1 當(dāng)i n時(shí) 當(dāng)1 in 時(shí)注：E為數(shù)組元素 大?。ㄗ止?jié)數(shù)）U(2)L(2)L(1)U(1)U(3)L(3)v2v3v1A(v1,v2,v3)注：E為數(shù)組元素 大小（字節(jié)數(shù)） V(

16、1)-L(1) *U(2)-L(2)+1*U(3)-L(3)+1*E+ V(2)-L(2) *U(3)-L(3)+1*E+ V(3)-L(3) *1*EP(2)P(3)P(1)其中P(i) = 1 當(dāng)i n時(shí) 當(dāng)1 in 時(shí)若令(不變部分)則地址 RC為數(shù)組元素地址計(jì)算公式中的不變部分。因?yàn)橹灰罃?shù)組的維數(shù)和每一維的上下界值，便可求得RC值。以前面所舉的二維數(shù)組B為例，若N = 3則 P(1) = U(2) - L(2) +1 = 1- (-2)+1 = 4P(2) = 1RC = = - 14 (-2)1E= -2E因此， 若有數(shù)組元素B( 2 , 1 ), 則它的地址為： = LOC 2

17、E+(24+11)ELOC + 7E其中P(i) = 1 當(dāng)i n時(shí) 當(dāng)1 in 時(shí)array B ( N, -2: 1 ) char ;b) 數(shù)組信息向量表（模板）功能：1、用于計(jì)算下標(biāo)變量地址 2、檢查下標(biāo)是否越界U(n)L(n)P(n).U(1)L(1)P(1)nRC上界下界計(jì)算地址用常量 大?。?n + 2注：1、數(shù)組模板所需的空間大小取決于數(shù)組的維數(shù)，即3n+2 無論是常界或變界數(shù)組，在編譯時(shí)就能確定數(shù)組模板的大小 2、常界數(shù)組，在編譯時(shí)就可造信息向量表；而變界數(shù)組信息向量表要在目標(biāo)程序運(yùn)行時(shí)才能造。編譯程序要生成相應(yīng)的指令一般形式：1-213142-2以前面所舉的二維數(shù)組B為例，若

18、N = 3 P(1) = U(2) - L(2) +1 = 1- (-2)+1 = 4P(2) = 1RC = = - 14 (-2)1= -2array B ( N, -2: 1 ) char ;數(shù)組信息向量表U(2)-上界L(2)-下界P(2)-計(jì)算地址常量U(1)-上界L(1)-下界P(1)-計(jì)算地址常量n-維數(shù)RC數(shù)組模板的一般形式如下左圖所示，而對(duì)于數(shù)組B的模板如下右圖所示：1-213142-2U(n)L(n)P(n)U(1)L(1)P(1)nRC.數(shù)組信息向量表array B (3, -2: 1 ) char ;數(shù)組模板數(shù)組聲明的ATG文法： array k initjn ( j

19、) t symbinsertj, n, t,k j dimen#j | , j dimen#j u banndsu| l : lowerbndl u upperbndu, larray B ( N, -2: 1 ) char ;p:= p+2; j := 0; /*維數(shù)計(jì)數(shù)器*/RCnP(1)L(1)U(1).P(n)L(n)U(n)運(yùn)行棧指針p活動(dòng)記錄數(shù)組信息表2) dimen#j : j := j + 1, 即統(tǒng)計(jì)維數(shù)1) 動(dòng)作程序 init 的功能為在分配給數(shù)組模板區(qū)中保留兩個(gè)存 儲(chǔ)單元，用來放 RC 和 n，并將維數(shù)計(jì)數(shù)器 j 清0。實(shí)際P(i)計(jì)算公式可利用 P(i) U(i+ 1)

20、 - L(i +1) +1P(i+1)4) lowerbnd 把 l = L(i ) upperbnd 把 u = U(i ), 并計(jì)算 P(i )5) 最后的動(dòng)作程序symbinsert是把數(shù)組名n，數(shù)組維數(shù) j 和數(shù)組元素類型 t 及數(shù)組標(biāo)志 k 填入符號(hào)表中 ；為數(shù)組分配存儲(chǔ)空間3) bannds將省略下界表達(dá)式情況的u = U(i), 但應(yīng)把相應(yīng)的L(i) 置成隱含值1, 然后計(jì)算P(i )注：由于P(i)的計(jì)算要依賴于P(i +1 ), 所以實(shí)際P(i)的值是反填的P(i) = 1 當(dāng)i n 時(shí)當(dāng)1 in 時(shí) u banndsu | l : lowerbndl u upperbndu

21、, l array k initjn ( j ) t symbinsertj, n, t,k4) lowerbndl 生成將 l = L(i) 的代碼 upperbndu 生成 把 u = U(i)的代碼, 生成計(jì)算 P(i) 的代碼； 生成將P(i ) 的值送模板區(qū)的代碼；5) symbinsertj, n, t,k a) 把n, j, t, ,k 填入符號(hào)表中 b) 生成調(diào)用運(yùn)行子程序代碼（計(jì)算RC, 并將計(jì)算結(jié)果和數(shù)組 名一起存入模板區(qū)；計(jì)算數(shù)組所需數(shù)據(jù)區(qū)大小，為數(shù)組分配存儲(chǔ)空間，并將頭地址填入符號(hào)表。）對(duì)于變界數(shù)組：記錄、過程的聲明-自學(xué)作業(yè)：試設(shè)計(jì)Pascal記錄變量（記錄中無大小可

22、變部分）的屬性翻譯文法，并構(gòu)造相應(yīng)的語(yǔ)義動(dòng)作程序。10.4 表達(dá)式的處理 分析表達(dá)式的主要目的是生成計(jì)算該表達(dá)式值的代碼。通常的做法是把表達(dá)式中的操作數(shù)裝載（LOAD）到操作數(shù)棧（或運(yùn)行棧）棧頂單元或某個(gè)寄存器中，然后執(zhí)行表達(dá)式所指定的操作，而操作的結(jié)果保留在棧頂或寄存器中。 注：操作數(shù)棧即操作棧，它可以和前述的運(yùn)行棧 （動(dòng)態(tài)存儲(chǔ)分配）合而為一，也可單獨(dú)設(shè)棧。本章中所指的操作數(shù)棧實(shí)際應(yīng)與動(dòng)態(tài)運(yùn)行（存儲(chǔ)分配）棧分開。請(qǐng)看下面的整型表達(dá)式ATG文法：有關(guān)的語(yǔ)義動(dòng)作為：procedure add; emit(ADD);end;procedure push(j); integer j; emit(LO

23、D, symbtbl (j).objaddr);end;procedure pushi(i); /*壓入整數(shù)*/ integer i; emit(LDC, i) ;end;. | +add5. | - sub6.7. 8. | *mul9. | /div10.nlookupnj pushj11. | ipushii12. | ()procedure lookup(n); string n; integer j; j:= symblookup( n); /*名字n表項(xiàng)在符號(hào)表中的位置*/ if j 1 then /*error*/ else return (j);end;proce

24、dure mul; emit(MUL); end; = = = = nlpnjphj = nlpnjphj = nlpnjphj +add = nlpnjphj +add = nlpnjphj +nlpnjphjadd = nlpnjphj +nlpnjphj*muladd = nlpnjphj +nlpnjphj*iphiimul add = nlpnjphj +nlpnjphj*iphiimuladd = nlpnjphj +nlpnjphj*iphiimuladd對(duì)于輸入表達(dá)式 x + y * 3：. | +add5. | - sub6.7. 8. | *mul9. | /

25、div10.nlookupnj pushj11. | ipushii12. | () ADDMULLDC, 3LOD, yLOD, x = = = = nlpnjphj = nlpnjphj = nlpnjphj +add = nlpnjphj +add = nlpnjphj +nlpnjphjadd = nlpnjphj +nlpnjphj*muladd = nlpnjphj +nlpnjphj*iphiimul add = nlpnjphj +nlpnjphj*iphiimuladd = nlpnjphj +nlpnjphj*iphiimuladd ADDMULLDC, 3LOD, y對(duì)于

26、輸入表達(dá)式 x + y * 3：. | +add5. | - sub6.7. 8. | *mul9. | /div10.nlookupnj pushj11. | ipushii12. | ()LOD, x上面所述的表達(dá)式處理實(shí)際上忽略了出現(xiàn)在表達(dá)式中各操作數(shù)類型的不同，且變量也僅限于簡(jiǎn)單變量。下面假定表達(dá)式中允許整型和實(shí)型混合運(yùn)算，并允許在 表達(dá)式中出現(xiàn)下標(biāo)變量（數(shù)組元素）。因此應(yīng)該增加有關(guān)類型一致性檢查和類型轉(zhuǎn)換的語(yǔ)義動(dòng)作，也要相應(yīng)產(chǎn)生計(jì)算下標(biāo)變量地址和取下標(biāo)變量值的有關(guān)指令。 t t s s t s u echo s u | + t add t, s v v u | - t

27、sub t, s v v uu s s u s u echo s u | *t mul t, s v v u | /t div t, s v v uti typeit | i pushii t | r pushir tj n lookup n j push j | n lookup n j (template j k k, j) k, j t offset k, t i i, j k, j checkdim k, j | , t offset k, t i i, j t t u:= s結(jié)果類型返回變量類型符號(hào)表入口維數(shù)類型返回維數(shù)i :k+維數(shù)檢查生成指令 越界檢查，計(jì)算地址公式中的可變部分

28、加載數(shù)組模板地址 維數(shù)計(jì)數(shù)k初值為0語(yǔ)義動(dòng)作add等應(yīng)作相應(yīng)改變：procedure add( t, s); string t, s; if t = real and s = integer then begin emit( CVN); /*次棧頂轉(zhuǎn)為實(shí)數(shù)*/ emit( ADD); return ( real); end; if t = integer and s = real then begin emit( CNV); /*棧頂轉(zhuǎn)為實(shí)數(shù)*/ emit( ADD); return ( real); end; emit( ADD); return ( t);end;procedure tem

29、plate(j); integer j; emit( TMP, symbtbl (j). objaddr); k:= 0; /*維數(shù)計(jì)數(shù)器初始化*/ return(k);end;procedure offset( k, t ); integer k; string t; k := k+1; if t integer then errmsg(數(shù)組下標(biāo)應(yīng)為整 型表達(dá)式, statno); else emit( OFS, k ); return (k);end; procedure checkdim( k, j); integer k, j; if k symbtbl (j).dim then er

30、rmsg(數(shù)組維數(shù)與 聲明不匹配, statno); else begin emit( ARR); emit( DER); end;end; 棧頂次棧頂越界檢查，計(jì)算地址公式中的可變部分模板入口地址生成數(shù)組元素地址加載數(shù)組元素內(nèi)容過程template發(fā)送一條目標(biāo)機(jī)指令TMP, 該指令把數(shù)組的模板地址加載到操作數(shù)棧頂，并將下標(biāo)（維數(shù)）計(jì)數(shù)器k清0。 offset過程要確保每一個(gè)下標(biāo)都是整型，而且發(fā)送一條OFS指令，該指令在運(yùn)行時(shí)要完成以下功能：1. 檢查第k個(gè)下標(biāo)值是否在棧頂并是否在上下界范圍內(nèi)2.使用下列遞歸函數(shù)，計(jì)算地址計(jì)算公式中可變部分： VP(0) = 0; VP(k) = VP(k-1

31、) + V(k) *P(k) 1kn該VP函數(shù)是由計(jì)算公式 導(dǎo)出的 下面以數(shù)組元素B(2,1)為例，說明（a）執(zhí)行TMP指令并形成第一個(gè)下標(biāo)值的情況（b）執(zhí)行第一 個(gè)OFS指令并形成第二個(gè)下標(biāo)值的情況（c）執(zhí)行第二個(gè)OFS指令及ARR指令后的情況 （d）執(zhí)行DER指令，最后在棧頂形成下標(biāo)變量B(2,1)的值(a)B(2,1)值.數(shù)據(jù)棧(b)(c)(d)12*4=8locB.V(2)VP(1)棧底18+1=9locB.V(2)VP(2)棧底 LOC+(-2)+9 =LOC+720locB.V(1)VP(0)棧底操作數(shù)棧1-213142-2.B的模板U(2)L(2)P(2)U(1)L(1)P(1)

32、#dimRClocB 處理邏輯表達(dá)式(關(guān)系表達(dá)式）的方法與處理算術(shù)表達(dá)式的方式基本相同。下面是邏輯表達(dá)式( x =y & yz | z x)生成的指令序列：LOD, ( ll, on )xLOD, ( ll, on )yEQLLOD, ( ll, on )yLOD, ( ll, on )zNEQANDLOD, ( ll, on )zLOD, ( ll, on )xLESORLNOT10.5 賦值語(yǔ)句的處理X:= Y+X;setL LLt:= resetLLsstorint, s ;procedure setL; return (true );end;指示取變量地址LDA ( ll, on )x

33、LOD ( ll, on )yLOD ( ll, on )xADDSTN置“左值 ”特征L為真置“左值 ”特征L為假表達(dá)式類型被賦變量類型類型轉(zhuǎn)換，生成STN指令setL是設(shè)置變量為“左值”（被賦變量），即將屬性L置trueresetL是設(shè)置變量為非被賦變量，即把屬性L置成falseprocedure resetL; return (false );end;指示取變量之值procedure storin(t,s); string t, s; if t s then /*生成進(jìn)行類型轉(zhuǎn)換的指令*/ emit(STN);end;IF THEN labA:IF THEN ELSE labA: lab

34、B: 10.6 控制語(yǔ)句的處理10.6.1 if語(yǔ)句JMF, labAJMF, labAJMP, labB其屬性翻譯文法及相應(yīng)的語(yǔ)義動(dòng)作程序:1. y y2. yIF brfy THEN 3. ylabprody |ELSE brzlabprodylabprodz 動(dòng)作程序brf的功能是生成JMF指令，并將轉(zhuǎn)移標(biāo)號(hào)返回給屬性yprocedure brf; string labx; labx := genlab; /*產(chǎn)生一標(biāo)號(hào)賦給labx*/ emit(JMF, labx); return (labx);end; 動(dòng)作程序labprod是把從繼承屬性y得到的標(biāo)號(hào)設(shè)置到目標(biāo)程序中procedur

35、e labprod(y); string y; setlab(y);/*在目標(biāo)程序當(dāng)前位置設(shè)標(biāo)號(hào)*/end; 動(dòng)作程序br是是生成JMP指令，并將轉(zhuǎn)移標(biāo)號(hào)返回給屬性zprocedure br; string labz; labz := genlab; emit( JMP, labz); return( labz); end;1. y y2. yIF brfy THEN 3. ylabprody |ELSE brzlabprodylabprodz10.6.4 for 循環(huán)語(yǔ)句for 語(yǔ)句例子： for i:= 1 to n by z do . end for;ATG文法1.a, f, r a,

36、f, r2.a, f, r for a := initloads to labgenr by loadida comparea, sf3.a, f, r do end for retbranchr labemitfinitload 只生成給循環(huán)變量賦初值的指令。 start: JMP, loop end_ loop:initloadsfor := to by do LDA, ()LOD, (expr1) loop:LOD, (expr2) LOD, (id) LOD, (expr3)STNJMP, startlabgenrcomparea, sf BGT, end_loop ADD STO,

37、(id)retbranchrlabprodfloadida1.a, f, r a, f, r2.a, f, r for a := initloads to labgenr by loadida comparea, sf3.a, f, r do end for retbranchr labprodfprocedure labgen string r; r := genlab; setlab(r); return ( r );end;procedure compare( a, s); address a; string f, s; emit( ADD); emit( STO, a ); f :=

38、genlab; emit( BGT, f ); setlab( s ); return( f );end;procedure labprod( f ) / 即labemit string f; setlab( f );end;procedure loadid( a ) address a; emit( LOD, a);end;10.7 過程調(diào)用和返回實(shí)現(xiàn)： 調(diào)用段（過程語(yǔ)句的目標(biāo)程序段）： 計(jì)算實(shí)參值 = 操作數(shù)棧棧頂 被調(diào)用段（過程說明的目標(biāo)程序段）： 從棧頂取得值 = 形參單元10.7.1 參數(shù)傳遞的基本形式如C語(yǔ)言，Ada語(yǔ)言的in參數(shù), Pascal 的值參數(shù)。1.傳值（call by

39、 value) 值調(diào)用過程體中對(duì)形參的處理： 對(duì)形參的訪問等于對(duì)相應(yīng)實(shí)參的訪問特點(diǎn): 數(shù)據(jù)傳遞是單向的3. 傳名（call by name ) 又稱“名字調(diào)用”。即把實(shí)參名字傳給形參。這樣在過程體中引用形參時(shí)，都相當(dāng)于對(duì)當(dāng)時(shí)實(shí)參變量的引用。 當(dāng)實(shí)參變量為下標(biāo)變量時(shí)，傳名和傳地址調(diào)用的效果可能會(huì)完全不同。 傳名參數(shù)傳遞方式，實(shí)現(xiàn)比較復(fù)雜，其目標(biāo)程序運(yùn)行效率較低, 現(xiàn)已很少采用。2.傳地址（call by reference) 引用調(diào)用 實(shí)現(xiàn)： 調(diào)用段： 計(jì)算實(shí)參地址 = 操作數(shù)棧棧頂 被調(diào)用段： 從棧頂取得地址 = 形參單元 過程體中對(duì)形參的處理： 通過對(duì)形參的間接訪問來訪問相應(yīng)的實(shí)參 特點(diǎn):

40、結(jié)果隨時(shí)送回調(diào)用段 如：FORTRAN, Pascal 的變量形參。如：ALGOL 的換名形參。begin integer I; array A1:10 integer; procedure P(x); integer x; begin . I := I + 1; x := x+ 5; end; begin I := 1; P( AI ); end;end;傳地址： I : 2A1: 6傳名： I : 2AI:= AI+5A1 = 6 A2 = 2A1 = 1 A2 = 7假定：A1 = 1 A2 = 210.7.2 過程調(diào)用處理與調(diào)用有關(guān)的動(dòng)作如下：1. 檢查該過程名是否已定義（過程名和函數(shù)

41、名不能用錯(cuò)），實(shí)參和形參在類型、順序、個(gè)數(shù)上是否一致。(查符號(hào)表）2. 加載實(shí)參（值或地址）3. 加載返回地址4. 轉(zhuǎn)入過程體入口地址例：有過程調(diào)用：process_symb(symb, cursor,replacestr);調(diào)用該過程生成的目標(biāo)代碼為： LOD, (addr of symb ) LOD, (addr of cursor ) LOD, (addr of replacestr) JSR, ( addr of process_symb):.傳值調(diào)用 若實(shí)參并非上例中所示變量，而是表達(dá)式，則應(yīng)生成相應(yīng)計(jì)算實(shí)參表達(dá)式值的指令序列。 JSR指令先把返回地址壓入操作數(shù)棧，然后轉(zhuǎn)到被調(diào)過程入

42、口地址。設(shè)過程說明的首部有如下形式：procedure process_symb(string:symbal, int: cur, string: repl); 則過程體目標(biāo)代碼的開始處應(yīng)生成以下指令，以存儲(chǔ)返回地址和形參的值。ALC, 4 + x /* x為定長(zhǎng)項(xiàng)空間 */STO, /* 保存返回地址 */STO, /* 保存replacestr */STO, /* 保存cursor */STO, /* 保存symb */過程調(diào)用時(shí)，實(shí)參加載指令是把實(shí)參變量?jī)?nèi)容（或地址）送入操作數(shù)棧頂，過程聲明處理時(shí)，應(yīng)先生成把操作數(shù)棧頂?shù)膶?shí)參送運(yùn)行棧AR中形參單元的指令。將操作數(shù)棧頂單元內(nèi)容存入運(yùn)行棧（動(dòng)

43、態(tài)存儲(chǔ)分配的數(shù)據(jù)區(qū)）當(dāng)前活動(dòng)記錄的形式參數(shù)單元。 可認(rèn)為此時(shí)運(yùn)行棧和操作數(shù)棧不是一個(gè)棧（分兩個(gè)棧處理）x: display+DL4 3loc2loc1 RA DL display xB過程調(diào)用的ATG文法： i , z initmm i , z genjsrii , z n lookupprocni, zi,z chklengthi , z | (i, z)i , z t chktypet, i, m, zz i , zi , z chklengthi , z | , t chktypet, i, m, zz i , zprocedure lookupproc(n); string n; in

44、teger i, z; i := lookup(n); /*查符號(hào)表*/ if i 1 then begin error( 過程, n ,未定義, statno); errorrecovery( panic ); /*應(yīng)急處理過程 */ return ( i := 0, z:= 0); end else return( i , z:= symtbl i.dim); /* z為形參數(shù)目*/end;實(shí)參個(gè)數(shù)計(jì)數(shù)，m初值為0形參數(shù)目過程名符號(hào)表入口位置procedure chktype(t, i, m, z); string t; integer m, i, z; if z 1 then begin error( 實(shí)參數(shù)大于形參數(shù), symtbl , statno); return ( z)