編譯原理-第七章

1、2022-5-1TJNU-COCIE-WJW1編譯原理編譯原理第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生王金偉計算機與信息工程學院天津師范大學TJNU-COCIE-WJW22022-5-1第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生l在詞法分析和語法分析之后的階段就是語義分析在詞法分析和語法分析之后的階段就是語義分析和中間代碼生成和中間代碼生成l本章把第六章介紹的有關語法制導翻譯的相關方本章把第六章介紹的有關語法制導翻譯的相關方法和技術用在中間代碼生成和語義分析上法和技術用在中間代碼生成和語義分析上l主要工作主要工作l靜態(tài)語義檢查靜態(tài)語義檢查l翻譯翻譯TJNU-C

2、OCIE-WJW32022-5-1l靜態(tài)語義檢查靜態(tài)語義檢查l類型檢查類型檢查: :如果操作符作用于不相容的操作數(shù)，如果操作符作用于不相容的操作數(shù)，編譯程序必須報告出錯信息。編譯程序必須報告出錯信息。，在，在C C語言中語言中”.”.”因該作用與結(jié)構(gòu)體變量，因該作用與結(jié)構(gòu)體變量，若作用于指針變量應用若作用于指針變量應用“-”-”l控制流檢查控制流檢查: :控制流語句必須使控制轉(zhuǎn)移到合控制流語句必須使控制轉(zhuǎn)移到合法的地方。法的地方。，在，在C C語言中語言中breakbreak語句使控制跳離包括語語句使控制跳離包括語句的最小句的最小whilewhile、forfor或或switchswitch語

3、句。如果不存語句。如果不存在包括它的這樣的語句應該報錯。在包括它的這樣的語句應該報錯。TJNU-COCIE-WJW42022-5-1l靜態(tài)語義檢查靜態(tài)語義檢查l一致性檢查一致性檢查: :很多場合要求對象只能被定義一次很多場合要求對象只能被定義一次，PascalPascal語言規(guī)定同一標識符在一個分程序語言規(guī)定同一標識符在一個分程序中只能被說明一次，同一中只能被說明一次，同一casecase語句的標號不能相語句的標號不能相同，枚舉類型的元素不能重復出現(xiàn)等等。同，枚舉類型的元素不能重復出現(xiàn)等等。l相關名字檢查相關名字檢查: :有時，同一名字必須出現(xiàn)兩次或有時，同一名字必須出現(xiàn)兩次或多次。多次。，A

4、daAda語言程序中，循環(huán)或程序塊可以有一語言程序中，循環(huán)或程序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯程序必須檢查這兩個地方用的名字是相同的。程序必須檢查這兩個地方用的名字是相同的。l其他其他: :如名字的作用域分析等。如名字的作用域分析等。TJNU-COCIE-WJW52022-5-1l翻譯（產(chǎn)生中間代碼）翻譯（產(chǎn)生中間代碼）l采用獨立于機器的中間代碼的好處：采用獨立于機器的中間代碼的好處：l便于進行與機器無關的代碼優(yōu)化工作便于進行與機器無關的代碼優(yōu)化工作l使編譯程序改變目標機更容易使編譯程序改變目標機更容易l使編譯程序的結(jié)構(gòu)在邏輯上更

5、為簡單明確。以中間語使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確。以中間語言為界面，編譯前端和后端的接口更清晰言為界面，編譯前端和后端的接口更清晰靜態(tài)語義檢查和中間代碼生成器的位置靜態(tài)語義檢查和中間代碼生成器的位置語法語法分析器分析器靜靜 態(tài)態(tài)檢查器檢查器中間代碼中間代碼生成器生成器中間中間代碼代碼符號流符號流中間代碼中間代碼優(yōu)化器優(yōu)化器TJNU-COCIE-WJW62022-5-1第七章第七章 語義分析和中間代碼產(chǎn)生語義分析和中間代碼產(chǎn)生n7.1 中間語言中間語言n7.2 說明語句說明語句n7.3 賦值語句的翻譯賦值語句的翻譯n7.4 分情況語句分情況語句n7.5 回填技術回填技術n7.6 類型檢查

6、類型檢查TJNU-COCIE-WJW72022-5-17.1中間語言中間語言n中間語言中間語言 源程序的中間表示方法源程序的中間表示方法n中間語言的形式中間語言的形式后綴式后綴式圖表示法圖表示法 三地址代碼三地址代碼TJNU-COCIE-WJW82022-5-1把運算量把運算量( (操作數(shù)操作數(shù)) )寫在前面，把算符寫在后面。寫在前面，把算符寫在后面。：原式原式后綴式后綴式a+ba+b，ab+ab+a a* *b b，abab* *一、一、后綴式后綴式TJNU-COCIE-WJW92022-5-11.表達式表達式E的后綴表示遞歸定義的后綴表示遞歸定義n如果如果E是變量和常數(shù)，則是變量和常數(shù)，則

