1、第6章 語法制導翻譯技術 2022/8/111內容提要引言翻譯文法語法制導翻譯自頂向下語法制導翻譯屬性翻譯文法屬性文法的自頂向下翻譯自底向上語法制導翻譯2022/8/1126.1 引言編譯程序的邏輯工作過程詞法分析和語法分析僅僅對源程序做形式變換和檢查。語義分析檢查程序語義是否正確中間代碼生成將語義分析后的結果翻譯成代碼上述工作過程采用串行處理方式實際應用中語法分析、語義分析、中間代碼生成采用并行處理方式詞法分析語法分析語義分析代碼優化目標代碼生成目標代碼源程序中間代碼生成2022/8/113并行處理方式： 對文法中的每個產生式都附加一些動作(語義分析、操作符號表、代碼生成等),在語法分析過程

2、中，每當需要使用一個產生式進行推導或歸約，語法分析程序除執行相應的語法分析動作外，還要執行相應的其它動作，完成語義分析和代碼生成等工作。（邊分析邊翻譯）并行處理方式涉及幾個概念翻譯文法語法制導翻譯屬性翻譯文法 2022/8/114翻譯文法：是上下文無關文法的推廣，通過在描述語言規則的文法產生式右部的適當位置加入動作而得到的文法 。6.2 翻譯文法例：設計一個能將中綴表達式翻譯成后綴表達式的翻譯器。假設輸入串為a+b*c輸入符號本身表示讀操作，用表示輸出操作則翻譯器的輸入輸出動作為： aa+bb*cc*+ *+abc為動作符號標記，由符號開始的符號串稱為一個動作符號。輸出結果由緊跟在符號之后的各

3、符號組成，即abc*+。2022/8/115例：構造中綴表達式文法的翻譯文法。 EE+T F(E) ET Fa TT*F Fb TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc把中綴表達式文法叫做輸入文法；在輸入文法上添加動作后形成的文法叫做翻譯文法使用中綴表達式文法推導得到終結符號串叫做輸入序列；使用翻譯文法推導得到的符號串稱為活動序列。從活動序列中去掉所有動作符號得到輸入序列，而所有動作符號組成的符號串稱為動作序列。從動作序列中去掉動作符號標記得到輸出序列（翻譯結果）2022/8/116例：對于符號串(a+b)*c用輸入文法推導輸入序列(a+b)*c:E =

4、T=T*F=F*F=(E)*F=(E+T)*F=(T+T)*F=(F+T)*F =(a+T)*F=(a+F)*F=(a+b)*F=(a+b)*c用翻譯文法推導活動序列(aa+bb+)*cc*:E =T=T*F*=F*F*=(E)*F*=(E+T+)*F*=(T+T+)*F* =(F+T+)*F*=(aa+T+)*F*=(aa+F+)*F* =(aa+bb+)*F*=(aa+bb+)*cc*將活動序列(aa+bb+)*cc*中的動作符號去掉得到輸入序列：(a+b)*c所有動作符號組成的符號串即動作序列為：ab+c* 去掉動作符號標記得到：ab+c* EE+T F(E) ET Fa TT*F Fb

5、 TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc2022/8/117語法制導翻譯：給定一輸入序列，根據翻譯文法得到翻譯該輸入序列的活動序列，從活動序列中分離出動作符號串，然后執行該動作符號串所規定的動作，從而得到翻譯結果。6.3 語法制導翻譯 例:根據算術表達式翻譯文法，對于輸入序列a+b*c推導出活動序列：aa+bb*cc*+ 其中： a+b*c 為輸入序列 abc*+ 為動作序列執行動作序列中的動作產生輸出序列abc*+；即輸入序列a+b*c的翻譯結果。 EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc2022/8/118將二元組（輸入

6、序列，動作序列）稱為一個對偶對偶集合稱為由給定翻譯文法所定義的翻譯由于翻譯文法是在輸入文法的產生式右部的適當位置插入動作符號形成的，因此，翻譯文法產生的動作序列受輸入語言的文法控制（語法制導）。語法制導翻譯：根據輸入語言的文法，分析各條產生式的語義(要求計算機所完成的操作)，分別編出完成這些操作的子程序或程序段(稱為語義子程序或語義動作)，并把這些子程序或程序段的名字作為動作符號插入到輸入文法各產生式右部的適當位置上，從而實現翻譯文法。 EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc EE+T F(E) ET Fa TT*F Fb TF Fc2022/8/11910語法制

