LGY-BY08語(yǔ)法制導(dǎo)翻譯和中間代碼生成課件

第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成賴國(guó)勇攀枝花學(xué)院計(jì)算機(jī)學(xué)院1賴國(guó)勇第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成賴國(guó)勇1賴國(guó)勇本章內(nèi)容重點(diǎn)難點(diǎn)教學(xué)要求教學(xué)內(nèi)容：語(yǔ)義分析概述；屬性文法；中間代碼生成。重點(diǎn)：三種中間語(yǔ)言：四元式、三元式、逆波蘭式。難點(diǎn)：三種中間語(yǔ)言：四元式、三元式、逆波蘭式。教學(xué)要求1、了解：屬性文法。2、理解：語(yǔ)義分析的功能。3、掌握：逆波蘭式、三元式和樹形表示、四元式。2賴國(guó)勇本章內(nèi)容重點(diǎn)難點(diǎn)教學(xué)要求教學(xué)內(nèi)容：2賴國(guó)勇第8章_目錄8.1語(yǔ)義處理概述8.2屬性文法，語(yǔ)法制導(dǎo)翻譯8.3中間代碼3賴國(guó)勇第8章_目錄8.1語(yǔ)義處理概述3賴國(guó)勇語(yǔ)義分析的基礎(chǔ)1、語(yǔ)義分析的內(nèi)容？2、靜態(tài)語(yǔ)義分析的主要任務(wù)？3、動(dòng)態(tài)語(yǔ)義分析的主要任務(wù)？4、語(yǔ)義的形式化描述？4賴國(guó)勇語(yǔ)義分析的基礎(chǔ)1、語(yǔ)義分析的內(nèi)容？4賴國(guó)勇源語(yǔ)言程序中間代碼匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析中間代碼生成代碼生成在編譯中的邏輯階段前端處理后端處理語(yǔ)義處理語(yǔ)義處理（語(yǔ)義分析和中間代碼生成）5賴國(guó)勇源語(yǔ)言程序中間代碼匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析中間代碼生語(yǔ)言的語(yǔ)義和編譯的語(yǔ)義處理工作靜態(tài)語(yǔ)義：語(yǔ)法規(guī)則的良形式條件。靜態(tài)語(yǔ)義檢查：審查靜態(tài)語(yǔ)義。動(dòng)態(tài)語(yǔ)義：程序單元執(zhí)行的操作。動(dòng)態(tài)語(yǔ)義處理：生成中間(目標(biāo))代碼。6賴國(guó)勇語(yǔ)言的語(yǔ)義和編譯的語(yǔ)義處理工作靜態(tài)語(yǔ)義：語(yǔ)法規(guī)則的良形式條件8.1語(yǔ)義處理概述7賴國(guó)勇8.1語(yǔ)義處理概述7賴國(guó)勇編譯階段-語(yǔ)義處理編譯階段語(yǔ)義處理語(yǔ)法分析后的源程序程序設(shè)計(jì)語(yǔ)言的語(yǔ)義靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見性規(guī)則兩大類。例如：類型相容性，變量先聲明后引用，名稱相關(guān)要求。動(dòng)態(tài)語(yǔ)義