7、E的后綴表示是的后綴表示是E本身本身n如果如果E是形如是形如E1 op E2的表達式，其中的表達式，其中op是任是任意的二元算符，則意的二元算符，則E的后綴表示是的后綴表示是E1 E2 op，其中其中E1和和E2分別是分別是E1和和E2的后綴表示的后綴表示n如果如果E是形如是形如op E1的表達式，其中的表達式，其中op是一元是一元算符，則算符，則E的后綴表示是的后綴表示是E1 op，其中，其中E1 是是E1的后綴表示的后綴表示n如果如果E是形如是形如(E1)的表達式，則的表達式，則E1的后綴表示的后綴表示也是也是E的后綴表示的后綴表示：后綴式不需要括號：后綴式不需要括號TJNU-COCIE-

8、WJW102022-5-1：賦值語句：賦值語句 a := b *（- c）+ b *（ - 34）的后綴式的后綴式：a b c-*b 34-*+ :=TJNU-COCIE-WJW112022-5-11.1.特點和形式特點和形式描述了源程序的自然層次結(jié)構(gòu)描述了源程序的自然層次結(jié)構(gòu)n語法樹語法樹(抽象語法樹抽象語法樹)n有向無環(huán)圖有向無環(huán)圖(DAG)二、二、圖表示法圖表示法TJNU-COCIE-WJW122022-5-1：a := b * - c + b * - c后綴式是抽象語法樹的線性表示后綴式是抽象語法樹的線性表示后根序遍歷后根序遍歷 a b c uminus * b c uminus *

9、+ :=assigna+*bcuminus(a)抽象語法樹抽象語法樹*uminuscbTJNU-COCIE-WJW132022-5-1assigna+*bcuminus(b) DAG：a:=b * - c+b * -c其中，其中，b*-c是公共子表達式是公共子表達式TJNU-COCIE-WJW142022-5-12.產(chǎn)生賦值語句抽象語法樹的屬性文法產(chǎn)生賦值語句抽象語法樹的屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則S id := E S.nptr := mknode(:=, mkleaf(id, id.place), E.nptr )E E1 + E2E.nptr := mknode(+, E1.np

10、tr, E2.nptr )E E1 * E2E.nptr := mknode(*, E1.nptr, E2.nptr )E -E1E.nptr := mknode(uminus, E1.nptr )E ( E1 ) E.nptr := E1.nptrE idE.nptr := mkleaf(id , id.place )TJNU-COCIE-WJW152022-5-1：賦值語句：賦值語句：a:=b*-c+b*-c 抽象語法樹的表示方法抽象語法樹的表示方法后綴式：后綴式：a b c uminus * b c uminus * + assignassign + * uminus id a id c

11、 id b * uminus id c id b id b id c unimus 1 * 0 2 id b id c unimus 5 * 4 6 + 3 7 id a assign 9 8 . 01234567891011TJNU-COCIE-WJW162022-5-11.一般形式一般形式包含三個地址：兩個操作數(shù)，一個結(jié)果包含三個地址：兩個操作數(shù)，一個結(jié)果x := y op z一系列的上述形式一系列的上述形式x, y, z是名字、常數(shù)和編譯器產(chǎn)生的臨時變量是名字、常數(shù)和編譯器產(chǎn)生的臨時變量op是算符，定點、浮點、邏輯，只能有一個是算符，定點、浮點、邏輯，只能有一個：x + y * z翻譯成

12、翻譯成t1 := y * zt2 := x + t1三、三、三地址代碼三地址代碼TJNU-COCIE-WJW172022-5-11.一般形式（續(xù)）一般形式（續(xù)）三地址代碼是三地址代碼是AST或或DAG的線性化表示的線性化表示nDAG圖對應的三地址代碼可能比相應的圖對應的三地址代碼可能比相應的AST對應的三地址代碼要優(yōu)化，因為可以復用中對應的三地址代碼要優(yōu)化，因為可以復用中間結(jié)果間結(jié)果TJNU-COCIE-WJW182022-5-1：相應于相應于a:=b * - c+b * -c的的AST和和DAG的三地址代碼的三地址代碼 t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t

13、3 t5 ： t2+t4 a ： t5 （a）對于）對于AST的代碼的代碼 t1：-c t2：b*t1 t5：t2+t2 a：= t5 （b）對于）對于DAG的代碼的代碼 TJNU-COCIE-WJW192022-5-12.三地址代碼的種類三地址代碼的種類(1)賦值語句：賦值語句：x := y op z，op是二元算術算符或邏輯算符是二元算術算符或邏輯算符(2)賦值語句：賦值語句：x := op z，op是一元算符，如：負號，邏輯非是一元算符，如：負號，邏輯非not等等(3)復寫語句：復寫語句：x := yTJNU-COCIE-WJW202022-5-12.三地址代碼的種類三地址代碼的種類(續(xù)

14、續(xù)1)(4)無條件轉(zhuǎn)移：無條件轉(zhuǎn)移：goto L，L是下一步要執(zhí)行的三地址語句的標號是下一步要執(zhí)行的三地址語句的標號(5)條件轉(zhuǎn)移語句：條件轉(zhuǎn)移語句：if x relop y goto L根據(jù)邏輯運算的結(jié)果決定是否執(zhí)行轉(zhuǎn)移根據(jù)邏輯運算的結(jié)果決定是否執(zhí)行轉(zhuǎn)移if a goto La為真跳到為真跳到L執(zhí)行，否則執(zhí)行執(zhí)行，否則執(zhí)行if后邊的語句后邊的語句TJNU-COCIE-WJW212022-5-12.三地址代碼的種類三地址代碼的種類(續(xù)續(xù)2)(6)過程調(diào)用語句：過程調(diào)用語句：param x和和call p, nn表示實參個數(shù)表示實參個數(shù)：call p(x1 , x2 , , xn )，表示成三地

