13.第六章屬性文法與語法制導(dǎo)翻譯(2)

1、6/13/20211第第6章屬性文法與章屬性文法與語法制導(dǎo)翻譯語法制導(dǎo)翻譯6/13/20212n屬性文法屬性文法n綜合屬性與繼承屬性綜合屬性與繼承屬性nS_屬性文法屬性文法nL_屬性文法屬性文法n語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述n翻譯模式翻譯模式6/13/202136.3 S-6.3 S-屬性文法的自下而上計(jì)算屬性文法的自下而上計(jì)算 nS- S-屬性文法屬性文法：只含有綜合屬性：只含有綜合屬性n綜合屬性可以在分析輸入符號串的同時(shí)綜合屬性可以在分析輸入符號串的同時(shí)由自下而上的分析器來計(jì)算。由自下而上的分析器來計(jì)算。n分析器可以保存與棧中文法符號有關(guān)的分析器可以保存與棧中文法符號有關(guān)的綜合屬性值，

2、每當(dāng)進(jìn)行歸約時(shí)，新的屬綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計(jì)算。號的屬性值來計(jì)算。 6/13/20214n在分析棧中使用一個(gè)附加的域來存放綜合在分析棧中使用一個(gè)附加的域來存放綜合屬性值屬性值 n假設(shè)語義規(guī)則假設(shè)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)A.a:=f(X.x,Y.y,Z.z)是對應(yīng)是對應(yīng)于產(chǎn)生式于產(chǎn)生式AXYZAXYZ的的 6/13/20215產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnLEnprint(valtop) print(valtop) EEEE1 1+T+Tvalvalntopntop :=

3、valtop-2+valtop := valtop-2+valtop ETETTTTT1 1* *F Fvalvalntopntop := valtop-2 := valtop-2* *valtop valtop TFTFF (E)F (E)valvalntopntop :=valtop-1 :=valtop-1Fdigit Fdigit 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 LEn print(E.val) LEn print(E.val) EEEE1 1+T E.val := E+T E.val := E1 1.val+T.val .val+T.val ET E.val :=T.val

4、 ET E.val :=T.val TTTT1 1* *F T.val :=TF T.val :=T1 1.val.val* * F.val F.val TF TF T.val :=F.val T.val :=F.val F (E) F.val :=E.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvalFdigit F.val :=digit.lexval6/13/20216 輸入輸入 state statesymsym val val 用到的產(chǎn)生式用到的產(chǎn)生式 3 3* *5+4n 05+4n 0 # # - - * *5+4n 055+4

5、n 05#3#3 -3 -3 * *5+4n 03 5+4n 03 #F#F -3 -3 FdigitFdigit * *5+4n 02 5+4n 02 #T#T -3 -3 TFTF 5+4n 027 5+4n 027#T#T* * -3 - -3 - +4n 0275 +4n 0275 #T#T* *5 5 -3 - 5 -3 - 5產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnLEnprint(valtop) print(valtop) EEEE1 1+T+Tvalntop := valtop-2+valtop valntop := valtop-2+valtop ETETTTTT1 1* *F

6、 Fvalntop := valtop-2valntop := valtop-2* *valtop valtop TFTFF (E)F (E)valntop :=valtop-1valntop :=valtop-1Fdigit Fdigit 6/13/20217 輸入輸入 statestatesymsym val val 用到的產(chǎn)生式用到的產(chǎn)生式 +4n 0275 +4n 0275 #T#T* *5 5 -3 - 5 -3 - 5 +4n 027 +4n 0271010#T#T* *F F -3 - 5 -3 - 5 FdigitFdigit +4n 02 +4n 02 #T#T -15 -1

7、5 TTTT* *F F +4n 01 +4n 01 #E#E -15 -15 ET ET 4n 016 4n 016 #E+ #E+ -15- -15- n 0165 n 0165 #E+4 #E+4 -15- 4 -15- 4產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnLEnprint(valtop) print(valtop) EEEE1 1+T+Tvalntop := valtop-2+valtop valntop := valtop-2+valtop ETETTTTT1 1* *F Fvalntop := valtop-2valntop := valtop-2* *valtop valto

