【正文】 看繼承屬性與綜合屬性 LEE + EE + E 83 5.post=3 .post=5 .post=8 .post=35+ .post=35+8+ (print(35+8+)) 13 LR分析翻譯方案的設(shè)計(jì) LR分析中的語法制導(dǎo)翻譯實(shí)質(zhì)上是對(duì) LR語法分析的擴(kuò)充： 1 擴(kuò)充 LR分析器的功能： 當(dāng)執(zhí)行歸約產(chǎn)生式的動(dòng)作時(shí) ， 也執(zhí)行產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作 。+39。 11 語義規(guī)則的兩種形式（續(xù) 3） 3 屬性作為分析樹的注釋 將屬性附著在分析樹對(duì)應(yīng)文法符號(hào)上，形成 注釋分析樹 。+39。 10 語義規(guī)則的兩種形式（續(xù) 2） LEE + E3 5E + E 8翻譯方案 1，自下而上計(jì)算， LR分析。 post(k):=lexval。 翻譯方案 1 print_post(post)。（設(shè)計(jì)與實(shí)現(xiàn)） 9 語義規(guī)則的兩種形式（續(xù) 1） 例 將中綴形式的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表示的語法制導(dǎo)定義和翻譯方案。 f(c1, c2, ..., ck) () ■ ()中屬性之間的依賴關(guān)系，實(shí)質(zhì)上反映了屬性計(jì)算的先后次序，即所有屬性 ci被計(jì)算之后才能計(jì)算屬性 b。 (2) 若 b是 α 中某文法符號(hào) Xi的屬性 ， c1, c2, ..., ck是 A的屬性 ， 或者是 α 中其它文法符號(hào)的屬性 ， 則稱 b是 Xi的 繼承屬性 。 為了簡(jiǎn)單，本章的文法一般為二義文法。 3 語法與語義（續(xù) 1） 檢查是否結(jié)構(gòu)正確的句子所表示的意思也合法； 執(zhí)行規(guī)定的語義動(dòng)作 ， 如： 表達(dá)式求值 符號(hào)表填寫 中間代碼生成等 3 語義分析的方法 語法制導(dǎo)翻譯 2 語義分析的兩個(gè)作用 4 屬性與語義規(guī)則 1 語法制導(dǎo)翻譯的基本思想 通俗地講： 以語法分析為基礎(chǔ) ， 伴隨語法分析的各個(gè)步驟 ，執(zhí)行相應(yīng)的語義動(dòng)作 。 2． switch (condition) { case condition1:stat1。 對(duì)于語法和語義： ? 語義不能離開語法獨(dú)立存在； ? 語義遠(yuǎn)比語法復(fù)雜； ? 同一語言結(jié)構(gòu)可包含多種含意 ， 不同語言結(jié)構(gòu)表示相同含意； ? 語法與語義之間沒有明確的界線。1 第四章 語法制導(dǎo)翻譯生成中間代碼 語法制導(dǎo)翻譯是處理語義的基本方法，它以語法分析為基礎(chǔ)，在語法分析得到語言結(jié)構(gòu)的結(jié)果時(shí)，對(duì)附著于此結(jié)構(gòu)的語義進(jìn)行處理，如計(jì)算表達(dá)式的值、生成中間代碼等。 例 1： 貓吃老鼠與老鼠吃貓 例 2： 程序設(shè)計(jì)語言中的分情況結(jié)構(gòu)： 1． case condition is case1: stat1。 case condition2:stat2。 具體方法： 1. 將文法符號(hào)所代表的語言結(jié)構(gòu)的意思 ， 用附著于該文法符號(hào)的 屬性 表示； 2. 用 語義規(guī)則 規(guī)定產(chǎn)生式所代表的語言結(jié)構(gòu)之間的關(guān)系（即屬性之間的關(guān)系），即用語義規(guī)則實(shí)現(xiàn)屬性計(jì)算。默認(rèn)解決二義的方法是規(guī)定常規(guī)意義下的優(yōu)先級(jí)和結(jié)合性。 (3) 稱 ()中屬性 b依賴于 屬性 c1, c2, ..., ck。 E→E1+E2 :=+ 3 屬性的定義 ** E→E1+E2 print() 8 語義規(guī)則的兩種形式 1 語法制導(dǎo)定義 用抽象的屬性和運(yùn)算符號(hào)表示的語義規(guī)則； (公式 ， 做什么 ) 2 翻譯方案 用具體屬性和運(yùn)算表示的語義規(guī)則 。虛擬屬性 print()可想象為:=print() 產(chǎn)生式 L→E E→E 1+E2 E→num 語法制導(dǎo)定義 print() := ||||39。 post(k):=39。 k:=k+1。 （以 3+5+8為例，歸約時(shí)翻譯） post:(3 5 + 8 +) 翻譯方案中需要考慮的問題： 1． 采用什么樣的語法分析方法； 2． 為屬性分配存儲(chǔ)空間； 3． 考慮計(jì)算次序。 k:=k+1。 產(chǎn)生式 語法制導(dǎo)定義 翻譯方案 L→E print()。 E→num :=。 由于是歸約時(shí)執(zhí)行語義動(dòng)作 ， 因此限制語義動(dòng)作僅能放在產(chǎn)生式右部的最右邊； 2 擴(kuò)充分析棧： 增加一個(gè)與分析棧并列的語義棧，用于存放分析棧中文法符號(hào)所對(duì)應(yīng)的屬性值。 語法制導(dǎo)定義 print() :=+。 val[top]:=val[top]+val[top+2]。 val[top]:=val[top]*val[top+2]。 例如 函數(shù)繪圖語言解釋器語法制導(dǎo)翻譯設(shè)計(jì) (第三次上機(jī)課 ) ： 1. 遞歸子程序可以設(shè)計(jì)為函數(shù) ， 用于返回必要的屬性值； 2. 適當(dāng)設(shè)計(jì)子程序中的臨時(shí)變量 ， 用于保存屬性值； 3. 將語義動(dòng)作嵌入在子程序的適當(dāng)位臵，正確計(jì)算屬性值。 4. 要求中間代碼具有如下特性，以便于編譯器的開發(fā)移植和代碼的優(yōu)化： ? 便于語法制導(dǎo)翻譯； ? 既與機(jī)器指令的結(jié)構(gòu)相近 ， 又與具體機(jī)器無關(guān) 。 x := first_token。 操作數(shù)進(jìn)棧 else pop(operators)。 （ 35+8+ pushu(3)） （ 3 5+8+ pushu(3) ） （ 35 +8+ pop(3和 5)， push((3+5))） （ 8 8+ pushu(8) ） （ 88 + pop(8和 8)， push(8+8)） （ 16 ） x := first_token。 計(jì)算 ， 并將結(jié)果進(jìn)棧 end if。 而實(shí)際上 ， 根據(jù)條件 e的取值 ， x和 y不能都計(jì)算： e p1 jez x p2 jump p1: y p2: (2) 其中： p1和 p2分別是標(biāo)號(hào)； p1 jez表示 e的結(jié)果為 0（假）則轉(zhuǎn)向 p1； p2 jump表示無條件轉(zhuǎn)向 p2。 result := arg1 op arg2 或 result := op arg1 或 op arg1 結(jié)果存放在 result中的二元運(yùn)算 arg1 op arg2 結(jié)果存放在 result中一元運(yùn)算 op arg1 一元運(yùn)算 op arg1 23 2 三地址碼的種類（ 98頁 ） 序號(hào) 三地址碼 四元式 （ 1） x := y op z (op, y, z, x) （ 2） x := op y (op, y, , x) （ 3） x := y (:=, y, , x) （ 4） goto L (j, , , L) （ 5） if x goto L (jnz, x, , L) （ 6） if x relop y goto L (jrelop, x, y, L) （ 7） param x (param, , , x) （ 8） call n, P (call, n, , P) （ 9） return y (return, , , y) （ 10） x := y[i] (=[], y[i], , x) （ 11） x[i] := y ([]=, y, , x[i]) （ 12） x := amp。 弱點(diǎn)： 給代碼的優(yōu)化帶來困難 。 產(chǎn)生式： (1) A→id :=E (2) E→E 1+E2 (3) E→E 1*E2 (4) E→(E 1) (5) E→ E1 (6) E→id 語義規(guī)則： {:=trip(:=， entry()， )} {:=trip(+， ， )} {:=trip(*， ， )} {:=} {:=trip(， ， )} {:=entry()} ② 三元式的語法制導(dǎo)翻譯 28 3 三地址碼的實(shí)現(xiàn)（續(xù) 2） (1) A→id :=E { :=trip(:=， entry()， )} (2) E→E 1+E2 { := trip(+， ， )} (3) E→E 1*E2 { := trip(*， ， )} (4) E→(E 1) { := } (5) E→ E1 { := trip(， ， )} (6) E→id { := entry()} Ax := E5E1 + E4a E2 * E3b c.code=a .code=b .code=c .code=(1)(*,b,c) .code=(3)(:=,x,(2)) .code=(2)(+,a,(1)) 三元式序列： (1) (*, b, c ) (2) (+, a,(1)) (3) (:=,x,(2)) 例 生成 x:=a+b*c的三元式 (LR分析 ) 29 3 三地址碼的實(shí)現(xiàn)（續(xù) 3） 四元式是對(duì)三元式的改進(jìn) ， 將表示計(jì)算結(jié)果的三元式序號(hào)用一個(gè)顯式的變量表示 ， 從而避免了三元式的值與三元式在三元組中的位臵相關(guān)的弱點(diǎn) 。 四元式的種類 四元式： 三地址碼： (op， arg1， arg2， result) result := arg1 op arg2 31 3 三地址碼的實(shí)現(xiàn)（續(xù) 5） 1. 屬性 .code： 表示存放運(yùn)算結(jié)果的變量； 2. 函數(shù) newtemp： 返回一個(gè)新的臨時(shí)變量 ， 如 T1， T2， ...等； 3. 過程 emit( op， arg1， arg2, result)： 生成一個(gè)四元式，若為一元運(yùn)算，則 arg2可空。 emit(*， ,)} {:=} {:=newtemp。 三元式、四元式與樹的語義規(guī)則設(shè)計(jì)的相似性 34 3 樹的優(yōu)化表示－ DAG 如果樹上若干個(gè)節(jié)點(diǎn)有完全相同的孩子 ， 則這些節(jié)點(diǎn)可以指向同一個(gè)孩子 ， 形成一個(gè)有向無環(huán)圖 （ Directed Acyclic Graph, DAG） 。 x:=*+ +a b a bT 1 / ( 1 ) T 2 / ( 2 )T 3 / ( 3 )T 4 / ( 4 )x:=*+a bT 3 / ( 3 )T 2 / ( 2 )T 1 / ( 1 )35 4 樹與其他中間代碼的關(guān)系 1. 樹表示的中間代碼與后綴式和三地址碼之間有內(nèi)在聯(lián)系； 2. 對(duì)樹進(jìn)行深度優(yōu)先后序遍歷 ， 得到的線性序列就是后綴式， 或者說后綴式是樹的一個(gè)線性化序列； 3. 樹的每個(gè)內(nèi)部節(jié)點(diǎn)和它的孩子對(duì)應(yīng)一個(gè)三元式或四元式。 ? 正確存儲(chǔ)各類信息； ? 適應(yīng)不同階段的需求； ? 便于有效地進(jìn)行查找 、 插入 、 刪除和修改等操作； ? 空間可以動(dòng)態(tài)擴(kuò)充 。 ? 存放方式： 關(guān)鍵字＋屬性 。 { double x。 關(guān) 鍵 字 屬 性X . . .任 何 復(fù) 雜結(jié) 構(gòu)42 名字的作用域 程序設(shè)計(jì)語言的名字可以出現(xiàn)在不同的范圍內(nèi) ， 并且可以具有不同的意義 。并列的兩個(gè)范圍內(nèi)的名字作用域互不相干，但是分別在嵌套的兩個(gè)范圍內(nèi)的名字，其作用域的問題就需要制定規(guī)則來限定，以使得任何一個(gè)名字在任何范圍內(nèi)涵義都是無二義的。 ① 程序塊 B中聲明的作用域包括 B； ② 如果名字 x不在 B中聲明 ， 那么 B中 x的出現(xiàn)是在外圍程序塊B39。 例子：找人 張三；一班張三；軟件學(xué)院張三；西電張三 45 名字的作用域（續(xù) 3） 例 符合作用域規(guī)則的 C++程序 。 /* B1層 ， 被 B0嵌套 */ printf(%d %d\n, a, b)。 /* B3層 ， 與 B2并列 */ printf(%d %d\n, a, b)。 // B1 4 { int a=2, c=4, d=5。 // B1 4 { int a=2, c=4, d=5。 修改可以用刪除＋插入代替 。 01ikm1S1 S2S3 S4其中：hash(S1)=hash(S2)=i hash(S3)=hash(S4)=k名字掛在兩個(gè)鏈上 (便于刪除操作 )： 1. 散列鏈 (hash link)： 鏈接所有具有相同 hash值的元素 ，