15、址語句：，表示成三地址語句：param x1param x2 param xncall p , n過程返回：過程返回：return yy表示返回值表示返回值TJNU-COCIE-WJW222022-5-12.三地址代碼的種類三地址代碼的種類(續(xù)續(xù)3)(7)數(shù)組引用賦值數(shù)組引用賦值x := y i x i := y(8)地址和指針的使用地址和指針的使用x := &yx := *y*x := yTJNU-COCIE-WJW232022-5-13.對賦值語句產(chǎn)生對賦值語句產(chǎn)生三地址代碼的屬性文法三地址代碼的屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則Sid:=ES.code:=E.codegen(i

16、d.place:=E.place)EE1+E2E.place:=newtemp; E.code:=E1.codeE2.codegen(E.place:=E1.place +E2.place)EE1*E2E.place:=newtemp; E.code:=E1.codeE2.codegen(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;E.code:=E1.codegen(E.place:=uminusE1.place)E(E1)E.place:=E1.place; E.code:=E1.codeEidE.place:=id.place; E.c

17、ode:=TJNU-COCIE-WJW242022-5-1其中：其中：(1)E.place表示存放表示存放E值的名字。值的名字。 (2)E.code表示對表示對E求值的三地址語句序列。求值的三地址語句序列。 (3)newtemp是個函數(shù)，對它的調(diào)用將產(chǎn)生一個新的是個函數(shù)，對它的調(diào)用將產(chǎn)生一個新的臨時變量臨時變量： 三地址語句序列是語法樹的線性表示，用臨時變?nèi)刂氛Z句序列是語法樹的線性表示，用臨時變量代替語法樹中的結(jié)點量代替語法樹中的結(jié)點實際實現(xiàn)中，三地址語句序列往往是被存放到一實際實現(xiàn)中，三地址語句序列往往是被存放到一個輸出文件中，而不是將三地址語句序列置入個輸出文件中，而不是將三地址語句序列

18、置入code屬屬性之中性之中TJNU-COCIE-WJW252022-5-14. 三地址代碼的具體實現(xiàn)三地址代碼的具體實現(xiàn)三地址代碼是一種抽象形式，其具體實現(xiàn)可用結(jié)構(gòu)三地址代碼是一種抽象形式，其具體實現(xiàn)可用結(jié)構(gòu)體來表示，有以下幾種表示方法：體來表示，有以下幾種表示方法： 四元式四元式 ：op, arg1, arg2, result三元式三元式 ：op, arg1, arg2 間接三元式：間接碼表間接三元式：間接碼表+三元式表三元式表TJNU-COCIE-WJW262022-5-1(1)四元式四元式op, arg1, arg2, resultnop：算符的內(nèi)部編碼：算符的內(nèi)部編碼narg1和和a

19、rg2分別表示兩個操作數(shù)分別表示兩個操作數(shù)nresult表示計算結(jié)果表示計算結(jié)果narg1、arg2和和result的內(nèi)容通常是符號表條目指針的內(nèi)容通常是符號表條目指針：n一元運算不需要使用一元運算不需要使用arg2的域的域nparam不使用不使用arg2和和result域域n條件和無條件轉(zhuǎn)移把目標語句的標號放在條件和無條件轉(zhuǎn)移把目標語句的標號放在result中中TJNU-COCIE-WJW272022-5-1：語句：語句a:=b*-c+b*-c 的的四元式表示四元式表示arg1arg2resultop(0)uminusct1(1)*bt1t2(2)uminusct3(3)*bt3t4(4)+

20、t2t4t5(5)Assignt5aTJNU-COCIE-WJW282022-5-1(2)三元式三元式op, arg1, arg2避免四元式引入臨時變量，可以用三地址語句的避免四元式引入臨時變量，可以用三地址語句的序號表示臨時變量序號表示臨時變量有有3個域的記錄結(jié)構(gòu)個域的記錄結(jié)構(gòu)nop：算符的內(nèi)部編碼：算符的內(nèi)部編碼narg1和和arg2分別表示操作數(shù)分別表示操作數(shù)n語句的結(jié)果通過語句的序號引用語句的結(jié)果通過語句的序號引用narg1、arg2的內(nèi)容通常是符號表條目指針或的內(nèi)容通常是符號表條目指針或三地址語句的序號三地址語句的序號(對于臨時變量對于臨時變量)TJNU-COCIE-WJW29202

