第5章 語義分析及中間代碼生成

1、2021-10-1712021-10-171編編 譯譯 原原 理理2021年10月17日S.PO.P語義分析、生成中間代碼語義分析、生成中間代碼生成目標(biāo)程序生成目標(biāo)程序代碼優(yōu)化代碼優(yōu)化語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理2021-10-1722021-10-172編編 譯譯 原原 理理2021年10月17日第第5 5章章語法制導(dǎo)翻譯技術(shù)和中間代碼生成語法制導(dǎo)翻譯技術(shù)和中間代碼生成 要求明確語義分析的要求明確語義分析的任務(wù)任務(wù) 明確明確屬性文法屬性文法和和語法制導(dǎo)翻譯語法制導(dǎo)翻譯的含義的含義 明確明確自底向上和自頂向下自底向上和自頂向下語法制導(dǎo)翻譯

2、的語法制導(dǎo)翻譯的區(qū)別和特點區(qū)別和特點 明確明確生成中間代碼的目的，中間代碼的幾生成中間代碼的目的，中間代碼的幾種形式種形式教學(xué)目標(biāo)教學(xué)目標(biāo)2021-10-1732021-10-173編編 譯譯 原原 理理2021年10月17日 屬性文法屬性文法 語法制導(dǎo)翻譯法的基本思想語法制導(dǎo)翻譯法的基本思想 常見的中間代碼常見的中間代碼 各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)教學(xué)內(nèi)容教學(xué)內(nèi)容2021-10-1742021-10-174編編 譯譯 原原 理理2021年10月17日詞法分析，語法分析詞法分析，語法分析：解決單詞和語言成分的識別：解決單詞和語言成分的識別及詞法和語法結(jié)

3、構(gòu)的檢查。語法結(jié)構(gòu)可形式化地用及詞法和語法結(jié)構(gòu)的檢查。語法結(jié)構(gòu)可形式化地用一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很容易地將其分析器構(gòu)造出來。容易地將其分析器構(gòu)造出來。本章要介紹的是本章要介紹的是語義分析和中間代碼生成技術(shù)語義分析和中間代碼生成技術(shù)。程序語言中間代碼目標(biāo)代碼程序語言中間代碼目標(biāo)代碼翻譯翻譯翻譯翻譯2021-10-1752021-10-175編編 譯譯 原原 理理2021年10月17日根據(jù)語義規(guī)則對識別出的各種語法成分析其含義，根據(jù)語義規(guī)則對識別出的各種語法成分析其含義，進行初步翻譯，生成相應(yīng)的中間代碼或直接生成目進行初步翻譯，生成相

4、應(yīng)的中間代碼或直接生成目標(biāo)代碼。標(biāo)代碼。（1）確定數(shù)據(jù)類型）確定數(shù)據(jù)類型（2）語義檢查）語義檢查動態(tài)語義檢查：在運行時刻進行動態(tài)語義檢查：在運行時刻進行 靜態(tài)語義檢查：在編譯時完成靜態(tài)語義檢查：在編譯時完成（3）識別含義，進行真正的翻譯）識別含義，進行真正的翻譯5.15.1語義分析的任務(wù)語義分析的任務(wù)2021-10-1762021-10-176編編 譯譯 原原 理理2021年10月17日類型檢查類型檢查?？刂屏鳈z查控制流檢查，確保控制語句有合法的轉(zhuǎn)向點。例，確?？刂普Z句有合法的轉(zhuǎn)向點。例如，如，C語言中的語言中的break語句使控制跳離包括該語句的語句使控制跳離包括該語句的最小的最小的swit

5、ch，while或或for語句。如果不存在包括它語句。如果不存在包括它的這樣的語句，則應(yīng)報錯。的這樣的語句，則應(yīng)報錯。靜態(tài)語義檢查靜態(tài)語義檢查2021-10-1772021-10-177編編 譯譯 原原 理理2021年10月17日靜態(tài)語義檢查靜態(tài)語義檢查一致性檢查一致性檢查。很多情況下要求對象只能被定義一。很多情況下要求對象只能被定義一次。例如，語言中規(guī)定一個標(biāo)識符在同一作用域中次。例如，語言中規(guī)定一個標(biāo)識符在同一作用域中只能被說明一次，同一只能被說明一次，同一case語句的標(biāo)號不能相同，枚語句的標(biāo)號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等。舉類型的元素不能重復(fù)出現(xiàn)等。相關(guān)名字檢查相關(guān)名字檢查。

6、有的語言中有時規(guī)定，同一名字。有的語言中有時規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，必須出現(xiàn)兩次或多次。例如，Ada語言中，循環(huán)或程語言中，循環(huán)或程序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，如同語句括號一般，編譯程序必須檢查它們的配尾，如同語句括號一般，編譯程序必須檢查它們的配對情況。對情況。2021-10-1782021-10-178編編 譯譯 原原 理理2021年10月17日實際應(yīng)用中比較流行的語義分析方法：實際應(yīng)用中比較流行的語義分析方法：基于基于屬性文法屬性文法的的語法制導(dǎo)翻譯方法語法制導(dǎo)翻譯方法 5.25.2語法制導(dǎo)翻譯語法制導(dǎo)翻

