編譯原理及實(shí)現(xiàn)技術(shù)：第六章 語(yǔ)義分析

1、第六章第六章 語(yǔ)義分析語(yǔ)義分析語(yǔ)義分析概述語(yǔ)義分析概述符號(hào)表符號(hào)表1 1 語(yǔ)義分析語(yǔ)義分析必要性必要性分類分類語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤功能功能1.11.1語(yǔ)義分析的必要性語(yǔ)義分析的必要性 語(yǔ)法和語(yǔ)義的區(qū)別語(yǔ)法和語(yǔ)義的區(qū)別 語(yǔ)法：關(guān)于什么樣的字符串才是該語(yǔ)言在組語(yǔ)法：關(guān)于什么樣的字符串才是該語(yǔ)言在組成結(jié)構(gòu)上合法的程序的法則。成結(jié)構(gòu)上合法的程序的法則。語(yǔ)義：關(guān)于結(jié)構(gòu)上合法的程序的意義法則。語(yǔ)義：關(guān)于結(jié)構(gòu)上合法的程序的意義法則。1.21.2語(yǔ)義分析的分類語(yǔ)義分析的分類 語(yǔ)義種類語(yǔ)義種類 指稱語(yǔ)義指稱語(yǔ)義 操作語(yǔ)義操作語(yǔ)義 公理語(yǔ)義公理語(yǔ)義 靜態(tài)語(yǔ)義靜態(tài)語(yǔ)義：在編譯階段：在編譯階段( (從程序文本上從程序文本

2、上) )可以檢可以檢查的語(yǔ)義。查的語(yǔ)義。 動(dòng)態(tài)語(yǔ)義動(dòng)態(tài)語(yǔ)義：通過程序的執(zhí)行才能檢查的語(yǔ)義。：通過程序的執(zhí)行才能檢查的語(yǔ)義。1.31.3語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤1.1. 各種條件表達(dá)式的各種條件表達(dá)式的類型類型是不是是不是booleanboolean型型? ?2.2. 運(yùn)算符的分量的運(yùn)算符的分量的類型類型是否相容是否相容? ?3.3. 賦值語(yǔ)句的左右部的賦值語(yǔ)句的左右部的類型類型是否相容是否相容? ?4.4. 形參和實(shí)參的形參和實(shí)參的類型類型是否相容是否相容? ?5.5. 下標(biāo)表達(dá)式的下標(biāo)表達(dá)式的類型類型是否為所允許的類型是否為所允許的類型? ?6.6. 函數(shù)說(shuō)明中的函數(shù)函數(shù)說(shuō)明中的函數(shù)類型類型和返回值

3、的類型是否一致和返回值的類型是否一致? ?7.7. VEVE中的中的V V是不是變量是不是變量, ,而且是數(shù)組類型？而且是數(shù)組類型？8.8. V.idV.id中的中的V V是不是變量是不是變量, ,而且是記錄類型而且是記錄類型? id? id是不是該記錄類型中是不是該記錄類型中的域名的域名? ?9.9. y+fy+f()()中的中的f f是不是函數(shù)名是不是函數(shù)名? ?形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致? ?10.10.p()p()語(yǔ)句中的語(yǔ)句中的p p是不是過程名是不是過程名? ?形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致? ?11.11.VV中的中的V V是不是指

4、針或文件變量？是不是指針或文件變量？12.12.變體記錄中表示情形的常量是否為合法類型變體記錄中表示情形的常量是否為合法類型? ?13.13.子界類型中的下界和上界類型是否相容子界類型中的下界和上界類型是否相容? ?下界是否小于等于上界？下界是否小于等于上界？語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤 cont.cont.1.1. 每個(gè)使用性標(biāo)識(shí)符是否都有每個(gè)使用性標(biāo)識(shí)符是否都有聲明聲明? ?在同層內(nèi)有無(wú)在同層內(nèi)有無(wú)標(biāo)識(shí)符被聲明多次標(biāo)識(shí)符被聲明多次? ?2.2. 標(biāo)號(hào)是否有標(biāo)號(hào)是否有聲明聲明? ?有無(wú)重復(fù)聲明和重復(fù)定位錯(cuò)誤有無(wú)重復(fù)聲明和重復(fù)定位錯(cuò)誤? ?有無(wú)非法轉(zhuǎn)入錯(cuò)誤？有無(wú)非法轉(zhuǎn)入錯(cuò)誤？1.41.4語(yǔ)義分析的功能語(yǔ)義

