《编译原理课件第12讲》由会员分享，可在线阅读，更多相关《编译原理课件第12讲（52页珍藏版）》请在金锄头文库上搜索。
1、语法制导的翻译,语义分析的任务：语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作。 语义检查：如，类型、运算、维数、越界等。 语义处理：如，变量的存储分配、表达式的求值、语句的翻译（中间代码的生成）等。 总目标：生成等价的中间代码。 语义分析的主流技术：语法制导翻译技术。,静态语义分析通常包括： 类型检查。 控制流检查。控制流语句必须使控制转移到合法 的地方。 一致性检查。 相关名字检查。有时，同一名字必须出现两次或 多次。例如，Ada语言程序中，循环或程序块可 以有一个名字，出现在这些结构的开头和结尾， 编译程序必须检查这两个地方用的名字是相同的。
2、名字的作用域分析,4.1 语法制导的翻译,动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,语法制导的翻译,语法制导的翻译,语义动作的计算是在对应产生式被归约时进行。 语义规则和产生式相联系的两种方式 语法制导定义 对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。 语法制导的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。,4.1 语法制导的定义,例 简单台式计算器的语法制导定义,属性文法（也称属性翻译
3、文法） Donald Ervin Knuth在1968年提出 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等。 属性可以进行计算和传递。 语义规则：对于文法的每个产生式都配备了一组属性的计算规则。,4.1 语法制导的定义,4.1 语法制导的定义,属性：对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等。与这些属性相关的信息，即属性值，可以在语法分析过程中计算和传递。属性加工的过程即语义的处理过程。如果X是文法符号，a是它的一个
4、属性，则X.a为X的属性a的值。 语法制导的定义是带属性和规则的上下文无关文法。 在语法制导定义中的文法被称为基础文法。,语法制导的定义 根据语法分析中产生式对应语义规则进行翻译方法称语法制导翻译（定义）。 语法制导：基于语法分析中用到的文法产生式。 翻译：完成语义分析的各项功能，不仅指生成中间代码。,4.1 语法制导的定义,4.1 语法制导的定义,4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性 每个文法产生式A 有一组形式为b := f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 综合属性：如果b是A的属性
5、，c1 , c2 , , ck 是产生式右部文法符号的属性或A的其它属性。 继承属性：如果b是产生式右部某个文法符号X的属性。 以上两种情况下，都说b依赖于属性c1 , c2 , , ck 。,属性值由分析树中它的子结点属性值来计算,属性值由结点的兄弟结点及父结点的属性值来计算。,继承属性和综合属性的性质,注意 终结符号只有综合属性，他们由词法分析器提供。 非终结符号既有综合属性也可有继承属性，文法的开始符号没有继承属性，除非另外加以说明。 文法符号的综合属性集和继承属性集的交集应为空。,10/52,继承属性和综合属性的性质,对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一
6、个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。 例，考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式ABC可能有规则： C.d:=B.c+1 A.b:=A.a+B.c 而属性A.a和B.c在其它地方计算。,基础文法,语义规则b := f(c1, c2, , ck )中，函数f通常是表达式（T
7、.val=F.val）。也有一些规则写成过程调用或程序段（打印值，输出中间代码等），称为产生副作用的操作（如：print(E.val)）可看成是产生式左部非终结符的虚拟综合属性。 属性文法是指语义规则函数无副作用的语法制导定义。,属性文法,4.1 语法制导的定义,4.1.2 综合属性 S属性定义：仅仅使用综合属性的语法制导定义,4.1 语法制导的定义,8+5*2 n的注释分析树,每个结点的属性值都标注出来的分析树，称为。,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,计算各结点属性值的过程称为分析树的注释或修饰。,4.1 语法制导的定义,分析树各结点属性的计
8、算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,20/52,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上
9、地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,8+5*2 n,4.1 语法制导的定义,注释分析树:结点的属性值都标注出来的分析树,8+5*2 n,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,产 生 式 语 义 规 则 LEn print(E.val
10、) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexval,继承属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。,4.1.3 继承属性,4.1 语法制导的定义,4.1.3 继承属性 int id, id, id,30/52,4.1 语法制导的定义,int id1, id2, id3的注
11、释分析树,句子real id1，id2，id3的带注释的分析树,id1,L,id2,L,id3,L,real,T,D,T.type=real,L.in=real,L.in=real,L.in=real,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),4.1.4 属性依赖图,输入串,分析树,依赖图,语义规则计算次序,4.1.4 属性依赖图,在一棵分
12、析树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。 为每一个包含过程调用的语义规则引入一个虚拟综合属性b，这样把每一个语义规则都写成 b:=f(c1,c2,ck) 的形式。 依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。,4.1.4 属性依赖图,EE1E2 E.val:=E1.val+E2.val,E1,+,E2,E,val,val,val,4.1.4 属性依赖图,for 分析树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n
13、 do for 结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,ck ) do for i:=1 to k do 从ci结点到b结点构造一条有向边；,4.1 语法制导的定义,4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 D TL L.in := T.type,4.1 语法制导的定义,4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 L L1, id L1.in := L.in; addtype (id.entry, L.in ),句子real id1，id2，id3的带注释的分析树的依赖图,id1,L,id2,L,id3,L,
14、real,T,D,4 type,5 in,6 - addtype(id.entry, L.in),7 in,8 addtype,9 in,10 addtype,1 entry,2 entry,3 entry,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),4.1 语法制导的定义,4.1.5 属性计算次序 拓扑排序：结点的一种排序，使得边只会从该次
15、序中先出现的结点到后出现的结点。 例：1，2，3，4，5，6，7，8，9，10,40/52,依赖图的任一拓扑排序都是一个合理的属性计算顺序,4.1.5 属性计算次序,如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。,4.1.5 属性计算次序,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。 属性文法说明的翻译是很精确的 基础文法用于建立输入符号串的语法分析树； 根据语义规则建立依赖图 从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。,输入串,分析树,依赖图,语义规则计算次序,int id1, id2, id3的分析树的依赖图,a4:=int;
16、a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9);,产 生 式 语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b Xx X.d :=2*X.c Yy Y.f := Y.e*3 Zz Z.g :=Z.h+1,例 考虑属性文法G。其中，S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g,假设S.a的初始值为0，输入串为xyz,S:a=0,X,Y,Z
