主講人：范敏陳意云張昱高等教育出版社編譯原理

-42023/9/1第4章語法制導(dǎo)的翻譯2引入復(fù)習詞法分析的任務(wù)和正規(guī)式的作用語法分析的任務(wù)和文法的作用思考語言結(jié)構(gòu)的屬性如何計算？何時計算？屬性值如何存放？2023/9/1第4章語法制導(dǎo)的翻譯3第1章編譯器概述第2章詞法分析第3章語法分析第4章語法制導(dǎo)的翻譯第5章類型檢查第6章運行時存儲空間的組織和管理第7章中間代碼生成第8章代碼生成第9章*代碼優(yōu)化第10章*編譯系統(tǒng)和運行系統(tǒng)第11章*面向?qū)ο笳Z言的編譯第12章*函數(shù)式語言的編譯目錄2023/9/1第4章語法制導(dǎo)的翻譯44.1語法制導(dǎo)的定義4.2S屬性定義的自下而上計算4.3L屬性定義的自上而下計算4.4L屬性的自下而上計算4.5遞歸計算第4章語法制導(dǎo)的翻譯2023/9/1第4章語法制導(dǎo)的翻譯5本章內(nèi)容介紹一種形式化的語義描述方法語法制導(dǎo)的翻譯，包括它的兩種具體形式：語法制導(dǎo)的定義和翻譯方案介紹語法制導(dǎo)的翻譯的實現(xiàn)方法2023/9/1第4章語法制導(dǎo)的翻譯6本章學(xué)習目標掌握綜合屬性、繼承屬性、語法樹、翻譯方案等概念掌握語法制導(dǎo)的定義方法掌握S屬性和L屬性的計算方法2023/9/1第4章語法制導(dǎo)的翻譯74.1語法制導(dǎo)的定義例：簡單臺式計算器的語法制導(dǎo)定義基礎(chǔ)文法(產(chǎn)生式)

語

義

規(guī)

則

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval注意基礎(chǔ)文法與拓廣文法的區(qū)別2023/9/1第4章語法制導(dǎo)的翻譯8基礎(chǔ)文法基礎(chǔ)文法是語法制導(dǎo)定義中的文法。其中，每個文法符號都有一組可以用于計算的屬性每個產(chǎn)生式A

有一組形式為b:=f(c1,c2,…,ck)的語義規(guī)則。其中f是函數(shù)，b,c1,c2,…,ck

是文法符號的屬性語義規(guī)則一組計算表達式計算相應(yīng)產(chǎn)生式中文法符號的屬性值4.1.1語法制導(dǎo)定義的形式2023/9/1第4章語法制導(dǎo)的翻譯9文法符號屬性分類繼承屬性：如果b是產(chǎn)生式右部某個文法符號X的屬性，c1,c2,…,ck

是產(chǎn)生式左部文法符號A的屬性或產(chǎn)生式右部文法符號屬性綜合屬性：如果b是A的屬性，c1,c2,…,ck

是產(chǎn)生式右部文法符號屬性或A的繼承屬性bbb:=f(c1,c2,…,ck)A

X

B屬于子結(jié)點B屬于父結(jié)點2023/9/1第4章語法制導(dǎo)的翻譯10S屬性定義：僅使用綜合屬性的語法制導(dǎo)定義產(chǎn)

生

式

語

義

規(guī)

則

L

E

n

print(E.val)虛擬屬性

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.1.2綜合屬性如何計算綜合屬性值？2023/9/1第4章語法制導(dǎo)的翻譯118+5*2n的計算：1.根據(jù)基礎(chǔ)文法畫出推導(dǎo)出句子的分析樹digitLEnTETFdigitT+*FFdigit2023/9/1第4章語法制導(dǎo)的翻譯128+5*2n的計算：2.標出分析樹中每個結(jié)點的屬性（如果有）digit.lexvalLE.valn