21、2-5-1arg1arg2op：語句語句a:=b*-c+b*-c 的的三元式表示三元式表示(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+ (1) (3)(5)Assigna(4)TJNU-COCIE-WJW302022-5-1：有些三地址語句要多個三元式表示有些三地址語句要多個三元式表示： xi := y op arg1 arg2(0) = x i (1) := (0) yy := xi op arg1 arg2(0) = x i(1) := y (0)TJNU-COCIE-WJW312022-5-1(3)間接三元式間接三元式在三元式基礎上，增加一個間接碼表在

22、三元式基礎上，增加一個間接碼表.該表按運算的先后順序列出有關三元式在三元表該表按運算的先后順序列出有關三元式在三元表中的位置。中的位置。TJNU-COCIE-WJW322022-5-1arg1arg2op間接代碼間接代碼：X:=(A+B)*C; Y:=D(A+B) 的間接的間接三元式表示三元式表示(1)+ A B(2)* (1) C(3)assign X (2)(4) D (1)(5)assign Y (4)(1)(2)(3)(1)(4)(5)TJNU-COCIE-WJW332022-5-1總結(jié)：總結(jié)：3種三地址代碼的表示形式的比較種三地址代碼的表示形式的比較式子之間的聯(lián)系式子之間的聯(lián)系所占空

23、間所占空間優(yōu)化優(yōu)化四元式四元式 臨時變量臨時變量較大較大易于調(diào)整次序，便易于調(diào)整次序，便于優(yōu)化的實施于優(yōu)化的實施三元式三元式 三元式的序號三元式的序號較小較小不易于調(diào)整次序，不易于調(diào)整次序，牽一發(fā)而動全身牽一發(fā)而動全身間接間接三元式三元式三元式的序號三元式的序號間接碼表間接碼表和四元式類似，和四元式類似，但如果臨時值但如果臨時值引用不止一次，引用不止一次，間接三元式的間接三元式的空間要節(jié)省一空間要節(jié)省一些些通過重排間接代碼通過重排間接代碼來實現(xiàn)來實現(xiàn)TJNU-COCIE-WJW342022-5-17.2 說明語句說明語句n說明語句的翻譯說明語句的翻譯：當翻譯一個過程或分程序的一系列說明語句時，

24、當翻譯一個過程或分程序的一系列說明語句時，便可為該過程的中的每個局部名字便可為該過程的中的每個局部名字(局部變量局部變量)分分配存儲空間，并在符號表中建立相應的表項，填配存儲空間，并在符號表中建立相應的表項，填寫該名字的有關信息，如：類型、在存儲器中的寫該名字的有關信息，如：類型、在存儲器中的相對地址等相對地址等n相對地址相對地址：相對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基相對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移值。址的一個偏移值。TJNU-COCIE-WJW352022-5-1nC，Java，Pascal和和Fortran這些語言的語法允許這些語言的語法允許一個過程中的所有聲明

25、集中在一起處理，把它們安一個過程中的所有聲明集中在一起處理，把它們安排在一個數(shù)據(jù)區(qū)中排在一個數(shù)據(jù)區(qū)中n在這種情況下，我們可用全局變量，例如在這種情況下，我們可用全局變量，例如offset，來記住下一個可用的相對地址。來記住下一個可用的相對地址。一、一、過程中的說明語句過程中的說明語句 TJNU-COCIE-WJW362022-5-1n聲明語句的翻譯模式聲明語句的翻譯模式計算名字的類型和相對地址計算名字的類型和相對地址P offset := 0 DDD ; DDid : T enter( , T.type , offset ); offset := offset + T.widt

26、h Tinteger T.type := integer; T.width := 4 Treal T.type := real; T.width := 8 Tarray num of T1 T.type := array( num.val , T1.type ); T.width := num.val * T1.width TT1 T.type := pointer( T1.type ); T.width := 4 TJNU-COCIE-WJW372022-5-1綜合屬性綜合屬性type和和width表示非終結(jié)符的類型和寬度表示非終結(jié)符的類型和寬度初始化的工作由第一個產(chǎn)生式完成初始化的工作由第

27、一個產(chǎn)生式完成P offset := 0 D改寫上述產(chǎn)生式，使得所有動作出現(xiàn)在產(chǎn)生式的改寫上述產(chǎn)生式，使得所有動作出現(xiàn)在產(chǎn)生式的右部的末端右部的末端P M DM offset := 0 TJNU-COCIE-WJW382022-5-11 .問題的提出問題的提出n 一般的語言中，標識符的作用在程序正文中有一一般的語言中，標識符的作用在程序正文中有一個確定的范圍。因此，同一個標識符在不同的程序個確定的范圍。因此，同一個標識符在不同的程序正文中可能標識不同的對象，具有不同的性質(zhì)，要正文中可能標識不同的對象，具有不同的性質(zhì)，要求分配不同的存儲空間。求分配不同的存儲空間。n于是提出下面的問題：于是提出下

28、面的問題：如何組織符號表，使得同一個標識符在不同的作用如何組織符號表，使得同一個標識符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。域中得到正確的引用而不產(chǎn)生混亂。n編譯程序分析說明語句時建立符號表，編譯執(zhí)行編譯程序分析說明語句時建立符號表，編譯執(zhí)行語句時查找符號表。語句時查找符號表。Lookup(id)返回正返回正確的確的 id.entry。二、二、作用域信息的保存作用域信息的保存TJNU-COCIE-WJW392022-5-12.嵌套過程的聲明嵌套過程的聲明當遇到一個嵌入的過程說明時，應當暫停包圍當遇到一個嵌入的過程說明時，應當暫停包圍此過程的外圍過程說明語句處理，而轉(zhuǎn)去處理此過程的外圍過程

29、說明語句處理，而轉(zhuǎn)去處理嵌套過程，等被嵌套過程處理完后再繼續(xù)。嵌套過程，等被嵌套過程處理完后再繼續(xù)。 可以采用以下的產(chǎn)生式描述嵌套過程可以采用以下的產(chǎn)生式描述嵌套過程P DD D ; D | id : T | proc id ; D1 ; STJNU-COCIE-WJW402022-5-12.嵌套過程的聲明（續(xù)）嵌套過程的聲明（續(xù)）符號表的處理符號表的處理n為每個過程建立一個獨立的符號表，可用鏈表實現(xiàn)為每個過程建立一個獨立的符號表，可用鏈表實現(xiàn)n當遇到過程說明當遇到過程說明D proc id ; D1 ; S時，就創(chuàng)建一時，就創(chuàng)建一張新符號表，把張新符號表，把D1中的所有說明的局部名字都填入中

30、的所有說明的局部名字都填入該符號表該符號表n新表有一個指向其最近外圍過程的符號表的指針新表有一個指向其最近外圍過程的符號表的指針nid表示的過程名作為其外圍過程的一個局部名字。表示的過程名作為其外圍過程的一個局部名字。TJNU-COCIE-WJW412022-5-1program sort(input, output) var a: array0.10 of integer;x:integer;procedure readarray;var i:integer;begin a end readarrayprocedure exchange(i, j:integer);beginx:=ai;ai

31、:=aj;aj:=xend exchange;procedure quicksort(m,n:integer);var k,v: integer;function partition(y,z:integer):integer;var i,j: integer;begin avexchange(i, j); end partition ;beginend quicksort ;beginend sort .TJNU-COCIE-WJW422022-5-1：P176TJNU-COCIE-WJW432022-5-13.嵌套過程的翻譯模式嵌套過程的翻譯模式(1)定義一些操作定義一些操作mktable(

32、previous)n建立新的符號表，并返回新符號表的指針。參建立新的符號表，并返回新符號表的指針。參數(shù)數(shù)previous指向直接外圍過程的符號表。指向直接外圍過程的符號表。previous放在新建符號表的表頭。放在新建符號表的表頭。enter(table, name, type, offset)n在在table指向的符號表中為變量名指向的符號表中為變量名name建立新建立新項，項，enter把類型把類型type和相對地址和相對地址offset置于該置于該項的域中。項的域中。TJNU-COCIE-WJW442022-5-13.嵌套過程的翻譯模式嵌套過程的翻譯模式(1)定義一些操作定義一些操作(續(xù)

33、續(xù))addwidth(table, width)n把符號表把符號表table所有名字占用的總寬度記錄在該所有名字占用的總寬度記錄在該符號表的表頭。符號表的表頭。enterproc(table, name, newtable)n在在table指向的符號表中為過程名指向的符號表中為過程名name建立新建立新項。參數(shù)項。參數(shù)newtable指向過程指向過程name的符號表。的符號表。 TJNU-COCIE-WJW452022-5-1(2)定義兩個棧定義兩個棧tblptr棧：棧：用于保存各過程的符號表指針用于保存各過程的符號表指針棧頂?shù)闹羔樦赶虍斶^程的前符號表棧頂?shù)闹羔樦赶虍斶^程的前符號表offset