程序單位描述的計(jì)算。編譯程序的語(yǔ)義處理工作靜態(tài)語(yǔ)義審查。解釋執(zhí)行動(dòng)態(tài)語(yǔ)義。8.18賴國(guó)勇編譯階段-語(yǔ)義處理編譯階段語(yǔ)義處理語(yǔ)法分析后的源程序程序設(shè)計(jì)靜態(tài)語(yǔ)義審查1、類型檢查。2、控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。3、一致性檢查。4、上下文相關(guān)性檢查。5、名字的作用域分析。8.19賴國(guó)勇靜態(tài)語(yǔ)義審查1、類型檢查。8.19賴國(guó)勇解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼（中間代碼或目標(biāo)代碼）8.110賴國(guó)勇解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼（中間代碼或目標(biāo)代碼）8.1例8.18.111賴國(guó)勇例8.18.111賴國(guó)勇語(yǔ)義處理的描述屬性文法：描述語(yǔ)義規(guī)則。語(yǔ)法制導(dǎo)翻譯：在語(yǔ)法分析的同時(shí)，執(zhí)行語(yǔ)義子程序：檢查靜態(tài)語(yǔ)義。翻譯(生成)中間(目標(biāo))代碼。8.112賴國(guó)勇語(yǔ)義處理的描述屬性文法：描述語(yǔ)義規(guī)則。8.112賴國(guó)勇語(yǔ)義處理的描述-例8.2P→D；ED→D；D|id:TT→char|integer|array[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表說(shuō)明；E代表表達(dá)式。如程序語(yǔ)句：key:integer;String:char;keymod1999語(yǔ)言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_error和void。假定所有數(shù)組都從下標(biāo)1開始8.113賴國(guó)勇語(yǔ)義處理的描述-例8.2P→D；E8.113賴國(guó)勇確定標(biāo)識(shí)符類型的語(yǔ)義描述（1）P→D；E（2）D→D；D（3）D→id:T{addtype(id.Entry，T.type)}（4）T→char{T.Type:=char}（5）T→integer{T.Type:=integer}（6）T→↑T1{T.Type:=pointer(T1.type)}（7）T→array[num]ofT1

{T.Type:=array(num.Val，T1.type)}8.114賴國(guó)勇確定標(biāo)識(shí)符類型的語(yǔ)義描述（1）P→D；E8.114賴國(guó)勇類型檢查的語(yǔ)義描述-例8.2S→id:=E {ifid.Type=E.Type ThenS.Type:=void elseS.Type:=type_error}S→ifEthenS1 {ifE.type=Boolean thenS.Type:=S1.type elseS.type:=type_error}S→whileEdoS1 {ifE.type=Boolean thenS.type:=S1.Type elseS.type:=type_error}8.115賴國(guó)勇類型檢查的語(yǔ)義描述-例8.2S→id:=E {ifi靜態(tài)語(yǔ)義分析的環(huán)境符號(hào)表（將在第9章詳細(xì)講述）：為語(yǔ)義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲(chǔ)類別、存儲(chǔ)（相對(duì)）位置等信息。8.116賴國(guó)勇靜態(tài)語(yǔ)義分析的環(huán)境符號(hào)表（將在第9章詳細(xì)講述）：8.116賴8.2屬性文法，語(yǔ)法制導(dǎo)翻譯 8.2.1屬性文法8.2.2兩種屬性8.2.3屬性計(jì)算方法8.2.4語(yǔ)法制導(dǎo)翻譯17賴國(guó)勇8.2屬性文法，語(yǔ)法制導(dǎo)翻譯 8.2.1屬性文法17賴國(guó)勇8.2.1屬性文法屬性文法A(attributegrammar)是一個(gè)三元組：A=(G，V，F(xiàn))，其中：G：是一個(gè)上下文無(wú)關(guān)文法。V：有窮的屬性集，每個(gè)屬性與文法的一終結(jié)符或非終結(jié)符相聯(lián)。F：關(guān)于屬性的屬性斷言或謂詞集。每個(gè)斷言與一個(gè)產(chǎn)生式相聯(lián)。而此斷言只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。18賴國(guó)勇8.2.1屬性文法屬性文法A(attributegramm屬性文法屬性文法是允許為每個(gè)終結(jié)符和非終結(jié)符配備一些屬性的文法。它既能描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法，又為其語(yǔ)義描述提供了手段。屬性文法由D.E.Knuth于1968年引進(jìn).后來(lái)才被用于編譯程序的設(shè)計(jì)。8.219賴國(guó)勇屬性文法屬性文法是允許為每個(gè)終結(jié)符和非終結(jié)符配備一些屬性的文例8.4屬性文法表達(dá)式文法E—>T+T|TorT T—>n|bET1+T2{T1.type=intT2.type=T1.typeE.type:=int}E

T1orT2{T1.type=boolT2.type=T1.typeE.type:=bool}Tn {T.type:=int}Tb {T.type:=bool}8.220賴國(guó)勇例8.4屬性文法表達(dá)式文法E—>T+T|Tor屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。賦值規(guī)則附加于語(yǔ)法規(guī)則之上。賦值與語(yǔ)法分析同時(shí)進(jìn)行，賦值過程就是語(yǔ)義處理過程。在推導(dǎo)語(yǔ)法樹的時(shí)候，諸屬性的值被計(jì)算并通過賦值規(guī)則層層傳遞。有的從語(yǔ)法規(guī)則左邊向右邊傳，有的從右邊向左邊傳。語(yǔ)法推導(dǎo)樹最后完成時(shí)，就得到開始符號(hào)的屬性值，也就是整個(gè)程序的語(yǔ)義。8.221賴國(guó)勇屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。8.221例8.6例如：定義表達(dá)式的文法如下(例8.6)EE+EE(E)En給出定義表達(dá)式值的屬性文法。我們?yōu)槲姆ǚ?hào)E引進(jìn)屬性符號(hào)val，用E.val表示E的值，屬性計(jì)算規(guī)則以賦值語(yǔ)句的形式給出，附在每個(gè)產(chǎn)生式后，并用大括號(hào)括起來(lái)。為了明確E的不同出現(xiàn)位置，用上角標(biāo)區(qū)別。終結(jié)符n的值是詞法分析程序提供的，這里用n.lex表示。下面給出屬性文法：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}屬性文法的主要思想有兩點(diǎn)：首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；其次對(duì)于每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。8.222賴國(guó)勇例8.6例如：定義表達(dá)式的文法如下(例8.6)我們?yōu)槲姆?.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inheritedandsynthesized(derived)attribute）。繼承屬性的計(jì)算規(guī)則自頂向下，從其父結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的。綜合屬性的計(jì)算規(guī)則自底向上，從其兄弟結(jié)點(diǎn)和子結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算。AX1X2…XnA的綜合屬性，計(jì)算T(A):=f(I(X1)，…，I(Xn))Xj的繼承屬性，計(jì)算T(Xj):=f(I(A)，...I(Xn))1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性.2)終結(jié)符只有綜合屬性.23賴國(guó)勇8.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inh語(yǔ)義規(guī)則在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b:=f(c1，c2…ck)這里，f是一個(gè)函數(shù)，而且或者（1）b是A的一個(gè)綜合屬性并且c1，c2…ck是產(chǎn)生式右邊文法符號(hào)的屬性;或者（2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1，c2…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。在兩種情況下，我們都說(shuō)屬性b依賴于屬性c1，c2…ck。8.224賴國(guó)勇語(yǔ)義規(guī)則在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之例8.7例如定義表達(dá)式值的屬性文法，E.val是一個(gè)綜合屬性的例子：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}考慮句子2＋（3＋1）的求值順序，將2＋（3＋1）的語(yǔ)法樹結(jié)點(diǎn)改為有附加屬性的結(jié)點(diǎn)（這樣的樹稱為帶注釋的語(yǔ)法樹）：E.val=6E.val=2E.val=4E.val=3E.val=1++n.lex=2n.lex=3n.lex=1()E.val=48.225賴國(guó)勇例8.7例如定義表達(dá)式值的屬性文法，E.val是一個(gè)綜合屬例8.8一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的定義非終結(jié)符E、T及F都有一個(gè)綜合屬性val，符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→En對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)。8.226賴國(guó)勇例8.8一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的定義非終結(jié)符E、T及F都有例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*8.227賴國(guó)勇例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.例8.10繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)*（或）兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。例，添加標(biāo)識(shí)符類型的語(yǔ)義描述：繼承屬性type產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1，idLidL.type:=T.typeT.type=integerT.type:=real

