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

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

2、構(gòu)或者聯(lián)合體;標識符的作用域(例1)var x,y,z : integer;procedure P( )；var x,y:integer；procedure Q( )；var x,z:real;begin.endbegin.endPascal語言過函嵌套的例子標識符的作用域(例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);標識符的作用域(3)int i , j ;void test(int j) real x ; int x ; . void main() char i ; int i ; “test”和 “main”的作用域是什么? 符號表的處理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)語義分析時對符號表的管理標識符聲明查找符號表檢查標識符是否已經(jīng)被聲明過;如果是，則重復(fù)聲明錯；如果不是，則建立標識符的內(nèi)部表示，將其放入符號表;標識符使用查找符號表檢查標識符是否有聲明；如果是，則取出標識符的屬性進行語義分析；如果不是，

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

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

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

8、-;全部化符號表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; ( 0, id, attributes )Symbol Table全局化符號表(駐留法)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,)(#,.)(#,.)基于外拉鏈散列表實現(xiàn)分程序結(jié)構(gòu)的符號表基本思想：采用“刪除式”全局符號表，符號表采用散列表實現(xiàn)：以標識符名字為主鍵，將名字作用到事先設(shè)計好的散列函數(shù)上，計算得到標識符的符號表地址。當出現(xiàn)重名標識符時，采用外拉鏈的方式化解沖突。標識符的最新定義出現(xiàn)在鏈表的頭部，總會被最先查到；當分程序無效，分程序中定義的標識符也會從表中直接刪除掉。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. 外拉鏈散列式符號表的構(gòu)造過程如下：符號表的接口創(chuàng)建符號表刪除符號表向符號表中添加表項查找某個標識符查找某個標識符的屬性作業(yè)寫出下列類型的內(nèi)部表示. typedef struct char name10; int age; person; typedef person List10; typedef union int data; real length; char name4; 作業(yè)(2) 寫出當分析下列程序時，創(chuàng)建符號表的過程。 (局部符號表和全局符號表(刪除法和駐留法均可) typedef struct char name30; int age