換行符T.valE.valT.valF.valdigit.lexvalT.val+*F.valF.valdigit.lexval注意注釋分析樹與分析樹之間的區(qū)別2023/9/1第4章語法制導(dǎo)的翻譯138+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.valT.valF.valdigit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章語法制導(dǎo)的翻譯148+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.valT.valF.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章語法制導(dǎo)的翻譯158+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.valT.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章語法制導(dǎo)的翻譯168+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章語法制導(dǎo)的翻譯178+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯188+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.val=5F.valdigit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯198+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯208+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯218+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯228+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.valnT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯238+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯248+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章語法制導(dǎo)的翻譯258+5*2n的計算：3.分析樹各結(jié)點屬性的計算可以自下而上、從左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5打印E屬性值Print(E.val)2023/9/1第4章語法制導(dǎo)的翻譯26利用分析樹對S屬性定義中綜合屬性的計算方法小結(jié)畫出句子（詞法記號流符號串）的分析樹標出每個結(jié)點的屬性（如果有）根據(jù)語義規(guī)則自下而上、從左到右完成各個結(jié)點屬性的計算2023/9/1第4章語法制導(dǎo)的翻譯27intid,id,id文法產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

4.1.3繼承屬性如何計算繼承屬性值？2023/9/1第4章語法制導(dǎo)的翻譯28intid1,id2,id3的注釋分析樹分析樹DintT,id3LLLid2id1,2023/9/1第4章語法制導(dǎo)的翻譯29intid1,id2,id3的注釋分析樹在注釋分析樹每個L結(jié)點，除傳遞繼承屬性in給子結(jié)點L1外，addtype過程在符號表中將L右子結(jié)點上標識符id的類型記為整型：addtype(id.entry,L.in)

DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,包含結(jié)點屬性T.typeid.entryL.in，虛擬屬性L1.in:=L.in2023/9/1第4章語法制導(dǎo)的翻譯30intid1,id2,id3的分析樹的依賴圖

描述結(jié)點屬性間依賴關(guān)系的有向圖稱為依賴圖

D

TL

{L.in:=T.type}4.1.4屬性依賴圖DintTLin

54type所有屬性可用結(jié)點表示2023/9/1第4章語法制導(dǎo)的翻譯31intid1,id2,id3的分析樹的依賴圖

L

L1,

id{L1.in:=L.in;

addtype(id.entry,L.in)}

DintT,id3LLLid2id1,1entry102entry3entryin

98in

76in

54typeaddtype(id.entry,L.in)導(dǎo)致的虛擬屬性注意：L有兩個屬性(繼承屬性in和虛擬屬性)2023/9/1第4章語法制導(dǎo)的翻譯32拓撲排序：屬性結(jié)點出現(xiàn)順序的一種排序，使得有向邊只從該次序中先出現(xiàn)的結(jié)點指向后出現(xiàn)的結(jié)點例：1，2，3，4，5，6，7，8，9，104.1.5屬性計算次序DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type只有結(jié)點屬性傳遞的方向性不夠2023/9/1第4章語法制導(dǎo)的翻譯33屬性計算過程（1）構(gòu)造輸入串的分析樹DintT,id3LLLid2id1,2023/9/1第4章語法制導(dǎo)的翻譯34屬性計算過程（1）構(gòu)造輸入串的分析樹；（2）構(gòu)造屬性依賴圖DintT,id3LLLid2id1,entryentryentryininintype2023/9/1第4章語法制導(dǎo)的翻譯35屬性計算過程（1）構(gòu)造輸入串的分析樹；（2）構(gòu)造屬性依賴圖；（3）對屬性結(jié)點進行拓撲排序DintT,id3LLLid2id1,1entry102entry3entryin98in76in54typeaddtype(id.entry,L.in)導(dǎo)致的虛擬屬性2023/9/1第4章語法制導(dǎo)的翻譯36屬性計算過程（1）構(gòu)造輸入串的分析樹；（2）構(gòu)造屬性依賴圖；（3）對屬性結(jié)點進行拓撲排序；（4）按拓撲排序的次序計算屬性DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type2023/9/1第4章語法制導(dǎo)的翻譯37DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type屬性計算過程a4:=integer;a5:=a4;addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7;addtype(id1.entry,a9);2023/9/1第4章語法制導(dǎo)的翻譯38語義規(guī)則的計算方法2023/9/1第4章語法制導(dǎo)的翻譯39語義規(guī)則的計算方法分析樹方法：前面介紹方法（編譯速度慢）2023/9/1第4章語法制導(dǎo)的翻譯40語義規(guī)則的計算方法分析樹方法：前面介紹方法（編譯速度慢）基于規(guī)則的方法：基于事先靜態(tài)確定語義規(guī)則的計算次序（手工構(gòu)造編譯器，時空改善）2023/9/1第4章語法制導(dǎo)的翻譯41語義規(guī)則的計算方法分析樹方法：前面介紹方法（編譯速度慢）基于規(guī)則的方法：基于事先靜態(tài)確定語義規(guī)則的計算次序（手工構(gòu)造編譯器，時空改善）忽略規(guī)則的方法：事先確定屬性的計算策略（如邊分析邊計算），那么語義規(guī)則的設(shè)計必須符合所選分析方法的限制（時空改善）2023/9/1第4章語法制導(dǎo)的翻譯42本節(jié)小結(jié)介紹了語法制導(dǎo)定義、繼承屬性、綜合屬性、屬性依賴圖、拓撲順序等概念詳細介紹了利用分析樹計算屬性的方法簡單對比了屬性計算的三種方法2023/9/1第4章語法制導(dǎo)的翻譯43作業(yè)P140：12023/9/1第4章語法制導(dǎo)的翻譯44思考語言結(jié)構(gòu)屬性計算的基礎(chǔ)是什么？依賴圖和拓撲順序有什么作用？它們對計算S屬性定義中的綜合屬性是否有用？計算語言結(jié)構(gòu)屬性的步驟是什么？本節(jié)在語法制導(dǎo)定義的基礎(chǔ)上通過分析樹研究了屬性計算次序的問題，那么如何在此基礎(chǔ)上編程實現(xiàn)呢？2023/9/1第4章語法制導(dǎo)的翻譯454.2S屬性定義的自下而上計算