8、p TFTFF (E)F (E)valntop :=valtop-1valntop :=valtop-1Fdigit Fdigit 6/13/20218 輸入輸入 statesym val 用到的產(chǎn)生式用到的產(chǎn)生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4Fdigit n 0169 #E+T -15- 4TF n 01#E -19 EE+T #En -19- #L -19 LEn產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*

9、valtop TFF (E)valntop :=valtop-1Fdigit 6/13/20219一遍掃描的處理方法一遍掃描的處理方法 n一遍掃描的處理方法是在語法分析的同一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值時(shí)計(jì)算屬性值 n所采用的語法分析方法所采用的語法分析方法n屬性的計(jì)算次序?qū)傩缘挠?jì)算次序nL L屬性文法屬性文法適合于一遍掃描的自上而下適合于一遍掃描的自上而下分析分析nS S屬性文法適合于一遍掃描的自下而上屬性文法適合于一遍掃描的自下而上分析分析 6/13/2021106.4 L-6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 n通過深度優(yōu)先的方法對語法樹進(jìn)行遍歷，通過

10、深度優(yōu)先的方法對語法樹進(jìn)行遍歷，計(jì)算屬性文法的所有屬性值計(jì)算屬性文法的所有屬性值nLL(1)LL(1)：自上而下分析方法，深度優(yōu)先建：自上而下分析方法，深度優(yōu)先建立語法樹立語法樹6/13/202111L- L-屬性文法屬性文法n一個(gè)屬性文法稱為一個(gè)屬性文法稱為L- L-屬性文法屬性文法，如果對于每，如果對于每個(gè)產(chǎn)生式個(gè)產(chǎn)生式AXAX1 1X X2 2XXn n，其每個(gè)語義規(guī)則中，其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是的每個(gè)屬性或者是綜合屬性，或者是X Xj j(1 (1 j j n)n)的一個(gè)繼承屬性且這個(gè)繼承屬性僅的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：依賴于：(1) (1) 產(chǎn)生式

11、產(chǎn)生式X Xj j的左邊符號的左邊符號X X1 1，X X2 2，X Xj-1j-1的屬性；的屬性；(2) A(2) A的繼承屬性。的繼承屬性。nS- S-屬性文法一定是屬性文法一定是L- L-屬性文法屬性文法6/13/202112非非L- L-屬性文法例子屬性文法例子產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 ALM ALM L.i := l(A.i) L.i := l(A.i) M.i :=m(L.s) M.i :=m(L.s) AQR AQR R.i := r(A.i) R.i := r(A.i) Q.i :=q(R.s) Q.i :=q(R.s) A.s :=f(Q.s) A.s :=f

12、(Q.s) 6/13/2021136.4.1 6.4.1 翻譯模式翻譯模式 n翻譯模式翻譯模式：給出了使用語義規(guī)則進(jìn)行：給出了使用語義規(guī)則進(jìn)行計(jì)算的次序，這樣就可把某些實(shí)現(xiàn)細(xì)計(jì)算的次序，這樣就可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來節(jié)表示出來n在翻譯模式中，和文法符號相關(guān)的屬在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里我們也稱性和語義規(guī)則（這里我們也稱語義動(dòng)語義動(dòng)作作），用花括號），用花括號 括起來，插入到產(chǎn)括起來，插入到產(chǎn)生式右部的合適位置上生式右部的合適位置上6/13/202114q翻譯模式示例：把帶加號和減號的中綴翻譯模式示例：把帶加號和減號的中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式表達(dá)式翻譯成相應(yīng)的后綴

13、表達(dá)式 ETR ETR Raddop T print(addop.lexeme) R Raddop T print(addop.lexeme) R1 1 | | Tnum print(num.val) Tnum print(num.val) 例：例：9-5+29-5+2- -E ET TR R9 9print(9)print(9)T TR R5 5print(5)print(5)print(-)print(-)+ +T T2 2print(2)print(2)R Rprint(+)print(+) 6/13/202115設(shè)計(jì)翻譯模式的原則設(shè)計(jì)翻譯模式的原則n設(shè)計(jì)翻譯模式時(shí)，必須保證當(dāng)某個(gè)動(dòng)作設(shè)