L1.type:=L.type

addtype(id.entry，L.type)

addtype(id.entry，L.type)8.228賴國(guó)勇例8.10繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)例8.10繼承屬性（續(xù)）

Realid1，id2，id3帶注釋的語(yǔ)法樹DL.type=realL.type=realL.type=realT.type=realrealid2id1id3..,,8.229賴國(guó)勇例8.10繼承屬性（續(xù)）

Realid1，id2，id例8.11P–>DSD–>varV;D|S–>V:=E;S|V–>x|y|z現(xiàn)在使用兩個(gè)屬性，name和dl，每當(dāng)一個(gè)新的變量聲明時(shí)，就把它的name屬性附給它，name屬性是綜合屬性。將所聲明的變量都放到一個(gè)變量名字清單中（用語(yǔ)義函數(shù)addlist實(shí)現(xiàn)），用屬性dl綜合聲明塊中聲明的所有變量。然后這個(gè)dl屬性又作為繼承屬性傳到后面的語(yǔ)句部分，每個(gè)語(yǔ)句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中。P–>DS{S.dl=D.dl}D1–>varV;D2|{D1.dl=addlist(V.name，D2.dl)}|{D1.dl=NULL}S1–>V:=E;S2|{check(V.name，S1.dl);S2.dl=S1.dl}V–>x|y|z{V.name='x'}|{V.name='y'}|{V.name='z'}8.230賴國(guó)勇例8.11P–>DS現(xiàn)在使用兩個(gè)屬性，name和dl，varx；vary；x:=e；PDdl={x，y}S

dl={x，y}varV；Ddl={y}V:=e；SxvarV；Ddl={}yy8.231賴國(guó)勇varx；vary；x:=e；PDdl={x，y}S