7、導翻譯的基本思想通俗地講，以語法分析為基礎，伴隨語法分析的各個步驟，執行相應的語義動作。具體方法： 1將文法符號所代表的語言結構的意思，用隸屬于該文法符號的屬性表示； 2用語義規則(語義規則的執行就是語義動作)規定產生式所代表的語言結構之間的關系（即屬性之間的關系），即用語義規則實現屬性計算。 3.語義動作(語義規則的執行)： 在語法分析的適當時刻（如推導或歸約）執行附著在對應產生式上的語義規則，以實現對語言結構語義的處理，如計算、查填符號表、生成中間代碼、發布出錯信息等。2022/8/11自頂向下的語法制導翻譯有遞歸下降翻譯和LL(1)翻譯。遞歸下降翻譯(在適當位置插入實現動作符號的子程序）

8、:例:算術表達式翻譯文法如下：(為輸出其后的符號串) EE+T+ ET TT*F* TF F(E) Faa Fbb Fcc消除左遞歸得到： ETEE +T+E|TFTT *F * T|F(E)|aa| bb| cc6.4 自頂向下語法制導翻譯 11FIRST(TE)=(,a,b,cFIRST(+T+E)=+FOLLOW(E)=#,)FIRST(FT )=(,a,b,cFIRST(*F * T)=*FOLLOW(T)=#,+,)FIRST(E)=(FIRST(aa)=aFIRST(bb)=bFIRST(cc)=c求FIRST集和FOLLOW集不考慮動作符號12對改寫后文法的每個非終結符號編寫一個

9、函數。對于產生式 ETE FIRST(TE)=(,a,b,c用E1表示EE() if(chFIRST(TE) T(); E1(); else error();2022/8/11ETEE +T+E|TFTT *F * T|F(E)|aa| bb| cc13對于產生式 E +T+E|-用E1表示EFIRST(+T+E)=+FOLLOW(E)=#,)E1()if(ch=+) ch = getnextsymbol(); T(); OUT(“+”); E1()； else if(chFOLLOW(E)return; else error();2022/8/11ETEE +T+E|TFTT *F * T|

10、F(E)|aa| bb| cc對于產生式 TFT -用T1表示TT()if(chFIRST(FT) F(); T1(); else error();2022/8/11ETEE +T+E|TFTT *F * T|F(E)|aa| bb| cc對于產生式T *F * T|FIRST(*F * T)=*FOLLOW(T)=#,+,)-用T1表示TT1 () if(ch=*) ch = getnextsymbol(); F ();OUT(“*”); T1 ()； else if(chFOLLOW(E)return; else error();2022/8/1115ETEE +T+E|TFTT *F *

11、 T|F(E)|aa| bb| cc對于產生式F(E)|aa| bb| cc F ( )if(ch=a)ch = getnextsymbol();OUT(“a”); else if(ch=b) ch=getnextsymbol();OUT(“b”); else if(ch=c) ch=getnextsymbol();OUT(“c”); else if(ch=(） ch = getnextsymbol(); E ( ); if(ch =)ch = getnextsymbol(); else error（）;2022/8/1116LL(1)翻譯器 例：輸入文法： AaBcD Ab Bc BaA D

12、cD Db 輸入文法的LL(1)分析表 符號輸入符號 abc#ABDAaBcDBaA AbDbBcDcD 翻譯文法：AvawBxcyDzAb Bcr BamA DcDn Dsb符號 輸入符號 abc#ABDAvawBxcyDzBamA AbDsbBcrDcDn 翻譯文法的LL(1)分析表 翻譯文法的動作符號同樣入棧，當其處于棧頂時，無條件出棧并執行其規定的操作，不移動讀符號指針。 構造翻譯文法分析表不考慮動作符號2022/8/1117aA.#v a w B.#B.#v出棧并執行，a出棧，w出棧并執行 符號 輸入符號 abc#ABDAvawBxcyDzBamA AbDsbBcrDcDn2022/

13、8/1118屬性：指與文法符號的類型和值等有關的一些語義信息，在編譯中用屬性描述被處理對象的語義特征。屬性代表與文法符號相關的語義信息。屬性的設置和語法結構的語義以及翻譯程序的需要有關。例如:文法符號X的類型屬性:X.type 文法符號X的值屬性:X.val文法符號X的代碼序列:X.code文法符號X的內存：X.place文法符號X的符號表入口指針: X.entry等。6.5 屬性翻譯文法 注：教材中用箭頭和 代替.2022/8/111920屬性、語義規則屬性和變量一樣，可以在語法分析過程中進行計算和傳遞。語義規則：屬性的計算規則，屬性的加工和計算過程。由語義處理過程、語義動作、語義子程序來實

14、現。屬性分為兩類：綜合屬性和繼承屬性。終結符只有綜合屬性, 由詞法分析器提供例：i.lexval表示單詞符號“數”的詞法值 id.entry表示單詞符號“標識符”的符號表入口非終結符既可以有綜合屬性也可以有繼承屬性注：教材中屬性前用表示綜合屬性， 表示繼承屬性2022/8/1121兩種屬性：綜合屬性綜合屬性用于“自下而上”傳遞信息。綜合屬性：在語法樹中，一個結點的綜合屬性值由其子結點的屬性值確定。通常結合自下而上的語法分析在每一個結點處使用語義規則計算綜合屬性的值 - 由下層子結點的屬性值計算上層父結點的綜合屬性值，隨著自下而上語法分析的進行，最終可計算出開始符號的綜合屬性值。A X1 X2

15、XnA.b X1.c1 X2 .c2 Xn . ckA X1X2Xn 綜合屬性A.b = f(c1,c2,ck) 帶屬性的語法樹2022/8/11例：設計一個語法分析程序接受算術表達式，并通過添加動作符號輸出表達式的值。已知符號串翻譯文法如下： SEANSWER EE+T ET TT*F TF F(E) FNUMANSWER的動作是輸出表達式的計算結果。表達式3+2*3的詞法分析結果如下： NUM3+ NUM2* NUM3其中NUM代表無符號整數,數字串表示該符號的屬性 2022/8/1122改寫每一個產生式，添加符號屬性變量名，并定義符號屬性之間的關系即屬性求值規則(語義規則)，得到： 屬性

16、文法 求值規則 S EqANSWERr r = q Ep Eq+ Tr p = q + r Ep Tq p = q Tp Tq* Fr p = q * r Tp Fq p = q Fp (Eq) p = q Fp NUMq p = q 通過自底向上進行求值的屬性，稱為綜合屬性，用來表示。終結符號的綜合屬性具有初始值，由詞法分析給出。 2022/8/1123SET+EANSWER F*TTFNUM3 FNUM2 NUM3 NUM3+ NUM2* NUM3的語法樹 NUM3 SE9 T6 +E3 ANSWER9 F3 *T2 T3 F3 F2 NUM2 NUM3 NUM3+ NUM2* NUM3帶

17、屬性計算的語法樹 屬性文法 求值規則 S EqANSWERr r = q Ep Eq+ Tr p = q + r Ep Tq p = q Tp Tq* Fr p = q * r Tp Fq p = q Fp (Eq) p = q Fp NUMq p = q 在歸約過程中完成屬性值的計算2022/8/112425兩種屬性：繼承屬性繼承屬性用于“自上而下”傳遞信息。繼承屬性：在語法樹中，一個結點的繼承屬性由此結點的父結點和(或)兄弟結點的某些屬性確定?？梢杂美^承屬性來表示程序語言結構中的上下文依賴關系。繼承屬性的計算可以結合自上而下的語法分析進行A X1 X XnA. ck X1.c1 X.b X

18、n.ci A X1X2XXn 繼承屬性 X.b = f(c1,c2,ck) 2022/8/11例：聲明語句文法 TYPE ID; ，ID 其中TYPE可為int，real，bool假設詞法分析程序輸出單詞符號時，對變量名輸出單詞記號ID和變量名；對TYPE輸出單詞記號TYPE和類型名。構造語法分析程序，能輸出變量名及其類型 2022/8/11261、添加語義動作SET_TYPE輸出變量名及類型，因此SET_TYPE帶有兩個屬性，即變量名和類型： SET_TYPEn1，t1語法分析程序讀到一個變量后，調用SET_TYPE。因此文法改寫為： (1) TYPE IDSET_TYPE ; (2) ，I

19、DSET_TYPE (3) 2、確定需要的屬性TYPE需要一個屬性(類型名)，即TYPEtID需要一個屬性(變量名)，即IDn需要一個屬性，即2022/8/11273、確定語義規則（屬性求值規則）產生式(1)的TYPEt 和IDn由詞法分析輸出得到。產生式(2)從詞法分析只能得到IDn ，令產生式(2)左邊 = 產生式(1)右邊,得到翻譯文法：TYPEtIDnSET_TYPEn1,t1 t2= t，t1= t ，n1= n（屬性求值規則）2) ，IDnSET_TYPEn1,t1 t2= t，t1= t ，n1= n（屬性求值規則）3 ) (1) TYPE ID SET_TYPE ;(2) ，I

20、DSET_TYPE (3) 2022/8/1128假設輸入符號串為int a,b；，詞法分析輸出為TYPEint IDa, Db； ，則帶有屬性的語法樹如圖所示按自頂向下或自左向右方式求得的屬性稱為繼承屬性, 其前面冠以表示。 聲明語句 ；SET_TYPEa, int IDa TYPEint 變量表int SET_TYPEb, int IDb 變量表int ， TYPEint IDa, Db；的語法樹 TYPEtIDnSET_TYPEn1,t1 (1)t2= t，(2)t1= t ，(3)n1= n（屬性求值規則）2) ，IDnSET_TYPEn1,t1 (4)t2= t，(5)t1= t ，

21、(6)n1= n（屬性求值規則）3 ) 2022/8/112930屬性文法：編譯技術中采用的一種語義描述工具，是一種適用于定義語言語義的特殊文法，即在語言的文法中增加了屬性的文法。實際上，屬性文法是對上下文無關文法的推廣。屬性翻譯文法：是以一個上下文無關文法為基礎, 為每個文法符號引進一組屬性(語義值)，對文法的每個產生式都配備一組與之相關聯的屬性的計算規則(語義規則)而得到的文法。或者說：符號具有屬性并帶有屬性求值規則的翻譯文法稱為屬性翻譯文法其具體定義如下：2022/8/111)文法的每個終結符、非終結符和動作符號都可以有一個有窮的屬性集。 2)每個非終結符和動作符號屬性可分為綜合屬性和繼

22、承屬性。3)繼承屬性的求值規則： 開始符號的繼承屬性具有初始值。 對產生式左部的非終結符，其繼承屬性則繼承前面產生式中該符號已有的繼承屬性值。 右部的符號，其繼承屬性由產生式中其它符號屬性值進行計算。（語法樹上的父親和兄弟）2022/8/11314)綜合屬性的求值規則： 終結符號的綜合屬性具有指定的初始值。在具體實現中，初始值由由詞法分析程序提供。 產生式右部的非終結符號的綜合屬性值，則取后面以該非終結符號為產生式左部時求得的綜合屬性值。 產生式的左部的非終結符號的綜合屬性值，由產生式中左部或右部的某些符號的屬性值進行計算。 給定一動作符號，其綜合屬性值用該動作符號的其它屬性值進行計算。 20