14、計(jì)翻譯模式時(shí)，必須保證當(dāng)某個(gè)動(dòng)作引用一個(gè)屬性時(shí)它必須是有定義的。引用一個(gè)屬性時(shí)它必須是有定義的。nL- L-屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引屬性文法本身就能確保每個(gè)動(dòng)作不會(huì)引用尚未計(jì)算出來的屬性。用尚未計(jì)算出來的屬性。 6/13/202116建立翻譯模式建立翻譯模式n當(dāng)只需要當(dāng)只需要綜合屬性綜合屬性時(shí)：為每一個(gè)語義規(guī)則時(shí)：為每一個(gè)語義規(guī)則建立一個(gè)包含賦值的動(dòng)作，并建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾放在相應(yīng)的產(chǎn)生式右邊的末尾 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 TTTT1 1* *F FT.val:=TT.val:=T1 1.val.valF.valF.val

15、建立產(chǎn)生式和語義動(dòng)作：建立產(chǎn)生式和語義動(dòng)作： TTTT1 1* *F F T.val:=TT.val:=T1 1.val.valF.valF.val6/13/202117建立翻譯模式建立翻譯模式n如果既有如果既有綜合屬性綜合屬性又有又有繼承屬性繼承屬性，在建立翻譯模，在建立翻譯模式時(shí)就必須保證：式時(shí)就必須保證：1. 1. 產(chǎn)生式右邊的符號的產(chǎn)生式右邊的符號的繼承屬性繼承屬性必須在這個(gè)符號以必須在這個(gè)符號以前的動(dòng)作中計(jì)算出來。前的動(dòng)作中計(jì)算出來。2. 2. 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號的一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號的綜合屬綜合屬性性。3. 3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符

16、的綜合屬性綜合屬性只有在它所引用只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾末尾。 SASA1 1A A2 2AA1 1.in:=1; A.in:=1; A2 2.in:=2.in:=2 AaAa print(A.in)print(A.in)6/13/202118基于數(shù)學(xué)格式語言基于數(shù)學(xué)格式語言EQN EQN n給定輸入給定輸入 E sub n .valE sub n .val非終結(jié)符非終結(jié)符B B（表示盒子）代表一個(gè)公式（表示盒子）代表一個(gè)公式產(chǎn)生式產(chǎn)生式B-BBB-BB

17、代表兩個(gè)盒子并置代表兩個(gè)盒子并置B-BB-B1 1 sub B sub B2 2代表代表B B2 2的大小比的大小比B B1 1小，并且放在下小，并且放在下角標(biāo)的位置角標(biāo)的位置E En n.val.valE En n.val.val6/13/202119識別輸入并進(jìn)行格式安放的識別輸入并進(jìn)行格式安放的L- L-屬性文法屬性文法 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 SBSB B.ps :=10B.ps :=10 S.ht :=B.htS.ht :=B.htBBBB1 1B B2 2 B B1 1.ps :=B.ps.ps :=B.ps B B2 2.ps :=B.ps.ps :=B.ps B.ht

18、:= max(BB.ht := max(B1 1.ht, B.ht, B2 2.ht).ht)BBBB1 1 sub B sub B2 2B B1 1.ps :=B.ps.ps :=B.ps B B2 2.ps :=shrink(B.ps).ps :=shrink(B.ps) B.ht :=disp(BB.ht :=disp(B1 1.ht, B.ht, B2 2.ht).ht)Btext Btext B.ht :=text.hB.ht :=text.hB.psB.psE En n.val.valE sub n .valE sub n .val6/13/202120翻譯模式翻譯模式S S B.

19、ps:=10B.ps:=10 B S.ht:=B.htB S.ht:=B.ht B B BB1 1.ps:=B.ps.ps:=B.ps B B1 1 B2.ps:=B.ps B2.ps:=B.ps B B2 2 B.ht:=max(B B.ht:=max(B1 1.ht,B.ht,B2 2.ht).ht) B B BB1 1.ps:=B.ps.ps:=B.ps B B1 1 sub Bsub B2 2.ps:=shrink(B.ps).ps:=shrink(B.ps) B B2 2 B.ht:=disp(B B.ht:=disp(B1 1.ht,B.ht,B2 2.ht).ht) B B te