8.2.3屬性計(jì)算方法樹遍歷的屬性計(jì)算方法設(shè)語(yǔ)法樹已經(jīng)建立起了，并且樹中已帶有開始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹，直至計(jì)算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。32賴國(guó)勇8.2.3屬性計(jì)算方法樹遍歷的屬性計(jì)算方法32賴國(guó)勇一遍掃描的處理方法與樹遍歷的屬性計(jì)算方法不同，一遍掃描在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是在語(yǔ)法分析構(gòu)造語(yǔ)法樹之后進(jìn)行屬性的計(jì)算，而且無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹。因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切相關(guān)：（1）所采用的語(yǔ)法分析方法（2）屬性的計(jì)算次序。8.233賴國(guó)勇一遍掃描的處理方法與樹遍歷的屬性計(jì)算方法不同，一遍掃描在語(yǔ)法8.2.4語(yǔ)法制導(dǎo)翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹）代碼生成（語(yǔ)法樹，匯編語(yǔ)言）設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言L1*到語(yǔ)言L2*的一個(gè)翻譯是由*到*的一個(gè)關(guān)系T，使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2。使(x，y)∈T的句子y叫做x的一個(gè)輸出.直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。34賴國(guó)勇8.2.4語(yǔ)法制導(dǎo)翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。34在語(yǔ)法分析的同時(shí)進(jìn)行語(yǔ)義處理從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬性文法的處理過程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析構(gòu)造語(yǔ)法分析樹，然后根據(jù)需要遍歷語(yǔ)法樹，并在語(yǔ)法樹的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。實(shí)現(xiàn)：輸入符號(hào)串 分析樹 屬性依賴圖 語(yǔ)義規(guī)則的計(jì)算順序8.235賴國(guó)勇在語(yǔ)法分析的同時(shí)進(jìn)行語(yǔ)義處理從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬例8.12：類形檢查例8.12：類形檢查ET1+T2{ifT1.type=intandT2.type=intThen E.type:=intelseerror}E

T1oT2{ifT1.type=boolandT2.type=boolthenE.type:=boolelseerror}