5、分析的功能 語(yǔ)義分析的內(nèi)容：語(yǔ)義分析的內(nèi)容： 類型分析；類型分析； 標(biāo)識(shí)符相關(guān)信息提??；標(biāo)識(shí)符相關(guān)信息提取； 語(yǔ)義分析的功能：語(yǔ)義分析的功能： 檢查語(yǔ)義錯(cuò)誤檢查語(yǔ)義錯(cuò)誤 構(gòu)造標(biāo)識(shí)符屬性表（符號(hào)表）構(gòu)造標(biāo)識(shí)符屬性表（符號(hào)表） 語(yǔ)義分析的實(shí)現(xiàn)：語(yǔ)義分析的實(shí)現(xiàn)： 與語(yǔ)法分析相結(jié)合與語(yǔ)法分析相結(jié)合語(yǔ)義分析的功能圖示語(yǔ)義分析的功能圖示語(yǔ)義分析語(yǔ)義分析語(yǔ)法分析樹語(yǔ)法分析樹TokenList語(yǔ)義定義語(yǔ)義定義自然語(yǔ)言描述規(guī)定自然語(yǔ)言描述規(guī)定符號(hào)表符號(hào)表判定語(yǔ)判定語(yǔ)義錯(cuò)誤義錯(cuò)誤2 2 符號(hào)表符號(hào)表符號(hào)名屬性xint, variable, pvoid, function, (int i), .詞法分析語(yǔ)法分析語(yǔ)義

6、分析中間代碼生成2.12.1地位地位符號(hào)名符號(hào)名類型類型指針指針大小大小xfunM2.22.2符號(hào)的內(nèi)部表示符號(hào)的內(nèi)部表示 值的內(nèi)部表示值的內(nèi)部表示 類型的內(nèi)部表示類型的內(nèi)部表示 標(biāo)識(shí)符的內(nèi)部表示標(biāo)識(shí)符的內(nèi)部表示.1值的內(nèi)部表示值的內(nèi)部表示基本類型：整型，實(shí)型基本類型：整型，實(shí)型無(wú)序類型：指針，數(shù)組，結(jié)構(gòu)體無(wú)序類型：指針，數(shù)組，結(jié)構(gòu)體有序類型：布爾，字符，枚舉，數(shù)組下標(biāo)有序類型：布爾，字符，枚舉，數(shù)組下標(biāo) 布爾常量：布爾常量：ord(false)=0, ord(true)= 1ord(false)=0, ord(true)= 1 字符常量：字符常量：ord(C) = ASC(C

7、)ord(C) = ASC(C) 枚舉常量：設(shè)有枚舉類型枚舉常量：設(shè)有枚舉類型( (D,A,B),D,A,B),則有則有ord(D)=0,ord(A)=1,ord(B)=2ord(D)=0,ord(A)=1,ord(B)=.2類型的內(nèi)部表示類型的內(nèi)部表示 類型的種類：標(biāo)準(zhǔn)、類型的種類：標(biāo)準(zhǔn)、子界、子界、枚舉、數(shù)組、枚舉、數(shù)組、記錄、集合、文件、記錄、集合、文件、指針類型等指針類型等Type=(intTy,boolTy,charTy,realTy, subTy,enumTy, Type=(intTy,boolTy,charTy,realTy, subTy,enumTy, arr

8、ayTy,recordTy,setTy,fileTy,pointerTy)arrayTy,recordTy,setTy,fileTy,pointerTy) 內(nèi)部表示：內(nèi)部表示：( (TypeIR)TypeIR)int/bool/int/bool/char/realchar/real：enum: enum: array:array:pointer: pointer: SizeTypeSizeTypeElementListLengthSizeTypeLowUpElementTypeSizeTypeTypeName2intTy2enumTyintPtr310arryTy04intPtrsize(po

9、inter)pointerTyintPtr實(shí)例實(shí)例int f(real x, char y)int f(real x, char y)bool t=true;bool t=true;enum a a1,a2,a3;enum a a1,a2,a3;real bM;real bM;char cchar c* *; ;return t;return t; 寫出各類型的內(nèi)部表示。寫出各類型的內(nèi)部表示。類和結(jié)構(gòu)體類和結(jié)構(gòu)體 結(jié)構(gòu)體結(jié)構(gòu)體 類類SizeKindFieldListnameKindTypeOff實(shí)例實(shí)例class Studentclass StudentString name;String n

10、ame;int age;int age;real mark;real mark;public Student(String n,int a, real m)public Student(String n,int a, real m)=n;=n;this.age=a;this.age=a;this.mark = m;this.mark = m; getgetsetset SizeKindFieldListnameKindTypeOffnamefieldKindcharPtr0agefieldKindintPtr1markfieldKindrealPtr3Stu