34、棧：棧：用于存放各嵌套過程的當前相對地址用于存放各嵌套過程的當前相對地址棧頂元素為當前被處理過程的下一個局部名字的棧頂元素為當前被處理過程的下一個局部名字的相對地址相對地址相應操作有：相應操作有：push(棧名棧名)：壓棧：壓棧pop(值，棧名值，棧名)：出棧：出棧top(棧名棧名)：返回棧頂：返回棧頂TJNU-COCIE-WJW462022-5-1P M D addwidth( top( tblptr ) , top( offset ) ); pop( tblptr ); pop( offset ) M t := mktable( nil ); push( t , tblprt ); pus

35、h( 0 , offset ) DD1 ; D2Dproc id ; N D1 ; S t := top( tblptr ); addwidth( t , top( offset ) ); pop( tblptr ); pop( offset ); enterproc( top( tblptr ), , t ) Did : T enter( top(tblptr), , T.type ,top( offset ) ); top( offset ) := top( offset ) + T.width N t := mktable( top( tblptr ) );

36、 push( t , tblprt ); push( 0 , offset ) TJNU-COCIE-WJW472022-5-1n非終結(jié)符非終結(jié)符M的語義動作最先完成的語義動作最先完成建立最外層作用域的符號表建立最外層作用域的符號表用最外層符號表初始棧用最外層符號表初始棧tblptr用用0初始化初始化offset棧棧n非終結(jié)符非終結(jié)符N的語義動作的語義動作建立一個新的作用域的符號表建立一個新的作用域的符號表在符號表棧中壓入新的符號表指針在符號表棧中壓入新的符號表指針用用0作為作為offset棧頂棧頂TJNU-COCIE-WJW482022-5-1n變量聲明變量聲明id : T不改變符號表棧不改

