LGY-BY08語法制導翻譯和中間代碼生成課件

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

程序單位描述的計算。編譯程序的語義處理工作靜態(tài)語義審查。解釋執(zhí)行動態(tài)語義。8.18賴國勇編譯階段-語義處理編譯階段語義處理語法分析后的源程序程序設計靜態(tài)語義審查1、類型檢查。2、控制流檢查?？刂屏髡Z句必須使控制轉移到合法的地方。3、一致性檢查。4、上下文相關性檢查。5、名字的作用域分析。8.19賴國勇靜態(tài)語義審查1、類型檢查。8.19賴國勇解釋執(zhí)行動態(tài)語義（計算）生成代碼（中間代碼或目標代碼）8.110賴國勇解釋執(zhí)行動態(tài)語義（計算）生成代碼（中間代碼或目標代碼）8.1例8.18.111賴國勇例8.18.111賴國勇語義處理的描述屬性文法：描述語義規(guī)則。語法制導翻譯：在語法分析的同時，執(zhí)行語義子程序：檢查靜態(tài)語義。翻譯(生成)中間(目標)代碼。8.112賴國勇語義處理的描述屬性文法：描述語義規(guī)則。8.112賴國勇語義處理的描述-例8.2P→D；ED→D；D|id:TT→char|integer|array[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表說明；E代表表達式。如程序語句：key:integer;String:char;keymod1999語言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_error和void。假定所有數(shù)組都從下標1開始8.113賴國勇語義處理的描述-例8.2P→D；E8.113賴國勇確定標識符類型的語義描述（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賴國勇確定標識符類型的語義描述（1）P→D；E8.114賴國勇類型檢查的語義描述-例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賴國勇類型檢查的語義描述-例8.2S→id:=E {ifi靜態(tài)語義分析的環(huán)境符號表（將在第9章詳細講述）：為語義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲類別、存儲（相對）位置等信息。8.116賴國勇靜態(tài)語義分析的環(huán)境符號表（將在第9章詳細講述）：8.116賴8.2屬性文法，語法制導翻譯 8.2.1屬性文法8.2.2兩種屬性8.2.3屬性計算方法8.2.4語法制導翻譯17賴國勇8.2屬性文法，語法制導翻譯 8.2.1屬性文法17賴國勇8.2.1屬性文法屬性文法A(attributegrammar)是一個三元組：A=(G，V，F(xiàn))，其中：G：是一個上下文無關文法。V：有窮的屬性集，每個屬性與文法的一終結符或非終結符相聯(lián)。F：關于屬性的屬性斷言或謂詞集。每個斷言與一個產生式相聯(lián)。而此斷言只引用該產生式左端或右端的終結符或非終結符相聯(lián)的屬性。18賴國勇8.2.1屬性文法屬性文法A(attributegramm屬性文法屬性文法是允許為每個終結符和非終結符配備一些屬性的文法。它既能描述程序設計語言的語法，又為其語義描述提供了手段。屬性文法由D.E.Knuth于1968年引進.后來才被用于編譯程序的設計。8.219賴國勇屬性文法屬性文法是允許為每個終結符和非終結符配備一些屬性的文例8.4屬性文法表達式文法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賴國勇例8.4屬性文法表達式文法E—>T+T|Tor屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。賦值規(guī)則附加于語法規(guī)則之上。賦值與語法分析同時進行，賦值過程就是語義處理過程。在推導語法樹的時候，諸屬性的值被計算并通過賦值規(guī)則層層傳遞。有的從語法規(guī)則左邊向右邊傳，有的從右邊向左邊傳。語法推導樹最后完成時，就得到開始符號的屬性值，也就是整個程序的語義。8.221賴國勇屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。8.221例8.6例如：定義表達式的文法如下(例8.6)EE+EE(E)En給出定義表達式值的屬性文法。我們?yōu)槲姆ǚ朎引進屬性符號val，用E.val表示E的值，屬性計算規(guī)則以賦值語句的形式給出，附在每個產生式后，并用大括號括起來。為了明確E的不同出現(xiàn)位置，用上角標區(qū)別。終結符n的值是詞法分析程序提供的，這里用n.lex表示。下面給出屬性文法：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}屬性文法的主要思想有兩點：首先對于每個文法符號引進相關的屬性符號；其次對于每個產生式寫出屬性值計算的規(guī)則。8.222賴國勇例8.6例如：定義表達式的文法如下(例8.6)我們?yōu)槲姆?.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inheritedandsynthesized(derived)attribute）。繼承屬性的計算規(guī)則自頂向下，從其父結點的屬性值計算出來的。綜合屬性的計算規(guī)則自底向上，從其兄弟結點和子結點的屬性值計算出來的。出現(xiàn)在產生式左邊的繼承屬性和出現(xiàn)在產生式右邊的綜合屬性不由所給定的產生式的屬性計算規(guī)則進行計算，它們由其它產生式的屬性規(guī)則計算。AX1X2…XnA的綜合屬性，計算T(A):=f(I(X1)，…，I(Xn))Xj的繼承屬性，計算T(Xj):=f(I(A)，...I(Xn))1)非終結符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性.2)終結符只有綜合屬性.23賴國勇8.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inh語義規(guī)則在一個屬性文法中，對應于每個產生式A都有一套與之相關聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1，c2…ck)這里，f是一個函數(shù)，而且或者（1）b是A的一個綜合屬性并且c1，c2…ck是產生式右邊文法符號的屬性;或者（2）b是產生式右邊某個文法符號的一個繼承屬性并且c1，c2…ck是A或產生式右邊任何文法符號的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1，c2…ck。8.224賴國勇語義規(guī)則在一個屬性文法中，對應于每個產生式A都有一套與之例8.7例如定義表達式值的屬性文法，E.val是一個綜合屬性的例子：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）的語法樹結點改為有附加屬性的結點（這樣的樹稱為帶注釋的語法樹）：E.val=6E.val=2E.val=4E.val=3E.val=1++n.lex=2n.lex=3n.lex=1()E.val=48.225賴國勇例8.7例如定義表達式值的屬性文法，E.val是一個綜合屬例8.8一個簡單臺式計算器的定義非終結符E、T及F都有一個綜合屬性val，符號digit有一個綜合屬性，它的值由詞法分析器提供。與產生式L→En對應的語義規(guī)則僅僅是打印由E產生的算術表達式的值的一個過程，我們可認為這條規(guī)則定義了L的一個虛屬性。某些非終結符加下標是為了區(qū)分一個產生式中同一非終結符多次出現(xiàn)。8.226賴國勇例8.8一個簡單臺式計算器的定義非終結符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賴國勇例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.例8.10繼承屬性一個結點的繼承屬性值是由此結點的父結點*（或）兄弟結點的某些屬性來決定的。例，添加標識符類型的語義描述：繼承屬性type產生式語義規(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賴國勇例8.10繼承屬性一個結點的繼承屬性值是由此結點的父結點例8.10繼承屬性（續(xù)）

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

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

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

8.2.3屬性計算方法樹遍歷的屬性計算方法設語法樹已經建立起了，并且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。32賴國勇8.2.3屬性計算方法樹遍歷的屬性計算方法32賴國勇一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描在語法分析的同時計算屬性值，而不是在語法分析構造語法樹之后進行屬性的計算，而且無需構造實際的語法樹。因為一遍掃描的處理方法與語法分析器的相互作用，它與下面兩個因素密切相關：（1）所采用的語法分析方法（2）屬性的計算次序。8.233賴國勇一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描在語法8.2.4語法制導翻譯一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標程序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設是輸入字母表且是輸出字母表。定義由語言L1*到語言L2*的一個翻譯是由*到*的一個關系T，使得T的定義域為L1且T的值域為L2。使(x，y)∈T的句子y叫做x的一個輸出.直觀地說，一個語法制導翻譯的基礎是一個文法，其中翻譯成分依附在每一產生式上。34賴國勇8.2.4語法制導翻譯一個翻譯是符號串對的一個集合。34在語法分析的同時進行語義處理從概念上講，語法制導翻譯即基于屬性文法的處理過程通常是這樣的：對單詞符號串進行語法分析構造語法分析樹，然后根據(jù)需要遍歷語法樹，并在語法樹的各結點處按語義規(guī)則進行計算。實現(xiàn)：輸入符號串 分析樹 屬性依賴圖 語義規(guī)則的計算順序8.235賴國勇在語法分析的同時進行語義處理從概念上講，語法制導翻譯即基于屬例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}編譯實現(xiàn):(LR)增加語義棧，歸約時進行語義動作.LL(1)匹配時進行語義動作.8.236賴國勇例8.12：類形檢查例8.12：類形檢查8.236賴國勇LR(0)分析表(1) ET

