編譯原理-第七章

1、編譯原理編譯原理第七章第七章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生王金偉計(jì)算機(jī)與信息工程學(xué)院天津師范大學(xué)TJNU-COCIE-WJW22021-12-22第七章第七章 語(yǔ)義分析和中間代碼產(chǎn)生語(yǔ)義分析和中間代碼產(chǎn)生l在詞法分析和語(yǔ)法分析之后的階段就是語(yǔ)義分析在詞法分析和語(yǔ)法分析之后的階段就是語(yǔ)義分析和中間代碼生成和中間代碼生成l本章把第六章介紹的有關(guān)語(yǔ)法制導(dǎo)翻譯的相關(guān)方本章把第六章介紹的有關(guān)語(yǔ)法制導(dǎo)翻譯的相關(guān)方法和技術(shù)用在中間代碼生成和語(yǔ)義分析上法和技術(shù)用在中間代碼生成和語(yǔ)義分析上l主要工作主要工作l靜態(tài)語(yǔ)義檢查靜態(tài)語(yǔ)義檢查l翻譯翻譯TJNU-COCIE-WJW32021-12-22l靜

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

3、樣的語(yǔ)句應(yīng)該報(bào)錯(cuò)。在包括它的這樣的語(yǔ)句應(yīng)該報(bào)錯(cuò)。TJNU-COCIE-WJW42021-12-22l靜態(tài)語(yǔ)義檢查靜態(tài)語(yǔ)義檢查l一致性檢查一致性檢查: :很多場(chǎng)合要求對(duì)象只能被定義一次很多場(chǎng)合要求對(duì)象只能被定義一次，PascalPascal語(yǔ)言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序語(yǔ)言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序中只能被說(shuō)明一次，同一中只能被說(shuō)明一次，同一casecase語(yǔ)句的標(biāo)號(hào)不能相語(yǔ)句的標(biāo)號(hào)不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。l相關(guān)名字檢查相關(guān)名字檢查: :有時(shí)，同一名字必須出現(xiàn)兩次或有時(shí)，同一名字必須出現(xiàn)兩次或多次。多次。，AdaAda語(yǔ)言程序中，循環(huán)或程序塊

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

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

6、E-WJW72021-12-227.1中間語(yǔ)言中間語(yǔ)言n中間語(yǔ)言中間語(yǔ)言 源程序的中間表示方法源程序的中間表示方法n中間語(yǔ)言的形式中間語(yǔ)言的形式后綴式后綴式圖表示法圖表示法 三地址代碼三地址代碼TJNU-COCIE-WJW82021-12-22把運(yùn)算量把運(yùn)算量( (操作數(shù)操作數(shù)) )寫在前面，把算符寫在后面。寫在前面，把算符寫在后面。：原式原式后綴式后綴式a+ba+b，abab+ +a a* *b b，abab* *一、一、后綴式后綴式TJNU-COCIE-WJW92021-12-221.表達(dá)式表達(dá)式E的后綴表示遞歸定義的后綴表示遞歸定義n如果如果E是變量和常數(shù)，則是變量和常數(shù)，則E的后綴表示

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

8、021-12-22：賦值語(yǔ)句：賦值語(yǔ)句 a := b *（- c）+ b *（ - 34）的后綴式的后綴式：a b c-*b 34-*+ :=TJNU-COCIE-WJW112021-12-221.1.特點(diǎn)和形式特點(diǎn)和形式描述了源程序的自然層次結(jié)構(gòu)描述了源程序的自然層次結(jié)構(gòu)n語(yǔ)法樹語(yǔ)法樹(抽象語(yǔ)法樹抽象語(yǔ)法樹)n有向無(wú)環(huán)圖有向無(wú)環(huán)圖(DAG)二、二、圖表示法圖表示法TJNU-COCIE-WJW122021-12-22：a := b * - c + b * - c后綴式是抽象語(yǔ)法樹的線性表示后綴式是抽象語(yǔ)法樹的線性表示后根序遍歷后根序遍歷 a b c uminus * b c uminus *

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

10、1.nptr, 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-WJW152021-12-22：賦值語(yǔ)句：賦值語(yǔ)句：a:=b*-c+b*-c 抽象語(yǔ)法樹的表示方法抽象語(yǔ)法樹的表示方法后綴式：后綴式：a b c uminus * b c uminus * + assignassign + * uminus id

11、a id c 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-WJW162021-12-221.一般形式一般形式包含三個(gè)地址：兩個(gè)操作數(shù)，一個(gè)結(jié)果包含三個(gè)地址：兩個(gè)操作數(shù)，一個(gè)結(jié)果x := y op z一系列的上述形式一系列的上述形式x, y, z是名字、常數(shù)和編譯器產(chǎn)生的臨時(shí)變量是名字、常數(shù)和編譯器產(chǎn)生的臨時(shí)變量op是算符，定點(diǎn)、浮點(diǎn)、邏輯，只能有一個(gè)是算符，定點(diǎn)、浮點(diǎn)、邏輯，只能有一個(gè)：x +