11、dentfieldKindPtr7get.3標(biāo)識(shí)符的內(nèi)部表示標(biāo)識(shí)符的內(nèi)部表示 常見標(biāo)識(shí)符種類：常量名、常見標(biāo)識(shí)符種類：常量名、類型名、類型名、變量變量名、名、函數(shù)名、過程名、函數(shù)名、過程名、域名域名。Kind=(consKind, typeKind, varKind,fieldKind, Kind=(consKind, typeKind, varKind,fieldKind, funcKindfuncKind，procKind)procKind) 內(nèi)部表示（內(nèi)部表示（AttributeIRAttributeIR）：）：常量名：常量名：變量名：變量名：類型名：類型名：過函名：過函

12、名：域名名：域名名：NameKindTypeValueNameKindTypeAccesLevelOffValueNameKindTypeNameKindTypeClassLevelOffParaCodeSizeForNameKindTypeoffM constKindintPtr10avarKindrealPtrdirect1 3Null/100mattypeKindPtrffuncKindintPtrformal15ffuncKindintPtractual1parListptrFt/fmarkvarKindIntPtr3層數(shù)和偏移層數(shù)和偏移 層數(shù)層數(shù)(level)(level) 過程過程

13、/ /函數(shù)的定義函數(shù)的定義( (不不) )可以可以嵌套；嵌套； 最外層程序的層數(shù)為最外層程序的層數(shù)為1(0)1(0); ; 偏移量偏移量(offset)(offset) 原因：執(zhí)行過程原因：執(zhí)行過程/ /函數(shù)的調(diào)用時(shí)函數(shù)的調(diào)用時(shí), , 需要為其中需要為其中的變量分配空間的變量分配空間; ; 計(jì)算：偏移量指的是變量針對(duì)其所在過程計(jì)算：偏移量指的是變量針對(duì)其所在過程/ /函函數(shù)的空間的首地址的偏移量數(shù)的空間的首地址的偏移量; ;實(shí)例實(shí)例#define Pi 3.14#define Pi 3.14bool g(real x, int bool g(real x, int * * y) y)int v

14、10;real z;return 0;int v10;real z;return 0;enum gender male,female;enum gender male,female;Main()Main()令當(dāng)前層數(shù)和偏移分別為令當(dāng)前層數(shù)和偏移分別為L(zhǎng) L和和0 0，構(gòu)造標(biāo)識(shí)符，構(gòu)造標(biāo)識(shí)符Pi,g,x,y,v,z,genderPi,g,x,y,v,z,gender的屬性表。的屬性表。NameKindTypeValueClassAccessLevelOff/ParaCodeSizeForPiconsreal3.14gfuncboolactuaLparaListPnullsizeFalsexvar

15、KrealdirectL+104yvarKp1indirecL+141vvarKa1directL+1520zvarKrealdirectL+1314gendvarKe1L0PtrSizeKindTypUpEleTypeintPtr2boolP1charP1realPt4p11poinintPta120arra9intPte11enuNameValuemale1female22.32.3符號(hào)表符號(hào)表 標(biāo)識(shí)符在不同位置的不同作用：標(biāo)識(shí)符在不同位置的不同作用： 聲明部分：定義了各種對(duì)象及對(duì)應(yīng)的屬性和使聲明部分：定義了各種對(duì)象及對(duì)應(yīng)的屬性和使用規(guī)則。用規(guī)則。 程序體：對(duì)所定義的對(duì)象進(jìn)行各種操作。程序

16、體：對(duì)所定義的對(duì)象進(jìn)行各種操作。 必要性必要性 TokenToken序列序列： 符號(hào)表（種類、類型等信息）：符號(hào)表（種類、類型等信息）：$IDidnameidnameAttribute.1建立和訪問建立和訪問有關(guān)符號(hào)表的操作：有關(guān)符號(hào)表的操作： 添加、作用域刪除、查詢添加、作用域刪除、查詢處理符號(hào)表的模塊：處理符號(hào)表的模塊： 定義符號(hào)表數(shù)據(jù)結(jié)構(gòu)定義符號(hào)表數(shù)據(jù)結(jié)構(gòu) 定義符號(hào)表上的操作定義符號(hào)表上的操作.2符號(hào)表的處理符號(hào)表的處理 符號(hào)表的作用：為語(yǔ)義檢查和代碼生成提符號(hào)表的作用：為語(yǔ)義檢查和代碼生成提供標(biāo)識(shí)符的語(yǔ)義信息。供標(biāo)識(shí)符的語(yǔ)義信息。 標(biāo)識(shí)符的處理思想：標(biāo)

