新版編譯原理課件

第四章靜態(tài)語義分析本章注重討論靜態(tài)語義的分析方法，過程程序設計語言中典型結(jié)構(gòu)的翻譯方法。第2章第3章1。第四章靜態(tài)語義分析

語法制導翻譯是處理語義的基本方法，它以語法分析為基礎，在語法分析得到語言結(jié)構(gòu)的結(jié)果時，處理此結(jié)構(gòu)對應的語義，如計算表達式的值、生成中間代碼等。主要內(nèi)容包括：

<1>語法制導翻譯的基本概念

<2>中間代碼簡介

<3>符號表簡介

<4>典型聲明語句與可執(zhí)行語句的翻譯2。4.1語法制導翻譯簡介

4.1.1語法與語義語法是指語言的結(jié)構(gòu)、即語言的“樣子”；語義是指附著于語言結(jié)構(gòu)上的實際含意，即語言的“意義”。

<1>語法與語義的關系語義不能離開語法獨立存在；語法與語義之間沒有明確的界線；語義遠比語法復雜；同一語言結(jié)構(gòu)可包含多種含意，不同語言結(jié)構(gòu)可表示相同含意。3。4.1.1語法與語義（續(xù)1）例1：程序設計語言中的分情況結(jié)構(gòu)：1．LinuxBashScript

caseconditionincase1)stat1

;;case2)stat2

;;

*)

…

;;

esac2．C/C++

switch(condition)

{

casecondition1:stat1;

casecondition2:stat2;

default:…

}

break;break;例2：“貓吃老鼠”，“老鼠吃貓”4。4.1.1語法與語義（續(xù)2）

檢查結(jié)構(gòu)正確的句子所表示的意思是否合法；執(zhí)行規(guī)定的語義動作，如： 表達式求值 符號表的查詢/填寫 中間代碼生成等<3>語義分析的方法語法制導翻譯（SyntaxDirectedTranslation）

<下頁><2>語義分析的兩個作用5。4.1.2屬性與語義規(guī)則<1>語法制導翻譯的基本思想簡單地講：以語法分析為基礎，伴隨語法分析的各個步驟，執(zhí)行相應的語義動作。具體方法：1.將文法符號所代表的語言結(jié)構(gòu)的意思，用附著于該文法符號的屬性表示；2.用語義規(guī)則規(guī)定產(chǎn)生式所代表的語言結(jié)構(gòu)之間的關系（即屬性之間的關系），即用語義規(guī)則實現(xiàn)語義(屬性)計算。語義規(guī)則的執(zhí)行：

在語法分析的適當時刻（如推導或歸約）執(zhí)行附著在對應產(chǎn)生式上的語義規(guī)則，以實現(xiàn)對語言結(jié)構(gòu)語義的處理，如計算、查填符號表、生成中間代碼、發(fā)布出錯信息等。6。4.1.2屬性與語義規(guī)則（續(xù)1）<2>屬性的抽象表示：.attr例如：E.val（值）

E.type（類型）

E.code（代碼序列）

E.place（存儲空間）<3>對文法的約定本章關注的是語法分析的基礎上的語義處理，忽略語法分析。為了簡單，本章的文法一般為二義文法。默認解決二義的方法是規(guī)定常規(guī)意義下的優(yōu)先級和結(jié)合性。7。4.1.2屬性與語義規(guī)則（續(xù)2）定義4.1

對于產(chǎn)生式A→α，其中α是由文法符號X1X2...Xn組成的序列，它的語義規(guī)則可以表示為(4.1)所示關于屬性的函數(shù)f：

b:=f(c1,c2,...,ck)(4.1)語義規(guī)則中的屬性存在下述性質(zhì)與關系：

(1)稱(4.1)中屬性b依賴于屬性c1,c2,...,ck。

(2)若b是A的屬性，c1,c2,...,ck是α中文法符號的屬性，或者A的其它屬性，則稱b是A的綜合屬性。

(3)若b是α中某文法符號Xi的屬性，c1,c2,...,ck是A的屬性，或者是α中其它文法符號的屬性，則稱b是Xi的繼承屬性。

(4)若語義規(guī)則的形式如下述(4.2)，則可將其想像為產(chǎn)生式左部文法符號A的一個虛擬屬性。屬性之間的依賴關系，在虛擬屬性上依然存在。

f(c1,c2,...,ck)(4.2)

■<4>屬性/語義規(guī)則的定義**注釋樹8。E→E1+E2

E.val:=+（E1.val,E2.val）E的屬性.val由E1

和E2

的相應屬性計算而來，因此我們說E的屬性依賴于E1和E2的屬性。從定義4.1可知： 語義規(guī)則就是屬性之間的計算， 屬性的依賴關系決定了計算的先后次序。例如：4.1.2屬性與語義規(guī)則（續(xù)3）9。4.1.3語義規(guī)則的兩種形式<1>語法制導定義(SyntaxDirectedDefinition)

用抽象的屬性和運算表示的語義規(guī)則；(公式，做什么)<2>翻譯方案(TranslationScheme)

用具體的屬性和運算表示的語義規(guī)則。(程序段，如何做)

忽略實現(xiàn)細節(jié)，二者作用等價。（類似：概要設計與詳細設計）語義規(guī)則也被習慣上稱為語義動作(Semanticaction)。10。4.1.3語義規(guī)則的兩種形式（續(xù)1）例4.1

