編譯原理：第6章 語義分析與中間代碼生成

1、 課 程 內(nèi) 容第 1 章 編 譯 引 論第 2 章 形式語言與自動機(jī)基礎(chǔ)第 3 章 詞法分析 (Lexical Analysis)第 4 章 語法分析(Syntax Analysis) 自上而下分析法第 5 章 語法分析(Syntax Analysis) 自下而上分析法第 6 章 語義分析與中間代碼生成第 7 章 運(yùn) 行 環(huán) 境第 8 章 代碼優(yōu)化（optimization）第 6 章 語義分析與中間代碼生成 6.1 語義分析綜述 6.2 語法制導(dǎo)翻譯與屬性文法 6.3 中間語言 6.4 符號表 6.5 類型檢查（自學(xué)） 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.1

2、 語義分析綜述 語義分析的地位Front end ( 分析 )Back end ( 綜合 )語義處理 編譯程序最實(shí)質(zhì)性的工作； 第一次對源程序的語義作出解釋，引 起源程序質(zhì)的變化。 Ch6 語義分析與中間代碼生成 6.1 語義分析綜述 語義分析的任務(wù) 按照語法分析器識別的語法范疇進(jìn)行語義檢查和處理，產(chǎn)生相應(yīng)的中間代碼或目標(biāo)代碼。 中間代碼 介于源語言和目標(biāo)代碼之間的一種代碼。 Ch6 語義分析與中間代碼生成 6.1 語義分析綜述 引入中間代碼的目的 1. 方便生成目標(biāo)代碼； 2. 便于優(yōu)化； 3. 便于移植。第 6 章 語義分析與中間代碼生成 6.1 語義分析綜述 6.2 語法制導(dǎo)翻譯與屬性文

3、法 6.3 中間語言 6.4 符號表 6.5 類型檢查（自學(xué)） 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法 語法制導(dǎo)翻譯 為文法的每一個產(chǎn)生式配一個相應(yīng)的語義子程序（或語義規(guī)則描述的語義動作），并在語法分析的同時調(diào)用它。 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法 屬性翻譯文法 把語義引入文法，給產(chǎn)生式中的文法符號附加“屬性”，構(gòu)成涉及語義的翻譯文法。 形式定義 A = （ G , V , F ） 其中： G： 一般為二型文法； V： 屬性的有窮集； F： 關(guān)于屬性的斷言或謂詞的有窮集。文法符號的語義性質(zhì)(語義屬性) Ch

4、6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法 屬性表示 N . t ( N是G符號，t是N的屬性) （終結(jié)符的屬性均為lexval）產(chǎn) 生 式語 義 規(guī) 則L EE E + TE TT T * FT FF (E)F digitprint( E .val )E .val = E1 .val + T .valE .val = T .valT .val = T1 .val F .valT .val = F .valF .val = E .valF .val = digit .lexval數(shù)、符號串、類型、存儲空間 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法 綜合屬性

5、 分析樹中,如果一個結(jié)點(diǎn)的屬性值是通過子結(jié)點(diǎn)的屬性值計(jì)算得到,則稱為綜合屬性。 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法例如， 3 * 5 + 4 ; LE; print( E .val )EE+T E.val = E1.val + T.valET E .val = T .valTT*F T.val = T1.valF.valTF T.val = F.valF(E) F.val = E.valFdigit F.val = digit.lexvalL;EE+TT*FFTdigitdigitFdigit.lexval=3.lexval=5.lexval=4.val=3.val

6、=3.val=5.val=15.val=15.val=4.val=4.val=19 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法 繼承屬性 分析樹中,如果一個結(jié)點(diǎn)的屬性值是由該結(jié)點(diǎn)的父結(jié)點(diǎn)和(或)兄弟結(jié)點(diǎn)的屬性定義的稱為繼承屬性。 綜合屬性 分析樹中,如果一個結(jié)點(diǎn)的屬性值是通過子結(jié)點(diǎn)的屬性值計(jì)算得到則稱為綜合屬性。 Ch6 語義分析與中間代碼生成 6.2 語法制導(dǎo)翻譯與屬性文法例如，float id1，id2 ， id3 DTL L .in = T .typeTint T .type = integerTfloat T .type = float LL,id L1 .in =

7、 L .in addtype(id.entry, L.in)Lid addtype(id.entry, L.in) DTLfloatL,id3L,id2id1.type=float.in=float.in=float.type=float.in=float.type=float.type=float第 6 章 語義分析與中間代碼生成 6.1 語義分析綜述 6.2 語法制導(dǎo)翻譯與屬性文法 6.3 中間語言 6.4 符號表 6.5 類型檢查（自學(xué)） 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.3 中間語言中間語言( 中間代碼)是語義程序的輸出。 中間語言的設(shè)計(jì)與應(yīng)用既要考慮