37、變符號表棧建立新的符號條目建立新的符號條目累加符號的寬度累加符號的寬度n過程的聲明處理結(jié)束時過程的聲明處理結(jié)束時addwidth記錄該符號表的所有名字的寬度記錄該符號表的所有名字的寬度更改符號表棧和更改符號表棧和offset棧棧過程名進入外圍符號表過程名進入外圍符號表TJNU-COCIE-WJW492022-5-14.記錄聲明的產(chǎn)生式記錄聲明的產(chǎn)生式T record D end為記錄的域名建立符號表為記錄的域名建立符號表T record L D end T.type := record( top ( tblptr ) ); T.width := top( offset ); pop( tblp

38、tr ); pop( offset ) L t := mktable( nil ); push( t , tblprt ); push( 0 , offset ) 看見關鍵字看見關鍵字record后，標記非終結(jié)符后，標記非終結(jié)符L為域名建立一個新的符號表為域名建立一個新的符號表Did : T的語義動作將域名的語義動作將域名id的信息填入該紀錄的符號表中的信息填入該紀錄的符號表中紀錄的域分析完后，紀錄的域分析完后，offset棧頂保存紀錄中所有數(shù)據(jù)對象的總寬度棧頂保存紀錄中所有數(shù)據(jù)對象的總寬度end后的動作將總寬度作為綜合屬性后的動作將總寬度作為綜合屬性T.width返回。把構(gòu)造器返回。把構(gòu)造器

39、record作用于該記錄的符號表指針，得到作用于該記錄的符號表指針，得到T.type，用于恢復記錄中的域名，用于恢復記錄中的域名的名字、類型和寬度的名字、類型和寬度TJNU-COCIE-WJW502022-5-17.3賦值語句的翻譯賦值語句的翻譯一、簡單算術表達式及賦值語句一、簡單算術表達式及賦值語句1.符號表中的名字符號表中的名字三地址代碼中用標識符對應的符號表條目指針三地址代碼中用標識符對應的符號表條目指針表示表示id的名字本身的名字本身nlookup()檢查是否在符號表中存在相應該檢查是否在符號表中存在相應該名字的入口名字的入口如果找到，則返回該名字對應表項