7、譯2021-10-1792021-10-179編編 譯譯 原原 理理2021年10月17日附加了一組附加了一組屬性屬性和和運算（語義）規(guī)則運算（語義）規(guī)則的的文法文法 5.2.1 屬性文法屬性文法文法符號文法符號X的屬性的屬性t常用常用X.t來表示來表示 語義規(guī)則是根據(jù)產(chǎn)生式所語義規(guī)則是根據(jù)產(chǎn)生式所蘊涵的語義蘊涵的語義操作建立起來的，操作建立起來的，并與并與語義分析的目標(biāo)語義分析的目標(biāo)有關(guān)有關(guān)不同的不同的產(chǎn)生式產(chǎn)生式對應(yīng)不同的語義規(guī)則對應(yīng)不同的語義規(guī)則不同的不同的分析目標(biāo)分析目標(biāo)也對應(yīng)不同的語義規(guī)則也對應(yīng)不同的語義規(guī)則 1. 屬性的表示屬性的表示2.語義規(guī)則語義規(guī)則的表示的表示語義信息語義信息

8、語義之間的關(guān)系語義之間的關(guān)系靜態(tài)語義檢查、符號靜態(tài)語義檢查、符號表操作、代碼生成及表操作、代碼生成及打印各種錯誤信息打印各種錯誤信息 2021-10-17102021-10-1710編編 譯譯 原原 理理2021年10月17日 非終結(jié)符非終結(jié)符E E、T T及及F F都有一個綜合屬性都有一個綜合屬性val,val,符號符號i i有一個綜合屬性，它的值由詞法分析器提供。有一個綜合屬性，它的值由詞法分析器提供。 某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)中同一非終結(jié)符多次出現(xiàn)語語 義義 規(guī)規(guī) 則則E E1+TE T T T1 * FT FF

9、(E)F i E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.valF.val=E.val F.val=i.lexval產(chǎn)生式產(chǎn)生式例例5.15.12021-10-17112021-10-1711編編 譯譯 原原 理理2021年10月17日5.2.2 語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：將將語義規(guī)則語義規(guī)則與與語法規(guī)則語法規(guī)則相結(jié)合，在相結(jié)合，在語法分析語法分析的過程中通過執(zhí)行的過程中通過執(zhí)行語義動作語義動作，計算語義屬，計算語義屬性值，從而完成預(yù)定的翻譯工作。性值，從而完成預(yù)定的翻譯工作。 YaccY

10、acc利用的就是語法制導(dǎo)翻譯方法，它使用符號利用的就是語法制導(dǎo)翻譯方法，它使用符號$表示表示產(chǎn)生式左端的屬性，產(chǎn)生式左端的屬性，$n$n表示存取產(chǎn)生式右端第表示存取產(chǎn)生式右端第n n個文法符個文法符號相聯(lián)的屬性號相聯(lián)的屬性expr : expr + expr $ = $1 + $3; 2021-10-17122021-10-1712編編 譯譯 原原 理理2021年10月17日自底向上語自底向上語法制導(dǎo)翻譯法制導(dǎo)翻譯自頂向下語自頂向下語法制導(dǎo)翻譯法制導(dǎo)翻譯語法制導(dǎo)翻譯的實現(xiàn)語法制導(dǎo)翻譯的實現(xiàn)2021-10-17132021-10-1713編編 譯譯 原原 理理2021年10月17日語法制導(dǎo)翻譯分

11、為兩種語法制導(dǎo)翻譯分為兩種處理方法處理方法：（1）語法制導(dǎo)定義（自底向上）：）語法制導(dǎo)定義（自底向上）：對每個產(chǎn)生式編制一個語義子程序，在進行語法分析的過對每個產(chǎn)生式編制一個語義子程序，在進行語法分析的過程中，程中，當(dāng)一個產(chǎn)生式獲得匹配時當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)則的計算次序等實現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。則的計算次序等實現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。（2）翻譯方案（自頂向下）：）翻譯方案（自頂向下）：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分在產(chǎn)生式右

12、部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進程，執(zhí)行遇到的語義動作。這是一種析的進程，執(zhí)行遇到的語義動作。這是一種動作與分析交動作與分析交錯錯的實現(xiàn)方案。的實現(xiàn)方案。2021-10-17142021-10-1714編編 譯譯 原原 理理2021年10月17日輸入符號串輸入符號串 分析樹分析樹執(zhí)行執(zhí)行語義規(guī)則語義規(guī)則 翻譯結(jié)果翻譯結(jié)果翻譯步驟翻譯步驟（）從分析樹得到描述結(jié)點屬性間依賴關(guān)系的（）從分析樹得到描述結(jié)點屬性間依賴關(guān)系的依賴圖依賴圖，由，由依賴圖得到語義規(guī)則的依賴圖得到語義規(guī)則的計算次序計算次序 （1）分析輸入符號串，建立）分析輸入符號串，建立分析語法樹分析語法樹（）進行語義規(guī)則的計算

13、，得到翻譯結(jié)果（）進行語義規(guī)則的計算，得到翻譯結(jié)果 2021-10-17152021-10-1715編編 譯譯 原原 理理2021年10月17日5.2.3 語法制導(dǎo)定義語法制導(dǎo)定義對每個產(chǎn)生式編制一個對每個產(chǎn)生式編制一個語義子程序語義子程序在進行語法分析的過程中，在進行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯綜合屬性綜合屬性繼承屬性繼承屬性自底向上自底向上傳遞信息傳遞信息自頂向下（自左自頂向下（自左向右）向右）傳遞信息傳遞信息2021-10-17162021-10-1716編編 譯譯 原原