Tn{T.type:=int}Tb{T.type:=bool}編譯實(shí)現(xiàn):(LR)增加語(yǔ)義棧，歸約時(shí)進(jìn)行語(yǔ)義動(dòng)作.LL(1)匹配時(shí)進(jìn)行語(yǔ)義動(dòng)作.8.236賴國(guó)勇例8.12：類形檢查例8.12：類形檢查8.236賴國(guó)勇LR(0)分析表(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.237賴國(guó)勇LR(0)分析表(1) ET+T8.237賴國(guó)勇分析步驟(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.238賴國(guó)勇分析步驟(1) ET+T8.238賴國(guó)勇對(duì)串n+b分析過程(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.239賴國(guó)勇對(duì)串n+b分析過程(1) ET+T8.239賴國(guó)勇8.3中間代碼40賴國(guó)勇8.3中間代碼40賴國(guó)勇概述中間代碼(Intermediatecode)(Intermediaterepresentation)(Intermediatelanguage)是源程序的一種內(nèi)部表示復(fù)雜性介于源語(yǔ)言和目標(biāo)機(jī)語(yǔ)言之間中間代碼的作用：使編譯程序的邏輯結(jié)構(gòu)更加簡(jiǎn)單明確，利于進(jìn)行與目標(biāo)機(jī)無(wú)關(guān)的優(yōu)化，利于在不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言。中間代碼的形式：逆波蘭式、四元式、三元式、間接三元式、樹。8.3算符左操作數(shù)右操作數(shù)結(jié)果41賴國(guó)勇概述中間代碼(Intermediatecode)(In例8.14逆波蘭四元式逆波蘭ABCD-*+ECD–N^/+四元式(1)(-CDT1)(2)(*BT1T2)(3)(+AT2T3)(4)(-CDT4)(5)(^T4NT5)(6)(/ET5T6)(7)(+T3T6T7)A+B*(C-D)+E/(C-D)^N8.342賴國(guó)勇例8.14逆波蘭四元式逆波蘭A例8.14三元式 (1)(-CD)(2)(*B(1))(3)(+A(2))(4)(-CD)(5)(^(4)N)(6)(/E(5))(7)(+(3)(6))A+B*(C-D)+E/(C-D)^N8.343賴國(guó)勇例8.14三元式 (1)(-C例8.14間接三元式間接三元式間接三元式序列間接碼表(1) (-CD) （1）(2) (*B(1)) （2）(3) (+A(2)) （3）(4) (^(1)N) （1）(5) (/E(4)) （4）(6) (+(3)（5)) （5） （6）A+B*(C-D)+E/(C-D)^N8.344賴國(guó)勇例8.14間接三元式間接三元式間接三元式序列中間代碼的層次中間代碼按照其與高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的接近程度，可以分成以下三個(gè)層次：高級(jí)：最接近高級(jí)語(yǔ)言，保留了大部分源語(yǔ)言的結(jié)構(gòu)。低級(jí)：最接近機(jī)器語(yǔ)言，能夠反映目標(biāo)機(jī)的系統(tǒng)結(jié)構(gòu)，因而經(jīng)常依賴于目標(biāo)機(jī)。中級(jí)：介于二者之間，與源語(yǔ)言和機(jī)器語(yǔ)言都有一定差異。8.345賴國(guó)勇中間代碼的層次中間代碼按照其與高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的接近程度，不同層次的中間代碼舉例源語(yǔ)言（高級(jí)語(yǔ)言）中間代碼（高級(jí)）中間代碼（中級(jí)）中間代碼（低級(jí)）floata[10][20];a[i][j+2];t1=a[i，j+2]t1=j+2t2=i*20t3=t1+t2t4=4*t3t5=addrat6=t5+t4t7=*t6r1=[fp-4]r2=[r1+2]r3=[fp-8]r4=r3*20r5=r4+r2r6=4*r5r7=fp–216f1=[r7+r6]8.346賴國(guó)勇不同層次的中間代碼舉例源語(yǔ)言中間代碼（高級(jí)）中間代碼（中級(jí)）本章結(jié)束！

ThankYou!47賴國(guó)勇本章結(jié)束！

ThankYou!47賴國(guó)勇第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成賴國(guó)勇攀枝花學(xué)院計(jì)算機(jī)學(xué)院48賴國(guó)勇第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成賴國(guó)勇1賴國(guó)勇本章內(nèi)容重點(diǎn)難點(diǎn)教學(xué)要求教學(xué)內(nèi)容：語(yǔ)義分析概述；屬性文法；中間代碼生成。重點(diǎn)：三種中間語(yǔ)言：四元式、三元式、逆波蘭式。難點(diǎn)：三種中間語(yǔ)言：四元式、三元式、逆波蘭式。教學(xué)要求1、了解：屬性文法。2、理解：語(yǔ)義分析的功能。3、掌握：逆波蘭式、三元式和樹形表示、四元式。49賴國(guó)勇本章內(nèi)容重點(diǎn)難點(diǎn)教學(xué)要求教學(xué)內(nèi)容：2賴國(guó)勇第8章_目錄8.1語(yǔ)義處理概述8.2屬性文法，語(yǔ)法制導(dǎo)翻譯8.3中間代碼50賴國(guó)勇第8章_目錄8.1語(yǔ)義處理概述3賴國(guó)勇語(yǔ)義分析的基礎(chǔ)1、語(yǔ)義分析的內(nèi)容？2、靜態(tài)語(yǔ)義分析的主要任務(wù)？3、動(dòng)態(tài)語(yǔ)義分析的主要任務(wù)？4、語(yǔ)義的形式化描述？51賴國(guó)勇語(yǔ)義分析的基礎(chǔ)1、語(yǔ)義分析的內(nèi)容？4賴國(guó)勇源語(yǔ)言程序中間代碼匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析中間代碼生成代碼生成在編譯中的邏輯階段前端處理后端處理語(yǔ)義處理語(yǔ)義處理（語(yǔ)義分析和中間代碼生成）52賴國(guó)勇源語(yǔ)言程序中間代碼匯編代碼詞法分析語(yǔ)義分析語(yǔ)法分析中間代碼生語(yǔ)言的語(yǔ)義和編譯的語(yǔ)義處理工作靜態(tài)語(yǔ)義：語(yǔ)法規(guī)則的良形式條件。靜態(tài)語(yǔ)義檢查：審查靜態(tài)語(yǔ)義。動(dòng)態(tài)語(yǔ)義：程序單元執(zhí)行的操作。動(dòng)態(tài)語(yǔ)義處理：生成中間(目標(biāo))代碼。53賴國(guó)勇語(yǔ)言的語(yǔ)義和編譯的語(yǔ)義處理工作靜態(tài)語(yǔ)義：語(yǔ)法規(guī)則的良形式條件8.1語(yǔ)義處理概述54賴國(guó)勇8.1語(yǔ)義處理概述7賴國(guó)勇編譯階段-語(yǔ)義處理編譯階段語(yǔ)義處理語(yǔ)法分析后的源程序程序設(shè)計(jì)語(yǔ)言的語(yǔ)義靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見性規(guī)則兩大類。例如：類型相容性，變量先聲明后引用，名稱相關(guān)要求。動(dòng)態(tài)語(yǔ)義

程序單位描述的計(jì)算。編譯程序的語(yǔ)義處理工作靜態(tài)語(yǔ)義審查。解釋執(zhí)行動(dòng)態(tài)語(yǔ)義。8.155賴國(guó)勇編譯階段-語(yǔ)義處理編譯階段語(yǔ)義處理語(yǔ)法分析后的源程序程序設(shè)計(jì)靜態(tài)語(yǔ)義審查1、類型檢查。2、控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。3、一致性檢查。4、上下文相關(guān)性檢查。5、名字的作用域分析。8.156賴國(guó)勇靜態(tài)語(yǔ)義審查1、類型檢查。8.19賴國(guó)勇解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼（中間代碼或目標(biāo)代碼）8.157賴國(guó)勇解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼（中間代碼或目標(biāo)代碼）8.1例8.18.158賴國(guó)勇例8.18.111賴國(guó)勇語(yǔ)義處理的描述屬性文法：描述語(yǔ)義規(guī)則。語(yǔ)法制導(dǎo)翻譯：在語(yǔ)法分析的同時(shí)，執(zhí)行語(yǔ)義子程序：檢查靜態(tài)語(yǔ)義。翻譯(生成)中間(目標(biāo))代碼。8.159賴國(guó)勇語(yǔ)義處理的描述屬性文法：描述語(yǔ)義規(guī)則。8.112賴國(guó)勇語(yǔ)義處理的描述-例8.2P→D；ED→D；D|id:TT→char|integer|array[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表說(shuō)明；E代表表達(dá)式。如程序語(yǔ)句：key:integer;String:char;keymod1999語(yǔ)言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_error和void。假定所有數(shù)組都從下標(biāo)1開始8.160賴國(guó)勇語(yǔ)義處理的描述-例8.2P→D；E8.113賴國(guó)勇確定標(biāo)識(shí)符類型的語(yǔ)義描述（1）P→D；E（2）D→D；D（3）D→id:T{addtype(id.Entry，T.type)}（4）T→char{T.Type:=char}（5）T→integer{T.Type:=integer}（6）T→↑T1{T.Type:=pointer(T1.type)}（7）T→array[num]ofT1

{T.Type:=array(num.Val，T1.type)}8.161賴國(guó)勇確定標(biāo)識(shí)符類型的語(yǔ)義描述（1）P→D；E8.114賴國(guó)勇類型檢查的語(yǔ)義描述-例8.2S→id:=E {ifid.Type=E.Type ThenS.Type:=void elseS.Type:=type_error}S→ifEthenS1 {ifE.type=Boolean thenS.Type:=S1.type elseS.type:=type_error}S→whileEdoS1 {ifE.type=Boolean thenS.type:=S1.Type elseS.type:=type_error}8.162賴國(guó)勇類型檢查的語(yǔ)義描述-例8.2S→id:=E {ifi靜態(tài)語(yǔ)義分析的環(huán)境符號(hào)表（將在第9章詳細(xì)講述）：為語(yǔ)義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲(chǔ)類別、存儲(chǔ)（相對(duì)）位置等信息。8.163賴國(guó)勇靜態(tài)語(yǔ)義分析的環(huán)境符號(hào)表（將在第9章詳細(xì)講述）：8.116賴8.2屬性文法，語(yǔ)法制導(dǎo)翻譯 8.2.1屬性文法8.2.2兩種屬性8.2.3屬性計(jì)算方法8.2.4語(yǔ)法制導(dǎo)翻譯64賴國(guó)勇8.2屬性文法，語(yǔ)法制導(dǎo)翻譯 8.2.1屬性文法17賴國(guó)勇8.2.1屬性文法屬性文法A(attributegrammar)是一個(gè)三元組：A=(G，V，F(xiàn))，其中：G：是一個(gè)上下文無(wú)關(guān)文法。V：有窮的屬性集，每個(gè)屬性與文法的一終結(jié)符或非終結(jié)符相聯(lián)。F：關(guān)于屬性的屬性斷言或謂詞集。每個(gè)斷言與一個(gè)產(chǎn)生式相聯(lián)。而此斷言只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。65賴國(guó)勇8.2.1屬性文法屬性文法A(attributegramm屬性文法屬性文法是允許為每個(gè)終結(jié)符和非終結(jié)符配備一些屬性的文法。它既能描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法，又為其語(yǔ)義描述提供了手段。屬性文法由D.E.Knuth于1968年引進(jìn).后來(lái)才被用于編譯程序的設(shè)計(jì)。8.266賴國(guó)勇屬性文法屬性文法是允許為每個(gè)終結(jié)符和非終結(jié)符配備一些屬性的文例8.4屬性文法表達(dá)式文法E—>T+T|TorT T—>n|bET1+T2{T1.type=intT2.type=T1.typeE.type:=int}E

T1orT2{T1.type=boolT2.type=T1.typeE.type:=bool}Tn {T.type:=int}Tb {T.type:=bool}8.267賴國(guó)勇例8.4屬性文法表達(dá)式文法E—>T+T|Tor屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。賦值規(guī)則附加于語(yǔ)法規(guī)則之上。賦值與語(yǔ)法分析同時(shí)進(jìn)行，賦值過程就是語(yǔ)義處理過程。在推導(dǎo)語(yǔ)法樹的時(shí)候，諸屬性的值被計(jì)算并通過賦值規(guī)則層層傳遞。有的從語(yǔ)法規(guī)則左邊向右邊傳，有的從右邊向左邊傳。語(yǔ)法推導(dǎo)樹最后完成時(shí)，就得到開始符號(hào)的屬性值，也就是整個(gè)程序的語(yǔ)義。8.268賴國(guó)勇屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。8.221例8.6例如：定義表達(dá)式的文法如下(例8.6)EE+EE(E)En給出定義表達(dá)式值的屬性文法。我們?yōu)槲姆ǚ?hào)E引進(jìn)屬性符號(hào)val，用E.val表示E的值，屬性計(jì)算規(guī)則以賦值語(yǔ)句的形式給出，附在每個(gè)產(chǎn)生式后，并用大括號(hào)括起來(lái)。為了明確E的不同出現(xiàn)位置，用上角標(biāo)區(qū)別。終結(jié)符n的值是詞法分析程序提供的，這里用n.lex表示。下面給出屬性文法：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}屬性文法的主要思想有兩點(diǎn)：首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；其次對(duì)于每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。8.269賴國(guó)勇例8.6例如：定義表達(dá)式的文法如下(例8.6)我們?yōu)槲姆?.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inheritedandsynthesized(derived)attribute）。繼承屬性的計(jì)算規(guī)則自頂向下，從其父結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的。綜合屬性的計(jì)算規(guī)則自底向上，從其兄弟結(jié)點(diǎn)和子結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算。AX1X2…XnA的綜合屬性，計(jì)算T(A):=f(I(X1)，…，I(Xn))Xj的繼承屬性，計(jì)算T(Xj):=f(I(A)，...I(Xn))1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性.2)終結(jié)符只有綜合屬性.70賴國(guó)勇8.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inh語(yǔ)義規(guī)則在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b:=f(c1，c2…ck)這里，f是一個(gè)函數(shù)，而且或者（1）b是A的一個(gè)綜合屬性并且c1，c2…ck是產(chǎn)生式右邊文法符號(hào)的屬性;或者（2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1，c2…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。在兩種情況下，我們都說(shuō)屬性b依賴于屬性c1，c2…ck。8.271賴國(guó)勇語(yǔ)義規(guī)則在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之例8.7例如定義表達(dá)式值的屬性文法，E.val是一個(gè)綜合屬性的例子：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}考慮句子2＋（3＋1）的求值順序，將2＋（3＋1）的語(yǔ)法樹結(jié)點(diǎn)改為有附加屬性的結(jié)點(diǎn)（這樣的樹稱為帶注釋的語(yǔ)法樹）：E.val=6E.val=2E.val=4E.val=3E.val=1++n.lex=2n.lex=3n.lex=1()E.val=48.272賴國(guó)勇例8.7例如定義表達(dá)式值的屬性文法，E.val是一個(gè)綜合屬例8.8一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的定義非終結(jié)符E、T及F都有一個(gè)綜合屬性val，符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→En對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)。8.273賴國(guó)勇例8.8一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的定義非終結(jié)符E、T及F都有例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*8.274賴國(guó)勇例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.例8.10繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)*（或）兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。例，添加標(biāo)識(shí)符類型的語(yǔ)義描述：繼承屬性type產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1，idLidL.type:=T.typeT.type=integerT.type:=real