20、xtB.ht:=text.htextB.ht:=text.hB.psB.ps1. 1. 產(chǎn)生式右邊的符號的產(chǎn)生式右邊的符號的繼承屬性繼承屬性必須在這個(gè)符必須在這個(gè)符號以前的動(dòng)作中計(jì)算出來。號以前的動(dòng)作中計(jì)算出來。2. 2. 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號的一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號的綜綜合屬性合屬性。3. 3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符的綜合屬性綜合屬性只有在它所只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常放在產(chǎn)生式右端的算這種屬性的動(dòng)作通常放在產(chǎn)生式右端的末尾末尾。6/13/2021216.4.2 6

21、.4.2 自頂向下翻譯自頂向下翻譯 n動(dòng)作是在處于相同位置上的符號被展開動(dòng)作是在處于相同位置上的符號被展開（匹配成功）時(shí)執(zhí)行的。（匹配成功）時(shí)執(zhí)行的。 n為了構(gòu)造不帶回溯的自頂向下語法分析，為了構(gòu)造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸必須消除文法中的左遞歸n當(dāng)消除一個(gè)翻譯模式的基本文法的左遞當(dāng)消除一個(gè)翻譯模式的基本文法的左遞歸時(shí)同時(shí)考慮歸時(shí)同時(shí)考慮屬性屬性適合帶適合帶綜合屬性綜合屬性的翻譯模式的翻譯模式 6/13/202122n關(guān)于算術(shù)表達(dá)式的左遞歸文法相應(yīng)的翻關(guān)于算術(shù)表達(dá)式的左遞歸文法相應(yīng)的翻譯模式譯模式EEEE1 1+T+TE.val:=EE.val:=E1 1.val+T.

22、val.val+T.valEEEE1 1-T -T E.val:=EE.val:=E1 1.val-T.val.val-T.valETET E.val:=T.valE.val:=T.valT(E)T(E)T.val:=E.valT.val:=E.valTnumTnumT.val:=num.valT.val:=num.valE T RE T RR + T RR + T R1 1R - T RR - T R1 1R R T ( E )T ( E )T numT num6/13/202123n消除左遞歸，構(gòu)造新的翻譯模式消除左遞歸，構(gòu)造新的翻譯模式 E TE TR.i:=T.valR.i:=T.va

23、l R RE.val:=R.sE.val:=R.sR +R + T TRR1 1.i:=R.i+T.val.i:=R.i+T.val R R1 1R.s:=RR.s:=R1 1.s.sR -R - T TRR1 1.i:=R.i-T.val.i:=R.i-T.val R R1 1R.s:=RR.s:=R1 1.s.sR R R.s:=R.iR.s:=R.iT ( E )T ( E )T.val:=E.valT.val:=E.valT numT numT.val:=num.valT.val:=num.valE T RE T RR +TRR +TR1 1R -TRR -TR1 1R R T ( E

24、 )T ( E )T numT numR.i: RR.i: R前面子表達(dá)式前面子表達(dá)式 的值的值R.s: R.s: 分析完分析完R R時(shí)子表時(shí)子表 達(dá)式的值達(dá)式的值6/13/202124計(jì)算表達(dá)式計(jì)算表達(dá)式9 95 52 2 E ET TR Rnumnumnum.val=9num.val=9T.val=9T.val=9R.i=9R.i=9- -T TR Rnumnumnum.val=5num.val=5T.val=5T.val=5R.i=4R.i=4+ +T TR Rnumnumnum.val=2num.val=2T.val=2T.val=2R.i=6R.i=6 R.s=6R.s=6R.s=6

25、R.s=6R.s=6R.s=6E.val=6E.val=6E TE T R.i:=T.val R.i:=T.val R R E.val:=R.s E.val:=R.s R +R + T T R R1 1.i:=R.i+T.val .i:=R.i+T.val R R1 1 R.s:= R R.s:= R1 1.s .s R -R - T T R R1 1.i:=R.i-T.val .i:=R.i-T.val R R1 1 R.s:= R R.s:= R1 1.s .s R R R.s:=R.i R.s:=R.i T ( E ) T.val:=E.val T ( E ) T.val:=E.val