8、從源語言到目標(biāo)語言的翻譯跨度又要考慮目標(biāo)機(jī)的指令集特點(diǎn)。中間語言N元式(三元式、間接三元式四元式)逆波蘭式圖 Ch6 語義分析與中間代碼生成 6.3 中間語言 一. 逆波蘭式(后綴式 )形式定義：e1e2 en ( n 1)運(yùn)算對象運(yùn)算符 a * b - aa+b*(c+d)*(e+f)例如， ab*a (表示單目)a b c d + * e f + * + IFthenelse(1) BZ (2)(3) BR(4)(5)引入兩個操作符：BZ、BR。BZ是二目操作符，如果第一運(yùn)算對象數(shù)的值為假，則產(chǎn)生一個到第二運(yùn)算對象的轉(zhuǎn)移。 BR則是一個單目操作符，它產(chǎn)生一個到運(yùn)算對象的轉(zhuǎn)移。 Ch6 語義

9、分析與中間代碼生成 6.3 中間語言Label2Label1JFJ例6.1 設(shè)有如下C程序片段 int k； i=j=0；h： k=100； if (ki+j) k-；i+; else k=i*2-j*2； goto h； Ch6 語義分析與中間代碼生成 6.3 中間語言逆波蘭式代碼：(1) i j 0 = =(2) k 100 =(3) k i j + ( ) BZ(4) k k 1 = (5) i i 1 + =(6) ( ) BR(7) k i 2*j2* =(8) (2) BR編號 78 二. N元式N個域的記錄結(jié)構(gòu) （ D1， D2，D3， ，Dn） OP域 操作對象域三元式、間接三

10、元式雙地址機(jī)指令形式 四元式三地址機(jī)指令形式 Ch6 語義分析與中間代碼生成 6.3 中間語言 常見N元式 其中： NO.:為產(chǎn)生的三元式的順序編號； OP : 是操作符； ARG1和ARG2為第一操作數(shù)和第二操作數(shù)。(也可以是前面某一個三元式的編號， 代表該三元式的計(jì)算結(jié)果被作為操作數(shù) ) Ch6 語義分析與中間代碼生成 6.3 中間語言三元式形式定義： NO. ( OP , ARG1 , ARG2 ) 間接三元式形式定義： 間接碼表 + 三元式表 例如，語句 X=A+B*C 的三元式表示為 NO. OP ARG1 ARG2(1)(2)(3)* B C+ A (1)= (2) X Ch6 語

11、義分析與中間代碼生成 6.3 中間語言 NO. OP ARG1 ARG2(1)(2)(3)(4)(5)(6)(7) X Y BZ (1) (5)= X ZBR (7) + Y 1 = (5) Z if XY then Z = X else Z = Y+1的三元式可以表示為 Ch6 語義分析與中間代碼生成 6.3 中間語言 (a+b)2 + (a+b)3 Ch6 語義分析與中間代碼生成 6.3 中間語言 其中：“” 表示冪運(yùn)算。 + 3 + a b 2 + a b OP ARG1 ARG2NO (a+b)2 + (a+b)3 的間接三元式 間接碼表 +, , , , 3 , , 2 + , a,

12、 b 三元式表 Ch6 語義分析與中間代碼生成 6.3 中間語言控制三元式代碼執(zhí)行順序 四元式形式定義： NO. ( OP , ARG1 , ARG2 ，Result) Ch6 語義分析與中間代碼生成 6.3 中間語言(a+b)2 + (a+b)3的四元式：* 注：Ti是臨時變量。(4) +， T2， T4 ，T5(3) , T3, 3， T4(1) , T1, 2， T2(0) + , a, b， T1(2) + , a, b， T3 NO. OP ARG1 ARG2 Result (1)(2)(3)(4)(5)(6)(7) X Y t1BZ t1 (5) = X ZBR (7) + Y 1

13、 t2 = t2 Z if XY then Z = X else Z = Y+1的四元式可以表示為 Ch6 語義分析與中間代碼生成 6.3 中間語言 三. 圖（樹） 一個三元式一棵子樹 OP子樹根 ARG1子樹左葉節(jié)點(diǎn) ARG2子樹右葉節(jié)點(diǎn) Ch6 語義分析與中間代碼生成 6.3 中間語言 (a+b)2 + (a+b)3三元式ab+ab+23 Ch6 語義分析與中間代碼生成 6.3 中間語言 +, , , , 3 + , a, b , , 2 + , a, b if XY then Z = X else Z = Y+1的樹可以表示為 Ch6 語義分析與中間代碼生成 6.3 中間語言zBRYYX