L1.type:=L.type

addtype(id.entry，L.type)

addtype(id.entry，L.type)8.275賴國(guó)勇例8.10繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)例8.10繼承屬性（續(xù)）

Realid1，id2，id3帶注釋的語(yǔ)法樹DL.type=realL.type=realL.type=realT.type=realrealid2id1id3..,,8.276賴國(guó)勇例8.10繼承屬性（續(xù)）

Realid1，id2，id例8.11P–>DSD–>varV;D|S–>V:=E;S|V–>x|y|z現(xiàn)在使用兩個(gè)屬性，name和dl，每當(dāng)一個(gè)新的變量聲明時(shí)，就把它的name屬性附給它，name屬性是綜合屬性。將所聲明的變量都放到一個(gè)變量名字清單中（用語(yǔ)義函數(shù)addlist實(shí)現(xiàn)），用屬性dl綜合聲明塊中聲明的所有變量。然后這個(gè)dl屬性又作為繼承屬性傳到后面的語(yǔ)句部分，每個(gè)語(yǔ)句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中。P–>DS{S.dl=D.dl}D1–>varV;D2|{D1.dl=addlist(V.name，D2.dl)}|{D1.dl=NULL}S1–>V:=E;S2|{check(V.name，S1.dl);S2.dl=S1.dl}V–>x|y|z{V.name='x'}|{V.name='y'}|{V.name='z'}8.277賴國(guó)勇例8.11P–>DS現(xiàn)在使用兩個(gè)屬性，name和dl，varx；vary；x:=e；PDdl={x，y}S