40、的指針如果找到，則返回該名字對應表項的指針如果找不到，則返回如果找不到，則返回nil表示沒有找到表示沒有找到2.賦值語句的翻譯方案賦值語句的翻譯方案生成三地址代碼生成三地址代碼TJNU-COCIE-WJW512022-5-1Sid := E p := lookup( ); if p nil then emit( p := E.place) else error EE1 + E2 E.place := newtemp; emit( E.place := E1.place + E2.place ) EE1 * E2 E.place := newtemp; emit( E.place

41、 := E1.place * E2.place ) E -E1 E.place := newtemp; emit( E.place := uminus E1.place ) E ( E1 ) E.place := E1.place Eid p := lookup( ); if p nil then E.place := p else error 移進規(guī)約過程移進規(guī)約過程A:=B+(-C)AA:=A:=BA:=EA:=E+A:=E+(A:=E+(-A:=E+(-CA:=E+(-EA:=E+(ET1=uminus CA:=E+(E)A:=E+EA:=ET2=B+T1SA=T2TJN

42、U-COCIE-WJW522022-5-1二、二、數(shù)組元素的翻譯數(shù)組元素的翻譯數(shù)組元素的定址數(shù)組元素的定址：對于一個數(shù)組，確定某個元素相對于數(shù)：對于一個數(shù)組，確定某個元素相對于數(shù)組首地址的偏移組首地址的偏移假設數(shù)組存儲在連續(xù)的存儲塊中假設數(shù)組存儲在連續(xù)的存儲塊中假設每個數(shù)組元素的寬度為假設每個數(shù)組元素的寬度為w，數(shù)組的首地址為，數(shù)組的首地址為base1.一維數(shù)組元素的定址一維數(shù)組元素的定址：A i n假設數(shù)組下標的下界為假設數(shù)組下標的下界為low，此時：，此時：base=&Alow A i 的相對地址是：的相對地址是：base + ( i low ) * w優(yōu)化的計算方式：優(yōu)化的計算方

43、式：i * w + (base low * w)后一部分可以在處理數(shù)組的說明語句時就計算出后一部分可以在處理數(shù)組的說明語句時就計算出來，存到數(shù)組來，存到數(shù)組A對應的符號表項中去，然后在分對應的符號表項中去，然后在分析析A i 時只需計算出時只需計算出i*w的值的值TJNU-COCIE-WJW532022-5-1二維數(shù)組A2,3的存儲布局二維數(shù)組A2,3的存儲布局第一行第一行A1,1A1,1A1,2A1,2A1,3A1,3A2,1A2,1A2,2A2,2A2,3A2,3A1,1A1,1A2,1A2,1A1,2A1,2A2,2A2,2A1,3A1,3A2,3A2,3第二行第二行行為主，如C、Pas

44、cal行為主，如C、Pascal列為主，如Fortran列為主，如Fortran第一列第一列第二列第二列第三列第三列2.多維數(shù)組的定址多維數(shù)組的定址存儲方式有兩種：數(shù)組元組的定址計算方式是不一樣的存儲方式有兩種：數(shù)組元組的定址計算方式是不一樣的 l行為主（一行接一行的存放）行為主（一行接一行的存放）l列為主（一列接一列的存放）列為主（一列接一列的存放）TJNU-COCIE-WJW542022-5-1(1)行為主的二維數(shù)組行為主的二維數(shù)組n元素的定址公式元素的定址公式A i1，i2 的相對地址：的相對地址：base + ( ( i1 low1 ) * n2 + ( i2 low2 ) ) * w

45、Low1和和low2分別是兩維的下界分別是兩維的下界n2是數(shù)組第二維的維展，即是數(shù)組第二維的維展，即i2可取值的個數(shù)，如果可取值的個數(shù)，如果high2是是i2值的上界，且這一維的步長為值的上界，且這一維的步長為1，則，則n2=high2 - low2 +1n地址計算的優(yōu)化公式：地址計算的優(yōu)化公式： ( ( i1 * n2 ) + i2 ) * w + (base - ( ( low1 * n2 ) + low2 ) * w)(2)列為主的二維數(shù)組的元素定址列為主的二維數(shù)組的元素定址n類似于行為主的二維數(shù)組：類似于行為主的二維數(shù)組： base + ( ( i1 low1 ) + ( i2 low

46、2 ) * n1 ) * wTJNU-COCIE-WJW552022-5-1(3)多維數(shù)組的定址計算多維數(shù)組的定址計算n行為主的數(shù)組，最右邊的下標變化最快行為主的數(shù)組，最右邊的下標變化最快A i1，i2，ik 的相對地址：的相對地址：( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 ) * nk + lowk ) * w由于在大多數(shù)情況下數(shù)組各維的維展是一個固定值，由于在大多數(shù)情況下數(shù)組各維的維展是一個固定值，所以上述公式的第二行可以在編譯時刻計算，并存所以上述公

47、式的第二行可以在編譯時刻計算，并存放在符號表中放在符號表中A的條目中的條目中n列為主的數(shù)組，最左邊的下標變化最快，其地址計算列為主的數(shù)組，最左邊的下標變化最快，其地址計算公式可以參照上述公式公式可以參照上述公式TJNU-COCIE-WJW562022-5-13.數(shù)組引用的描述數(shù)組引用的描述(1) 產(chǎn)生式描述產(chǎn)生式描述L id Elist | idElist Elist , E | E其中，其中，Elist代表下標表達式的列表，表達式中間用代表下標表達式的列表，表達式中間用，號分隔。號分隔。改寫上述產(chǎn)生式，使數(shù)組名字改寫上述產(chǎn)生式，使數(shù)組名字id和最左下標表達式和最左下標表達式E相相聯(lián)系：聯(lián)系：

48、L Elist | idElist Elist , E | id En目的是在對目的是在對Elist進行翻譯時，隨時知道符號表中數(shù)進行翻譯時，隨時知道符號表中數(shù)組組id的全部信息。的全部信息。n為為Elist配備一個綜合屬性配備一個綜合屬性array，用它來傳遞符號表，用它來傳遞符號表中數(shù)組中數(shù)組id項的指針。項的指針。TJNU-COCIE-WJW572022-5-1(2)幾個定義幾個定義：屬性屬性Elist.ndim表示表示Elist中的下標表達式的個數(shù)中的下標表達式的個數(shù)函數(shù)函數(shù)Limit( array， j )返回數(shù)組返回數(shù)組(array指向的符號表項所記指向的符號表項所記錄的數(shù)組錄的數(shù)

49、組)第第j維的元素個數(shù)維的元素個數(shù)(維展維展)函數(shù)函數(shù)Invariant( array )取得數(shù)組的地址計算的不變部分，取得數(shù)組的地址計算的不變部分，即地址計算公式第二行中除即地址計算公式第二行中除base外的其它部分的值外的其它部分的值( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 ) * nk + lowk ) * w屬性屬性Elist.place存儲臨時變量在符號表中的表項地址存儲臨時變量在符號表中的表項地址(3)采用遞推計算方法實現(xiàn)采用遞推計算方法實現(xiàn)E

50、list的計算的計算(上式中的第一項上式中的第一項)：e1 = i1em = em-1 * nm + im當當m=k時，時， ek = ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )TJNU-COCIE-WJW582022-5-14.數(shù)組定址的翻譯模式數(shù)組定址的翻譯模式(1)在賦值語句中引用數(shù)組的文法在賦值語句中引用數(shù)組的文法(1) S L := E(2) E E + E(3) E ( E )(4) E L(5) L Elist (6) L id(7) Elist Elist , E(8) Elist id ETJNU-COCIE-WJW59202

51、2-5-1(2)各個產(chǎn)生式的三地址代碼生成各個產(chǎn)生式的三地址代碼生成(1) S L := E if L.offset = null then /* L是簡單名字是簡單名字*/ emit( L.place := E.place ); else emit( L.place L.offset :=E.place ) 如果如果L是簡單名字，產(chǎn)生正常的賦值；否則產(chǎn)生對由是簡單名字，產(chǎn)生正常的賦值；否則產(chǎn)生對由L的兩的兩個屬性確定的存儲單元的索引賦值。個屬性確定的存儲單元的索引賦值。(2) EE1 +E2 E.place := newtemp; emit( E.place := E1.place + E2

52、.place) (3) E ( E ) E.place := E1.place TJNU-COCIE-WJW602022-5-1(4) E L if L.offset = null then/* L是簡單名字是簡單名字*/ E.place := L.place; else begin E.place := newtemp; emit( E.place := L.place L.offset ) end 如果如果E產(chǎn)生數(shù)組元素產(chǎn)生數(shù)組元素L，則需要，則需要L的右值，可用索引得到存儲的右值，可用索引得到存儲單元單元L.place L.offset的內(nèi)容的內(nèi)容TJNU-COCIE-WJW612022

53、-5-1(5) L Elist L.place := newtemp; emit( L.place := Elist.array - invariant(Elist.array); L.offset := newtemp; emit( L.offset := w * Elist.place ) (6) L id L.place := id.place; L.offset := null ( ( ( (i1 n2 + i2 ) n3 + i3 ) ) nk + ik) w+ base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w L.plac

54、e和和L.offset都是新的臨時變量，都是新的臨時變量，L.place對應第二項；對應第二項；L.offset保存保存w乘以乘以Elist.place的值，對應第一項的值，對應第一項 TJNU-COCIE-WJW622022-5-1(7) Elist Elist1 , E t := newtemp; m := Elist1.ndim + 1; emit( t := Elist1.place * limit( Elist1.array , m ); emit( t := t + E.place); Elist.array := Elist1.array; Elist.place := t; E

55、list.ndim := m 當看見下一個下標表達式時，使用遞推公式當看見下一個下標表達式時，使用遞推公式e1 = i1em = em-1 * nm + imElist1.place對應對應em-1 ，Elist.place對應對應em如果如果Elist1有有m 1個成分。那么產(chǎn)生式左邊的個成分。那么產(chǎn)生式左邊的Elist有有m個成分個成分TJNU-COCIE-WJW632022-5-1(8) Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place E.place保存表達式保存表達式E的值的值也是遞

56、推公式也是遞推公式e1 = i1em = em-1 * nm + imm = 1時的值時的值TJNU-COCIE-WJW642022-5-1：A是是10*20的數(shù)組，即的數(shù)組，即n1=10，n2=20，取，取w=4，假設數(shù)組的第一個元素是假設數(shù)組的第一個元素是A 1 , 1 求賦值語句求賦值語句x:=Ay , z的三地址代碼。的三地址代碼。(其中每個變量，用它們的名字來代替其中每個變量，用它們的名字來代替id.place)解：不變量：解：不變量：Base - ( ( low1 * n2 ) + low2 ) * w = A - ( 1 * 20 + 1 ) * 4 =A - 84可變量：可變量

57、：( i1 * n2 + i2 ) * w = (y * 20 + z ) * 4t1 := y * 20t1 := t1 + z Elist Elist1 , E t2 := A 84t3 := 4 * t1 L Elist t4 := t2 t3 E Lx := t4 S L := ETJNU-COCIE-WJW652022-5-1S S: := =L L. .p pl la ac ce e = = x xL L. .o of ff fs se et t = = n nu ul ll lE E. .p pl la ac ce e = = t t 4 4L L. .p pl la ac ce

58、 e = = t t 2 2L L. .o of ff fs se et t = = t t 3 3E El li is st t. .p pl la ac ce e = = t t 1 1E El li is st t. .n nd di im m = = 2 2E El li is st t. .a ar rr ra ay y = = A A E El li is st t. .p pl la ac ce e = = y yE El li is st t. .n nd di im m = = 1 1E El li is st t. .a ar rr ra ay y = = A A, ,E

59、E. .p pl la ac ce e = = z zL L. .p pl la ac ce e = = z zL L. .o of ff fs se et t = = n nu ul ll lz zE E. .p pl la ac ce e = = y yL L. .p pl la ac ce e = = y yL L. .o of ff fs se et t = = n nu ul ll ly y A ATJNU-COCIE-WJW662022-5-17.4布爾表達式的翻譯布爾表達式的翻譯一、一、概述概述1.布爾表達式的作用布爾表達式的作用計算邏輯值計算邏輯值在改變控制流的語句中作為條件表

60、達式在改變控制流的語句中作為條件表達式n條件語句：條件語句：if then或或if then elsen循環(huán)：循環(huán)：while do，for等等2.布爾表達式的文法布爾表達式的文法E E or E | E and E | not E | ( E ) | id relop id | true | false用用relop.op屬性確定屬性確定relop是是,=,=,!=中的哪個中的哪個算符的結(jié)合性和優(yōu)先性算符的結(jié)合性和優(yōu)先性nor和和and都是左結(jié)合的都是左結(jié)合的nor的優(yōu)先級最低，其次是的優(yōu)先級最低，其次是and，not的優(yōu)先級最高的優(yōu)先級最高TJNU-COCIE-WJW672022-5-13. 表示布爾表達