14、 理理2021年10月17日 print(E.val)print(E.val)打印由打印由E E產(chǎn)生的算術(shù)表達(dá)式的值，產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這條規(guī)則定義了可認(rèn)為這條規(guī)則定義了L L的一個的一個虛屬性虛屬性。 L EE E1+TE T T T1 * FT FF (E)F iprint(E.val) E.val=E1.val+T.valE.val=T.val T.val=T1.val F.val T.val=F.valF.val=E.valF.val=i.lexval例例5.5.綜合屬性綜合屬性語語 義義 規(guī)規(guī) 則則產(chǎn)生式產(chǎn)生式2021-10-17172021-10-1717編編 譯譯 原原

15、 理理2021年10月17日 一個結(jié)點的綜合屬性一個結(jié)點的綜合屬性值是其值是其子結(jié)點子結(jié)點的某些的某些屬性來決定的屬性來決定的+3+3* *4 4的注釋分析樹的注釋分析樹通常使用通常使用自底向上自底向上的分析方法的分析方法在在每個結(jié)點每個結(jié)點處使用語義規(guī)則處使用語義規(guī)則來計算綜合屬性值來計算綜合屬性值當(dāng)一個當(dāng)一個產(chǎn)生式獲得匹配產(chǎn)生式獲得匹配時，時，就調(diào)用相應(yīng)的語義子程序就調(diào)用相應(yīng)的語義子程序從從葉結(jié)點到根結(jié)點葉結(jié)點到根結(jié)點進行計算進行計算 只含有只含有綜合屬性綜合屬性的語法制的語法制導(dǎo)定義稱為導(dǎo)定義稱為S S屬性定義屬性定義2021-10-17182021-10-1718編編 譯譯 原原 理理

16、2021年10月17日5.2.5 S屬性定義與自底向上翻譯屬性定義與自底向上翻譯 LRLR分析器可以改造為一個翻譯器，在對輸入串分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算進行語法分析的同時對屬性進行計算 LRLR分析器增加分析器增加屬性值（語義）棧屬性值（語義）棧 2021-10-17192021-10-1719編編 譯譯 原原 理理2021年10月17日步步 驟驟狀狀 態(tài)態(tài) 棧棧符符 號號 棧棧屬屬 性性 值值 棧棧剩余符號串剩余符號串分分 析析 動動 作作10#2+3*4#移進移進205#2+3*4#用用Fi歸約歸約303#F2+3*4#用用TF歸約歸約402#

17、T2+3*4#用用ET歸約歸約501#E23*4#移進移進6016#E+2*4#移進移進70165#E+32*4#用用Fi歸約歸約80163#E+F23*4#用用TF歸約歸約90169#E+T23*4#移進移進1001697#E+T*234#移進移進11016975#E+T*423#用用Fi歸約歸約1201697 10#E+T*F234#用用TT*F歸約歸約130169#E+T2 (12)#用用EE+T歸歸約約1401#E (14)#acc2021-10-17202021-10-1720編編 譯譯 原原 理理2021年10月17日產(chǎn)生式產(chǎn)生式語語 義義 規(guī)規(guī) 則則D TL T int T fl

18、oat L L1,idL idL.in=T.typeT.type=intT.type=floatL1.in=L.in enter(id.entry,L.in) enter(id.entry,L.in)例例5.35.3繼承屬性繼承屬性L.inint id1,id2,id3DL.in= intL.in= intL.in= intT.type=intintid2id1id3.， 一個結(jié)點的繼承屬性值一個結(jié)點的繼承屬性值是由其是由其父結(jié)點或兄弟結(jié)父結(jié)點或兄弟結(jié)點點的某些屬性決定的的某些屬性決定的2021-10-17212021-10-1721編編 譯譯 原原 理理2021年10月17日1、文法非終結(jié)符

19、既有綜合屬性，也可有繼承屬性；、文法非終結(jié)符既有綜合屬性，也可有繼承屬性；2、開始符號沒有繼承屬性；、開始符號沒有繼承屬性；3、終結(jié)符只有綜合屬性，由詞法分析器提供。、終結(jié)符只有綜合屬性，由詞法分析器提供。幾點說明：幾點說明：2021-10-17222021-10-1722編編 譯譯 原原 理理2021年10月17日生成中間代碼的生成中間代碼的目的目的(1)便于優(yōu)化便于優(yōu)化(2)便于移植便于移植常見的中間代碼常見的中間代碼形式形式：后綴式后綴式三地址代碼三地址代碼（四元式、三元式和間接三元式（四元式、三元式和間接三元式 ）圖形圖形（抽象語法樹、有向無環(huán)圖）（抽象語法樹、有向無環(huán)圖） 中間代碼：

20、一種介于中間代碼：一種介于源語言和目標(biāo)語言之間源語言和目標(biāo)語言之間的中間語言形式的中間語言形式5.5.中間代碼中間代碼2021-10-17232021-10-1723編編 譯譯 原原 理理2021年10月17日.java java源程序文件.class 二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯JavaJava語言語言2021-10-17242021-10-1724編編 譯譯 原原 理理2021年10月17日.NET.NET框架框架 2021-10-17252021-10-1725編編 譯譯 原原 理理2021年10月17日GCCGCC 2021-10-17262021-10-

21、1726編編 譯譯 原原 理理2021年10月17日中綴表示中綴表示后綴表示后綴表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特點特點1、運算對象出現(xiàn)的順序和原有順序（從左到右）相同、運算對象出現(xiàn)的順序和原有順序（從左到右）相同2、運算符按實際計算順序（從左到右）出現(xiàn)、運算符按實際計算順序（從左到右）出現(xiàn)3、運算符緊跟在運算對象的后面出現(xiàn)，且沒有括號、運算符緊跟在運算對象的后面出現(xiàn)，且沒有括號優(yōu)點：簡明、便于計值優(yōu)點：簡明、便于計值5.3.1 后綴式后綴式2021-10-17272021-10-1727編編 譯譯 原原 理理2021

