《哈工大编译原理5-1.1》由会员分享，可在线阅读，更多相关《哈工大编译原理5-1.1（70页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法制导翻译,2,程序设计语言中更重要的一个方面，是附着在语言结构上的语义,语法表述的是语言的形式，或者说是语言的样子和结构,语义揭示了程序本身的涵义、施加于语言结构上的限制或者要执行的动作,“老鼠吃猫” 问题,语法正确的句子，它的语义可能存在问题,3,语义分析的任务： 检查语言结构的语义是否正确,执行所规定的语义动作,如表达式的求值、,符号表的填写、,中间代码的生成,4,语法制导翻译的基本思想：,对于文法: E E1+T E T T F F digit,digitlexval为digit的属性；,F.val、T.val、E.val为文法符号F、T、E对应的属性值,将语言结构的语义以属
2、性(attribute)的形式赋予代表此结构的文法符号，,5,当digit为常数时， digitlexval为digit在常数表中的入口,当digit为标识符时， digitlexval为digit在符号表中的入口；,F.val、T.val、E.val 可以看作是中间变量,6,E E1+T,E val := E1 val+T val,F digit,F val := digitlexval,T F,T val := F val,E T,E val := T val,而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式；,在语法分析推导或归约的每一步骤中，通过语
3、义规则实现对属性的计算，以达到对语义的处理,7,换句话说是：为每一个产生式配上语义规则并且在适当的时候执行这些规则。,即当归约（或推导）到某个产生式时，除了按照产生式进行相应的代换之外(语法分析)，,还要按照产生式所对应的语义规则执行相应的语义动作，,如计算表达式、查填符号表、产生中间代码(语义分析),8,语法制导翻译是目前最常用的语义分析技术,语法分析建立语法分析树,语义分析-遍历语法分析树,语法制导翻译-建立与遍历同时完成,9,例1 台式计算器程序的语法制导定义,产生式 语义规则,LEn print(Eval) E E1+T E val := E1 val+T val E T E val
4、:= 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 := digitlexval,3*5 +4的分析过程,12,10,3,*,F,5,T,F,E,+,T,F,4,E,T,3*5 +4的语法分析过程,11,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,3*5 +4的语义分析过
5、程,12,5.1 语法制导定义(Syntax-directed definitions),语法制导定义也叫属性文法，,通过每一 个产生式和一个语义规则集合相关联。,它是在上 下文无关文法的基础上，,通过每个文法 符号和一个属性集合相关联，,语义规则用来计算与产生式中出现的 符号相关联的属性的值 。,9,13,属性,属性可以代表任何对象：,字符串、数字、类型、内存单元或其它对象,综合属性,继承属性,14,5.1.1 属性,1b是A属性，,在一个语法制导定义中，,规则可表示为：b= f（c1，c2，,ck）,其中：f是一个函数，且满足下面两种情况之一：,c1,c2,ck是中的文 法符号的属性，,或
6、者A的其它属性，则 称b是A的综合属性；,AP 都有与之相关联的一套语义规则，,15,在两种情况下，都说属性b依赖于属性c1，c2，ck。,2c1,c2,ck是A或中的任何文法 符号的属性,则称b是中的符号的 一个继承属性。,16,5.1.2 综合属性,综合属性从下到上包括自身，其属性可从后代和自身的其它属性计算得到,S-属性定义: 只使用综合属性的语法制导定义。,利用S-属性定义进行语义分析时,结点属性值的计算正好和自底向上分析建立分析树结点同步进行。,17,例1 台式计算器程序的S-属性定义,产生式 语义规则,LEn print(Eval) E E1+T E val := E1 val+T
7、 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 := digitlexval,3*5 +4的分析过程,18,3,*,F,5,T,F,E,+,T,F,4,E,T,3*5 +4的语法分析过程,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,Eval:=15,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,n,L,19,19,d
8、igitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,20,在分析树中为每个文法符号上加上它们的属性，则称为带注释的分析树，简称注释分析树,综合属性值的计算方法,在建立每一个结点处使用语义规则来计算综合属性值，,即在 用哪个产生式进行归约后，,就执行那个产生式的s-属性定义计算属性的值，,从叶结点到根结点进行计算,对于s-属性定义，通常使用自底向上的分析方法，,21,5.1.3 继承属性 继承属性值是由此结点的父
9、结点和或兄弟结点的某些属性值来决定的。,继承属性从上到下包括兄弟，也即继承属性从前辈和兄弟的属性计算得到,22,表2 带有继承属性L.in的语法制导定义,产生式 语义规则 DTL Lin:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype(id entry,L in),23,练习：设AS为文法的综合属性集，AI为继承属性集，则下列语法制导定义中,PxQR Q.b=R.d R.c=1 R.e=Q.a,Q u Q.a=3,产生式 语义
10、规则,24,PyQR Q.b=R.f R.c=Q.a R.e=2,Rv R.d=R.c R.f=R.e,试求AS和AI,25,解：由1知：Q.b,R.eAI,整理：AS=Q.a,R.d,R.f AI=Q.b,R.c,R.e,由3知： R.cAI,由4知： R.d,R.f AS,由2知：Q.a=3AS,26,5.2 语义规则,语义规则通常有两种表现形式：,语义规则也叫语义子程序或语义动作,语法制导定义和翻译模式,27,5.2.1 语法制导定义,语法制导定义是关于语言翻译高层次规格说明，,例：下面是将中缀表达式转化为后缀表达式的文法和相应的语法制导定义,它隐藏了具体实现细节，,使用户不用显式地说明
11、翻译发生的顺序,28,产生式 语法制导定义 L E print(E.val) E E1+E2 E.val=E1.val|E2.val|+ E digit E.val=Digit.lexval,语法制导定义 只考虑“做什么”，用抽象的属性表示文法符号所代表的语义,29,翻译模式也叫翻译方案,5.2.2翻译模式,一个翻译模式是一个上下文无关文法，,其中被称为语义动作的程序段被嵌入到产生式的右部。,一个翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。,30,这是一种语法分析和语义动作交错的表示法，,翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,他表达在按深
12、度优先遍历分析树的过程中何时执行语义动作。,31,例2： 一个简单的翻译模式（中缀变后缀） ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val),32,3+5的语义翻译过程,E,R,T,Pr3,3,T,+,Pr+,5,R,Pr5,结果：35+,33,翻译方案不仅要考虑“做什么”，还要考虑“怎么做”,某种意义上说，语法制导定义类似于算法，而翻译方案更象程序,34,带有继承属性L.in的翻译方案,DT Lin:=T type L T int T type :=integer T real T type :=real L L1 in :=L i
13、n L1,idaddtype(id entry,L in) L id addtype(id entry,L in) ,例5 . 3 变量说明的类型定义 int a,b,c,35,D,L.in=t.type,L,real,L1.in=L.in,id3,L1.in=L.in,id2,id1,句子real id1,id2,id3的带继承属性的分析树,T,T.type=real,L,L,Add(L.in),Add(L.in),Add(L.in),36,例：文法G的产生式如下： S（L） S a L L,S L S 1.试写出一个语法制导定义，输出配对括号个数 2.写一个翻译方案，打印每个a的嵌套深度,
14、37,解：1.为S，L引入属性h 产生式 语法制导定义 S（L） S.h=L.h+1 S a S.h=0 L L1,S L.h=L1.h+S.h L S L.h=s.h S S print(S.h),38,(,a,S,S.h=0,L,(,a,L.h=0,S,S.h=0,L,L.h=0,),S,S.h=1,L,L.h=1,),S,S.h=2,(a,(a)的分析过程,39,2.为S，L引入属性d,翻译方案如下 S S.d=0 S S（ L.d=S.d+1 L） S a print(s.d) L L1.d=L.d L1, S.d=L.dS L S.d=L.d S,40,S,S.h=0,S,(,L.d=1,L,),L.d=1,L,S.d=1,S,S.d=1,S,Print(1),a,(,L.d=2,L,),S.d=2,S,Print(2),a,