12、y * z翻譯成翻譯成t1 := y * zt2 := x + t1三、三、三地址代碼三地址代碼TJNU-COCIE-WJW172021-12-221.一般形式（續(xù)）一般形式（續(xù)）三地址代碼是三地址代碼是AST或或DAG的線性化表示的線性化表示nDAG圖對(duì)應(yīng)的三地址代碼可能比相應(yīng)的圖對(duì)應(yīng)的三地址代碼可能比相應(yīng)的AST對(duì)應(yīng)的三地址代碼要優(yōu)化，因?yàn)榭梢詮?fù)用中對(duì)應(yīng)的三地址代碼要優(yōu)化，因?yàn)榭梢詮?fù)用中間結(jié)果間結(jié)果TJNU-COCIE-WJW182021-12-22：相應(yīng)于相應(yīng)于a:=b * - c+b * -c的的AST和和DAG的三地址代碼的三地址代碼 t1 ： -c t2 ： b* t1 t3 ：

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

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

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

16、:=ES.code:=E.codegen(id.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.codeEid

17、E.place:=id.place; E.code:=TJNU-COCIE-WJW242021-12-22其中：其中：(1)E.place表示存放表示存放E值的名字。值的名字。 (2)E.code表示對(duì)表示對(duì)E求值的三地址語(yǔ)句序列。求值的三地址語(yǔ)句序列。 (3)newtemp是個(gè)函數(shù)，對(duì)它的調(diào)用將產(chǎn)生一個(gè)新的是個(gè)函數(shù)，對(duì)它的調(diào)用將產(chǎn)生一個(gè)新的臨時(shí)變量臨時(shí)變量： 三地址語(yǔ)句序列是語(yǔ)法樹的線性表示，用三地址語(yǔ)句序列是語(yǔ)法樹的線性表示，用臨時(shí)變臨時(shí)變量代替量代替語(yǔ)法樹中的結(jié)點(diǎn)語(yǔ)法樹中的結(jié)點(diǎn)實(shí)際實(shí)現(xiàn)中，三地址語(yǔ)句序列往往是被存放到一實(shí)際實(shí)現(xiàn)中，三地址語(yǔ)句序列往往是被存放到一個(gè)輸出文件中，而不是將三地址

18、語(yǔ)句序列置入個(gè)輸出文件中，而不是將三地址語(yǔ)句序列置入code屬屬性之中性之中TJNU-COCIE-WJW252021-12-224. 三地址代碼的具體實(shí)現(xiàn)三地址代碼的具體實(shí)現(xiàn)三地址代碼是一種抽象形式，其具體實(shí)現(xiàn)可用結(jié)構(gòu)三地址代碼是一種抽象形式，其具體實(shí)現(xiàn)可用結(jié)構(gòu)體來(lái)表示，有以下幾種表示方法：體來(lái)表示，有以下幾種表示方法： 四元式四元式 ：op, arg1, arg2, result三元式三元式 ：op, arg1, arg2 間接三元式：間接碼表間接三元式：間接碼表+三元式表三元式表TJNU-COCIE-WJW262021-12-22(1)四元式四元式op, arg1, arg2, resul

19、tnop：算符的內(nèi)部編碼：算符的內(nèi)部編碼narg1和和arg2分別表示兩個(gè)操作數(shù)分別表示兩個(gè)操作數(shù)nresult表示計(jì)算結(jié)果表示計(jì)算結(jié)果narg1、arg2和和result的內(nèi)容通常是符號(hào)表?xiàng)l目指針的內(nèi)容通常是符號(hào)表?xiàng)l目指針：n一元運(yùn)算不需要使用一元運(yùn)算不需要使用arg2的域的域nparam不使用不使用arg2和和result域域n條件和無(wú)條件轉(zhuǎn)移把目標(biāo)語(yǔ)句的標(biāo)號(hào)放在條件和無(wú)條件轉(zhuǎn)移把目標(biāo)語(yǔ)句的標(biāo)號(hào)放在result中中TJNU-COCIE-WJW272021-12-22：語(yǔ)句：語(yǔ)句a:=b*-c+b*-c 的的四元式表示四元式表示arg1arg2resultop(0)uminusct1(1)*