14、BZ(4)xz=(5)1(4)=+(5)(1)(2)(3)樹編號樹編號 ab+ab+23樹線性化：后序遍歷 逆波蘭式幾種表示間關(guān)系 Ch6 語義分析與中間代碼生成 6.3 中間語言“單步”表示 三元式 Ch6 語義分析與中間代碼生成 6.3 中間語言語法分析的結(jié)果為樹；逆波蘭式適于棧式存儲的計(jì)算機(jī)（堆棧機(jī)）；四元式便于優(yōu)化；間接三元式優(yōu)化時的時空效率類似于四元式。綜述：第 6 章 語義分析與中間代碼生成 6.1 語義分析綜述 6.2 語法制導(dǎo)翻譯與屬性文法 6.3 中間語言 6.4 符號表 6.5 類型檢查（自學(xué)） 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.4 符號表

15、 源程序流基本組成單位特點(diǎn) 關(guān)鍵字：表示語句性質(zhì)，反映語句結(jié)構(gòu)； 標(biāo)識符：表示程序中各種實(shí)體； 如，變量名；常量名；標(biāo)號名；過程名；函數(shù)名；文件名，數(shù)組名 V: name , type , addr , level array: name , type , addr , dim , level , size Ch6 語義分析與中間代碼生成 6.4 符號表語句標(biāo)號: name , addr , 定義否 過程、函數(shù): name , addr , 形參 反映了標(biāo)識符的語義特征屬性，是翻譯的依據(jù)。 記錄于符號表中（namelist） 整個編譯過程中動態(tài)地采集、記錄、變更、引用 Ch6 語義分析與中間代

16、碼生成 6.4 符號表例如，設(shè)有C程序片段 : int i , a4 ; i=a2 ; 詞法語法語義分析i, a 符號表i.type 符號表a.type 符號表a.維數(shù) 符號表a.每維大小 符號表 類型檢查； 數(shù)組越界檢查； 回填addr; Ch6 語義分析與中間代碼生成 6.4 符號表 符號表 存放源程序中有關(guān)標(biāo)識符的屬性信息的數(shù)據(jù)結(jié)構(gòu)。 符號表作用語義檢查依據(jù)；代碼生成時地址分配依據(jù)。收集標(biāo)識符屬性信息； 符號表結(jié)構(gòu) 屬性信息域 名字域 Ch6 語義分析與中間代碼生成 6.4 符號表 常見標(biāo)識符類的主要屬性與作用1. 標(biāo)識符名。作用：查重(考慮作用域和可視性前提)2. 類型。作用：存儲空間

17、分配；可施加運(yùn)算的檢查等3. 存儲類別。作用：提供語義處理、檢查、存儲 分配的依據(jù)。4. 作用域、可視性。作用：動態(tài)活動環(huán)境支持，提 供量所在層次；第 6 章 語義分析與中間代碼生成 6.1 語義分析綜述 6.2 語法制導(dǎo)翻譯與屬性文法 6.3 中間語言 6.4 符號表 6.5 類型檢查（自學(xué)） 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.6 語句翻譯與中間代碼生成 語句翻譯設(shè)計(jì)要點(diǎn) 1. 根據(jù)語義確定語句的目標(biāo)結(jié)構(gòu) ；源語句中間及目標(biāo)代碼的布局If E then S1 測E S1.codeE.f:Goto E.f E.code Ch6 語義分析與中間代碼生成 6.6

18、語句翻譯與中間代碼生成2. 確定中間代碼 ； 3. 根據(jù)目標(biāo)結(jié)構(gòu)和語義規(guī)則，構(gòu)造語義 子程序（轉(zhuǎn)換翻譯程序） ；4. 涉及的實(shí)現(xiàn)技術(shù) 語句翻譯設(shè)計(jì)要點(diǎn) 1. 根據(jù)語義確定語句的目標(biāo)結(jié)構(gòu) ；6.6 語句翻譯與中間代碼生成 6.6.1 說明類語句的翻譯 6.6.2 賦值語句與表達(dá)式翻譯 6.6.3 控制流類語句翻譯 6.6.4 數(shù)組說明與數(shù)組元素引用的翻譯 6.6.5 過程、函數(shù)說明和調(diào)用的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 說明類語句 語言中定義性信息，一般不產(chǎn)生目標(biāo)代碼，其作用是輔