23、22/8/1132翻譯要求：翻譯輸出是四元式代碼 輸出符號串中的每個雙目運算都用一個四元式表示。四元式的順序與執行時的運算順序相同。四元式有三個參數，從左到右為左操作數，右操作數，運算結果。 例：翻譯器將表達式a+b翻譯成如下四元式 ADD a , b , t1 其中t1是臨時變量，保存表達式的結果。 對于表達式：a+a*b，詞法分析得到IDa+IDa * IDb，屬性翻譯文法翻譯得到： MULT a b , t1 ADD a t1 , t2 例：算術表達式的翻譯文法：EE+T ETTT*F TFF(E) FID 2022/8/11331、設計翻譯文法：EE+TADDETTT*FMULTTFF

24、(E)FID 2022/8/11342、確定屬性和求值規則，構造屬性翻譯文法1)令每個非終結符有一個綜合屬性：臨時變量，保存由它產生的表達式結果。2)輸入符號ID有一個綜合屬性：符號的變量名。3)動作符號有三個繼承屬性：左操作數、右操作數、運算結果。屬性翻譯文法如下：ExEq+TrADDy,z,t， y = q, z = r,t = NEWT，x = tExTp x = pTxTq*FrMULTy,z,t，y = q,z = r, t = NEWT，x = tTxFp ， x = pFx(Ep)，x = pFxIDp ，x = p函數NEWT返回一個新的臨時變量名，按產生順序分別為t1、t2、