20、bt1t2(2)uminusct3(3)*bt3t4(4)+t2t4t5(5)Assignt5aTJNU-COCIE-WJW282021-12-22(2)三元式三元式op, arg1, arg2避免四元式引入臨時(shí)變量，可以用三地址語(yǔ)句的避免四元式引入臨時(shí)變量，可以用三地址語(yǔ)句的序號(hào)表示臨時(shí)變量序號(hào)表示臨時(shí)變量有有3個(gè)域的記錄結(jié)構(gòu)個(gè)域的記錄結(jié)構(gòu)nop：算符的內(nèi)部編碼：算符的內(nèi)部編碼narg1和和arg2分別表示操作數(shù)分別表示操作數(shù)n語(yǔ)句的結(jié)果通過(guò)語(yǔ)句的序號(hào)引用語(yǔ)句的結(jié)果通過(guò)語(yǔ)句的序號(hào)引用narg1、arg2的內(nèi)容通常是符號(hào)表?xiàng)l目指針或的內(nèi)容通常是符號(hào)表?xiàng)l目指針或三地址語(yǔ)句的序號(hào)三地址語(yǔ)句的序號(hào)(

21、對(duì)于臨時(shí)變量對(duì)于臨時(shí)變量)TJNU-COCIE-WJW292021-12-22arg1arg2op：語(yǔ)句語(yǔ)句a:=b*-c+b*-c 的的三元式表示三元式表示(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+ (1) (3)(5)Assigna(4)TJNU-COCIE-WJW302021-12-22：有些三地址語(yǔ)句要多個(gè)三元式表示有些三地址語(yǔ)句要多個(gè)三元式表示： xi := y op arg1 arg2(0) = x i (1) := (0) yy := xi op arg1 arg2(0) = x i(1) := y (0)TJNU-COCIE-WJW3120

22、21-12-22(3)間接三元式間接三元式在三元式基礎(chǔ)上，增加一個(gè)間接碼表在三元式基礎(chǔ)上，增加一個(gè)間接碼表.該表按運(yùn)算的先后順序列出有關(guān)三元式在三元表該表按運(yùn)算的先后順序列出有關(guān)三元式在三元表中的位置。中的位置。TJNU-COCIE-WJW322021-12-22arg1arg2op間接代碼間接代碼：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-WJW332021-12-22總結(jié)：總結(jié)：3種三地

23、址代碼的表示形式的比較種三地址代碼的表示形式的比較式子之間的聯(lián)系式子之間的聯(lián)系所占空間所占空間優(yōu)化優(yōu)化四元式四元式 臨時(shí)變量臨時(shí)變量較大較大易于調(diào)整次序，便易于調(diào)整次序，便于優(yōu)化的實(shí)施于優(yōu)化的實(shí)施三元式三元式 三元式的序號(hào)三元式的序號(hào)較小較小不易于調(diào)整次序，不易于調(diào)整次序，牽一發(fā)而動(dòng)全身牽一發(fā)而動(dòng)全身間接間接三元式三元式三元式的序號(hào)三元式的序號(hào)間接碼表間接碼表和四元式類似，和四元式類似，但如果臨時(shí)值但如果臨時(shí)值引用不止一次，引用不止一次，間接三元式的間接三元式的空間要節(jié)省一空間要節(jié)省一些些通過(guò)重排間接代碼通過(guò)重排間接代碼來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn)TJNU-COCIE-WJW342021-12-227.2 說(shuō)

24、明語(yǔ)句說(shuō)明語(yǔ)句n說(shuō)明語(yǔ)句的翻譯說(shuō)明語(yǔ)句的翻譯：當(dāng)翻譯一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，當(dāng)翻譯一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，便可為該過(guò)程的中的每個(gè)局部名字便可為該過(guò)程的中的每個(gè)局部名字(局部變量局部變量)分分配存儲(chǔ)空間，并在符號(hào)表中建立相應(yīng)的表項(xiàng)，填配存儲(chǔ)空間，并在符號(hào)表中建立相應(yīng)的表項(xiàng)，填寫該名字的有關(guān)信息，如：類型、在存儲(chǔ)器中的寫該名字的有關(guān)信息，如：類型、在存儲(chǔ)器中的相對(duì)地址等相對(duì)地址等n相對(duì)地址相對(duì)地址：相對(duì)靜態(tài)數(shù)據(jù)區(qū)基址或活動(dòng)記錄中局部數(shù)據(jù)區(qū)基相對(duì)靜態(tài)數(shù)據(jù)區(qū)基址或活動(dòng)記錄中局部數(shù)據(jù)區(qū)基址的一個(gè)偏移值。址的一個(gè)偏移值。TJNU-COCIE-WJW352021-12-22nC，Ja

25、va，Pascal和和Fortran這些語(yǔ)言的語(yǔ)法允許這些語(yǔ)言的語(yǔ)法允許一個(gè)過(guò)程中的所有聲明集中在一起處理，把它們安一個(gè)過(guò)程中的所有聲明集中在一起處理，把它們安排在一個(gè)數(shù)據(jù)區(qū)中排在一個(gè)數(shù)據(jù)區(qū)中n在這種情況下，我們可用全局變量，例如在這種情況下，我們可用全局變量，例如offset，來(lái)記住下一個(gè)可用的相對(duì)地址。來(lái)記住下一個(gè)可用的相對(duì)地址。一、一、過(guò)程中的說(shuō)明語(yǔ)句過(guò)程中的說(shuō)明語(yǔ)句 TJNU-COCIE-WJW362021-12-22n聲明語(yǔ)句的翻譯模式聲明語(yǔ)句的翻譯模式計(jì)算名字的類型和相對(duì)地址計(jì)算名字的類型和相對(duì)地址P offset := 0 DDD ; DDid : T enter( id.nam

26、e , T.type , offset ); offset := offset + T.width 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-WJW372021-12-22綜合屬性綜合屬性type和和wi