22、年10月17日分別給出下列表達(dá)式的后綴表示分別給出下列表達(dá)式的后綴表示1. -a+b*(-c+d)2. X:=-(a+b)/(c-d)-(a+b*c)3. a=c b=d4. ab+c ada+bea-bc-d+*+Xab+-cd-/abc*+-:=ac= bd=abc+ ad ab+e 2021-10-17282021-10-1728編編 譯譯 原原 理理2021年10月17日5.3.2 三地址代碼三地址代碼種類種類（1）x = y op z形式的賦值語句，其中形式的賦值語句，其中op是二元運算符。是二元運算符。（2）x = op y形式的賦值語句，其中形式的賦值語句，其中op是一元運算符。

23、是一元運算符。（3）x = y形式的賦值語句。形式的賦值語句。（4）無條件轉(zhuǎn)移語句）無條件轉(zhuǎn)移語句goto L，表示下一個要執(zhí)行的語句是，表示下一個要執(zhí)行的語句是標(biāo)號為標(biāo)號為L的語句。的語句。（5）條件轉(zhuǎn)移語句）條件轉(zhuǎn)移語句if x rop y goto L中，中，rop為關(guān)系運算符，為關(guān)系運算符，如果如果x和和y滿足關(guān)系滿足關(guān)系rop，就轉(zhuǎn)而執(zhí)行標(biāo)號為，就轉(zhuǎn)而執(zhí)行標(biāo)號為L的語句，否則的語句，否則順序執(zhí)行下一個語句。順序執(zhí)行下一個語句。2021-10-17292021-10-1729編編 譯譯 原原 理理2021年10月17日（6）過程調(diào)用語句）過程調(diào)用語句param x 和和call p ,

24、 n。源程序中的過程。源程序中的過程調(diào)用語句調(diào)用語句p(x1，x2，xn)可以產(chǎn)生如下的三地址代碼：可以產(chǎn)生如下的三地址代碼：param x1param x2 param xncall p, n其中其中n為實參個數(shù)。過程返回語句形如為實參個數(shù)。過程返回語句形如return y，其中，其中y為為過程返回的一個值。過程返回的一個值。 2021-10-17302021-10-1730編編 譯譯 原原 理理2021年10月17日（7）變址賦值：）變址賦值：x= yi，把從，把從y開始的第開始的第i個存儲單元的值賦給個存儲單元的值賦給x。xi= y，把，把y的值賦給的值賦給x開始的第開始的第i個存儲單元

25、。個存儲單元。其中，其中，x，y和和i都代表數(shù)據(jù)對象。都代表數(shù)據(jù)對象。（8）地址和指針賦值：）地址和指針賦值：x=&y，把，把y的地址賦給的地址賦給x。x= y，把，把y指示的地址單元中的內(nèi)容賦給指示的地址單元中的內(nèi)容賦給x。 x = y，把，把x指向的存儲單元的值置為指向的存儲單元的值置為y。2021-10-17312021-10-1731編編 譯譯 原原 理理2021年10月17日2具體實現(xiàn)具體實現(xiàn)四元式四元式操作符操作符 操作數(shù)操作數(shù)1 操作數(shù)操作數(shù)2 結(jié)果結(jié)果結(jié)果：通常是由編譯引進的臨時變量結(jié)果：通常是由編譯引進的臨時變量例例: X=(A+B)*(C+D)-E+, A, B, T1+,

26、 C, D, T2*, T1, T2, T3-, T3, E, T4=, T4, 一一, XT1,T2,T3,T4為臨時變量，為臨時變量，由四元式優(yōu)化比較方便由四元式優(yōu)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T42021-10-17322021-10-1732編編 譯譯 原原 理理2021年10月17日操作符操作符 左操作符數(shù)左操作符數(shù) 右操作數(shù)右操作數(shù) 表達(dá)式的三元式：表達(dá)式的三元式：w*x+(y+z)(1) *, w, x(2) +, y, z(3) +, (1), (2) 第三個三元第三個三元式中的操作數(shù)式中的操作數(shù)(1)(2)表示第表示第(1)和第和第(2)

27、條三元式的計條三元式的計算結(jié)果。算結(jié)果。三三元式元式2021-10-17332021-10-1733編編 譯譯 原原 理理2021年10月17日例：例： A=B+C*D/E F=C*D三元式三元式(1) *, C, D(2) / , (1), E(3) +, B, (2) (4) =, A, (3)(5) *, C, D(6) =, F, (1)不便于代碼優(yōu)化：刪不便于代碼優(yōu)化：刪除某些三元式后可能除某些三元式后可能需作一系列的修改需作一系列的修改 三元式三元式(1) *, C, D(2) / , (1), E(3) +, B, (2) (4) =, A, (3)(5) =, F, (1)間接