25、。動作符號ADDy,z,t 輸出ADD y,z,t動作符號MULTy,z,t 輸出MULT y,z,t2022/8/1135IDa Ex Tr +Eq Fp *Tq Tp Fx Fx IDa IDb MULTy,z,t ADDy,z,t 表達式a+a*b的屬性語法樹 Et2 Tt1 Ea Fb Ta Ta Fa Fa MULTa,z,t ADDa,z,t 產生新變量t2 產生新變量t1 ExEq +TrADDy,z,t， y = q, z = r,t = NEWT，x = tExTp x = pTxTq *FrMULTy,z,t，y = q,z = r, t = NEWT，x = tTxFp

26、， x = pFx(Ep)，x = pFxIDp ，x = p2022/8/1136MULTa,b,t MULTa,b,t1 ADDa,t1,t ADDa,t1,t2 屬性翻譯文法的語法樹需要保證完整性，即保證所有屬性能通過計算賦值。不同分析方法對文法有不同要求。L-屬性翻譯文法 ：自頂向下分析時保證語法樹的完整性6.6 屬性文法的自頂向下翻譯2022/8/11372022/8/1138 屬性翻譯文法是L-屬性翻譯文法，當且僅當對其中的每個產生式AX1X2Xn，下面三個條件成立：1右部符號Xi(1in)的繼承屬性之值，僅依賴于X1,X2,Xi-1的任意屬性或A的繼承屬性（P133繼承屬性規則的