dl={x，y}varV；Ddl={y}V:=e；SxvarV；Ddl={}yy8.278賴國(guó)勇varx；vary；x:=e；PDdl={x，y}S

8.2.3屬性計(jì)算方法樹遍歷的屬性計(jì)算方法設(shè)語(yǔ)法樹已經(jīng)建立起了，并且樹中已帶有開始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹，直至計(jì)算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。79賴國(guó)勇8.2.3屬性計(jì)算方法樹遍歷的屬性計(jì)算方法32賴國(guó)勇一遍掃描的處理方法與樹遍歷的屬性計(jì)算方法不同，一遍掃描在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是在語(yǔ)法分析構(gòu)造語(yǔ)法樹之后進(jìn)行屬性的計(jì)算，而且無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹。因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切相關(guān)：（1）所采用的語(yǔ)法分析方法（2）屬性的計(jì)算次序。8.280賴國(guó)勇一遍掃描的處理方法與樹遍歷的屬性計(jì)算方法不同，一遍掃描在語(yǔ)法8.2.4語(yǔ)法制導(dǎo)翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹）代碼生成（語(yǔ)法樹，匯編語(yǔ)言）設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言L1*到語(yǔ)言L2*的一個(gè)翻譯是由*到*的一個(gè)關(guān)系T，使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2。使(x，y)∈T的句子y叫做x的一個(gè)輸出.直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。81賴國(guó)勇8.2.4語(yǔ)法制導(dǎo)翻譯一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。34在語(yǔ)法分析的同時(shí)進(jìn)行語(yǔ)義處理從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬性文法的處理過程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析構(gòu)造語(yǔ)法分析樹，然后根據(jù)需要遍歷語(yǔ)法樹，并在語(yǔ)法樹的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。實(shí)現(xiàn)：輸入符號(hào)串 分析樹 屬性依賴圖 語(yǔ)義規(guī)則的計(jì)算順序8.282賴國(guó)勇在語(yǔ)法分析的同時(shí)進(jìn)行語(yǔ)義處理從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬例8.12：類形檢查例8.12：類形檢查ET1+T2{ifT1.type=intandT2.type=intThen E.type:=intelseerror}E

T1oT2{ifT1.type=boolandT2.type=boolthenE.type:=boolelseerror}

Tn{T.type:=int}Tb{T.type:=bool}編譯實(shí)現(xiàn):(LR)增加語(yǔ)義棧，歸約時(shí)進(jìn)行語(yǔ)義動(dòng)作.LL(1)匹配時(shí)進(jìn)行語(yǔ)義動(dòng)作.8.283賴國(guó)勇例8.12：類形檢查例8.12：類形檢查8.236賴國(guó)勇LR(0)分析表(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.284賴國(guó)勇LR(0)分析表(1) ET+T8.237賴國(guó)勇分析步驟(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.285賴國(guó)勇分析步驟(1) ET+T8.238賴國(guó)勇對(duì)串n+b分析過程(1) ET

+T(2) E

T

oT(3) Tn(4) Tb8.286賴國(guó)勇對(duì)串n+b分析過程(1) ET+T8.239賴國(guó)勇8.3中間代碼87賴國(guó)勇8.3中間代碼40賴國(guó)勇概述中間代碼(Intermediatecode)(Intermediaterepresentation)(Intermediatelanguage)是源程序的一種內(nèi)部表示復(fù)雜性介于源語(yǔ)言和目標(biāo)