编译程序原理与实现：第6章 语义分析(2)

1、第六章 语义分析6.1 语义分析概述6.2 符号表6.3 类型的语义分析6.4 声明的语义分析6.5 程序体的语义分析6.6 属性文法和动作文法6.2 符号表标识符的作用域局部化符号表全局化符号表符号表的接口函数标识符的作用域作用域(scope)程序中的每个标识符都有自己的作用域;标识符的作用域是标识符可见(visible)或有效的(effective)一个程序片段,称为程序的局部化单位; 通常一个程序局部化单位是一个子程序(函数)或者分程序;一个标识符的作用域从声明该标识符的位置开始到其所在的局部化单位的结束(其中要去掉其内部声明的同名标识符的作用域);特别地, 域名的作用域是包含该域名的结

2、构或者联合体;标识符的作用域(例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)语义分析时对符号表的管理标识符声明查找符号表检查标识符是否已经被声明过;如果是，则重复声明错；如果不是，则建立标识符的内部表示，将其放入符号表;标识符使用查找符号表检查标识符是否有声明；如果是，则取出标识符的属性进行语义分析；如果不是，

5、则未声明错；退出局部化单位,“删除” 该局部化单位里声明的所有标识符;符号表的组织第一，易于查找顺序查找折半查找散列表(hash table)第二，反映标识符的作用域，保证每次标识符的有效属性都能被找到;局部化: 每个局部化单位的符号表作为一个独立的表处理, 即把每个局部化单位的符号表作为建表和查表单位;全局化:把整个程序的符号表统一处理;局部化符号表Scope栈保存当前所有局部化单位符号表的首地址;局部化实现原理:进入局部化单位,建立一个新的空符号表,并将地址压入Scope栈;遇到定义性标识符(声明), 查当前符号表判定是否有重复定义,如果没有则将其属性登记到当前符号表中;遇到使用性标识符,

6、查符号表(从当前符号表查,如果没有,再依次查scope栈中下一个符号表,如果都没有,没有声明错;否则,找到对应的属性);结束一个局部化单位时,删除当前符号表, 弹出scope栈顶元素;每个局部化单位的符号表可以是线性表; 二叉树; 散列表局部化符号表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; Scope栈0全局化符号表全局化实现原理整个程序用一个符号表, 该符号表的组织可以是线性表; 二叉树; 散列表每个局部化单位对应一个唯一的局部化编号num;符号表的表项为(num, id,

7、 attributes);初始化: CurrentNum = 0;每当进入一个新的局部化单位时, CurrentNum+;遇到定义性标识符(声明),检查所有对应CurrentNum的表项,判定是否有重复定义,如果没有则将其属性及其CurrentNum登记到符号表中;遇到使用性标识符,查符号表,(查所有num=CurrentNum的表项，且按照CurrentNum, CurrentNum-1, CurrentNum-2, 0的顺序查找)如果都没有,则为标识符未声明错;否则,最先查到的表项为标识符对应的属性;结束一个局部化单位时,”删除”所有CurrentNum对应的表项, 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,)(#,.)(#,.)基于外拉链散列表实现分程序结构的符号表基本思想：采用“删除式”全局符号表，符号表采用散列表实现：以标识符名字为主键，将名字作用到事先设计好的散列函数上，计算得到标识符的符号表地址。当出现重名标识符时，采用外拉链的方式化解冲突。标识符的最新定义出现在链表的头部，总会被最先查到；当分程序无效，分程序中定义的标识符也会从表中直接删除掉。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. 外拉链散列式符号表的构造过程如下：符号表的接口创建符号表删除符号表向符号表中添加表项查找某个标识符查找某个标识符的属性作业写出下列类型的内部表示. typedef struct char name10; int age; person; typedef person List10; typedef union int data; real length; char name4; 作业(2) 写出当分析下列程序时，创建符号表的过程。 (局部符号表和全局符号表(删除法和驻留法均可) typedef struct char name30; int age