27、限制）； （L的含義：符號的繼承屬性只依賴于該符號左邊的屬性值）2左部符號A的綜合屬性之值僅依賴于A的繼承屬性或(和)右部符號Xi(1in)的任意屬性（P133綜合屬性規則的限制） ；3對一動作符號而言，其綜合屬性之值是以該動作符號的繼承屬性或產生式右部的任意屬性為變元的函數（P133繼承屬性規則的限制） 。條件2、3避免求值的循環依賴；給定文法后可通過構造依賴圖進行拓撲排序證明）例：文法中有產生式為： AI1S2,S3BI4CS5DS6I7,I8EI9根據L-屬性的限制條件，I4=F(I1)、S2=G(I7,S6)合法，而I4=H(S2)不合法 。條件1條件2L-屬性文法翻譯的實現遞歸下降翻

28、譯 處理思路和處理不帶屬性的翻譯文法相同，由于屬性的存在需要改造對非終結符的處理方法： 1)若非終結符具有屬性，則該非終結符的分析函數具有形參，形參數目等于其屬性個數。 2)對于繼承屬性，采用值傳遞方式，將繼承屬性值傳入被調函數，即在函數調用中所對應的實參是繼承屬性的值。 3)對于綜合屬性，采用引用（地址）傳遞方式，以便將值回傳給主調函數,即實參是一個變量引用（地址），在函數返回之前，把綜合屬性的值賦給該變量。 2022/8/1139為了進行屬性翻譯的程序設計，作下述約定： 1) 將屬性名用作變量名和參數名。 2)所有出現在左部的同名非終結符，應具有相同的屬性名表。例:產生式 LabEi Rj

29、， i,j = b,a = i + 2 Lxy Hzw， w = y, z = 2, x = z + y 改成： Lab EiRj， i,j = b,a = j + 2 Lab Hzw， w = b,z = 2,a = z + b 2022/8/11403) 若兩個屬性值相同，則給它們相同的名字，但左部符號的屬性值相等時，不能改變成相同的名字。規則SAaBbCc，當b=a，c=a時， 可寫成SA aBaCa規則LaAbfc ，當a=b, c=b時， 可寫成LaAafa規則LabaBcCd ,當c=a, d=a時， 可寫成LabaBaCa但當b=a時，不能寫成LaaaBa Ca理由：左部非終結符

30、號的屬性將作為該非終結符號分析函數的形參，而一個函數的形參不能重名。如函數L(int a,int b)不可寫成L(int a,int a)。2022/8/1141采用C語言編寫屬性翻譯程序時采用的方法：1)形式參數：產生式左部非終結符的屬性名表設計成相應函數的形參表；將繼承屬性的形參名說明為值形參(即簡單變量)，綜合屬性形參名說明為指針變量。2)局部變量：產生式中與在左部出現的屬性名不同的屬性名變成相應函數的局部變量。3)非終結符的代碼：對于右部出現的每個非終結符的函數調用，該非終結符的屬性作為實參。2022/8/11424)輸入符號的代碼：對文法中出現的每個輸入符號(即終結符號)，將賦值語句