26、T num T.val:=num.val T num T.val:=num.val 6/13/202125一般方法一般方法n假設(shè)有翻譯模式：假設(shè)有翻譯模式： AAAA1 1Y YA.a:=A.a:=g(Ag(A1 1.a,Y.y).a,Y.y) AX AXA.a:=A.a:=f(X.x)f(X.x) 它的每個(gè)文法符號都有一個(gè)綜合屬性，用小寫它的每個(gè)文法符號都有一個(gè)綜合屬性，用小寫字母表示，字母表示，g g和和f f是任意函數(shù)。是任意函數(shù)。q消除左遞歸：消除左遞歸： AXRAXR RYR | RYR | q翻譯模式變?yōu)榉g模式變?yōu)?：A XA XR.i:=R.i:=f (X.x)f (X.x)

27、R RA.a:=R.sA.a:=R.sR Y R Y RR1 1.i:=.i:=g(R.i,Y.y)g(R.i,Y.y) R R1 1R.s:=RR.s:=R1 1.s.sR R R.s:=R.iR.s:=R.iR.i: RR.i: R前面子表達(dá)式前面子表達(dá)式 的值的值R.s: R.s: 分析完分析完R R時(shí)子表時(shí)子表 達(dá)式的值達(dá)式的值6/13/202126XYY XYY X XA A A.a=f(X.x)A.a=f(X.x) Y Y1 1A A A.a=g(f(X.x),YA.a=g(f(X.x),Y1 1.y).y)Y Y2 2A A A.a=g(g(f(X.x),YA.a=g(g(f(X

28、.x),Y1 1.y), Y.y), Y2 2.y) .y) AAAA1 1Y YA.a:=A.a:=g(Ag(A1 1.a,Y.y).a,Y.y) AXAXA.a:=A.a:=f(X.x)f(X.x) 6/13/202127XYY XYY A AX XR R R.i=f(X.x)R.i=f(X.x)Y Y1 1R R R.i= g(f(X.x),YR.i= g(f(X.x),Y1 1.y).y)Y Y2 2R R R.i= g(g(f(X.x),YR.i= g(g(f(X.x),Y1 1.y), Y.y), Y2 2.y) .y) R.s= g(g(f(X.x),YR.s= g(g(f(X.

29、x),Y1 1.y), Y.y), Y2 2.y) .y) R.s= g(g(f(X.x),YR.s= g(g(f(X.x),Y1 1.y), Y.y), Y2 2.y).y)R.s= g(g(f(X.x),YR.s= g(g(f(X.x),Y1 1.y), Y.y), Y2 2.y).y)A.a= g(g(f(X.x),YA.a= g(g(f(X.x),Y1 1.y), Y.y), Y2 2.y).y)A XA X R.i:= R.i:=f (X.x)f (X.x) R A.a:=R.s R A.a:=R.sR Y RR Y R1 1.i:=.i:=g(R.i,Y.y)g(R.i,Y.y)

30、R R1 1 R.s:=R R.s:=R1 1.s.sR R R.s:=R.i R.s:=R.i6/13/202128構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化成翻譯模式成翻譯模式 EEEE1 1+T+TE.nptr:=mknode(+,EE.nptr:=mknode(+,E1 1.nptr,T.nptr).nptr,T.nptr)EEEE1 1-T-TE.nptr:=mknode(-E.nptr:=mknode(-,E,E1 1.nptr,T.nptr).nptr,T.nptr)ETETE.nptr:=T.nptrE.nptr:=T.nptr6/13/202129構(gòu)造抽