語法樹是分析樹的濃縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點語法樹的例子：if-then-elseBS1S24.2.1語法樹算符運算對象ifBthenS1elseS2復(fù)習S屬性定義？2023/9/1第4章語法制導(dǎo)的翻譯464.2S屬性定義的自下而上計算

語法樹是分析樹的濃縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點語法樹的例子：if-then-elseBS1S24.2.1語法樹算符運算對象ifBthenS1elseS28+5*2算符優(yōu)先級別？2023/9/1第4章語法制導(dǎo)的翻譯474.2S屬性定義的自下而上計算

語法樹是分析樹的濃縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點語法樹的例子：if-then-elseBS1S2+*84.2.1語法樹算符運算對象ifBthenS1elseS28+5*22023/9/1第4章語法制導(dǎo)的翻譯484.2S屬性定義的自下而上計算

語法樹是分析樹的濃縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點語法樹的例子：if-then-elseBS1S2+*2584.2.1語法樹算符運算對象ifBthenS1elseS28+5*22023/9/1第4章語法制導(dǎo)的翻譯494.2S屬性定義的自下而上計算

語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為內(nèi)部結(jié)點語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹if-then-elseBS1S2+*2584.2.1語法樹算符運算對象ifBthenS1elseS28+5*22023/9/1第4章語法制導(dǎo)的翻譯504.2.2構(gòu)造語法樹的語法制導(dǎo)定義語法樹的存儲語法樹的結(jié)點可以用有若干域的記錄來實現(xiàn)對于算符結(jié)點：一個域存放算符，該域作為該結(jié)點的標記，其余兩個域含指向運算對象的指針三地址對于基本運算對象結(jié)點：一個域存放運算對象類別，另一個域存放其值二地址用于語法制導(dǎo)翻譯時，一個結(jié)點可能還有其它域來保存加在該結(jié)點的其它屬性值（即域中保存屬性值存儲位置的指針）結(jié)點的類型2023/9/1第4章語法制導(dǎo)的翻譯51產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf

(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

用于構(gòu)造算術(shù)表達式語法樹的語法制導(dǎo)定義mkleaf(id,entry)：建立標識符id的結(jié)點，結(jié)點的entry域用于存放該標識符條目的指針2023/9/1第4章語法制導(dǎo)的翻譯52產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf

(num,num.val)

用于構(gòu)造算術(shù)表達式語法樹的語法制導(dǎo)定義mkleaf(num,val)：建立數(shù)num的結(jié)點，結(jié)點的val域用于存放該數(shù)值2023/9/1第4章語法制導(dǎo)的翻譯53產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

用于構(gòu)造算術(shù)表達式語法樹的語法制導(dǎo)定義mknode(op,left,right)：建立算符op的結(jié)點，指針域left和right分別存放該算符左、右運算對象的指針2023/9/1第4章語法制導(dǎo)的翻譯54a+5*b的語法樹的構(gòu)造P112結(jié)點屬性E.nptrT.nptrF.nptrE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口變量aleftright數(shù)值5變量b2023/9/1第4章語法制導(dǎo)的翻譯55a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯56a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯57a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯58a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯59a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯60a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯61a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯62a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口aleftright5b自下而上、從左到右構(gòu)造語法樹2023/9/1第4章語法制導(dǎo)的翻譯63a+5*b的語法樹的構(gòu)造+id*numid2023/9/1第4章語法制導(dǎo)的翻譯64S屬性可以由自下而上分析器在語法分析輸入時完成計算，即“邊分析邊計算”自下而上分析器用棧保存已經(jīng)分析的子樹的信息，S屬性定義的翻譯器可以借助LR分析器的生成器來實現(xiàn)LR分析器可以把文法符號的綜合屬性放在它的棧內(nèi)，每當歸約時，根據(jù)出現(xiàn)在棧頂?shù)漠a(chǎn)生式右部符號串中符號的屬性來計算左部符號的綜合屬性4.2.3S屬性的自下而上計算復(fù)習LR分析器的工作原理：棧內(nèi)可以不存儲文法符號綜合屬性來自于子節(jié)點或自身的繼承屬性2023/9/1第4章語法制導(dǎo)的翻譯65將LR分析器增加一個域來保存綜合屬性值ZZ.zYY.yXX.x......棧statevaltop2023/9/1第4章語法制導(dǎo)的翻譯66將LR分析器增加一個域來保存綜合屬性值ZZ.zYY.yXX.x......棧statevaltop若產(chǎn)生式A

→XYZ的語義規(guī)則是A.a:=f(X.x,Y.y,Z.z)右部符號從左至右壓入棧內(nèi)2023/9/1第4章語法制導(dǎo)的翻譯67將LR分析器增加一個域來保存綜合屬性值ZZ.zYY.yXX.x......若產(chǎn)生式A

→XYZ的語義規(guī)則是A.a:=f(X.x,Y.y,Z.z)，那么歸約后：......AA.a......棧statevaltoptoptop=top-2Top’2023/9/1第4章語法制導(dǎo)的翻譯68例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

語義規(guī)則

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexvalTop’2023/9/1第4章語法制導(dǎo)的翻譯69例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexvalTop’2023/9/1第4章語法制導(dǎo)的翻譯70例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

nEE.val............產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置Top’2023/9/1第4章語法制導(dǎo)的翻譯71例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

TT.val+EE.val......產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置Top’2023/9/1第4章語法制導(dǎo)的翻譯72例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

TT.val..................產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不變

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置2023/9/1第4章語法制導(dǎo)的翻譯73例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

FF.val*TT.val......產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不變

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置Top’2023/9/1第4章語法制導(dǎo)的翻譯74例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