27、dth表示非終結(jié)符的類型和寬度表示非終結(jié)符的類型和寬度初始化的工作由第一個(gè)產(chǎn)生式完成初始化的工作由第一個(gè)產(chǎn)生式完成P offset := 0 D改寫上述產(chǎn)生式，使得所有動(dòng)作出現(xiàn)在產(chǎn)生式的改寫上述產(chǎn)生式，使得所有動(dòng)作出現(xiàn)在產(chǎn)生式的右部的末端右部的末端P M DM offset := 0 TJNU-COCIE-WJW382021-12-221 .問(wèn)題的提出問(wèn)題的提出n 一般的語(yǔ)言中，標(biāo)識(shí)符的作用在程序正文中有一一般的語(yǔ)言中，標(biāo)識(shí)符的作用在程序正文中有一個(gè)確定的范圍。因此，同一個(gè)標(biāo)識(shí)符在不同的程序個(gè)確定的范圍。因此，同一個(gè)標(biāo)識(shí)符在不同的程序正文中可能標(biāo)識(shí)不同的對(duì)象，具有不同的性質(zhì)，要正文中可能標(biāo)識(shí)不

28、同的對(duì)象，具有不同的性質(zhì)，要求分配不同的存儲(chǔ)空間。求分配不同的存儲(chǔ)空間。n于是提出下面的問(wèn)題：于是提出下面的問(wèn)題：如何組織符號(hào)表，使得同一個(gè)標(biāo)識(shí)符在不同的作用如何組織符號(hào)表，使得同一個(gè)標(biāo)識(shí)符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。域中得到正確的引用而不產(chǎn)生混亂。n編譯程序分析說(shuō)明語(yǔ)句時(shí)建立符號(hào)表，編譯執(zhí)行編譯程序分析說(shuō)明語(yǔ)句時(shí)建立符號(hào)表，編譯執(zhí)行語(yǔ)句時(shí)查找符號(hào)表。語(yǔ)句時(shí)查找符號(hào)表。Lookup(id)返回正返回正確的確的 id.entry。二、二、作用域信息的保存作用域信息的保存TJNU-COCIE-WJW392021-12-222.嵌套過(guò)程的聲明嵌套過(guò)程的聲明當(dāng)遇到一個(gè)嵌入的過(guò)程說(shuō)明時(shí)，

29、應(yīng)當(dāng)暫停包圍當(dāng)遇到一個(gè)嵌入的過(guò)程說(shuō)明時(shí)，應(yīng)當(dāng)暫停包圍此過(guò)程的外圍過(guò)程說(shuō)明語(yǔ)句處理，而轉(zhuǎn)去處理此過(guò)程的外圍過(guò)程說(shuō)明語(yǔ)句處理，而轉(zhuǎn)去處理嵌套過(guò)程，嵌套過(guò)程，等被嵌套過(guò)程處理完后再繼續(xù)。等被嵌套過(guò)程處理完后再繼續(xù)。 可以采用以下的產(chǎn)生式描述嵌套過(guò)程可以采用以下的產(chǎn)生式描述嵌套過(guò)程P DD D ; D | id : T | proc id ; D1 ; STJNU-COCIE-WJW402021-12-222.嵌套過(guò)程的聲明（續(xù)）嵌套過(guò)程的聲明（續(xù)）符號(hào)表的處理符號(hào)表的處理n為每個(gè)過(guò)程建立一個(gè)獨(dú)立的符號(hào)表，可用鏈表實(shí)現(xiàn)為每個(gè)過(guò)程建立一個(gè)獨(dú)立的符號(hào)表，可用鏈表實(shí)現(xiàn)n當(dāng)遇到過(guò)程說(shuō)明當(dāng)遇到過(guò)程說(shuō)明D pro

30、c id ; D1 ; S時(shí)，就創(chuàng)建一時(shí)，就創(chuàng)建一張新符號(hào)表，把張新符號(hào)表，把D1中的所有說(shuō)明的局部名字都填入中的所有說(shuō)明的局部名字都填入該符號(hào)表該符號(hào)表n新表有一個(gè)指向其最近外圍過(guò)程的符號(hào)表的指針新表有一個(gè)指向其最近外圍過(guò)程的符號(hào)表的指針nid表示的過(guò)程名作為其外圍過(guò)程的一個(gè)局部名字。表示的過(guò)程名作為其外圍過(guò)程的一個(gè)局部名字。TJNU-COCIE-WJW412021-12-22program sort(input, output) var a: array0.10 of integer;x:integer;procedure readarray;var i:integer;begin a e

31、nd readarrayprocedure exchange(i, j:integer);beginx:=ai;ai:=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-WJW422021-12-22：P176TJNU-CO

32、CIE-WJW432021-12-223.嵌套過(guò)程的翻譯模式嵌套過(guò)程的翻譯模式(1)定義一些操作定義一些操作mktable(previous)n建立新的符號(hào)表，并返回新符號(hào)表的指針。參建立新的符號(hào)表，并返回新符號(hào)表的指針。參數(shù)數(shù)previous指向直接外圍過(guò)程的符號(hào)表。指向直接外圍過(guò)程的符號(hào)表。previous放在新建符號(hào)表的表頭。放在新建符號(hào)表的表頭。enter(table, name, type, offset)n在在table指向的符號(hào)表中為變量名指向的符號(hào)表中為變量名name建立新建立新項(xiàng)，項(xiàng)，enter把類型把類型type和相對(duì)地址和相對(duì)地址offset置于該置于該項(xiàng)的域中。項(xiàng)的域中