31、插入到函數中它所對應的NEXTSYM之前，把保存在讀符號程序NEXTSYM中的終結符號屬性(某個全局變量中)賦給輸入符號屬性中的每個屬性變量（讀下一個符號前賦值）。5)動作符號的代碼：對出現在文法中的每個動作符號，插入代碼對動作符號的綜合屬性進行計算，并且把結果賦給對應于該綜合屬性的變量，然后執行相應動作。2022/8/11436)屬性規則的代碼：與每個產生式有關的屬性求值規則，插入其代碼以便對屬性求值規則的右部求值，并把結果賦給該規則左部的每個變量?？梢园堰@些代碼放在屬性計算規則的所有自變量已知之后，且函數值被使用之前的任何地方。7)主程序：MAIN函數中，對文法開始符號的每一個綜合屬性的名

32、字變成主程序的局部變量，然后調用開始符號對應的函數。2022/8/1144例：為算術表達式的L-屬性翻譯文法編寫遞歸下降翻譯器。EtTpEptEpt+Tr ADDp,r,t0 Et0t t0 = NEWT Ept t = pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0 = NEWT Tpt t = pFp (Ep) | IDp 2022/8/1145如何得到該文法？1、消除左遞歸2、命名改造2022/8/1146ExEq +TrADDy,z,t， y = q, z = r,t = NEWT，x = tExTp x = pTxTq *FrMULTy,z,t，y = q,z =

33、 r, t = NEWT，x = tTxFp ， x = pFx(Ep)，x = pFxIDp ，x = pExTpEqy x=y q=pEqy+Tr ADDp,s,t0 Et1t t0 = NEWT p=q s=r t1=t0 y=t Eqy y=qTxFpTqy x=y q=pTqy*Fr MULTp,s,t0 Tt0t t0 =NEWT p = q s=r t1=t0 y=t Tqy y=qFq (Ep) | IDp q=p消除左遞歸ETF+TEIDETFIDT2022/8/1147命名處理EtTpEptEpt+Tr ADDp,r,t0 Et0t t0 = NEWT Ept t = pT

34、tFpTptTpt*Fr MULTp,r,t0 Tt0t t0 = NEWT Tpt t = pFp (Ep) | IDp ExTpEqy x=y q=pEqy+Tr ADDp,s,t0 Et1t t0 = NEWT p=q s=r t1=t0 y=t Eqy y=qTxFpTqy x=y q=pTqy*Fr MULTp,s,t0 Tt0t t0 =NEWT p = q s=r t1=t0 y=t Tqy y=qFq (Ep) | IDp q=p對產生式EtTpEpt ，t為綜合屬性,形參用指針變量int E(int *t) int es=0; int p; es=T(&p); es=E1(p

35、,t); return(es);EtTpEptEpt+Tr ADDp,r,t0 Et0t t0 = NEWT Ept t = pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0 = NEWT Tpt t = pFp (Ep) | IDp 方法1方法2方法32022/8/1148對產生式Ept+Tr ADDp,r,t0 Et0t 和 Eptp為繼承屬性,形參用整型變量,t為綜合屬性,形參用指針變量int E1(int p,int *t) int r, es, t0; if (ch = +) ch = getword(); es = T(&r); t0 = NEWT(); prin