FF.val..................產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不變

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不變

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置2023/9/1第4章語法制導(dǎo)的翻譯75例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

)EE.val(......產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不變

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不變

F

(E)

val[top

2]

:=val[top

1]

F

digit

F.val:=digit.lexval棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置Top’2023/9/1第4章語法制導(dǎo)的翻譯76例：臺式計算器的語法制導(dǎo)定義改成棧操作代碼

digitdigit.lexval..................產(chǎn)

生

式

代碼段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不變

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不變

F

(E)

val[top

2]

:=val[top

1]

F

digit

val[top]不變棧statevaltop:=左邊為歸約后左部文法符號的屬性值，下標為值的存儲位置2023/9/1第4章語法制導(dǎo)的翻譯774.3L屬性定義的自上而下計算邊分析邊翻譯的方式能否用于繼承屬性？屬性的計算次序受分析方法所限定的分析樹結(jié)點建立次序的限制2023/9/1第4章語法制導(dǎo)的翻譯784.3L屬性定義的自上而下計算邊語法分析邊翻譯的方式能否用于繼承屬性？屬性的計算次序受分析方法所限定的分析樹結(jié)點建立次序的限制語法分析方法的共同特點：分析樹的結(jié)點是自左向右生成如果屬性信息自左向右流動，那么就有可能在分析的同時完成L屬性計算L代表屬性從左向右傳遞的方向2023/9/1第4章語法制導(dǎo)的翻譯79（1）如果每個產(chǎn)生式A

X1

X2…Xj…Xn

的每條語義規(guī)則計算的屬性是A的綜合屬性；或者（2）如果是Xj

的繼承屬性，1

j

n,但它僅依賴于：該產(chǎn)生式中Xj左邊（兄弟結(jié)點）符號X1,X2,…,Xj-1的屬性A的繼承屬性 那么語法制導(dǎo)定義是L屬性定義4.3.1L屬性定義2023/9/1第4章語法制導(dǎo)的翻譯80（1）如果每個產(chǎn)生式A

X1

X2…Xj…Xn

的每條語義規(guī)則計算的屬性是A的綜合屬性；或者（2）如果是Xj

的繼承屬性，1

j

n,但它僅依賴于：該產(chǎn)生式中Xj左邊（兄弟結(jié)點）符號X1,X2,…,Xj-1的屬性A的繼承屬性 那么語法制導(dǎo)定義是L屬性定義S屬性定義是L屬性定義的一個特例2023/9/1第4章語法制導(dǎo)的翻譯81例：變量類型聲明的語法制導(dǎo)定義是一個L屬性定義

產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

2023/9/1第4章語法制導(dǎo)的翻譯82計算屬性需要考慮執(zhí)行語義規(guī)則的時機翻譯方案將語義動作放在{}內(nèi)，并將它當作文法符號插入產(chǎn)生式右部任何位置語義動作插入的位置就是產(chǎn)生式的項目中的點的位置執(zhí)行時機：當語法分析到該文法符號（語義動作）而進行推導(dǎo)或歸約時，執(zhí)行該語義動作4.3.2翻譯方案什么是項目？2023/9/1第4章語法制導(dǎo)的翻譯83只有綜合屬性的翻譯方案的建立 首先為每條語義規(guī)則建立一個放在一對{}括號內(nèi)賦值動作，然后把這些動作分別放在對應(yīng)產(chǎn)生式右部的末端2023/9/1第4章語法制導(dǎo)的翻譯84例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)}

2023/9/1第4章語法制導(dǎo)的翻譯85例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}

R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章語法制導(dǎo)的翻譯86例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章語法制導(dǎo)的翻譯87例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章語法制導(dǎo)的翻譯88例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

關(guān)注動作2023/9/1第4章語法制導(dǎo)的翻譯89例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

關(guān)注動作2023/9/1第4章語法制導(dǎo)的翻譯90例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5

2，則輸出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

關(guān)注動作2023/9/1第4章語法制導(dǎo)的翻譯91有繼承屬性的翻譯方案的建立

建立含有繼承屬性翻譯方案的規(guī)則： （1）產(chǎn)生式右部符號的繼承屬性必須在先于該符號的動作中計算 （2）一個動作不能引用該動作右邊符號的綜合屬性

（3）左部非終結(jié)符的綜合屬性只能在它所引用的所有屬性都計算完后才能計算，且計算該屬性的動作通常放在產(chǎn)生式右部末端2023/9/1第4章語法制導(dǎo)的翻譯92例：數(shù)學(xué)排版語言EQN

Esub1.valS

BB

B1B2

B

B1

subB2B

textE1.valS

BB1B2B1subB2B2textsubtexttext2023/9/1第4章語法制導(dǎo)的翻譯93例：數(shù)學(xué)排版語言EQN（B.ps為繼承屬性）

Esub1.val產(chǎn)

生

式

語

義

規(guī)

則

S

B

B.ps:=10;S.ht:=B.ht

B

B1B2

B1.ps:=B.ps;B2.ps:=B.ps;B.ht:=max(B1.ht,B2.ht)B

B1

subB2

B1.ps:=B.ps;B2.ps:=shrink(B.ps);B.ht:=disp(B1.ht,B2.ht)B

text

B.ht:=text.h

*B.ps

E1.val2023/9/1第4章語法制導(dǎo)的翻譯94例：數(shù)學(xué)排版語言EQN（B.ps為繼承屬性）

S

{B.ps:=10} B {S.ht:=B.ht}

B

