当前位置 博文首页 > kbtx的博客:编译原理-第五章-语义分析之属性文法、属性计算
属性文法,也称属性翻译文法
Knuth在1968年提出
以上下文无关文法为基础
产生式 | 语义规则 |
---|---|
L→En | print(E.val) |
E→E1+T | E.val := E1.val + T.val |
E → T | E.val := T.val |
T→T1*F | T.val := T1.val*F.val |
T→F | T.val := F.val |
F→(E) | F.val := E.val |
F→digit | F.val := digit.lexval |
每一个产生式可配备一条或多条语义规则,这些语义规则说明了每一个产生式所涉及的语法单位之间的语义关系,通过属性计算表达。
产生式 | 语义规则 |
---|---|
D→TL | L.in := T.type |
T → int | T.type := integer |
T → real | T.type := real |
T→T1*F | T.val := T1.val*F.val |
L → L1,id | L1.in := L.in addtype(id.entry, L.in) |
L → id | addtype(id.entry, L.in) |
对于 L → L1,id,其对应的第一条语义规则 L1.in := L.in 说明 (产生式右侧的) L1的继承属性由(产生式左侧的) L 的继承属性得到;其对应的第二条语义规则 addtype(id.entry, L.in) 调用了addtype函数,实现在符号表中找到 id 在符号表的入口,并将入口的类型信息设置为 L.in 的值。 可以认为(左部的)L有一个虚拟的综合属性 L.s 用于接收该函数的返回值。
对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。
如产生式 L → L1,id对应的语义规则 L1.in := L.in 提供了对出现在产生式右面的 L1的继承属性 L1.in的计算规则
如产生式 E → T对应的语义规则 E.val:=T.val 提供了对出现在产生式左面的 E 的综合属性 E.val 的计算规则
对出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算,由其它产生式的属性规则计算或者由属性计算器的参数提供
如产生式 L → id 对应的语义规则addtype(id.entry, L.in)中 用到了产生式左边的L的继承属性 L.in ,这个语义规则只能使用 L.in 但不能定义如何计算, L.in 的计算应当由其他规则定义
如产生式 D → TL 对应的语义规则 L.in := T.type中 用到了产生式右边的T的综合属性 T.type,这条语义规则同样只能使用T.type而不能定义如何计算。
语义规则所描述的工作可以是任何能用函数调用表示的过程,包括属性计算、静态语义检查、符号表操作、代码生成等。
语法树描述了语法构成单位之间的层次关系,是一种层次结构。
对语法树进行拓广,为每一个节点标上属性,可以得到带(属性)注释的语法树:
例如
产生式 | 语义规则 |
---|---|
D→TL | L.in := T.type |
T → int | T.type := integer |
T → real | T.type := real |
T→T1*F | T.val := T1.val*F.val |
L → L1,id | L1.in := L.in addtype(id.entry, L.in) |
L → id | addtype(id.entry, L.in) |
请点击小标题打开视频观看
基于属性文法的处理方法
通过寻找属性之间的依赖关系,来确定属性计算的先后顺序,选择相应的语义规则,完成语义计算。
//第一遍循环
for (结点 n : 语法树){
for(文法符号属性 a : n){
在依赖图中为a建立结点;
}
}
//第二遍循环
for (结点 n : 语法树){
for(语义规则 b : n){
//语义规则的形式为 b := f(c1,c2,...,ck)
//ci为b所依赖的属性
for(依赖属性 c: b){
构造从 c 指向 b 的有向边;
}
}
}
产生式 | 语义规则 |
---|---|
D→TL | L.in := T.type |
T → int | T.type := integer |
T → real | T.type := real |
T→T1*F | T.val := T1.val*F.val |
L → L1,id | L1.in := L.in addtype(id.entry, L.in) |
L → id | addtype(id.entry, L.in) |
语句 real id1,id2,id3
的依赖图可以画成:
注意⑦⑨⑩是虚拟结点
通过树遍历的方法计算属性的值
while(还有未被计算的属性){
VisitNode(S);//S 是开始符号
}
//从根节点开始递归计算属性
void VisitNode(Node N){
if(N是非终结符){
//N的继承属性应该已经被计算出或者由编译器提供
//假定当前产生式是 N-> X1 X2 ... Xm,共m项
for(int i=1;i<=m;i++){
if(Xi 是非结符){
计算Xi 中能够计算的继承属性;
VisitNode(Xi);
计算Xi 中能够计算的综合属性;
}
}
计算N中能够计算的综合属性;
}
}
反复调用VisitNode(S)直到所有继承属性和综合属性都能被计算出来或者不再有更多的属性可以被计算为止。
第一次调用可以计算出Z.h=0
和Z.g=1
第二次调用可以计算出X.c=1
、X.d=2
和S.b=0
第三次调用可以计算出Y.e=0
和Y.f=0
请直接观看视频。
抽象语法树(Abstract Syntax Tree,AST),在语法树中去掉那些对翻译不必要的信息,从而获得更有效的源程序中间表示
3*5+4:
函数声明 | 作用 |
---|---|
mknode(op, left, right) | 建立一个运算符号结点,标号是op, 两个域left和right分别指向左子树和右子树 |
mkleaf(id, entry) | 建立一个标识符结点,标号为id, 一个域entry指向标识符在符号表中的入口 |
mkleaf(num, val) | 建立一个数结点,标号为num, 一个域val用于存放数的值 |
运用以上函数,可以写出以下产生式的语义规则:
产 生 式 | 语 义 规 则 |
---|---|
E→E1+T | E.nptr := mknode(‘+’, E1.nptr, T.nptr ) 注意:此时我们认为E1和T已经被构建成了某一语法子树的根节点 |
E→E1-T | E.nptr := mknode(‘-’, E1.nptr, T.nptr ) |
E→T | E.nptr := T.nptr |
T→ (E) | T.nptr := E.nptr 括号对于计算是多余的 |
T→id | T.nptr := mkleaf ( id, id.entry ) |
T→num | T.nptr := mkleaf ( num, num.val ) |
显然这种抽象语法树特别适合于自下而上的属性计算。
a - 4 + c
对应的抽象语法树如下:
由于考试不考 复习时间有限,后续内容不再做记录,请自行寻找国防科技大学编译原理公开课进行观看。