17、識(shí)符的處理思想：1.1. 遇到遇到定義性定義性標(biāo)識(shí)符時(shí)，在符號(hào)表中填寫被標(biāo)識(shí)符時(shí)，在符號(hào)表中填寫被定義標(biāo)識(shí)符的符號(hào)項(xiàng)；定義標(biāo)識(shí)符的符號(hào)項(xiàng)；2.2. 遇到遇到使用性使用性標(biāo)識(shí)符時(shí)，用該標(biāo)識(shí)符查符號(hào)標(biāo)識(shí)符時(shí)，用該標(biāo)識(shí)符查符號(hào)表求得其屬性。表求得其屬性。標(biāo)識(shí)符的特點(diǎn)標(biāo)識(shí)符的特點(diǎn) 標(biāo)識(shí)符的作用域：標(biāo)識(shí)符有效的最大程序段標(biāo)識(shí)符的作用域：標(biāo)識(shí)符有效的最大程序段 嵌套作用域規(guī)則：當(dāng)存在標(biāo)識(shí)符的嵌套聲明嵌套作用域規(guī)則：當(dāng)存在標(biāo)識(shí)符的嵌套聲明時(shí)，最近定義的屬性為標(biāo)識(shí)符的當(dāng)前屬性時(shí)，最近定義的屬性為標(biāo)識(shí)符的當(dāng)前屬性 局部化單位：允許有聲明的程序段局部化單位：允許有聲明的程序段P:Var x ,y,zVar x,m