33、。TJNU-COCIE-WJW442021-12-223.嵌套過(guò)程的翻譯模式嵌套過(guò)程的翻譯模式(1)定義一些操作定義一些操作(續(xù)續(xù))addwidth(table, width)n把符號(hào)表把符號(hào)表table所有名字占用的總寬度記錄在該所有名字占用的總寬度記錄在該符號(hào)表的表頭。符號(hào)表的表頭。enterproc(table, name, newtable)n在在table指向的符號(hào)表中為過(guò)程名指向的符號(hào)表中為過(guò)程名name建立新建立新項(xiàng)。參數(shù)項(xiàng)。參數(shù)newtable指向過(guò)程指向過(guò)程name的符號(hào)表。的符號(hào)表。 TJNU-COCIE-WJW452021-12-22(2)定義兩個(gè)棧定義兩個(gè)棧tblptr

34、棧：棧：用于保存各過(guò)程的符號(hào)表指針用于保存各過(guò)程的符號(hào)表指針棧頂?shù)闹羔樦赶虍?dāng)過(guò)程的前符號(hào)表?xiàng)ｍ數(shù)闹羔樦赶虍?dāng)過(guò)程的前符號(hào)表offset棧：棧：用于存放各嵌套過(guò)程的當(dāng)前相對(duì)地址用于存放各嵌套過(guò)程的當(dāng)前相對(duì)地址棧頂元素為當(dāng)前被處理過(guò)程的下一個(gè)局部名字的棧頂元素為當(dāng)前被處理過(guò)程的下一個(gè)局部名字的相對(duì)地址相對(duì)地址相應(yīng)操作有：相應(yīng)操作有：push(棧名棧名)：壓棧：壓棧pop(值，棧名值，棧名)：出棧：出棧top(棧名棧名)：返回棧頂：返回棧頂TJNU-COCIE-WJW462021-12-22P M D addwidth( top( tblptr ) , top( offset ) ); pop( tb

35、lptr ); pop( offset ) M t := mktable( nil ); push( t , tblprt ); push( 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(

36、offset ) := top( offset ) + T.width N t := mktable( top( tblptr ) ); push( t , tblprt ); push( 0 , offset ) TJNU-COCIE-WJW472021-12-22n非終結(jié)符非終結(jié)符M的語(yǔ)義動(dòng)作最先完成的語(yǔ)義動(dòng)作最先完成建立最外層作用域的符號(hào)表建立最外層作用域的符號(hào)表用最外層符號(hào)表初始棧用最外層符號(hào)表初始棧tblptr用用0初始化初始化offset棧棧n非終結(jié)符非終結(jié)符N的語(yǔ)義動(dòng)作的語(yǔ)義動(dòng)作建立一個(gè)新的作用域的符號(hào)表建立一個(gè)新的作用域的符號(hào)表在符號(hào)表?xiàng)Ｖ袎喝胄碌姆?hào)表指針在符號(hào)表?xiàng)Ｖ袎喝胄碌?/p>

37、符號(hào)表指針用用0作為作為offset棧頂棧頂TJNU-COCIE-WJW482021-12-22n變量聲明變量聲明id : T不改變符號(hào)表?xiàng)２桓淖兎?hào)表?xiàng)＝⑿碌姆?hào)條目建立新的符號(hào)條目累加符號(hào)的寬度累加符號(hào)的寬度n過(guò)程的聲明處理結(jié)束時(shí)過(guò)程的聲明處理結(jié)束時(shí)addwidth記錄該符號(hào)表的所有名字的寬度記錄該符號(hào)表的所有名字的寬度更改符號(hào)表?xiàng)：透姆?hào)表?xiàng)：蚾ffset棧棧過(guò)程名進(jìn)入外圍符號(hào)表過(guò)程名進(jìn)入外圍符號(hào)表TJNU-COCIE-WJW492021-12-224.記錄聲明的產(chǎn)生式記錄聲明的產(chǎn)生式T record D end為記錄的域名建立符號(hào)表為記錄的域名建立符號(hào)表T record L D e

38、nd T.type := record( top ( tblptr ) ); T.width := top( offset ); pop( tblptr ); pop( offset ) L t := mktable( nil ); push( t , tblprt ); push( 0 , offset ) 看見關(guān)鍵字看見關(guān)鍵字record后，標(biāo)記非終結(jié)符后，標(biāo)記非終結(jié)符L為域名建立一個(gè)新的符號(hào)表為域名建立一個(gè)新的符號(hào)表Did : T的語(yǔ)義動(dòng)作將域名的語(yǔ)義動(dòng)作將域名id的信息填入該紀(jì)錄的符號(hào)表中的信息填入該紀(jì)錄的符號(hào)表中紀(jì)錄的域分析完后，紀(jì)錄的域分析完后，offset棧頂保存紀(jì)錄中所有數(shù)據(jù)對(duì)