19、助完成編譯。例如， 常量說明，變量說明，類型說明， 對象說明，標(biāo)號說明 說明類語句的處理 相關(guān)說明的屬性信息填入符號表，提供語義檢查和存儲分配的依據(jù)。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 一. 常量定義語句的翻譯 二. 簡單說明類語句 三. 復(fù)合類型說明語句 6.6.1 說明類語句的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯常量說明語句的文法CONST_DEF CONST ; ; id=num 常量說明語句的語義子程序 num.ord=look_con_table(num.lexval); id.ord=nu

20、m.ord; id.type= num.type; id.kind=constant; add(id.entry;id.ord; id.type; id.kind) 一. 常量定義語句的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 CONST 標(biāo)識符常量； CONST pi=3.1416; true=1; true pi13.1416 addr type kind namenamelistvalueconslistRCONSBCONSCONST pi=3.1415926;3.1415926舉例說明： Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.

21、6.1 說明類 語句翻譯 一. 常量定義語句的翻譯 二. 簡單說明類語句 三. 復(fù)合類型說明語句 6.6.1 說明類語句的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 翻譯方案和語義子程序Dint id fill(ENTRY(id)，int)；D.AT=int Dfloat id fill(ENTRY(id)，float)；D.AT=float DD，id; fill(ENTRY(id)，D1 .AT)； D.AT=D1 .AT * 其中：D.AT：非終結(jié)符D的屬性。fill(P, A): 完成把性質(zhì)A填入P所指的符號表入口的相應(yīng)數(shù)據(jù)項(xiàng)中的函數(shù)。ENTR

22、Y(i)：給出i所代表的量在符號表中的入口的函數(shù) 二. 簡單說明類語句 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯int i , j ;float a ,b ;類型變量表 name kind type addr iVI0 jVI4 aVR8 bV R16 namelist舉例說明： Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 一. 常量定義語句的翻譯 二. 簡單說明類語句 三. 復(fù)合類型說明語句 6.6.1 說明類語句的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 三. 復(fù)合類型說明

23、語句 T struct LD VL id | D D;F | FF type V;V V, id | 其中： L： 結(jié)構(gòu)類型名； D：結(jié)構(gòu)成員； V：變量表； F： 結(jié)構(gòu)成員項(xiàng)； id: 標(biāo)識符； Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯 語義處理涉及 (1) 結(jié)構(gòu)成員與該結(jié)構(gòu)相關(guān)； (2) 結(jié)構(gòu)的存儲：一個結(jié)構(gòu)的所有成員項(xiàng) 連續(xù)存放(簡單方式)； (3) 結(jié)構(gòu)的引用是結(jié)構(gòu)成員的引用，不能 整體引用；（成員信息須單獨(dú)記錄） 例如， struct date int year, month, day; today, yesterday; Ch6 語義分析與中間

24、代碼生成 6.6 語句翻譯 6.6.1 說明類 語句翻譯14084LEN 52CV d12Iarray c4RV b0IV a OFFSET type kind name 結(jié)構(gòu)成員分表name kind addr k1struct namelist例如，struct k1 int a; float b; int c10; char d; 第 6 章 語義分析與中間代碼生成 6.6.1 說明類語句的翻譯 6.6.2 賦值語句與表達(dá)式翻譯 6.6.3 控制流類語句翻譯 6.6.4 數(shù)組說明與數(shù)組元素引用的翻譯 6.6.5 過程、函數(shù)說明和調(diào)用的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯

25、與中間代碼生成 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 賦值語句形式定義 A V = E 賦值語句目標(biāo)結(jié)構(gòu)* 賦值語句的處理集中在表達(dá)式的處理上 計(jì)算E.code E值 VCode區(qū) Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 A i=E GEN(=，E.PLACE， _，ENTRY(i) 賦值語句翻譯語義子程序其中: GEN(OP，ARG1，ARG2，RESULT): 函數(shù)。 把四元式(OP，ARG1，ARG2，RESULT) 填入四元式表。 E.PLACE：表示存放E值的變量名在符號表的 入口地址。 E

26、NTRY(i)：給出i表示的單詞在符號表中的入口。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 (2) “=”的處理： “=”左右部類型相容性檢查和轉(zhuǎn)換 ； 賦值語句語義處理 (1) 表達(dá)式處理(產(chǎn)生表達(dá)式的中間代碼)； Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 表達(dá)式形式定義 E E op E | op E | id 其中： OP: 為運(yùn)算符； E, id: 運(yùn)算對象。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 (1) E E OP E E.PLACE=NEWTE

27、MP； GEN(OP, E1.PLACE, E2.PLACE, E.PLACE) (2) E OP E E.PLACE=NEWTEMP； GEN(OP, E1.PLACE，_, E.PLACE) (3) E id E.PLACE=ENTRY(id) 表達(dá)式翻譯的語義子程序 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.2 賦值 語句與表達(dá)式翻譯 寫出語句a=b+c+d翻譯后的四元式代碼：賦值 語句與表達(dá)式翻譯舉例：(+ b c t1)(+ t1 d t2)(= t2 - a) +id=+idididAEEEEE第 6 章 語義分析與中間代碼生成 6.6.1 說明類語句的翻譯 6.6

28、.2 賦值語句與表達(dá)式翻譯 6.6.3 控制流類語句翻譯 6.6.4 數(shù)組說明與數(shù)組元素引用的翻譯 6.6.5 過程、函數(shù)說明和調(diào)用的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 控制流語句: 改變程序執(zhí)行順序，引起程序執(zhí)行發(fā)生跳轉(zhuǎn)的語句。 程序設(shè)計(jì)語言中出現(xiàn)頻繁的語句； 為可執(zhí)行語句，要產(chǎn)生相應(yīng)的目標(biāo)代碼； 控制流程的變換，依靠代碼中的跳轉(zhuǎn)指 令與對應(yīng)跳轉(zhuǎn)的語句標(biāo)號。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 控制流語句特點(diǎn) 改變程序執(zhí)行順序，引起

29、程序執(zhí)行發(fā)生跳轉(zhuǎn)（向前或向后）。 跳轉(zhuǎn)目標(biāo)與依據(jù)語句標(biāo)號 顯式：位于源語句之前； （如， L1： S;） 隱式：內(nèi)含于源語句之中且在源 程序中未標(biāo)識的； Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯If (er) S1; else S2for ( e1; e2; e3) S ; 跳出循環(huán)體繼續(xù) 循環(huán)體 開 始 循環(huán)體終值判別 er=T跳轉(zhuǎn)目標(biāo) er=F跳轉(zhuǎn)目標(biāo)跳出if 繼續(xù)循環(huán)變量重賦值 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯一. 語句標(biāo)號與拉鏈返填技術(shù)條件語句的翻譯循環(huán)語句的翻譯 四. 多分支語句的翻譯6.6.3

30、控制流類語句翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 語句標(biāo)號處理 控制流類語句處理面對的公共問題和實(shí)現(xiàn)技術(shù) 語句標(biāo)號處理 先定義后引用 先引用后定義 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯語句標(biāo)號 定義性出現(xiàn) （如， L1: S ;） 使用性出現(xiàn) （如， goto L1 ;） addr 定義否(flag)標(biāo)號名語句標(biāo)號表（LT）標(biāo)號所標(biāo)識的源語句的中間代碼序列的第一條代碼的存放地址1表示定義性出現(xiàn)0表示使用性出現(xiàn) Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 對多遍掃描

31、的編譯器 視為一種情況(先定義后引用) 處理。例如， 20: c=a*b ; goto 20; goto 20; Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 *, a, b, c j, , , q j, , , q q-1 q k n Code區(qū)q120 LT20: c=a*b;goto 20;goto 20;20: c=a*b ; goto 20; goto 20; Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 適用于一遍掃描的編譯器；例如， goto 20; goto 20; 20: c=a*b ; 產(chǎn)生這2條語句的

32、代碼時，還未掃描到20號語句，即沒有生成該語句的代碼，因此轉(zhuǎn)向的目標(biāo)地址未定。拉鏈-返填技術(shù)處理標(biāo)號先引用后定義的情況： Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 goto 20; goto 20; 20: c=a*b ; ( j , , , 0 ) p Code區(qū)p020 LT q200q ( j , , , p )鏈尾 r201r ( *, a, b, c)返填 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 goto 20; goto 20; 20: c=a*b ; p ( j , , , 0 )Code區(qū)200p

33、 LT q200q ( j , , , p )拉鏈 r201r ( *, a, b, c)返填rr Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 注意：鏈尾標(biāo)志在代碼區(qū)的四元式中，鏈頭在標(biāo)號表中，鏈在與同一語句標(biāo)號相關(guān)的跳轉(zhuǎn)代碼中； 3. 返填次序: 2. 拉鏈次序： p q尾頭q p ( 在代碼區(qū)跳轉(zhuǎn)指令中(addr=0) )尾頭 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯一. 語句標(biāo)號與拉鏈返填技術(shù)條件語句的翻譯循環(huán)語句的翻譯 四. 多分支語句的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制

34、流類 語句翻譯二. 條件語句的翻譯 條件語句文法: S if (E) then S1 | if (E) S1 else S2 | while (E) S1 其中： E：條件表達(dá)式 (有語義值 E.True和 E.False)； S1, S2: 語句； Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯計(jì)算EE?S1非0= 0 S if (E) then S1 E.trueE.false 測E S1.codeE.true:E.false:Goto E.trueGoto E.false E.codeE.true:E.false: Ch6 語義分析與中間代碼生成 6.6

35、 語句翻譯 6.6.3 控制流類 語句翻譯 條件語句翻譯的語義子程序 S if E then S1 E.true=newlabel； E.false=newlabel； S.code=E.code|GEN(jT ，_，_，E.true)| GEN(jF ，_，_，E.false)| GEN(E.true：) | S1.code| GEN(E.false：) Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯計(jì)算EE?S1= 0非0 S if (E) then S1E.false 測E S1.codeE.false:Goto E.false E.codeE.fals

36、e: Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 條件語句翻譯的語義子程序 S if E then S1 E.false=newlabel； S.code=E.code|GEN(jF ，_，_，E.false)| S1.code| GEN(E.false：) Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯if (E) S1 else S2計(jì)算EE?S1E.true:E.false:非0= 0S2Next:E.trueE.falseNext 測E S1.codeE.true:E.false:Goto E.false goto

37、 Next S2.code Next :Goto E.true E.code Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯S if E then S1 else S2 E.true=newlabel； E.false=newlabel； S.next=newlabel； S.code=E.code | GEN(jT ，_，_，E.true) | GEN (jF ，_，_，E.false) | GEN (E.true：| S1.code | GEN (j，_，_，S.next) | GEN (E.false：) | S2.code|GEN(S.next ： )

38、 條件語句翻譯的語義子程序 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯if (E) S1 else S2計(jì)算EE?S1E.false:非0= 0S2Next:E.falseNext 測E S1.codeE.false:Goto E.false goto Next S2.code Next : E.code Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯S if E then S1 else S2 E.false=newlabel； S.next=newlabel； S.code=E.code | GEN (jF ，_，_，

39、E.false) | S1.code | GEN (j，_，_，S.next) | GEN (E.false：) | S2.code|GEN(S.next ： ) 條件語句翻譯的語義子程序 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 while (E) S1計(jì)算EE?E.true:E.false:=0非0S1E.begin:E.trueE.falsebegin 測E S1.codeE.true:E.false:Goto E.falsegoto begin begin :Goto E.true E.code Ch6 語義分析與中間代碼生成 6.6 語句翻譯

40、6.6.3 控制流類 語句翻譯S while (E) S1 E.true=newlabel； E.false=newlabel； S.begin=newlabel； S.code=GEN(S.begin：) | E.code | GEN(jT ，_，_，E.true) | GEN(jF ，_，_，E.false) | GEN(E.true：) | S1.code | GEN(j，_，_，S.begin)| GEN(E.false：) 條件語句翻譯的語義子程序 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 while (E) S1計(jì)算EE?E.false:=0

41、非0S1E.begin:E.falsebegin 測E S1.codeE.false:Goto E.falsegoto begin begin : E.code Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯S while (E) S1 E.false=newlabel； S.begin=newlabel； S.code=GEN(S.begin：) | E.code | GEN(jF ，_，_，E.false) | S1.code | GEN(j，_，_，S.begin)| GEN(E.false：) 條件語句翻譯的語義子程序 Ch6 語義分析與中間代碼生成

42、6.6 語句翻譯 6.6.3 控制流類 語句翻譯例6.2 if (AB & BC ) S1 else S2用到的語法：Sif C S else SCC & T|TTididNDA Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯例6.2 if (AB & BC ) S1 else S2L1L2L3 ( A B T1) ( B C T2) (JT T3 _ 0 ) (JF T3 _ 0 ) S1.code 36 S2.code(J _ _ 0 )10:14:18:20:24:28:32:36:40:44:320L3240L2200L1128281140L1:L2:

43、L3:結(jié)果S1S20 非0計(jì)算AB & BC (& T1 T2 T3) 3640JT L1JF L2 S1.codeL2:goto L3 L1: AB & BC S2.codeL3: Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯一. 語句標(biāo)號與拉鏈返填技術(shù)條件語句的翻譯循環(huán)語句的翻譯 四. 多分支語句的翻譯6.6.3 控制流類語句翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯計(jì)算e1計(jì)算e2S計(jì)算e3e2?L1:L2:L4:L3:= 0非0 ( jT, _, _, L2) ( jF, _, _, L3) e3.code

44、 ( j , _, _, L1) S.code ( j , _, _, L4)L4:L1:L2:L3:e1.codee2.code測e2三. 循環(huán)語句的翻譯 A for ( e1 ; e2 ; e3 ) SL1L3L4L2 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯循環(huán)語句的翻譯的語義子程序 A for ( e1 ; e2 ; e3 ) S L1=newlabel；L2=newlabel； L3=newlabel；L4=newlabel； A.code=e1.code |GEN(L1：) | e2.code | GEN(jT，_，_，L2) | GEN(j

45、F，_，_，L3) | GEN(L4：) | e3.code | GEN(j，_，_，L1) |GEN(L2：) | S.code |GEN(j ，_，_，L4) | GEN(L3：) ( jT, _, _, L2) ( jF, _, _, L3) e3.code ( j , _, _, L1) S.code ( j , _, _, L4)L4:L1:L2:L3:e1.codee2.code測e2給出如下C程序段的目標(biāo)代碼結(jié)構(gòu)： for ( e1; e2; e3;) for ( t1; t2; t3;) if ( er ) S1; S2; L1L2L3L4L5L7L6L9L8 Ch6 語義分析

46、與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯L1:L2:L4:L3:計(jì)算e1計(jì)算e2S1計(jì)算t3e2?= 0非0計(jì)算t1計(jì)算t2t2?非0計(jì)算erer?非0計(jì)算e3= 0S2L5L6L7L8L9e1.codee2.code測e2值( jT , , , L3 )( jF , , , L9 )e3.code( j , , , L1 )t1.codet2.codet3.code( j , , , L4 )er.code測t2值測er值( jF , , , L7 )S1.codeS2.code( j , , , L5 )L1:L2:L3:L4:L5:L6:L7:( jT , , ,

47、 L6 )( jF , , , L8 )L8:( j , , , L2 )L9: Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯設(shè)有下列C語言的語句（注： Li是設(shè)定的語句標(biāo)號,在注釋中標(biāo)識出所在位置）i=j=0;for ( ; j=0, i=0, i=100; L2：i+,j-)if (E1) S1; / if L3: (E1) L4: S1;S2; / L5: S2;其中：S1和S2代表語句，對應(yīng)的四元式分別為S1.code和S2.code；E1代表?xiàng)l件表達(dá)式，對應(yīng)的四元式為E1.code。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控

48、制流類 語句翻譯1給出該語句的四元式形式的目標(biāo)代碼結(jié)構(gòu)，填入下表。說明：無條件轉(zhuǎn)移操作符用“j”表示；條件成立轉(zhuǎn)移的操作符用“jT”表示；條件不成立轉(zhuǎn)移的操作符用“jF”表示。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯Adresscode備注(可有可無)2. 給出中間代碼生成后對應(yīng)該段代碼填寫的下列語句標(biāo)號表內(nèi)容（按填寫標(biāo)號表的實(shí)際順序）。 注：設(shè)編譯器是一遍掃描的編譯器。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯語句標(biāo)號(Li)定義與否標(biāo)志(1表示已定義，0反之)Addr Ch6 語義分析與中間代碼生成 6.6

49、語句翻譯 6.6.3 控制流類 語句翻譯一. 語句標(biāo)號與拉鏈返填技術(shù)條件語句的翻譯循環(huán)語句的翻譯 四. 多分支語句的翻譯6.6.3 控制流類語句翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯四. 多分支語句的翻譯 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯計(jì)算e值e?S1S2SnSn+1L1:L3:L2n-1:L2:L2n-2:next

50、:L2n : Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯四. 多分支語句的翻譯 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯e.code測C1S1.code(j, _, _, next)測C2S2.code(j, _, _, next)測CnSn.code(j, _, _, next)Sn+1.code L1: L2: L3: L4: L2

51、n-2: L2n-1: L2n: next:jT L1jF L2jT L3jF L4 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類 語句翻譯 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 e.code(j, _, _, test)S1.code(j, _, _, next)S2.code(j, _, _, next)Sn.code(j, _, _, next)Sn+1.code(j, _, _, next)If e=c1 goto

52、L1If e=c2 goto L2If e=cn goto Lngoto Ln+1 L1: Ln+1: test: next: L2: Ln:測試表 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.3 控制流類語句翻譯第 6 章 語義分析與中間代碼生成 6.6.1 說明類語句的翻譯 6.6.2 賦值語句與表達(dá)式翻譯 6.6.3 控制流類語句翻譯 6.6.4 數(shù)組說明與數(shù)組元素引用的翻譯 6.6.5 過程、函數(shù)說明和調(diào)用的翻譯 Ch6 語義分析與中間代碼生成 6.6 語句翻譯與中間代碼生成 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯一. 數(shù)組說明t

53、ype A d1 d2 dn ；type A d1 . d1 d2 . d2 dn . dn ；數(shù)組類型數(shù)組名數(shù)組維數(shù)、每維大小、數(shù)組體積n: di個數(shù) di的值d1*d2* *dn Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯數(shù)組說明的語義處理 填表，登記數(shù)組的屬性信息。typenamedimdim_valuevol符號表公共、等長信息 （符號表）與計(jì)算數(shù)組元素地址有關(guān)、不等長信息 （信息向量表） Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯例6.3設(shè)有說明 int a22； float b4；abnamelist b

54、array R a array Iname kind type addr數(shù)組第一個元素地址a計(jì)算數(shù)元地址不變部分C體積 =d1*d2*dn維數(shù)第n維大小第二維大小第一維大小信息向量表 若為上下界需計(jì)算： a(2.10)10-2+1=9何時計(jì)算？動態(tài)數(shù)組如何處理？returnb0Cb14a0Ca2*2222信息向量表4*1 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯二. 數(shù)組元素引用type A d1 d2 dn ； 數(shù)組說明 A i1 i2 in 數(shù)組引用 * 不能整體引用，僅對單一數(shù)組元素引用。 數(shù)組元素引用的語義處理 語義檢查： 類型匹配；下標(biāo)越界檢查

55、； 產(chǎn)生代碼：數(shù)組元素地址計(jì)算的中間代碼。 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯數(shù)組元素地址計(jì)算編譯時能否完成？一般不能 A i1 i2 in 中 ik多為表達(dá)式 如， ai+j-1j+ 運(yùn)行時得到下標(biāo)值涉及數(shù)組元素地址計(jì)算的有關(guān)知識 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 數(shù)組存儲方式 (線性連續(xù))按行存儲按列存儲 例如， int a22;a11a10a01a00 a0按行a11a01a10a00 a0按列a01add = a0+1*bytea01add = a0+2*byte Ch6 語義分析與中間代碼生

56、成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 數(shù)組元素地址計(jì)算 據(jù)存儲方式，通過下述規(guī)則計(jì)算數(shù)組元素位置 (順序號) + a0 對一維數(shù)組 int an; / 默認(rèn)下標(biāo)下界=0 則 aiaddr = a0 +( i ) ( 若數(shù)組下標(biāo)下限=1，則ai = a0 + ( i-1 ) ) Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 對二維數(shù)組 int anm ; 則 aijaddr = a0 +( i *m + j) 若數(shù)組下標(biāo)下限=1，則 aijadd = a0 +(i-1) *m + ( j-1) Ch6 語義分析與中間代碼生成 6.6 語句翻譯

57、6.6.4 數(shù)組說明與引用翻譯 對n維數(shù)組 int ad1 d2 dn; 則 ai1 i2 in add = a0 +( i1 *d2*d3 * *dn + i2 *d3 *d4* *dn + + in-1 *dn + in)含ik,是可變部分，程序運(yùn)行時方可知。進(jìn)一步考慮更一般的情況：若數(shù)組下標(biāo)下限0 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 則 ai1 i2 in add = a0 +( (i1-1) *d2*d3 * *dn + (i2 -1) *d3 *d4* *dn + + (in-1 -1) *dn + ( in -1) ) = a0 + i

58、1d2d3 dn + i2d3d4 dn+in-1dn +in (d2d3 dn +d3d4 dn + +dn+1)V不變 C變換返回若數(shù)組下標(biāo)下限=1 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 ai1 i2 in add = a0 + i1d2d3 dn + i2d3d4 dn+in-1dn +in (d2d3 dn +d3d4 dn + +dn+1)V不變 C = a0 C + V = CUN + Vconspartvarpart編譯時計(jì)算,填入內(nèi)情向量表據(jù)數(shù)元引用情況，產(chǎn)生計(jì)算的中間代碼，程序運(yùn)行時算出。信息向量表 Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.4 數(shù)組說明與引用翻譯 數(shù)組元素引用目標(biāo)結(jié)構(gòu)V.codeV值 VCUN = a0 CT = CUN + V計(jì)算V的中間代碼計(jì)算 CUN數(shù)組元素地址 T Ch6 語義分析與中間代碼生成 6.6 語句翻譯 6.6.