18、,nx:=1;m:=x+1;y:=x+1;x:=0;Q:局部化區(qū)入口局部化區(qū)入口 Proc p(Proc p( Func f(Func f( Record beginRecord begin標(biāo)識(shí)符處理的原則標(biāo)識(shí)符處理的原則 符號(hào)表的種類：符號(hào)表的種類：全局符號(hào)表、局部符號(hào)表全局符號(hào)表、局部符號(hào)表 處理原則：處理原則：1.1. 進(jìn)入一個(gè)局部化區(qū)時(shí)，進(jìn)入一個(gè)局部化區(qū)時(shí)，記錄記錄本層符號(hào)表的位置本層符號(hào)表的位置 2.2. 遇到定義性標(biāo)識(shí)符時(shí)，遇到定義性標(biāo)識(shí)符時(shí)，構(gòu)造構(gòu)造其語(yǔ)義信息，查本層其語(yǔ)義信息，查本層符號(hào)表，若存在，則有重復(fù)聲明錯(cuò)誤，否則將語(yǔ)符號(hào)表，若存在，則有重復(fù)聲明錯(cuò)誤，否則將語(yǔ)義信息填入表

19、中義信息填入表中 3.3. 遇到一個(gè)使用性標(biāo)識(shí)符時(shí)，遇到一個(gè)使用性標(biāo)識(shí)符時(shí)，查表查表（從里層到外（從里層到外層），查不到則有未定義標(biāo)識(shí)符錯(cuò)誤，否則構(gòu)造層），查不到則有未定義標(biāo)識(shí)符錯(cuò)誤，否則構(gòu)造新的新的TOKENTOKEN4.4. 退出一個(gè)局部化區(qū)時(shí)，退出一個(gè)局部化區(qū)時(shí)，作廢作廢本層符號(hào)表本層符號(hào)表語(yǔ)義分析例子語(yǔ)義分析例子int x,y;int x,y;void swap(int void swap(int * *a,int a,int * *b)b)int tmp;int tmp;temp=temp=* *a; a; * *a=a=* *b;b;* *b=tmp;b=tmp; void mai

20、n()void main()x=10; y=20;x=10; y=20;swap(&x,&y);swap(&x,&y); NameKindTypeAccessLevelOffParaListCodeForwardxvarKindintPtrdir00yvarKindintPtrdir01swapfuncKindNullactural0swapParaListswapCfalseavarKinda-ptrindir10bvarKindb-ptrindir11tmpvarKindintPtrdir12#mainfuncKindNullactual0NullmainC

21、False#ptrsizekindeleTypea-ptr1pointerTyintPtrb-ptr1pointerTyintPtr符號(hào)表的分類符號(hào)表的分類 單表結(jié)構(gòu)單表結(jié)構(gòu) vs. vs. 多表結(jié)構(gòu)多表結(jié)構(gòu) 單表：?jiǎn)伪恚簶?biāo)識(shí)符都放在同一張符號(hào)表中標(biāo)識(shí)符都放在同一張符號(hào)表中 多表：多表：常量、變量、類型、函數(shù)、等分別存放常量、變量、類型、函數(shù)、等分別存放 局部表局部表 vs. vs. 全局表全局表 局部式：局部式：每個(gè)局部化單位建立一個(gè)獨(dú)立符號(hào)表每個(gè)局部化單位建立一個(gè)獨(dú)立符號(hào)表 全局式：全局式：整個(gè)程序的符號(hào)表作為一個(gè)表整個(gè)程序的符號(hào)表作為一個(gè)表全局符號(hào)表的局部化全局符號(hào)表的局部化思想思想特點(diǎn)

22、特點(diǎn)刪除法 離開局部化區(qū)時(shí)刪除思路簡(jiǎn)單，實(shí)現(xiàn)容易，信息不留存駐留法 離開局部化區(qū)時(shí)標(biāo)記信息留存，實(shí)現(xiàn)相對(duì)復(fù)雜（輔助數(shù)據(jù)結(jié)構(gòu)）刪除法刪除法 vs. vs. 駐留法駐留法局部化實(shí)例局部化實(shí)例intint main() main() intint a; a; float float b,db,d; ; intint c; c; float a; float a; intint d; d; float c; float c; float d; float d; /. /. a= a=b+c+db+c+d; ; char d; char d; return 0; return 0; namekindty

23、peaccessleveloffextraformainfuncKintPtractural0nullfalseavarKiintPtrdir101bvarKirealPtdir111dvarKirealPtdir131cvarKiintPtrdir152avarKirealPtdir162dvarKiintPtrdir183cvarKirealPtdir193dvarKirealPtdir1114#dvarKicharPdir183局部符號(hào)表管理局部符號(hào)表管理ScopeScope棧棧 用于存放當(dāng)前有效的局部化區(qū)的局部符號(hào)用于存放當(dāng)前有效的局部化區(qū)的局部符號(hào)表首地址；表首地址； 進(jìn)入新局部化區(qū)

24、時(shí)新符號(hào)表首地址入棧；進(jìn)入新局部化區(qū)時(shí)新符號(hào)表首地址入棧； 退出局部化區(qū)時(shí)棧頂?shù)刂烦鰲?。退出局部化區(qū)時(shí)棧頂?shù)刂烦鰲?。?biāo)號(hào)的語(yǔ)義分析標(biāo)號(hào)的語(yǔ)義分析 標(biāo)號(hào)出現(xiàn)的位置：標(biāo)號(hào)出現(xiàn)的位置：標(biāo)號(hào)聲明：標(biāo)號(hào)聲明：label label 1 1, , 2 2, , , , n n; ;標(biāo)號(hào)定位標(biāo)號(hào)定位（語(yǔ)句前）：語(yǔ)句前）：i i：StatementStatement；標(biāo)號(hào)使用（標(biāo)號(hào)使用（GotoGoto后）：后）：goto goto i i; ; 標(biāo)號(hào)部分的語(yǔ)義錯(cuò)誤：標(biāo)號(hào)部分的語(yǔ)義錯(cuò)誤： 標(biāo)號(hào)重復(fù)聲明；標(biāo)號(hào)重復(fù)聲明； 標(biāo)號(hào)重復(fù)定位；標(biāo)號(hào)重復(fù)定位； 標(biāo)號(hào)有定位而無(wú)聲明；標(biāo)號(hào)有定位而無(wú)聲明； 標(biāo)號(hào)有使用而無(wú)定位；

25、標(biāo)號(hào)有使用而無(wú)定位； GotoGoto語(yǔ)句有非法轉(zhuǎn)入語(yǔ)句有非法轉(zhuǎn)入. .標(biāo)號(hào)部分語(yǔ)義分析原理標(biāo)號(hào)部分語(yǔ)義分析原理 設(shè)置五種表：設(shè)置五種表：LDECLDEC，LDEFLDEF，LUSELUSE，SLSL，PLPL LDECLDEC表表：( (Flag, LabelFlag, Label，)； LDEFLDEF、LUSELUSE表：表：( (Label)Label)； SLSL表：表：(kind(kind，LDEFaddrLDEFaddr，LUSEaddr)LUSEaddr)； PLPL表：表：(LDECaddr(LDECaddr，LDEFaddr)LDEFaddr)； 標(biāo)號(hào)的語(yǔ)義分析原理標(biāo)號(hào)的語(yǔ)義分析原理1 1）進(jìn)入一個(gè)進(jìn)入一個(gè)過過/ /函函時(shí)，將本層時(shí)，將本層LDECLDEC和和LDEFLDEF的地址填入的地址