28、三元式間接三元式執(zhí)行順序執(zhí)行順序(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張三元式的執(zhí)行次序用另一張表表示表表示, 優(yōu)化時三元式可以不優(yōu)化時三元式可以不變，僅僅改變其執(zhí)行順序表變，僅僅改變其執(zhí)行順序表2021-10-17342021-10-1734編編 譯譯 原原 理理2021年10月17日例：例：x = y +y z + y z 抽象語法樹抽象語法樹5.3.3 圖形表示圖形表示有向無環(huán)圖有向無環(huán)圖2021-10-17352021-10-1735編編 譯譯 原原 理理2021年10月17日5.95.9PL/0PL/0編譯程序的語義分析編譯程序的語義分析特點：將語義子程序嵌入到每

29、個遞歸過程中特點：將語義子程序嵌入到每個遞歸過程中，通過遞歸子，通過遞歸子程序內(nèi)部的局部量和參數(shù)傳遞語義信息。程序內(nèi)部的局部量和參數(shù)傳遞語義信息。對于某個產(chǎn)生式，不必產(chǎn)生式右部所有符號掃描后再處理，對于某個產(chǎn)生式，不必產(chǎn)生式右部所有符號掃描后再處理，可在處理一個符號后，隨時加進有關(guān)該符號的語義子程序。可在處理一個符號后，隨時加進有關(guān)該符號的語義子程序。自頂向下語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯回憶回憶“4.7 PL/04.7 PL/0編譯程序的語法分析編譯程序的語法分析”（見第（見第4 4章講義）章講義）2021-10-17362021-10-1736編編 譯譯 原原 理理2021年10月17日

30、 為 dx，tx 置初值，暫時將代碼 code的下標(biāo)指針 cx 值保存在 table 表中 N Y N N Y N Y 常量說明處理 sym=procsym? 在 table 表中登記過程名 變量說明處理 遞歸調(diào)用 block, 參數(shù) lev+1 測試 sym 是否為語句開始符? 出錯 處理 在 table 表中返回過程體入口口 Y sym=constsym? sym=varsym? block 說明部說明部分分2021-10-17372021-10-1737編編 譯譯 原原 理理2021年10月17日Y Y N N N sym=procsym? 在 table 表中登記過程名 變量說明處理

31、遞歸調(diào)用 block, 參數(shù) lev+1 取單詞 getsym 測試 sym 是否為語句后跟符? 出錯 處理 調(diào)用列目標(biāo)程序函數(shù) 返回 測試 sym 是否為語句開始符? 出錯 處理 在 table 表中返回過程體入口口 生成開辟數(shù)據(jù)段指令：ini 0 a 調(diào)用語句處理函數(shù) 生成退出數(shù)據(jù)段指令： opr 0 0 Y 2021-10-17382021-10-1738編編 譯譯 原原 理理2021年10月17日5.9.1 說明部分的分析說明部分的分析 對每個過程的對每個過程的說明對象說明對象填寫符號表填寫符號表 具體要填寫標(biāo)識符的具體要填寫標(biāo)識符的名字、屬性、所在層次和分名字、屬性、所在層次和分配的

32、相對位置配的相對位置等等 標(biāo)識符的標(biāo)識符的屬性屬性不同時，所需要填寫的信息也有所不同時，所需要填寫的信息也有所不同不同 符號表的填寫是由符號表的填寫是由enterenter函數(shù)來完成的函數(shù)來完成的2021-10-17392021-10-1739編編 譯譯 原原 理理2021年10月17日enum objectconstant,variable,procedure; /枚舉定義常量、變量和過程枚舉定義常量、變量和過程enum object kind;struct table1/符號表為結(jié)構(gòu)體型數(shù)據(jù)符號表為結(jié)構(gòu)體型數(shù)據(jù) char name AL; /標(biāo)識符名字，最長為標(biāo)識符名字，最長為AL，已定義

33、為，已定義為10 enum object kind; /標(biāo)識符名字的屬性，為常量、變量或過程標(biāo)識符名字的屬性，為常量、變量或過程 int val,level,adr, size; struct table1 tableTXMAX+1; /符號表用一維數(shù)組符號表用一維數(shù)組table來表示，最多有來表示，最多有TXMAX項，項，TXMAX已定義為已定義為1002021-10-17402021-10-1740編編 譯譯 原原 理理2021年10月17日const a=35const a=35，b=49b=49；var cvar c，d d，e e；procedure pprocedure p；var

34、 gvar g namename kind level/val adr size表格管理表格管理a a b b c c d d e e p p c co on ns st ta an nt t c co on ns st ta an nt t v va ar ri ia ab bl le e v va ar ri ia ab bl le e v va ar ri ia ab bl le e p pr ro oc ce ed du ur re e 3 35 5 4 49 9 l le ev v l le ev v l le ev v l le ev v d dx x d dx x+ +1 1 d

35、 dx x+ +2 2 4 4 g g v va ar ri ia ab bl le e l le ev v+ +1 1 d dx x 2021-10-17412021-10-1741編編 譯譯 原原 理理2021年10月17日變量定義語句的處理變量定義語句的處理if(strcmp(sym,varsym)=0) getsym(); do vardeclaration( );/處理一個變量處理一個變量 while (strcmp(sym,comma)=0) getsym(); vardeclaration( ); if (strcmp(sym,semicolon)=0) getsym(); el

36、se error(5); while (strcmp(sym,ident)=0);2021-10-17422021-10-1742編編 譯譯 原原 理理2021年10月17日if(strcmp(sym,varsym)=0) /* 遇到變量說明符號，處理變量說明遇到變量說明符號，處理變量說明 */ getsym(); do vardeclaration(); /* 處理一個變量處理一個變量 */ while (strcmp(sym,comma)=0) getsym(); vardeclaration(); if(strcmp(sym,semicolon)=0) getsym(); else er

37、ror(5); /* 漏掉了漏掉了,或或; */ while (strcmp(sym,ident)=0); 變量定義語句的處理變量定義語句的處理變量說明部分變量說明部分-var-var標(biāo)識符標(biāo)識符 ，標(biāo)識符，標(biāo)識符 ； 2021-10-17432021-10-1743編編 譯譯 原原 理理2021年10月17日變量定義語句的處理變量定義語句的處理void vardeclaration() if(strcmp(sym,ident)=0) enter(variable); /* 填寫符號表填寫符號表 */ getsym(); else error(4); /* var后應(yīng)為標(biāo)識符后應(yīng)為標(biāo)識符 */

38、2021-10-17442021-10-1744編編 譯譯 原原 理理2021年10月17日void enter(enum object k)void enter(enum object k) tx=tx+1; / tx=tx+1; /* * 表的登記項目增加表的登記項目增加 * */ / strcpy(,id); / strcpy(,id); /* * 記錄標(biāo)識符的名字記錄標(biāo)識符的名字 * */ / tabletx.kind=k; / tabletx.kind=k; /* * 標(biāo)識符的種類（常量、變量或過程）標(biāo)識符的種類（常量、變量或過程）*

39、*/ / switch(k) / switch(k) /* * 分類別登記符號表分類別登記符號表 * */ / case constant: / case constant: /* * 常量常量 * */ / if(numAMAX) if(numAMAX) error(31); / error(31); /* * 常數(shù)大于常數(shù)大于AMAX 2047 AMAX 2047 * */ / num=0; num=0; tabletx.val=num; / tabletx.val=num; /* * 登記常數(shù)的值登記常數(shù)的值 * */ / break; break; case variable: / c

40、ase variable: /* * 變量變量 * */ / tabletx.level=lev; / tabletx.level=lev; /* * 登記變量的層次登記變量的層次 * */ / tabletx.adr=dx; / tabletx.adr=dx; /* * 登記變量的地址登記變量的地址 * */ / dx+; dx+; break; break; case procedure: / case procedure: /* * 過程過程 * */ / tabletx.level=lev; / tabletx.level=lev; /* * 登記過程的層次登記過程的層次 * */ /

41、 break; break; 函數(shù)函數(shù)enterenter的實現(xiàn)的實現(xiàn)2021-10-17452021-10-1745編編 譯譯 原原 理理2021年10月17日5.9.2 過程體部分的分析過程體部分的分析 根據(jù)根據(jù)當(dāng)前讀入的符號當(dāng)前讀入的符號就可以立即斷定它應(yīng)屬于哪就可以立即斷定它應(yīng)屬于哪一種語句，當(dāng)語法正確時就生成相應(yīng)語句功能的一種語句，當(dāng)語法正確時就生成相應(yīng)語句功能的目標(biāo)代碼。目標(biāo)代碼。 凡遇到凡遇到標(biāo)識符標(biāo)識符，都要調(diào)用，都要調(diào)用position函數(shù)查找符號表函數(shù)查找符號表 若該標(biāo)識符已定義，則若該標(biāo)識符已定義，則返回它在符號表中的位置返回它在符號表中的位置，并據(jù)，并據(jù)此取得有關(guān)屬性信

42、息，然后翻譯生成相應(yīng)的目標(biāo)代碼此取得有關(guān)屬性信息，然后翻譯生成相應(yīng)的目標(biāo)代碼 若符號表中沒有該標(biāo)識符，則若符號表中沒有該標(biāo)識符，則返回返回0，表示出錯，表示出錯 注意查找符號表時是注意查找符號表時是從后向前查從后向前查 2021-10-17462021-10-1746編編 譯譯 原原 理理2021年10月17日 if (strcmp(sym,beginsym)=0)if (strcmp(sym,beginsym)=0) getsym( ); getsym( ); statement(add(temp3,fsys),plev); statement(add(temp3,fsys),plev);

43、while(in(sym,add(temp4,statbegsys)=1) while(in(sym,add(temp4,statbegsys)=1) if (strcmp(sym,semicolon)=0) getsym(); if (strcmp(sym,semicolon)=0) getsym(); else error(10); else error(10); / /* *語句之間漏了語句之間漏了；* */ / statement(add(temp3,fsys),plev); statement(add(temp3,fsys),plev); if (strcmp(sym,endsym)

44、=0) if (strcmp(sym,endsym)=0) getsym(); getsym(); else error(17); else error(17); / /* *丟了丟了endend或或；* */ / := begin := begin;endend2021-10-17472021-10-1747編編 譯譯 原原 理理2021年10月17日 if (strcmp(sym,ident)=0)if (strcmp(sym,ident)=0) i=position(id); i=position(id); if(i=0)error(ll); if(i=0)error(ll); / /*

45、 *標(biāo)識符未說明標(biāo)識符未說明* */ / else if(tablei.kind!=variable) else if(tablei.kind!=variable) error(12); error(12); / /* *賦值語句中賦值語句中, , 賦值號左部標(biāo)識符屬性應(yīng)是變量賦值號左部標(biāo)識符屬性應(yīng)是變量* */ / i=0; i=0; getsym(); getsym(); if (strcmp(sym,becomes)=0) getsym(); if (strcmp(sym,becomes)=0) getsym(); else error(13); else error(13); / /*

46、 *賦值語句左部標(biāo)識符后應(yīng)是賦值號賦值語句左部標(biāo)識符后應(yīng)是賦值號:=:=* */ / expression(fsys); expression(fsys); if (i!=0) if (i!=0) gen(sto,plev-tablei.level,tablei.adr);gen(sto,plev-tablei.level,tablei.adr); / /* *將棧頂內(nèi)容送入某變量單元中將棧頂內(nèi)容送入某變量單元中* */ / := := :=:= 2021-10-17482021-10-1748編編 譯譯 原原 理理2021年10月17日 if(strcmp(sym,readsym)=0)if

47、(strcmp(sym,readsym)=0) getsym(); getsym(); if (strcmp(sym,lparen)!=0) error(24); if (strcmp(sym,lparen)!=0) error(24); else else do do getsym(); getsym(); if (strcmp(sym,ident)=0) i=position(id); if (strcmp(sym,ident)=0) i=position(id); else i=0; else i=0; if (i=0) error( if (i=0) error(3232);); el

48、se else gen(opr,0,16);gen(opr,0,16);/ /* *從命令行讀入一個輸入置于棧頂從命令行讀入一個輸入置于棧頂* */ / gen(sto,plev-tablei.level,tablei.adr);gen(sto,plev-tablei.level,tablei.adr); / /* *將棧頂內(nèi)容送入某變量單元中將棧頂內(nèi)容送入某變量單元中* */ / getsym(); getsym(); while(strcmp(sym,comma)=0); while(strcmp(sym,comma)=0); if (strcmp(sym,rparen)!=0) if (

49、strcmp(sym,rparen)!=0) error(22); error(22);while(in (sym,fsys)=0) getsym(); while(in (sym,fsys)=0) getsym(); else getsym(); else getsym(); =read(=read(， )2021-10-17492021-10-1749編編 譯譯 原原 理理2021年10月17日5.9.3 PL/0編譯程序目標(biāo)代碼的結(jié)構(gòu)編譯程序目標(biāo)代碼的結(jié)構(gòu) 目標(biāo)代碼目標(biāo)代碼pcodepcode是一種假想棧式計算機的是一種假想棧式計算機的匯編語言。匯編語言。 指令格式：指令格式：f l a

50、f l af f功能碼功能碼l l層次差層次差a a根據(jù)不同的指令有所區(qū)別根據(jù)不同的指令有所區(qū)別2021-10-17502021-10-1750編編 譯譯 原原 理理2021年10月17日struct instruction /* 目標(biāo)代碼的結(jié)構(gòu)目標(biāo)代碼的結(jié)構(gòu) */ enum fct f; int l; int a; struct instruction codeCXMAX+1; /* 記錄所生成的目標(biāo)代碼記錄所生成的目標(biāo)代碼 */2021-10-17512021-10-1751編編 譯譯 原原 理理2021年10月17日f flainiini0 0常常 量量litlit0 常常 量量 lod

51、lod層次差層次差 數(shù)據(jù)地址數(shù)據(jù)地址 stosto層次差層次差 數(shù)據(jù)地址數(shù)據(jù)地址 calcal層次差層次差 程序地址程序地址 jmpjmp0 0程序地址程序地址 jpcjpc0 0程序地址程序地址 opropr0 0運算類別運算類別 8 8條目標(biāo)指令條目標(biāo)指令層次差層次差為變量名或過程名引用和聲明之間的靜態(tài)層次差為變量名或過程名引用和聲明之間的靜態(tài)層次差程序地址程序地址為目標(biāo)數(shù)組為目標(biāo)數(shù)組codecode的下標(biāo)的下標(biāo)數(shù)據(jù)地址數(shù)據(jù)地址為變量在局部存貯中的相對地址為變量在局部存貯中的相對地址2021-10-17522021-10-1752編編 譯譯 原原 理理2021年10月17日23條指令詳解條

52、指令詳解根據(jù)上面的解釋去理解函數(shù)根據(jù)上面的解釋去理解函數(shù)interpret( )2021-10-17532021-10-1753編編 譯譯 原原 理理2021年10月17日5.9.4 PL/0編譯程序目標(biāo)代碼的生成編譯程序目標(biāo)代碼的生成 PL/0PL/0語言的代碼生成是由函數(shù)語言的代碼生成是由函數(shù)gengen完成。完成。 gengen有三個參數(shù)，分別代表目標(biāo)代碼的功有三個參數(shù)，分別代表目標(biāo)代碼的功能碼，層差和位移量。能碼，層差和位移量。gen(opr,0,16); gen(sto,lev-level,adr)gen(opr,0,16); gen(sto,lev-level,adr) 生成的代碼

53、順序放在數(shù)組生成的代碼順序放在數(shù)組codecode中中codecode為一維數(shù)組，數(shù)組元素為結(jié)構(gòu)體型數(shù)為一維數(shù)組，數(shù)組元素為結(jié)構(gòu)體型數(shù)據(jù)。每個元素就是一條目標(biāo)指令。據(jù)。每個元素就是一條目標(biāo)指令。cxcx為指令為指令的指針，由的指針，由0 0開始順序增加開始順序增加目標(biāo)代碼的順序是內(nèi)層過程的在前邊，主目標(biāo)代碼的順序是內(nèi)層過程的在前邊，主程序的目標(biāo)代碼在最后程序的目標(biāo)代碼在最后2021-10-17542021-10-1754編編 譯譯 原原 理理2021年10月17日void gen(x,y,z)void gen(x,y,z)enum fct x;enum fct x;int y,z;int y,

54、z; if (cxCXMAX)if (cxCXMAX) printf(program too long); printf(program too long); codecx.f=x;codecx.f=x;codecx.l=y;codecx.l=y;codecx.a=z;codecx.a=z;cx+;cx+; 代碼生成的實現(xiàn)代碼生成的實現(xiàn)2021-10-17552021-10-1755編編 譯譯 原原 理理2021年10月17日代碼生成的規(guī)則代碼生成的規(guī)則（1）每個過程開始前，生成）每個過程開始前，生成1條條jmp 0 0指令，若連續(xù)嵌套說明幾個過程，指令，若連續(xù)嵌套說明幾個過程，則連續(xù)生成幾條

55、則連續(xù)生成幾條jmp 0 0指令。這條指令的含義是可以跳轉(zhuǎn)到相應(yīng)的過程，指令。這條指令的含義是可以跳轉(zhuǎn)到相應(yīng)的過程，其中跳轉(zhuǎn)地址是在此過程的目標(biāo)代碼生成后，再進行回填。其中跳轉(zhuǎn)地址是在此過程的目標(biāo)代碼生成后，再進行回填。（2）進入每個過程后，首先生成一條）進入每個過程后，首先生成一條ini 0 a指令（指令（a=局部變量數(shù)局部變量數(shù)+3），其），其含義是在數(shù)據(jù)棧中為被調(diào)用的過程開辟含義是在數(shù)據(jù)棧中為被調(diào)用的過程開辟a個單元的數(shù)據(jù)區(qū)。個單元的數(shù)據(jù)區(qū)。（3）一個過程結(jié)束后，生成一條）一個過程結(jié)束后，生成一條opr 0 0指令，表明返回調(diào)用點。指令，表明返回調(diào)用點。（4）在語句中遇到常量（不論是常數(shù)

56、還是常量標(biāo)識符）時，生成一條）在語句中遇到常量（不論是常數(shù)還是常量標(biāo)識符）時，生成一條lit 0 a指令（指令（a=常量值），其含義是將常量值置于數(shù)據(jù)棧的棧頂。這條指令是在常量值），其含義是將常量值置于數(shù)據(jù)棧的棧頂。這條指令是在factor函數(shù)中生成的。函數(shù)中生成的。（5）在語句中遇到變量時，生成一條）在語句中遇到變量時，生成一條lod lev-level adr指令，其中，指令，其中，lev是該是該語句所在過程段的層次，語句所在過程段的層次， level是變量說明的層次，是變量說明的層次， adr是變量的相對地址。是變量的相對地址。這條指令也是在這條指令也是在factor函數(shù)中生成的。函數(shù)中

57、生成的。（6）有關(guān)表達(dá)式及各種語句的翻譯規(guī)則見下面的詳細(xì)解釋。）有關(guān)表達(dá)式及各種語句的翻譯規(guī)則見下面的詳細(xì)解釋。 2021-10-17562021-10-1756編編 譯譯 原原 理理2021年10月17日表達(dá)式的翻譯表達(dá)式的翻譯 算術(shù)表達(dá)式算術(shù)表達(dá)式條件表達(dá)式條件表達(dá)式后綴式后綴式Y(jié) op ZY Z opNo.No.f fla100100lodlodY Y層次差層次差Y Y相對地址相對地址101101lodlodZ Z層次差層次差Z Z相對地址相對地址102102opropr-OP OP 2021-10-17572021-10-1757編編 譯譯 原原 理理2021年10月17日opr 0

58、1棧頂元素取反棧頂元素取反opr 0 2次棧頂與棧頂相加，退兩個棧元素，相加次棧頂與棧頂相加，退兩個棧元素，相加值進棧值進棧opr 0 3次棧頂減去棧頂次棧頂減去棧頂opr 0 4次棧頂乘以棧頂次棧頂乘以棧頂opr 0 5次棧頂除以棧頂次棧頂除以棧頂opr 0 6棧頂元素的奇偶判斷棧頂元素的奇偶判斷opr 0 8次棧頂與棧頂是否相等次棧頂與棧頂是否相等opr 0 9次棧頂與棧頂是否不等次棧頂與棧頂是否不等opr 0 10次棧頂是否小于棧頂次棧頂是否小于棧頂opr 0 11次棧頂是否大于等于棧頂次棧頂是否大于等于棧頂opr 0 12次棧頂是否大于棧頂次棧頂是否大于棧頂opr 0 13次棧頂是否小

59、于等于棧頂次棧頂是否小于等于棧頂2021-10-17582021-10-1758編編 譯譯 原原 理理2021年10月17日將將T(ident“=” expression)依次翻譯成：依次翻譯成：T(expression)sto l a （將棧頂元素值賦給層差為將棧頂元素值賦給層差為l、相對位置為、相對位置為a的變量的變量即即ident）No.No.f fla100100lodlodY Y層次差層次差Y Y相對地址相對地址101101lodlodZ Z層次差層次差Z Z相對地址相對地址102102opropr-OP OP 103103stostoX X層次差層次差 X X相對地址相對地址賦值語

60、句的翻譯賦值語句的翻譯 X := Y op Z2021-10-17592021-10-1759編編 譯譯 原原 理理2021年10月17日將將T(“read” “(” ident ”)” )翻譯成：翻譯成：opr 0 16（先讀入一個數(shù)據(jù)置于棧頂）（先讀入一個數(shù)據(jù)置于棧頂）sto l a（將棧頂元素即剛讀入的數(shù)據(jù)出棧，值賦給層（將棧頂元素即剛讀入的數(shù)據(jù)出棧，值賦給層差為差為l、相對位置為、相對位置為a的變量）的變量）read、write語句的翻譯語句的翻譯 將將T(“write” “(” ident ”)” )翻譯成：翻譯成：opr 0 14（輸出棧頂?shù)臄?shù)據(jù)）（輸出棧頂?shù)臄?shù)據(jù)）opr 0 15