計算中綴形式的算術表達式的后綴形式，并打印。需要的語法制導定義和翻譯方案。產(chǎn)生式L→EE→E1+E2E→num

語法制導定義print(E.post)E.post:=E1.post||E2.post||'+';E.post:=num.lexval;

翻譯方案1print_post(post);post[k]:='+';k:=k+1;post[k]:=lexval;k:=k+1;產(chǎn)生式翻譯方案2L→E E→E1+E2print(+);E→numprint(lexval);虛擬屬性：print(E.post)可想象為：L.p:=print(E.post)返回11。4.1.3語義規(guī)則的兩種形式（續(xù)2）例4.1，自下而上計算，LR分析。（以3+5+8為例，歸約時翻譯）post:翻譯方案中需要考慮的問題：1．采用什么樣的語法分析方法；2．為屬性分配存儲空間；3．考慮計算次序。語法制導定義－算法

翻譯方案－程序?qū)崿F(xiàn)， 方法不唯一產(chǎn)生式 翻譯方案1L→E print_post(post);E→E1+E2 post[k]:='+';k:=k+1;E→num post[k]:=lexval;k:=k+1;產(chǎn)生式 翻譯方案2L→E E→E1+E2 print(+);E→num print(lexval);35+8+k35+8+打?。?2。4.1.3語義規(guī)則的兩種形式（續(xù)3）<3>屬性作為分析樹的注釋將屬性附著在分析樹對應文法符號上，形成注釋分析樹。產(chǎn)生式語法制導定義 翻譯方案L→E print(E.post);E→E1+E2E.post:=E1.post||E2.post||'+';print(+);E→numE.post:=num.lexval; print(lexval);

例4.2

3+5+8的分析樹和注釋分析樹：

.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))13。4.1.3語義規(guī)則的兩種形式（續(xù)4）注釋分析樹上看：綜合屬性是自下而上計算的繼承屬性是自上而下計算的約定：除非特別提醒，本章討論的語法制導翻譯是綜合屬性；且采用LR分析。<4>綜合屬性與繼承屬性的計算次序語義規(guī)則定義14。4.1.4LR分析翻譯方案的設計LR分析中的語法制導翻譯實質(zhì)上是對LR語法分析的擴充：1.擴充LR分析器的功能： 當執(zhí)行歸約的動作時，也執(zhí)行相應產(chǎn)生式對應的語義動作。由于是歸約時執(zhí)行語義動作，因此限制語義動作僅能放在產(chǎn)生式右部的最右邊；2.擴充分析棧： 增加一個與分析棧并列的語義棧，用于存放分析棧中文法符號所對應的屬性值。15。n

4.1.4LR分析翻譯方案的設計（續(xù)1）例如：

E→E1+E2val[top]:=val[top]+val[top+2];E→nval[top]:=lexval;對于表達式：5+3求值當歸約為左部E時，同時也得到了值8。5Etopval？+toptop3EE816。4.1.4LR分析翻譯方案的設計（續(xù)2）例4.3

3+5*8求值的語法制導翻譯。翻譯方案print(val[top]);val[top]:=val[top]+val[top+2];val[top]:=val[top]*val[top+2];val[top]:=lexval;產(chǎn)生式L→EE→E1+E2E→E1*E2E→n語法制導定義print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;17。4.1.4LR分析翻譯方案的設計（續(xù)3）（格局的變化）分析棧語義棧 輸入 格局動作，語義動作# # 3+5*8# shift#n # +5*8# E→n，val[top]:=lexval#E #3 +5*8# shift#E+ #3? 5*8# shift#E+n#3? *8# E→n，val[top]:=lexval#E+E #3?5 *8# shift#E+E* #3?5?8# shift#E+E*n#3?5?# E→n，val[top]:=lexval#E+E*E#3?5?8# E→E1*E2，val[top]:=val[top]*val[top+2];#E+E #3?40# E→E1+E2，val[top]:=val[top]+val[top+2];#E #43 # L→E,print(val[top])#L #43 # acc修改教材P14335818。4.1.5遞歸下降分析翻譯方案的設計

遞歸下降方法是用程序?qū)崿F(xiàn)對非終結(jié)符的展開和對終結(jié)符的匹配。翻譯方案的設計需要解決兩個問題：1．如何在遞歸下降子程序中嵌入語義動作：

產(chǎn)生式右部的任何位置；2．如何為文法符號的屬性設計存儲空間：

函數(shù)返回值、參數(shù)、變量等。

例如函數(shù)繪圖語言識別器語法制導翻譯設計：1.遞歸子程序可以設計為函數(shù)，用于返回必要的屬性值；2.適當設計子程序中的臨時變量，用于保存屬性值；3.將語義動作嵌入在子程序的合適位置，正確計算屬性值。閱讀：

教材中相關例子例如：表達式

Expression19。//表達式的遞歸下降子程序structExprNode*Expression(){structExprNode*left,*right;

Token_Typetoken_tmp;

left

=Term();

while(token.type==PLUS||token.type==MINUS)

{token_tmp=token.type;

MatchToken(token_tmp);

right

=Term();

left=MakeExprNode(token_tmp,left,rig