編譯程序原理與實(shí)現(xiàn)：第6章 語(yǔ)義分析(2)

1、第六章 語(yǔ)義分析6.1 語(yǔ)義分析概述6.2 符號(hào)表6.3 類(lèi)型的語(yǔ)義分析6.4 聲明的語(yǔ)義分析6.5 程序體的語(yǔ)義分析6.6 屬性文法和動(dòng)作文法6.2 符號(hào)表標(biāo)識(shí)符的作用域局部化符號(hào)表全局化符號(hào)表符號(hào)表的接口函數(shù)標(biāo)識(shí)符的作用域作用域(scope)程序中的每個(gè)標(biāo)識(shí)符都有自己的作用域;標(biāo)識(shí)符的作用域是標(biāo)識(shí)符可見(jiàn)(visible)或有效的(effective)一個(gè)程序片段,稱(chēng)為程序的局部化單位; 通常一個(gè)程序局部化單位是一個(gè)子程序(函數(shù))或者分程序;一個(gè)標(biāo)識(shí)符的作用域從聲明該標(biāo)識(shí)符的位置開(kāi)始到其所在的局部化單位的結(jié)束(其中要去掉其內(nèi)部聲明的同名標(biāo)識(shí)符的作用域);特別地, 域名的作用域是包含該域名的結(jié)

2、構(gòu)或者聯(lián)合體;標(biāo)識(shí)符的作用域(例1)var x,y,z : integer;procedure P( )；var x,y:integer；procedure Q( )；var x,z:real;begin.endbegin.endPascal語(yǔ)言過(guò)函嵌套的例子標(biāo)識(shí)符的作用域(例2)帶有分程序嵌套的C程序的例子int a,b;void main() int a = 1; int b = 1; int b = 2; int a = 3; printf(“a=%d,b=%dn”,a,b); int a = 3; printf(“a=%d,b=%dn”,a,b); printf(“a=%d,b=%dn

3、”,a,b);標(biāo)識(shí)符的作用域(3)int i , j ;void test(int j) real x ; int x ; . void main() char i ; int i ; “test”和 “main”的作用域是什么? 符號(hào)表的處理int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; j: (intPtr, varKind, 0, 1, dir)i: (intPtr, varKind, 0, 0, dir)test: (voidPtr, routKind, 0, )j: (i

4、ntPtr, varKind, 1, 0, dir)x: (realPtr, varKind, 1, 1, dir)x: (intPtr, varKind, 1, ?, dir)main: (voidPtr, routKind, 0, )i: (charPtr, varKind, 1, 0, dir)i: (intPtr, varKind, 1, 1, dir)語(yǔ)義分析時(shí)對(duì)符號(hào)表的管理標(biāo)識(shí)符聲明查找符號(hào)表檢查標(biāo)識(shí)符是否已經(jīng)被聲明過(guò);如果是，則重復(fù)聲明錯(cuò)；如果不是，則建立標(biāo)識(shí)符的內(nèi)部表示，將其放入符號(hào)表;標(biāo)識(shí)符使用查找符號(hào)表檢查標(biāo)識(shí)符是否有聲明；如果是，則取出標(biāo)識(shí)符的屬性進(jìn)行語(yǔ)義分析；如果不是，

5、則未聲明錯(cuò)；退出局部化單位,“刪除” 該局部化單位里聲明的所有標(biāo)識(shí)符;符號(hào)表的組織第一，易于查找順序查找折半查找散列表(hash table)第二，反映標(biāo)識(shí)符的作用域，保證每次標(biāo)識(shí)符的有效屬性都能被找到;局部化: 每個(gè)局部化單位的符號(hào)表作為一個(gè)獨(dú)立的表處理, 即把每個(gè)局部化單位的符號(hào)表作為建表和查表單位;全局化:把整個(gè)程序的符號(hào)表統(tǒng)一處理;局部化符號(hào)表Scope棧保存當(dāng)前所有局部化單位符號(hào)表的首地址;局部化實(shí)現(xiàn)原理:進(jìn)入局部化單位,建立一個(gè)新的空符號(hào)表,并將地址壓入Scope棧;遇到定義性標(biāo)識(shí)符(聲明), 查當(dāng)前符號(hào)表判定是否有重復(fù)定義,如果沒(méi)有則將其屬性登記到當(dāng)前符號(hào)表中;遇到使用性標(biāo)識(shí)符,