39、象的總寬度棧頂保存紀(jì)錄中所有數(shù)據(jù)對(duì)象的總寬度end后的動(dòng)作將總寬度作為綜合屬性后的動(dòng)作將總寬度作為綜合屬性T.width返回。把構(gòu)造器返回。把構(gòu)造器record作用于該記錄的符號(hào)表指針，得到作用于該記錄的符號(hào)表指針，得到T.type，用于恢復(fù)記錄中的域名，用于恢復(fù)記錄中的域名的名字、類型和寬度的名字、類型和寬度TJNU-COCIE-WJW502021-12-227.3賦值語(yǔ)句的翻譯賦值語(yǔ)句的翻譯一、簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句一、簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句1.符號(hào)表中的名字符號(hào)表中的名字三地址代碼中用標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表?xiàng)l目指針三地址代碼中用標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表?xiàng)l目指針表示表示id的名字

40、本身的名字本身nlookup()檢查是否在符號(hào)表中存在相應(yīng)該檢查是否在符號(hào)表中存在相應(yīng)該名字的入口名字的入口如果找到，則返回該名字對(duì)應(yīng)表項(xiàng)的指針如果找到，則返回該名字對(duì)應(yīng)表項(xiàng)的指針如果找不到，則返回如果找不到，則返回nil表示沒(méi)有找到表示沒(méi)有找到2.賦值語(yǔ)句的翻譯方案賦值語(yǔ)句的翻譯方案生成三地址代碼生成三地址代碼TJNU-COCIE-WJW512021-12-22Sid := E p := lookup( ); if p nil then emit( p := E.place) else error EE1 + E2 E.place := newtemp; emi