31、象語法樹的屬性文法定義轉(zhuǎn)化成構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化成翻譯模式翻譯模式 E E T TR.i:=T.nptrR.i:=T.nptr R RE.nptr:=R.sE.nptr:=R.sR R + + T TRR1 1.i:=mknode(+,R.i,T.nptr).i:=mknode(+,R.i,T.nptr) R R1 1R.s:=RR.s:=R1 1.s.sR R - - T TRR1 1.i:=mknode(.i:=mknode(,R.i,T.nptr),R.i,T.nptr) R R1 1R.s:=R.sR.s:=R.sR R R.s:=R.iR.s:=R.iT T ( E )(

32、 E )T.nptr:=E.nptrT.nptr:=E.nptrT T ididT.nptr:=mkleaf(id,id.entry)T.nptr:=mkleaf(id,id.entry)T T numnumT.nptr:=mkleaf(num,num.val)T.nptr:=mkleaf(num,num.val)6/13/202130使用繼承屬性構(gòu)造使用繼承屬性構(gòu)造a a4 4c c的抽象語法樹的抽象語法樹E ET TR RididTo entry for aTo entry for aididT.T.nptrnptr- -T Tnumnumnumnum4 4T.T.nptrnptrR.R.

33、 i i- -R R+ +T TR RididTo entry for cTo entry for cididT.T.nptrnptrR.R. i i+ +R.R. i i R.R. s sR.R. s sR.R. s sE.E.nptrnptrE T R.i:=T.nptr R E.nptr:=R.sE T R.i:=T.nptr R E.nptr:=R.sR + T RR + T R1 1.i:=mknode(+,R.i,T.nptr) R.i:=mknode(+,R.i,T.nptr) R1 1 R.s:=R R.s:=R1 1.s.sR - T RR - T R1 1.i:=mknod

34、e(.i:=mknode(,R.i,T.nptr) R,R.i,T.nptr) R1 1 R.s:=R.s R.s:=R.sR R R.s:=R.i R.s:=R.iT ( E )T ( E ) T.nptr:=E.nptr T.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entry)T id T.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val)T num T.nptr:=mkleaf(num,num.val)6/13/2021316.4.3 6.4.3 遞歸下降翻譯器的設(shè)計(jì)遞歸下降翻譯器的設(shè)計(jì)

35、 n如何在遞歸下降分析中實(shí)現(xiàn)翻譯模式，如何在遞歸下降分析中實(shí)現(xiàn)翻譯模式，構(gòu)造遞歸下降翻譯器構(gòu)造遞歸下降翻譯器 6/13/202132設(shè)計(jì)遞歸下降翻譯器的方法設(shè)計(jì)遞歸下降翻譯器的方法n 1. 1. n對每個(gè)非終結(jié)符對每個(gè)非終結(jié)符A A構(gòu)造一個(gè)函數(shù)過程，對構(gòu)造一個(gè)函數(shù)過程，對A A的每個(gè)的每個(gè)繼承屬性繼承屬性設(shè)置一個(gè)設(shè)置一個(gè)形式參數(shù)形式參數(shù)n函數(shù)的函數(shù)的返回值返回值為為A A的的綜合屬性綜合屬性（作為記錄，（作為記錄，或指向記錄的一個(gè)指針，記錄中有若干域，或指向記錄的一個(gè)指針，記錄中有若干域，每個(gè)屬性對應(yīng)一個(gè)域）。為了簡單，我們假每個(gè)屬性對應(yīng)一個(gè)域）。為了簡單，我們假設(shè)每個(gè)非終結(jié)只有一個(gè)綜合屬性設(shè)

36、每個(gè)非終結(jié)只有一個(gè)綜合屬性nA A對應(yīng)的函數(shù)過程中，為出現(xiàn)在對應(yīng)的函數(shù)過程中，為出現(xiàn)在A A的產(chǎn)生式的產(chǎn)生式中的每一個(gè)文法符號的每一個(gè)中的每一個(gè)文法符號的每一個(gè)屬性屬性都設(shè)置一都設(shè)置一個(gè)個(gè)局部變量局部變量。6/13/202133設(shè)計(jì)遞歸下降翻譯器的方法設(shè)計(jì)遞歸下降翻譯器的方法n2. 2. 非終結(jié)符非終結(jié)符A A對應(yīng)的函數(shù)過程中，根據(jù)當(dāng)前對應(yīng)的函數(shù)過程中，根據(jù)當(dāng)前的輸入符號決定使用哪個(gè)產(chǎn)生式候選。的輸入符號決定使用哪個(gè)產(chǎn)生式候選。6/13/202134設(shè)計(jì)遞歸下降翻譯器的方法設(shè)計(jì)遞歸下降翻譯器的方法n3. 3. 每個(gè)產(chǎn)生式對應(yīng)的程序代碼中，按照從左到右的次每個(gè)產(chǎn)生式對應(yīng)的程序代碼中，按照從左到右