+T(2) E

T

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

+T(2) E

T

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

+T(2) E

T

oT(3) Tn(4) Tb8.239賴國勇對串n+b分析過程(1) ET+T8.239賴國勇8.3中間代碼40賴國勇8.3中間代碼40賴國勇概述中間代碼(Intermediatecode)(Intermediaterepresentation)(Intermediatelanguage)是源程序的一種內部表示復雜性介于源語言和目標機語言之間中間代碼的作用：使編譯程序的邏輯結構更加簡單明確，利于進行與目標機無關的優(yōu)化，利于在不同目標機上實現(xiàn)同一種語言。中間代碼的形式：逆波蘭式、四元式、三元式、間接三元式、樹。8.3算符左操作數(shù)右操作數(shù)結果41賴國勇概述中間代碼(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賴國勇例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賴國勇例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賴國勇例8.14間接三元式間接三元式間接三元式序列中間代碼的層次中間代碼按照其與高級語言和機器語言的接近程度，可以分成以下三個層次：高級：最接近高級語言，保留了大部分源語言的結構。低級：最接近機器語言，能夠反映目標機的系統(tǒng)結構，因而經常依賴于目標機。中級：介于二者之間，與源語言和機器語言都有一定差異。8.345賴國勇中間代碼的層次中間代碼按照其與高級語言和機器語言的接近程度，不同層次的中間代碼舉例源語言（高級語言）中間代碼（高級）中間代碼（中級）中間代碼（低級）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賴國勇不同層次的中間代碼舉例源語言中間代碼（高級）中間代碼（中級）本章結束！

ThankYou!47賴國勇本章結束！

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

程序單位描述的計算。編譯程序的語義處理工作靜態(tài)語義審查。解釋執(zhí)行動態(tài)語義。8.155賴國勇編譯階段-語義處理編譯階段語義處理語法分析后的源程序程序設計靜態(tài)語義審查1、類型檢查。2、控制流檢查?？刂屏髡Z句必須使控制轉移到合法的地方。3、一致性檢查。4、上下文相關性檢查。5、名字的作用域分析。8.156賴國勇靜態(tài)語義審查1、類型檢查。8.19賴國勇解釋執(zhí)行動態(tài)語義（計算）生成代碼（中間代碼或目標代碼）8.157賴國勇解釋執(zhí)行動態(tài)語義（計算）生成代碼（中間代碼或目標代碼）8.1例8.18.158賴國勇例8.18.111賴國勇語義處理的描述屬性文法：描述語義規(guī)則。語法制導翻譯：在語法分析的同時，執(zhí)行語義子程序：檢查靜態(tài)語義。翻譯(生成)中間(目標)代碼。8.159賴國勇語義處理的描述屬性文法：描述語義規(guī)則。8.112賴國勇語義處理的描述-例8.2P→D；ED→D；D|id:TT→char|integer|array[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表說明；E代表表達式。如程序語句：key:integer;String:char;keymod1999語言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_error和void。假定所有數(shù)組都從下標1開始8.160賴國勇語義處理的描述-例8.2P→D；E8.113賴國勇確定標識符類型的語義描述（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賴國勇確定標識符類型的語義描述（1）P→D；E8.114賴國勇類型檢查的語義描述-例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賴國勇類型檢查的語義描述-例8.2S→id:=E {ifi靜態(tài)語義分析的環(huán)境符號表（將在第9章詳細講述）：為語義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲類別、存儲（相對）位置等信息。8.163賴國勇靜態(tài)語義分析的環(huán)境符號表（將在第9章詳細講述）：8.116賴8.2屬性文法，語法制導翻譯 8.2.1屬性文法8.2.2兩種屬性8.2.3屬性計算方法8.2.4語法制導翻譯64賴國勇8.2屬性文法，語法制導翻譯 8.2.1屬性文法17賴國勇8.2.1屬性文法屬性文法A(attributegrammar)是一個三元組：A=(G，V，F(xiàn))，其中：G：是一個上下文無關文法。V：有窮的屬性集，每個屬性與文法的一終結符或非終結符相聯(lián)。F：關于屬性的屬性斷言或謂詞集。每個斷言與一個產生式相聯(lián)。而此斷言只引用該產生式左端或右端的終結符或非終結符相聯(lián)的屬性。65賴國勇8.2.1屬性文法屬性文法A(attributegramm屬性文法屬性文法是允許為每個終結符和非終結符配備一些屬性的文法。它既能描述程序設計語言的語法，又為其語義描述提供了手段。屬性文法由D.E.Knuth于1968年引進.后來才被用于編譯程序的設計。8.266賴國勇屬性文法屬性文法是允許為每個終結符和非終結符配備一些屬性的文例8.4屬性文法表達式文法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賴國勇例8.4屬性文法表達式文法E—>T+T|Tor屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。賦值規(guī)則附加于語法規(guī)則之上。賦值與語法分析同時進行，賦值過程就是語義處理過程。在推導語法樹的時候，諸屬性的值被計算并通過賦值規(guī)則層層傳遞。有的從語法規(guī)則左邊向右邊傳，有的從右邊向左邊傳。語法推導樹最后完成時，就得到開始符號的屬性值，也就是整個程序的語義。8.268賴國勇屬性賦值屬性有不同的類型，可以象變量一樣地被賦值。8.221例8.6例如：定義表達式的文法如下(例8.6)EE+EE(E)En給出定義表達式值的屬性文法。我們?yōu)槲姆ǚ朎引進屬性符號val，用E.val表示E的值，屬性計算規(guī)則以賦值語句的形式給出，附在每個產生式后，并用大括號括起來。為了明確E的不同出現(xiàn)位置，用上角標區(qū)別。終結符n的值是詞法分析程序提供的，這里用n.lex表示。下面給出屬性文法：EE1+E2 {E.val:=E1.val+E2.val}E(E1) {E.val:=E1.val}En {E.val:=n.lex}屬性文法的主要思想有兩點：首先對于每個文法符號引進相關的屬性符號；其次對于每個產生式寫出屬性值計算的規(guī)則。8.269賴國勇例8.6例如：定義表達式的文法如下(例8.6)我們?yōu)槲姆?.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inheritedandsynthesized(derived)attribute）。繼承屬性的計算規(guī)則自頂向下，從其父結點的屬性值計算出來的。綜合屬性的計算規(guī)則自底向上，從其兄弟結點和子結點的屬性值計算出來的。出現(xiàn)在產生式左邊的繼承屬性和出現(xiàn)在產生式右邊的綜合屬性不由所給定的產生式的屬性計算規(guī)則進行計算，它們由其它產生式的屬性規(guī)則計算。AX1X2…XnA的綜合屬性，計算T(A):=f(I(X1)，…，I(Xn))Xj的繼承屬性，計算T(Xj):=f(I(A)，...I(Xn))1)非終結符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性.2)終結符只有綜合屬性.70賴國勇8.2.2兩種屬性屬性分為兩種:繼承屬性和綜合屬性（inh語義規(guī)則在一個屬性文法中，對應于每個產生式A都有一套與之相關聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1，c2…ck)這里，f是一個函數(shù)，而且或者（1）b是A的一個綜合屬性并且c1，c2…ck是產生式右邊文法符號的屬性;或者（2）b是產生式右邊某個文法符號的一個繼承屬性并且c1，c2…ck是A或產生式右邊任何文法符號的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1，c2…ck。8.271賴國勇語義規(guī)則在一個屬性文法中，對應于每個產生式A都有一套與之例8.7例如定義表達式值的屬性文法，E.val是一個綜合屬性的例子：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）的語法樹結點改為有附加屬性的結點（這樣的樹稱為帶注釋的語法樹）：E.val=6E.val=2E.val=4E.val=3E.val=1++n.lex=2n.lex=3n.lex=1()E.val=48.272賴國勇例8.7例如定義表達式值的屬性文法，E.val是一個綜合屬例8.8一個簡單臺式計算器的定義非終結符E、T及F都有一個綜合屬性val，符號digit有一個綜合屬性，它的值由詞法分析器提供。與產生式L→En對應的語義規(guī)則僅僅是打印由E產生的算術表達式的值的一個過程，我們可認為這條規(guī)則定義了L的一個虛屬性。某些非終結符加下標是為了區(qū)分一個產生式中同一非終結符多次出現(xiàn)。8.273賴國勇例8.8一個簡單臺式計算器的定義非終結符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賴國勇例8.9:3*5+4的帶注釋的分析樹只使用綜合屬性.LE.例8.10繼承屬性一個結點的繼承屬性值是由此結點的父結點*（或）兄弟結點的某些屬性來決定的。例，添加標識符類型的語義描述：繼承屬性type產生式語義規(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賴國勇例8.10繼承屬性一個結點的繼承屬性值是由此結點的父結點例8.10繼承屬性（續(xù)）

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

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

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

8.2.3屬性計算方法樹遍歷的屬性計算方法設語法樹已經建立起了，并且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。79賴國勇8.2.3屬性計算方法樹遍歷的屬性計算方法32賴國勇一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描在語法分析的同時計算屬性值，而不是在語法分析構造語法樹之后進行屬性的計算，而且無需構造實際的語法樹。因為一遍掃描的處理方法與語法分析器的相互作用，它與下面兩個因素密切相關：（1）所采用的語法分析方法（2）屬性的計算次序。8.280賴國勇一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描在語法8.2.4語法制導翻譯一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標程序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設是輸入字母表且是輸出字母表。定義由語言L1*到語言L2*的一個翻譯是由*到*的一個關系T，使得T的定義域為L1且T的值域為L2。使(x，y)∈T的句子y叫做x的一個輸出.直觀地說，一個語法制導翻譯的基礎是一個文法，其中翻譯成分依附在每一產生式上。81賴國勇8.2.4語法制導翻譯一個翻譯是符號串對的一個集合。34在語法分析的同時進行語義處理從概念上講，語法制導翻譯即基于屬性文法的處理過程通常是這樣的：對單詞符號串進行語法分析構造語法分析樹，然后根據(jù)需要遍歷語法樹，并在語法樹的各結點處按語義規(guī)則進行計算。實現(xiàn)：輸入符號串 分析樹 屬性依賴圖 語義規(guī)則的計算順序8.282賴國勇在語法分析的同時進行語義處理從概念上講，語法制導翻譯即基于屬例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}編譯實現(xiàn):(LR)增加語義棧，歸約時進行語義動作.LL(1)匹配時進行語義動作.8.283賴國勇例8.12：類形檢查例8.12：類形檢查8.236賴國勇LR(0)分析表(1) ET

+T(2) E

T

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

+T(2) E

T

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

+T(2) E

T

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