国防科技大学：《编译原理》课程电子教案（PPT教学课件）第6章 属性文法和语法制导翻译

编译原理 第六章 属性文法和语法制导翻译 http://sei.nudt.edu.cn/cp 网上教学系统：070606302：编译原理

编译原理 第六章 属性文法和语法制导翻译 http://sei.nudt.edu.cn/cp 网上教学系统: 070606302: 编译原理

6.1 属性文法 属性文法（也称属性翻译文法） ☐Knuth在1968年提出 口在上下文无关文法的基础上，为每个文法 符号（终结符或非终结符）配备若干相关 的“值”（称为属性）。 ■属性代表与文法符号相关信息，如类型、 值、代码序列、符号表内容等 ■属性可以进行计算和传递 ■语义规则：对于文法的每个产生式都配备 了一组属性的计算规则 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 6.1 属性文法 ◼ 属性文法（也称属性翻译文法） Knuth在1968年提出 在上下文无关文法的基础上，为每个文法 符号（终结符或非终结符）配备若干相关 的“值”（称为属性）。 ◼属性代表与文法符号相关信息，如类型、 值、代码序列、符号表内容等 ◼属性可以进行计算和传递 ◼语义规则：对于文法的每个产生式都配备 了一组属性的计算规则

属性 口综合属性：“自下而上”传递信息 口继承属性：“自上而下”传递信息 ■在一个属性文法中，对应于每个产生式A→ 都有一套与之相关联的语义规则，每条规则的 形式为： b:=f(C1.C2...,Ck) 这里，是一个函数，而且或者 1.b是A的个综合属性并且c1,C2,,Ck是产生式 右边文法符号的属性，或者 2.b是产生式右边某个文法符号的一个继承属性 琴扇晨雅c4是A或产生武岩边任荷受摆精 并且c 属性b依赖于属性C1,C2,,Ck 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 属性 综合属性：“自下而上”传递信息 继承属性：“自上而下”传递信息 ◼ 在一个属性文法中，对应于每个产生式A→ 都有一套与之相关联的语义规则，每条规则的 形式为： b:=f(c1 ,c2 ,…,ck ) 这里，f是一个函数，而且或者 1. b是A的一个综合属性并且c1 ,c2 ,…,ck是产生式 右边文法符号的属性，或者 2. b是产生式右边某个文法符号的一个继承属性 并且c1 ,c2 ,…,ck 是A或产生式右边任何文法符 号的属性。  属性b依赖于属性c1 ,c2 ,…,ck

说明 口终结符只有综合属性，由词法分析器提供 口非终结符既可有综合属性也可有继承属性，文 法开始符号的所有继承属性作为属性计算前的 初始值 口对出现在产生式右边的继承属性和出现在产生 式左边的综合属性都必须提供一个计算规则。 属性计算规则中只能使用相应产生式中的文法 符号的属性 口出现在产生式左边的继承属性和出现在产生式 右边的综合属性不由所给的产生式的属性计算 规则进行计算，它们由其它产生式的属性规则 计算或者由属性计算器的参数提供 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 说明 终结符只有综合属性，由词法分析器提供 非终结符既可有综合属性也可有继承属性，文 法开始符号的所有继承属性作为属性计算前的 初始值 对出现在产生式右边的继承属性和出现在产生 式左边的综合属性都必须提供一个计算规则。 属性计算规则中只能使用相应产生式中的文法 符号的属性 出现在产生式左边的继承属性和出现在产生式 右边的综合属性不由所给的产生式的属性计算 规则进行计算，它们由其它产生式的属性规则 计算或者由属性计算器的参数提供

语义规则所描述的工作可以包括属性计 算、静态语义检查、符号表操作、代码 生成等等。 ■例，考虑非终结符A,B和C,其中，A 有一个继承属性a和一个综合属性b,B 有综合属性c,C有继承属性d。产生式 A→BC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c 而属性A.a和B.c在其它地方计算 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 语义规则所描述的工作可以包括属性计 算、静态语义检查、符号表操作、代码 生成等等。 ◼ 例，考虑非终结符A，B和C，其中，A 有一个继承属性a和一个综合属性b，B 有综合属性c，C有继承属性d。产生式 A→BC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c 而属性A.a和B.c在其它地方计算

产生式 语义规则 L→En print(E.val) E→E1+T E.val :E.val+T.val E→T E.val =T.val T→T1*F T.val :=T.val*F.val T→F T.val :=F.val F→(E) F.val :=E.val F→digit F.val :=digit.lexval 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 产 生 式 L→En E→E1+T E→T T→T1 *F T→F F→ (E) F→digit 语 义 规 则 print(E.val) E.val := E1 .val+T.val E.val :=T.val T.val :=T1 .val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval

■综合属性 口在语法树中，一个结点的综合属性的值由其 子结点的属性值确定。 口使用自底向上的方法在每一个结点处使用语 义规则计算综合属性的值 ■仅仅使用综合属性的属性文法称S一属性 文法 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 综合属性 在语法树中，一个结点的综合属性的值由其 子结点的属性值确定。 使用自底向上的方法在每一个结点处使用语 义规则计算综合属性的值 ◼ 仅仅使用综合属性的属性文法称S－属性 文法

产生式 语义规则 L→En print(E.val) E→E1+T E.val :E.val+T.val E-T E.val :=T.val T→T1*F T.val :=T.val*F.val T→F T.val :=F.val F→(E) F.val :=E.val F→digit F.val :=digit.lexval 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 产 生 式 L→En E→E1+T E→T T→T1 *F T→F F→ (E) F→digit 语 义 规 则 print(E.val) E.val := E1 .val+T.val E.val :=T.val T.val :=T1 .val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval

产生式 语义规则 LEn print(E.val) 3*5+4n的带注释的语法树 E→E1+T E.val :E.val+T.val E-T E.val :=T.val T→T*F T.val :=T1.val*F.val T→F T.val :=F.val F→(E) F.val :=E.val E.val-=19 n F→digit I F.val :=digit.lexval E.val-15 T.val=4 T.val=15 F.val=4 T.val=3 F.val=5 digit.lexval=4 / F.val-3 digit.lexval=5 digit.lexval=3 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 3*5+4n的带注释的语法树 digit.lexval=3 F.val=3 T.val=3 * digit.lexval=5 F.val=5 T.val=15 E.val=15 + digit.lexval=4 F.val=4 T.val=4 E.val=19 n L 产 生 式 语 义 规 则 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

■继承属性 口在语法树中，一个结点的继承属性由此结点 的父结点和/或兄弟结点的某些属性确定 口用继承属性来表示程序设计语言结构中的上 下文依赖关系很方便 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 继承属性 在语法树中，一个结点的继承属性由此结点 的父结点和/或兄弟结点的某些属性确定 用继承属性来表示程序设计语言结构中的上 下文依赖关系很方便