6、查符號(hào)表(從當(dāng)前符號(hào)表查,如果沒(méi)有,再依次查scope棧中下一個(gè)符號(hào)表,如果都沒(méi)有,沒(méi)有聲明錯(cuò);否則,找到對(duì)應(yīng)的屬性);結(jié)束一個(gè)局部化單位時(shí),刪除當(dāng)前符號(hào)表, 彈出scope棧頂元素;每個(gè)局部化單位的符號(hào)表可以是線(xiàn)性表; 二叉樹(shù); 散列表局部化符號(hào)表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; Scope棧0全局化符號(hào)表全局化實(shí)現(xiàn)原理整個(gè)程序用一個(gè)符號(hào)表, 該符號(hào)表的組織可以是線(xiàn)性表; 二叉樹(shù); 散列表每個(gè)局部化單位對(duì)應(yīng)一個(gè)唯一的局部化編號(hào)num;符號(hào)表的表項(xiàng)為(num, id,

7、 attributes);初始化: CurrentNum = 0;每當(dāng)進(jìn)入一個(gè)新的局部化單位時(shí), CurrentNum+;遇到定義性標(biāo)識(shí)符(聲明),檢查所有對(duì)應(yīng)CurrentNum的表項(xiàng),判定是否有重復(fù)定義,如果沒(méi)有則將其屬性及其CurrentNum登記到符號(hào)表中;遇到使用性標(biāo)識(shí)符,查符號(hào)表,(查所有num=CurrentNum的表項(xiàng)，且按照CurrentNum, CurrentNum-1, CurrentNum-2, 0的順序查找)如果都沒(méi)有,則為標(biāo)識(shí)符未聲明錯(cuò);否則,最先查到的表項(xiàng)為標(biāo)識(shí)符對(duì)應(yīng)的屬性;結(jié)束一個(gè)局部化單位時(shí),”刪除”所有CurrentNum對(duì)應(yīng)的表項(xiàng), CurrentNum

8、-;全部化符號(hào)表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; ( 0, id, attributes )Symbol Table全局化符號(hào)表(駐留法)int i , j ;void test ( int j ) real x ; j int x ; x x void main() char i ; int i ; x bool x; x(0,i,0,0,intptr,)(0,j,0,1,intptr,)(0,test,0,voidptr,)(1,j,1,0,intptr,)(1,

9、x,1,1,realptr,)(2,x,1,3,intptr,)(#,.)(2,x,1,3,boolptr,)(#,.)(#,.)基于外拉鏈散列表實(shí)現(xiàn)分程序結(jié)構(gòu)的符號(hào)表基本思想：采用“刪除式”全局符號(hào)表，符號(hào)表采用散列表實(shí)現(xiàn)：以標(biāo)識(shí)符名字為主鍵，將名字作用到事先設(shè)計(jì)好的散列函數(shù)上，計(jì)算得到標(biāo)識(shí)符的符號(hào)表地址。當(dāng)出現(xiàn)重名標(biāo)識(shí)符時(shí)，采用外拉鏈的方式化解沖突。標(biāo)識(shí)符的最新定義出現(xiàn)在鏈表的頭部，總會(huì)被最先查到；當(dāng)分程序無(wú)效，分程序中定義的標(biāo)識(shí)符也會(huì)從表中直接刪除掉。1. main()2. 3. int a；4. float b，d；5. 6 int c；7. float a；8. 9. int d;1

10、0. float c;11. 12. float d;13. 14. a=b+c+d;15. 16. 17. 18. char d;19. 20. 21. 外拉鏈散列式符號(hào)表的構(gòu)造過(guò)程如下：符號(hào)表的接口創(chuàng)建符號(hào)表刪除符號(hào)表向符號(hào)表中添加表項(xiàng)查找某個(gè)標(biāo)識(shí)符查找某個(gè)標(biāo)識(shí)符的屬性作業(yè)寫(xiě)出下列類(lèi)型的內(nèi)部表示. typedef struct char name10; int age; person; typedef person List10; typedef union int data; real length; char name4; 作業(yè)(2) 寫(xiě)出當(dāng)分析下列程序時(shí)，創(chuàng)建符號(hào)表的過(guò)程。 (局部符號(hào)表和全局符號(hào)表(刪除法和駐留法均可) typedef struct char name30; int age