37、的次序，對于單詞符號（終結(jié)符）、非終結(jié)符和語義動(dòng)作序，對于單詞符號（終結(jié)符）、非終結(jié)符和語義動(dòng)作分別作以下工作：分別作以下工作：i) i) 對于帶有綜合屬性對于帶有綜合屬性x x的終結(jié)符的終結(jié)符X X，把，把x x的值存入為的值存入為X.xX.x設(shè)置的變量中。然后產(chǎn)生一個(gè)匹配設(shè)置的變量中。然后產(chǎn)生一個(gè)匹配X X的調(diào)用，并繼的調(diào)用，并繼續(xù)讀入一個(gè)輸入符號。續(xù)讀入一個(gè)輸入符號。ii) ii) 對于每個(gè)非終結(jié)符對于每個(gè)非終結(jié)符B B，產(chǎn)生一個(gè)右邊帶有函數(shù)調(diào)用，產(chǎn)生一個(gè)右邊帶有函數(shù)調(diào)用的賦值語句的賦值語句c=B(b1,b2,bk)c=B(b1,b2,bk)，其中，其中，b1,b2,bkb1,b2,bk

38、是為是為B B的的繼承屬性繼承屬性設(shè)置的變量，設(shè)置的變量，c c是為是為B B的的綜合屬性綜合屬性設(shè)置的變量。設(shè)置的變量。iii) iii) 對于語義動(dòng)作，把動(dòng)作的代碼抄進(jìn)分析器中，用代對于語義動(dòng)作，把動(dòng)作的代碼抄進(jìn)分析器中，用代表屬性的變量來代替對屬性的每一次引用。表屬性的變量來代替對屬性的每一次引用。6/13/202135構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化成構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化成翻譯模式翻譯模式 E E T TR.i:=T.nptrR.i:=T.nptr R RE.nptr:=R.sE.nptr:=R.sR R + + T TRR1 1.i:=mknode(+,R.i,T.npt

39、r).i:=mknode(+,R.i,T.nptr) R R1 1R.s:=RR.s:=R1 1.s.sR R - - T TRR1 1.i:=mknode(.i:=mknode(,R.i,T.nptr),R.i,T.nptr) R R1 1R.s:=R.sR.s:=R.sR R R.s:=R.iR.s:=R.iT T ( E )( E )T.nptr:=E.nptrT.nptr:=E.nptrT T ididT.nptr:=mkleaf(id,id.entry)T.nptr:=mkleaf(id,id.entry)T T numnumT.nptr:=mkleaf(num,num.val)T.

40、nptr:=mkleaf(num,num.val)6/13/202136n非終結(jié)符非終結(jié)符E E、R R、T T的函數(shù)及其參數(shù)類型的函數(shù)及其參數(shù)類型 functionfunction E:AST-node;E:AST-node;functionfunction R(in:AST-node): AST-node;R(in:AST-node): AST-node;functionfunction T: AST-node;T: AST-node;n 用用oddopoddop代表和代表和 R oddopR oddop T TRR1 1.i:=mknode(addop.lexme, R.i,T.nptr

41、).i:=mknode(addop.lexme, R.i,T.nptr) R R1 1R.s:=RR.s:=R1 1.s.s R R R.s:=R.iR.s:=R.i6/13/202137 產(chǎn)生式產(chǎn)生式Raddop TR|Raddop TR| 的分析過程的分析過程 procedure R; procedure R; begin begin if sym=addop then begin if sym=addop then begin advance;T; Radvance;T; R end end else begin / else begin /* *do nothingdo nothing* */ / end end end; end; 6/13/202138 function R ( funct