{B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B

{B1.ps:=B.ps}

B1 sub {B2.ps:=shrink(B.ps)} B2 {B.ht:=disp(B1.ht,B2.ht)}

B

text {B.ht:=text.h

*B.ps}規(guī)則一規(guī)則三2023/9/1第4章語法制導(dǎo)的翻譯95例：左遞歸的消除可能引起繼承屬性(可能原 來只有綜合屬性）-算術(shù)表達式語法制導(dǎo)定義產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

2023/9/1第4章語法制導(dǎo)的翻譯96 算術(shù)表達式文法

E

E+T|T

T

T

*

F|F

F

(E)|id 消除左遞歸后文法：

E

TR R

+TR1

|

T

FW

W

*

FW1

|

F

(E)|idA

Aa|b消除直接左遞歸：A

bA

A

aA

|

其中：R和W為引入的輔助文法符號2023/9/1第4章語法制導(dǎo)的翻譯97E

T {R.i:=T.nptr}

R

{E.nptr:=R.s}R

+ T {R1.i

:=mknode(‘+’,R.i,T.nptr)}

R1

{R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr}

W

{T.nptr:=W.s}W

* F {W1.i

:=mknode(‘*’,W.i,F.nptr)}

W1

{W.s:=W1.s}W

{W.s:=W.i}F

(E) {F.nptr:=E.nptr}F

id {F.nptr:=mkleaf(id,id.entry)}F

num {F.nptr:=mkleaf(num,num.entry)}R和W的i屬性是繼承屬性2023/9/1第4章語法制導(dǎo)的翻譯98E

T {R.i:=T.nptr} R {E.nptr:=R.s}R

+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=W.s}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}F

(E) {F.nptr:=E.nptr}F

id {F.nptr:=mkleaf(id,id.entry)}F

num {F.nptr:=mkleaf(num,num.entry)}2023/9/1第4章語法制導(dǎo)的翻譯99用算術(shù)表達式語法制導(dǎo)定義構(gòu)造a*5*b語法樹12345678910111213141516TF.nptrF.nptridi

W**F.nptridnumididnum5**指向符號表中a的入口指向符號表中b的入口i

W

siW

略去了E

TR

T

部分遞歸：自上而下從左到右推導(dǎo)而非歸約2023/9/1第4章語法制導(dǎo)的翻譯100把預(yù)測分析器的構(gòu)造方法推廣到翻譯方案的 實現(xiàn)（每個非終結(jié)符都對應(yīng)一個過程或函數(shù)）——參見p126算法4.1）：適用于自上而下分析例：產(chǎn)生式R

+TR|

的分析過程： procedureR; begin iflookahead=‘+’thenbegin match(‘+’);T;R end elsebegin/*

什么也不做*/ end end

4.3.3預(yù)測分析器的設(shè)計預(yù)測分析器的特點？2023/9/1第4章語法制導(dǎo)的翻譯101產(chǎn)生式R

+TR|

的語法樹的遞歸下降構(gòu)造：functionR(i:

syntax_tree_node):

syntax_tree_node; var nptr,i1,s1,s:

syntax_tree_node;

addoplexeme:char; begin iflookahead=‘+’thenbegin /*

匹配產(chǎn)生式R

+TR

*/ addoplexeme:=lexval;/*

載入運算符*/ match(‘+’); nptr:=T;

i1:=mknode(addoplexme,i,nptr);

s1:=R(i1);

s:=s1 end elses:=i;/*

產(chǎn)生式

R

*/ returns end;R:i,sT:nptr+:addoplexeme2023/9/1第4章語法制導(dǎo)的翻譯102改變文法可能導(dǎo)致繼承屬性或綜合屬性例如：消除左遞歸可能產(chǎn)生繼承屬性

Pascal的聲明，如m,n:integer D

L:T

T

integer|char

L

L,id|id4.3.4用綜合屬性代替繼承屬性2023/9/1第4章語法制導(dǎo)的翻譯103Pascal的聲明，如m,n:integer D

L:T

T

integer|char

L

L,id|id改成從右向左歸約 D

idL

L

,idL|:T

T

integer|char2023/9/1第4章語法制導(dǎo)的翻譯104Pascal的聲明，如m,n:integer D

L:T

T

integer|char

L

L,id|id改成從右向左歸約 D