36、tf(“ ADD %c,%c,%cn,p,r,t0); es = E1(t0,t); return(es); else if(ch =( |ch =# ) *t = p;return(0); else error(); .Ept+Tr ADDp,r,t0 Et0t t0 = NEWT Ept t = p.方法4，但+無屬性方法5，動作符號無綜合屬性方法62022/8/1149int NEWT() static int i = 64; i = i+1; return(i);對產生式TtFpTptt為綜合屬性,形參用指針變量int T(int *t) int es=0,p; es=F(&p); e

37、s=T1(p,t); return(es);EtTpEptEpt+Tr ADDp,r,t0 Et0t t0 = NEWT Ept t = pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0 = NEWT Tpt t = pFp (Ep) | IDp 2022/8/1150int T1(int p,int *t) int r,es,t0; if (ch = *) ch = getword(); es = F(&r); t0 = NEWT(); printf(“ MULT %c,%c,%cn,p,r,t0); es=T1(t0,t); return(es); else if(ch

38、=+ |ch =# |ch =) ) *t=p; return(0); else error();.Tpt*Fr MULTp,r,t0 Tt0t t0 = NEWT Tpt t = p. 2022/8/1151對產生式Tpt*Fr MULTp,r,t0 Tt0t和T pt，p為繼承屬性,形參用整型變量；t為綜合屬性,形參用指針變量int F(int *p) int es=0; if (ch=( ) ch=getword(); es=E(p); if (ch!=) return(3); else ch=getword();return(es); else if (isalpha(ch) *p=c

39、h; ch=getword(); return(es); else return(4); 對產生式Fp(Ep)|IDpp為綜合屬性,形參用指針變量方法42022/8/1152主程序：1、MAIN函數中對開始符號的每一個綜合屬性作為其局部變量；2、調用開始符號對應的函數，如果實參對應開始符號的繼承屬性，則以值參方式傳入該屬性的初始值；如果對應開始符號的綜合屬性，則傳入該屬性局部變量的地址。 EtTpEptmain() int es = 0, t; printf(請輸入算術表達式(操作數只能是單個字母)：); ch = getword(); printf(輸出四元式為：n); es = E(&t)

40、; if (es = 0) printf(n翻譯成功!n); else printf(n表達式有語法錯誤!n);方法7（1）方法7（2）2022/8/1153運行程序輸入：a*(b+c)+b*d輸出四元式序列為：其中A、B、C、D都是臨時變量。 ADD b,c,AMULT a,A,BMULT b,d,CADD B,C,D2022/8/115455輸入：NUM2 *NUM 4 +NUM 6 #Et0tNUM2*EtTpFpTpt+FrEptTrNUM6Fp2022/8/11TptNUM4F2T2tF4MULT p,r,t0MULT 2,r,t0MULT 2,4,t0MULT 2,4,8Tt0tT

41、8tADD p,r,t0F6T6tT88T28T8E8tT6T66E814ADD 8,6,t0ADD 8,6,14E14tE1414E14調用進入返回遞歸下降翻譯程序的運行（將文法中ID改為NUMt0 = p+r t0 = p*r）L-屬性文法翻譯的實現LL(1)法 擴充翻譯文法的LL(1)翻譯器：對所有符號，符號本身和屬性同時進棧。將棧符號設計為兩部分(符號名、屬性域)例：對符號串ABC，假定A有屬性A1和A2，B有屬性B1，C無屬性。入棧后如圖所示。 A屬性 A1屬性 A2B屬性B1C#2022/8/1156例：文法SEpANSWERr r = pEp+EqErADDA1,A2R A1 =

42、 q, A2 = r, R = A1 + A2, p = REp*EqErMULTA1,A2R A1 = q, A2 = r, R = A1 * A2, p = R EpNUMq p = q構造其翻譯器 步驟：1、棧符號設計2、構造LL(1)分析表3、設計語義動作2022/8/11571、棧符號設計根據屬性類型確定屬性域的存放內容，可存放屬性值和指向屬性值的指針。對于綜合屬性，其屬性域存放一個指針，指向存貯該屬性值的單元。對于繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧時為空，但在該棧符號變成棧頂符號之前的某一時刻，必須通過計算賦值，即在成為棧頂時，繼承屬性的屬性域必須有值。20

43、22/8/1158MULT 繼承屬性1 繼承屬性2 綜合屬性指針 ADD繼承屬性1 繼承屬性2 綜合屬性指針 ANSWER 繼承屬性NUM 綜合屬性指針E綜合屬性指針 S S的棧符號 E的棧符號 NUM的棧符號 ANSWER的棧符號 ADD的棧符號 MULT的棧符號 SEpANSWERr r = pEp+EqErADDA1,A2R A1 = q, A2 = r, R = A1 + A2, p = REp*EqErMULTA1,A2R A1 = q, A2 = r, R = A1 * A2, p = REpNUMq p = q2022/8/11592、構造屬性翻譯文法LL(1)分析表。 符號 輸

44、入符號 +*NUM#SE121314 LL(1)析表 (1)SEpANSWERr r=p(2)Ep+EqErADDA1,A2R A1=q, A2=r, R= 1 + A2, p=R(3)Ep*EqErMULTA1,A2R A1=q, A2 =r, R= A1 * A2, p=R(4)EpNUMq p=q2022/8/11603、語義動作設計假定要求翻譯器計算輸出由文法定義的表達式值,三個動作符號的翻譯動作為：1) ADD：把頭兩個域的內容相加并將結果存貯在第三個域所指的單元中，然后出棧。2) MULT：把頭兩個域的內容相乘并將結果存貯在第三個域所指的單元中，然后出棧。3) ANSWER：輸出屬

45、性域的內容結果，然后出棧。 2022/8/11611)#入棧，文法開始符號S入棧，輸入指針指向符號+NUM2NUM3# S#符號棧： 輸入串+NUM2NUM3# EpANSWERr#符號棧： 2)查分析表S行+列，入棧，因為r = p，所以Ep為指向ANSWERr的指針。 符號 輸入符號 +*NUM#SE121314輸入符號串+NUM2NUM3#的分析過程：2022/8/1162(1)SEpANSWERr r = p(2)Ep+EqErADDA1,A2R A1 = q, A2 = r, R = A1 + A2, p = R(3)Ep*EqErMULTA1,A2R A1 = q, A2 = r,

46、 R = A1 * A2, p = R(4)EpNUMq p = qNUM2NUM3# EqErADDA1A2RANSWERr#符號棧： 3)查分析表E行+列,E出棧前,Ep指向ANSWERr,因為Ep=ADDR,所以ADDR指向ANSWERr;新入棧的Eq Er,分別指向ADDA1A2;因棧頂為+,+出棧,讀下一個符號。 符號 輸入符號 +*NUM#SE1213142022/8/1163EpANSWERr#(1)SEpANSWERr r = p(2)Ep+EqErADDA1,A2R A1 = q, A2 = r, R = A1 + A2, p = R.+NUM2NUM3# NUM3# ErA

47、DD2A2RANSWERr#符號棧： 4)查分析表E行NUM列，E出棧前,Eq指向ADDA1,而Eq =NUMq,所以NUMq入棧,把NUM 2放入E出棧前Eq指向的單元ADDA1。然后，NUM出棧,讀下一個符號。 2022/8/1164.(4)EpNUMq p = q符號 輸入符號 +*NUM#SE1213 14 符號棧： EqErADDA1A2RANSWERr#NUM2NUM3# 符號 輸入符號 +*NUM#SE1213 14 5) 查分析表E行NUM列，E出棧前,Er指向ADDA2,而Er=NUMq,所以NUMq入棧,把NUM3放入Er指向的單元ADDA2。然后NUM出棧，讀下一個符號。

48、 # ADD23RANSWERr#符號棧： 2022/8/1165.(4)EpNUMq p = qNUM3# ErADD2A2RANSWERr#符號棧： 6)棧頂為動作符號ADD：把頭兩個域內容2和3相加，并把計算結果5存貯在第三個域ADDR所指的ANSWERr中，出棧。# ANSWER5#符號棧： 2022/8/1166符號 輸入符號 +*NUM#SE1213 14 .(2)Ep+EqErADDA1,A2R A1 = q, A2 = r, R = A1 + A2, p = R# ADD23RANSWERr#符號棧： 7)棧頂為動作符號ANSWER,輸出屬性域的內容5，出棧。棧內為#，輸入指針

49、指向#，成功結束。 #符號棧： 2022/8/1167(1)SEpANSWERr r = p.符號 輸入符號 +*NUM#SE1213 14 # ANSWER5#符號棧： 波蘭翻譯文法：對于一個文法,當且僅當文法中每個產生式右部的所有動作符號都只出現在所有輸入符號和非終結符號的右邊,則稱此類翻譯文法為波蘭翻譯文法。例：0)S E1)EE +TADD2)ET3)TT *FMULT4)TF 5)F(E) 6)Fi 0)S E1)E E +T2)ET3)TT *F4)TF 5)F(E) 6)F i 6.7 自底向上的語法制導翻譯 2022/8/1168狀態 ACTION GOTO i+*()#ETF0S5S41231S6A2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R5算術表達式的LR分析表 使用帶動作符號的產生式歸約要執行動作符號規定的動作。波蘭翻譯0)SE1)EE +TADD2)ET3)TT *FMULT4)TF 5)F(E) 6)Fi 2022/8/1169步