41、t( E.place := E1.place + E2.place ) EE1 * E2 E.place := newtemp; emit( E.place := 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 移進(jìn)規(guī)約過(guò)程移進(jìn)規(guī)約過(guò)程A:=B+(-C)AA:=A:=BA:=EA:=E+A:

42、=E+(A:=E+(-A:=E+(-CA:=E+(-EA:=E+(ET1=uminus CA:=E+(E)A:=E+EA:=ET2=B+T1SA=T2TJNU-COCIE-WJW522021-12-22二、二、數(shù)組元素的翻譯數(shù)組元素的翻譯數(shù)組元素的定址數(shù)組元素的定址：對(duì)于一個(gè)數(shù)組，確定某個(gè)元素相對(duì)于數(shù)：對(duì)于一個(gè)數(shù)組，確定某個(gè)元素相對(duì)于數(shù)組首地址的偏移組首地址的偏移假設(shè)數(shù)組存儲(chǔ)在連續(xù)的存儲(chǔ)塊中假設(shè)數(shù)組存儲(chǔ)在連續(xù)的存儲(chǔ)塊中假設(shè)每個(gè)數(shù)組元素的寬度為假設(shè)每個(gè)數(shù)組元素的寬度為w，數(shù)組的首地址為，數(shù)組的首地址為base1.一維數(shù)組元素的定址一維數(shù)組元素的定址：A i n假設(shè)數(shù)組下標(biāo)的下界為假設(shè)數(shù)組下標(biāo)的下

43、界為low，此時(shí)：，此時(shí)：base=&Alow A i 的相對(duì)地址是：的相對(duì)地址是：base + ( i low ) * w優(yōu)化的計(jì)算方式：優(yōu)化的計(jì)算方式：i * w + (base low * w)后一部分可以在處理數(shù)組的說(shuō)明語(yǔ)句時(shí)就計(jì)算出后一部分可以在處理數(shù)組的說(shuō)明語(yǔ)句時(shí)就計(jì)算出來(lái)，存到數(shù)組來(lái)，存到數(shù)組A對(duì)應(yīng)的符號(hào)表項(xiàng)中去，然后在分對(duì)應(yīng)的符號(hào)表項(xiàng)中去，然后在分析析A i 時(shí)只需計(jì)算出時(shí)只需計(jì)算出i*w的值的值TJNU-COCIE-WJW532021-12-22二維數(shù)組A2,3的存儲(chǔ)布局二維數(shù)組A2,3的存儲(chǔ)布局第一行第一行A1,1A1,1A1,2A1,2A1,3A1,3A2,1A2

44、,1A2,2A2,2A2,3A2,3A1,1A1,1A2,1A2,1A1,2A1,2A2,2A2,2A1,3A1,3A2,3A2,3第二行第二行行為主，如C、Pascal行為主，如C、Pascal列為主，如Fortran列為主，如Fortran第一列第一列第二列第二列第三列第三列2.多維數(shù)組的定址多維數(shù)組的定址存儲(chǔ)方式有兩種：數(shù)組元組的定址計(jì)算方式是不一樣的存儲(chǔ)方式有兩種：數(shù)組元組的定址計(jì)算方式是不一樣的 l行為主（一行接一行的存放）行為主（一行接一行的存放）l列為主（一列接一列的存放）列為主（一列接一列的存放）TJNU-COCIE-WJW542021-12-22(1)行為主的二維數(shù)組行為主的

45、二維數(shù)組n元素的定址公式元素的定址公式A i1，i2 的相對(duì)地址：的相對(duì)地址：base + ( ( i1 low1 ) * n2 + ( i2 low2 ) ) * wLow1和和low2分別是兩維的下界分別是兩維的下界n2是數(shù)組第二維的維展，即是數(shù)組第二維的維展，即i2可取值的個(gè)數(shù)，如果可取值的個(gè)數(shù)，如果high2是是i2值的上界，且這一維的步長(zhǎng)為值的上界，且這一維的步長(zhǎng)為1，則則n2=high2 - low2 +1n地址計(jì)算的優(yōu)化公式：地址計(jì)算的優(yōu)化公式： ( ( i1 * n2 ) + i2 ) * w + (base - ( ( low1 * n2 ) + low2 ) * w)(2)

46、列為主的二維數(shù)組的元素定址列為主的二維數(shù)組的元素定址n類似于行為主的二維數(shù)組：類似于行為主的二維數(shù)組： base + ( ( i1 low1 ) + ( i2 low2 ) * n1 ) * wTJNU-COCIE-WJW552021-12-22(3)多維數(shù)組的定址計(jì)算多維數(shù)組的定址計(jì)算n行為主的數(shù)組，最右邊的下標(biāo)變化最快行為主的數(shù)組，最右邊的下標(biāo)變化最快A i1，i2，ik 的相對(duì)地址：的相對(duì)地址：( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 ) * nk

47、+ lowk ) * w由于在大多數(shù)情況下數(shù)組各維的維展是一個(gè)固定值，由于在大多數(shù)情況下數(shù)組各維的維展是一個(gè)固定值，所以上述公式的第二行可以在編譯時(shí)刻計(jì)算，并存所以上述公式的第二行可以在編譯時(shí)刻計(jì)算，并存放在符號(hào)表中放在符號(hào)表中A的條目中的條目中n列為主的數(shù)組，最左邊的下標(biāo)變化最快，其地址計(jì)算列為主的數(shù)組，最左邊的下標(biāo)變化最快，其地址計(jì)算公式可以參照上述公式公式可以參照上述公式TJNU-COCIE-WJW562021-12-223.數(shù)組引用的描述數(shù)組引用的描述(1) 產(chǎn)生式描述產(chǎn)生式描述L id Elist | idElist Elist , E | E其中，其中，Elist代表下標(biāo)表達(dá)式的列

48、表，表達(dá)式中間用代表下標(biāo)表達(dá)式的列表，表達(dá)式中間用，號(hào)分隔。號(hào)分隔。改寫上述產(chǎn)生式，使數(shù)組名字改寫上述產(chǎn)生式，使數(shù)組名字id和最左下標(biāo)表達(dá)式和最左下標(biāo)表達(dá)式E相相聯(lián)系：聯(lián)系：L Elist | idElist Elist , E | id En目的是在對(duì)目的是在對(duì)Elist進(jìn)行翻譯時(shí)，隨時(shí)知道符號(hào)表中數(shù)進(jìn)行翻譯時(shí)，隨時(shí)知道符號(hào)表中數(shù)組組id的全部信息。的全部信息。n為為Elist配備一個(gè)綜合屬性配備一個(gè)綜合屬性array，用它來(lái)傳遞符號(hào)表，用它來(lái)傳遞符號(hào)表中數(shù)組中數(shù)組id項(xiàng)的指針。項(xiàng)的指針。TJNU-COCIE-WJW572021-12-22(2)幾個(gè)定義幾個(gè)定義：屬性屬性Elist.ndim

49、表示表示Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)中的下標(biāo)表達(dá)式的個(gè)數(shù)函數(shù)函數(shù)Limit( array， j )返回?cái)?shù)組返回?cái)?shù)組(array指向的符號(hào)表項(xiàng)所記指向的符號(hào)表項(xiàng)所記錄的數(shù)組錄的數(shù)組)第第j維的元素個(gè)數(shù)維的元素個(gè)數(shù)(維展維展)函數(shù)函數(shù)Invariant( array )取得數(shù)組的地址計(jì)算的不變部分，取得數(shù)組的地址計(jì)算的不變部分，即地址計(jì)算公式第二行中除即地址計(jì)算公式第二行中除base外的其它部分的值外的其它部分的值( ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )* w+base( ( low1 * n2 + low2 ) * n3 + low3 )

50、 * nk + lowk ) * w屬性屬性Elist.place存儲(chǔ)臨時(shí)變量在符號(hào)表中的表項(xiàng)地址存儲(chǔ)臨時(shí)變量在符號(hào)表中的表項(xiàng)地址(3)采用遞推計(jì)算方法實(shí)現(xiàn)采用遞推計(jì)算方法實(shí)現(xiàn)Elist的計(jì)算的計(jì)算(上式中的第一項(xiàng)上式中的第一項(xiàng))：e1 = i1em = em-1 * nm + im當(dāng)當(dāng)m=k時(shí)，時(shí)， ek = ( ( ( i1 * n2 + i2 ) * n3 + i3 ) ) * nk + ik )TJNU-COCIE-WJW582021-12-224.數(shù)組定址的翻譯模式數(shù)組定址的翻譯模式(1)在賦值語(yǔ)句中引用數(shù)組的文法在賦值語(yǔ)句中引用數(shù)組的文法(1) S L := E(2) E E +

51、E(3) E ( E )(4) E L(5) L Elist (6) L id(7) Elist Elist , E(8) Elist id ETJNU-COCIE-WJW592021-12-22(2)各個(gè)產(chǎn)生式的三地址代碼生成各個(gè)產(chǎn)生式的三地址代碼生成(1) S L := E if L.offset = null then /* L是簡(jiǎn)單名字是簡(jiǎn)單名字*/ emit( L.place := E.place ); else emit( L.place L.offset :=E.place ) 如果如果L是簡(jiǎn)單名字，產(chǎn)生正常的賦值；否則產(chǎn)生對(duì)由是簡(jiǎn)單名字，產(chǎn)生正常的賦值；否則產(chǎn)生對(duì)由L的兩的兩個(gè)

52、屬性確定的存儲(chǔ)單元的索引賦值。個(gè)屬性確定的存儲(chǔ)單元的索引賦值。(2) EE1 +E2 E.place := newtemp; emit( E.place := E1.place + E2.place) (3) E ( E ) E.place := E1.place TJNU-COCIE-WJW602021-12-22(4) E L if L.offset = null then/* L是簡(jiǎn)單名字是簡(jiǎn)單名字*/ E.place := L.place; else begin E.place := newtemp; emit( E.place := L.place L.offset ) end 如果

53、如果E產(chǎn)生數(shù)組元素產(chǎn)生數(shù)組元素L，則需要，則需要L的右值，可用索引得到存儲(chǔ)的右值，可用索引得到存儲(chǔ)單元單元L.place L.offset的內(nèi)容的內(nèi)容TJNU-COCIE-WJW612021-12-22(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 ( ( ( (i

54、1 n2 + i2 ) n3 + i3 ) ) nk + ik) w+ base ( ( ( (low1 n2 + low2) n3 + low3) ) nk + lowk ) w L.place和和L.offset都是新的臨時(shí)變量，都是新的臨時(shí)變量，L.place對(duì)應(yīng)第二項(xiàng)；對(duì)應(yīng)第二項(xiàng)；L.offset保存保存w乘以乘以Elist.place的值，對(duì)應(yīng)第一項(xiàng)的值，對(duì)應(yīng)第一項(xiàng) TJNU-COCIE-WJW622021-12-22(7) Elist Elist1 , E t := newtemp; m := Elist1.ndim + 1; emit( t := Elist1.place * l

55、imit( Elist1.array , m ); emit( t := t + E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := m 當(dāng)看見下一個(gè)下標(biāo)表達(dá)式時(shí)，使用遞推公式當(dāng)看見下一個(gè)下標(biāo)表達(dá)式時(shí)，使用遞推公式e1 = i1em = em-1 * nm + imElist1.place對(duì)應(yīng)對(duì)應(yīng)em-1 ，Elist.place對(duì)應(yīng)對(duì)應(yīng)em如果如果Elist1有有m 1個(gè)成分。那么產(chǎn)生式左邊的個(gè)成分。那么產(chǎn)生式左邊的Elist有有m個(gè)成分個(gè)成分TJNU-COCIE-WJW632021-12-22(8)

56、Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place E.place保存表達(dá)式保存表達(dá)式E的值的值也是遞推公式也是遞推公式e1 = i1em = em-1 * nm + imm = 1時(shí)的值時(shí)的值TJNU-COCIE-WJW642021-12-22：A是是10*20的數(shù)組，即的數(shù)組，即n1=10，n2=20，取，取w=4，假設(shè)數(shù)組的第一個(gè)元素是假設(shè)數(shù)組的第一個(gè)元素是A 1 , 1 求賦值語(yǔ)句求賦值語(yǔ)句x:=Ay , z的三地址代碼。的三地址代碼。(其中每個(gè)變量，用它們的名字來(lái)代替其中每個(gè)變量，用它

57、們的名字來(lái)代替id.place)解：不變量：解：不變量：Base - ( ( low1 * n2 ) + low2 ) * w = A - ( 1 * 20 + 1 ) * 4 =A - 84可變量：可變量：( 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-WJW652021-12-22S S: := =L L. .p pl la ac

58、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 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

59、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 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

60、ll ly y A ATJNU-COCIE-WJW662021-12-227.4布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯一、一、概述概述1.布爾表達(dá)式的作用布爾表達(dá)式的作用計(jì)算邏輯值計(jì)算邏輯值在改變控制流的語(yǔ)句中作為條件表達(dá)式在改變控制流的語(yǔ)句中作為條件表達(dá)式n條件語(yǔ)句：條件語(yǔ)句：if then或或if then elsen循環(huán)：循環(huán)：while do，for等等2.布爾表達(dá)式的文法布爾表達(dá)式的文法E E or E | E and E | not E | ( E ) | id relop id | true | false用用relop.op屬性確定屬性確定relop是是,=,=,!=中的哪個(gè)中的哪個(gè)算符的結(jié)合性和優(yōu)