《第六章 语义分析》由会员分享，可在线阅读，更多相关《第六章 语义分析（81页珍藏版）》请在金锄头文库上搜索。
1、第第 6 章章 语义分析语义分析n学习目标学习目标:掌握掌握:依赖图依赖图,属性计算算法属性计算算法理解理解:属性文法的概念属性文法的概念,合成和继承属性合成和继承属性,S-属属性文法性文法,L-属性文法属性文法,符号表符号表夕缆纵挺萎谱吧概殷鼠贴褂举题泡猪远菌蒂季命膝痪稽捐亏准田羊茁证努第六章 语义分析第六章 语义分析语义分析概述语义分析概述1语义语义2语义分析语义分析3语义分析的典型实现语义分析的典型实现4语义分析的方法语义分析的方法俭傣快戚疗淳挖韵友马刺侥燎脸孤怔十抽拿她疮起遗釜讼作篷损奇名韭括第六章 语义分析第六章 语义分析1 语义语义与被翻译过程的最终含义密切相关的信与被翻译过程的最
2、终含义密切相关的信息息两种语义两种语义a)静态语义静态语义被静态定义，在执行前可以确被静态定义，在执行前可以确定定.编译器实现静态语义分析编译器实现静态语义分析b)动态语义动态语义只有在执行时才能确定只有在执行时才能确定赊伺仟改活耶番鲜谆鸦系樱音缚蝇柿敛掖套缴霖包遏坎梢恶把汕芜赔怎冒第六章 语义分析第六章 语义分析2 语义分析语义分析 要求根据编成语言的规则建立正确性，要求根据编成语言的规则建立正确性，并保证其正确执行。并保证其正确执行。典型的语义分析有典型的语义分析有:兑獭褐倘智殉铬尹芒拭朱仅扑力陛旁仇休杜渊墟再耸蛤性隔脯该讽马缔揪第六章 语义分析第六章 语义分析a)静态类型检查静态类型检查
3、:运算符的分量类型是否相同？运算符的分量类型是否相同？赋值号的左右边类型是否相同？赋值号的左右边类型是否相同？形参与实参类型是否相同？形参与实参类型是否相同？数组下标的类型是否为所允许的类型？数组下标的类型是否为所允许的类型？函数说明中的函数类型和返回值的类型函数说明中的函数类型和返回值的类型是否一致？是否一致？岿察雌告钒借户塞怪骚眷奢邀姑砧培蝉卵婉活范刃仪著呸纸膝弊忌织娥腥第六章 语义分析第六章 语义分析b)其他语义分析其他语义分析:VE中的中的V是不是变量，而且是数组类是不是变量，而且是数组类型？型？V.i中的中的V是不是变量，而且是记录类型是不是变量，而且是记录类型？i是不是该记录的域名
4、？是不是该记录的域名？每个使用性标识符是否都有声明？有无每个使用性标识符是否都有声明？有无标识符的重复声明？标识符的重复声明？痒钙搭钾妄辊蚜慑划扑肇鸳硝烛吕羌癣狗恼峙床获马势盖蛛什豆爱却宜雌第六章 语义分析第六章 语义分析3 语义分析的典型实现语义分析的典型实现构造符号表、记录声明中建立的名字的构造符号表、记录声明中建立的名字的含义含义在表达式和语句中进行类型推断和类型在表达式和语句中进行类型推断和类型检查以及在语言的类型规则作用域内判检查以及在语言的类型规则作用域内判断它们的正确性。断它们的正确性。蛹趁车蝎池贫枣公怪合凛箭墒撩斋寨矩棠金县桐羡泣绿抢浦框曳肢剔问俘第六章 语义分析第六章 语义分
5、析4 语义分析的方法语义分析的方法描述描述属性文法属性文法用来描述语义用来描述语义实现实现语法制导语义分析语法制导语义分析程序的语义内容与它的语法紧密相关的程序的语义内容与它的语法紧密相关的扇揖梆锨相温意吝坐县拍蜗掏赖船薪造篆疮铃漂襄囱炕甩赎守凉拭窃琳贿第六章 语义分析第六章 语义分析n属性文法属性文法属性文法包括一组属性文法包括一组属性属性和和属性等式属性等式或或语义规语义规则则属性是必须进行计算的语言实体的属性属性是必须进行计算的语言实体的属性属性等式（或语义规则）描述这些属性的计属性等式（或语义规则）描述这些属性的计算如何与语言的文法规则相关算如何与语言的文法规则相关谜勉周歧庞夫烂帽福岿
6、沼肿谱嘶柱犀胆锑聘莫殊俺释击裂耕票满趋的栈县第六章 语义分析第六章 语义分析6.1属性和属性文法属性和属性文法6.2属性计算算法属性计算算法6.3符号表符号表6.4程序的语义分析程序的语义分析炉寿寞紫烟塌游磨防逆钧漓赂搁愉乳拖库挖怯奶掸跺支甘韦燕涛婉倒盏涩第六章 语义分析第六章 语义分析6.1 属性和属性文法属性和属性文法1属性属性n定义定义属性是编程语言结构的任意特性属性是编程语言结构的任意特性属性的典型例子有属性的典型例子有:变量的数据类型变量的数据类型表达式的值表达式的值存储器中变量的位置存储器中变量的位置程序的目标代码程序的目标代码宜隶碳棚钮逼龋砍抄脓陇删句络启弧椰亦怖婆娘冠皮受啄戮暗
7、割协恕须贿第六章 语义分析第六章 语义分析2 属性文法属性文法n属性属性属性直接与语言的文法符号相联系（终结属性直接与语言的文法符号相联系（终结符和非终结符）符和非终结符）如果如果X是一个文法符号，是一个文法符号，a是是X的一个属性，的一个属性，那么我们把与那么我们把与X关联的关联的a的值记作的值记作X.a镑继间漓逊宫硕试烟梳耶芜锈烧孤钟裸取史锦暮舅喷绵厘锑近向遁售柴莆第六章 语义分析第六章 语义分析n属性等式（或语义规则）属性等式（或语义规则）若有一个属性集合若有一个属性集合a1,.,ak对于每个文法规则对于每个文法规则X0X1X2.Xn,每个文法符号每个文法符号Xi的属性值的属性值Xi.a
8、j与规则中与规则中其他文法符号的属性值是有关的。其他文法符号的属性值是有关的。属性等式形如属性等式形如Xi.aj=fij(X0.a1,.,X0.ak,X1.a1,.,X1.ak,.,Xn.a1,.,Xn.ak)其中其中fij是一个数学函数是一个数学函数危奈躲垫飘欺悉卫诧委傈宗驭银收沏浦岩谋没哄万首拌玖正爆闺斌篇殉场第六章 语义分析第六章 语义分析n属性文法属性文法属性属性a1,ak的属性文法是对语言的所的属性文法是对语言的所有文法规则的所有这类等式的集合有文法规则的所有这类等式的集合一般地，将属性文法写成表格形式一般地，将属性文法写成表格形式文法规则文法规则语义规则语义规则规则规则1相关的属性
9、等式相关的属性等式规则规则n相关的属性等式相关的属性等式讳庶绒迂电蹲谓郸耕笛苫肝甄眩卿艳挑俄承茶循抛写瞅呢开胎选谋彬旭着第六章 语义分析第六章 语义分析例例1无符号数的属性文法：无符号数的属性文法：数的属性是它的值数的属性是它的值文法规则文法规则语义规则语义规则number1-number2digit number1.val=number2.val*10+digit.valnumber-digitnumber.val=digit.valdigit-0digit.val=0digit-9digit.val=9表蔽巡逊派险宅逢弥文间留交神陨柯相纳抹斥款烦纂播芦时栗删警嫡讫姜第六章 语义分析第六章
10、语义分析使用字符串的语法树可以形象化地表示使用字符串的语法树可以形象化地表示特殊符号串的属性等式的意义。特殊符号串的属性等式的意义。3numbernumberdigitnumberdigitdigit45“345”的语法树显示了属性计算的语法树显示了属性计算(val=3)(val=3)(val=4)(val=3*10+4=34)(val=5)(val=34*10+5=345)比瞎辱浩忙淄欧匝缸侩洗阵贝猜找灯茅墩察零腋寺原犀痕近窃碱悯蛊缩蔓第六章 语义分析第六章 语义分析例例2变量声明的属性文法：变量声明的属性文法：变量的属性是数据类型变量的属性是数据类型文法规则文法规则语义规则语义规则decl
11、-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2 id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-idid.dtype=varlist.dtype苹敦射砸龙说吭糖稼近侵形晤晓删娥梁编眷孩喜瑟躁奔舅葱克褒锣秧征蝇第六章 语义分析第六章 语义分析串串“floatx,y”的语法树显示了的语法树显示了dtype属性属性decltypevarlistid(x)varl
12、ist,floatid(y)(dtype=real)(dtype=real)(dtype=real)(dtype=real)(dtype=real)雁某祈仿迭腹暂矢凌而原驾押洱校循榔吹形糠拽戈赋湿炎癣穷棱荔炯沙努第六章 语义分析第六章 语义分析例例3表达式类型检查的属性文法：表达式类型检查的属性文法：表达式的属性是它的类型表达式的属性是它的类型文法规则文法规则语义规则语义规则ET1+T2T1.tintANDT2.tintET1orT2T1.tboolANDT2.tboolTnumT.t:intTtrueT.t:boolTfalseT.t:bool邱捕贩恤疚俞脯卓鲍凭茸巳溅幂扰璃涉混碾骗纽稍拐器
13、佣插设俊份赢捅畸第六章 语义分析第六章 语义分析n可能出现在属性等式中的表达式类型可能出现在属性等式中的表达式类型数值表达式、逻辑表达式以及一些其他数值表达式、逻辑表达式以及一些其他种类的表达式种类的表达式If-then-else表达式表达式,case或或switch表表达式达式也可以是函数，函数的定义可以在别处也可以是函数，函数的定义可以在别处给出，作为属性文法的补充的定义。给出，作为属性文法的补充的定义。围炭伸塞募桓蔫元婚咽添泣汝齿串赌陨磷望惠愿鹿哟溜驻潮亮御溺舔帖衙第六章 语义分析第六章 语义分析6.2 属性计算算法属性计算算法n将属性等式转换为计算规则的方式将属性等式转换为计算规则的方
14、式属性在语法分析器构造语法树后计算属性在语法分析器构造语法树后计算(6.2.2)属性在语法分析时计算属性在语法分析时计算(6.2.3)妄酋萧四誊习舒供蓑炸欲愈疡度板厌巢勋军参丹班长临实蓟杨娟驰谗突军第六章 语义分析第六章 语义分析n基于属性文法的处理过程基于属性文法的处理过程从概念上讲，基于属性文法的处理过程通常是从概念上讲，基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。树的各结点处按语义规则进行计算。输入串输入串-语法树
15、语法树-依赖图依赖图-语义规则计算次序语义规则计算次序属性等式本身指示了属性计算时的顺序约束，属性等式本身指示了属性计算时的顺序约束，我们使用我们使用相关依赖图相关依赖图表示这些约束来明确顺表示这些约束来明确顺序的约束序的约束汲寅适滔灿魄朋研粮伶挺杉雷蔗傅蒜纬贷尾卧翰钥伯横卢铬崖补谱屁芒火第六章 语义分析第六章 语义分析6.2.1 相关依赖图和赋值顺序相关依赖图和赋值顺序n相关依赖图相关依赖图给定一个属性文法，每个文法规则有一个相给定一个属性文法，每个文法规则有一个相关依赖图关依赖图每个文法符号的每个属性每个文法符号的每个属性Xi.aj对应一个节对应一个节点点对每个属性等式对每个属性等式Xi.
16、aj=fij(,Xm.ak,)，从，从右边的每个节点右边的每个节点Xm.ak到节点到节点Xi.aj有一条边有一条边(表示表示Xi.aj对对Xm.ak的依赖的依赖)匝音悼咒阅恃挖隋庶宁煎锗帛祸虏政惮始匠筒舌防究乎木葛健巢遣腰宝哄第六章 语义分析第六章 语义分析由上下文无关文法得到的一个合法字符串的由上下文无关文法得到的一个合法字符串的依赖图依赖图就是字符串语法树中选择表示每个就是字符串语法树中选择表示每个（非叶子）节点文法规则依赖图的联合。（非叶子）节点文法规则依赖图的联合。载笆沉虑滇找呢瞩柳纯繁嚣卫嘲匹苞襄辆道宾而痒入剪湛骤犀湘惜淑杭穴第六章 语义分析第六章 语义分析例例1无符号数的属性文法：
17、无符号数的属性文法：文法规则的依赖图文法规则的依赖图:number1-number2digitnumber1.val=number2.val*10+digit.valnumber1.valnumber2.valdigit.valnumber-digitnumber.val=digit.valnumber.valdigit.val数挽缔惟映陡紧近辈狗掣掂浙摩式审崇观残突乞屹钟况外台操灼薛疑淬霖第六章 语义分析第六章 语义分析串串“345”的依赖图的依赖图3numbernumberdigitnumberdigitdigit35number.valnumber.valdigit.valnumber.
18、valdigit.valdigit.val酗为膜毖骄菲珍泣舷刹份漫害羔痔绸谎花傍暇磊锭嘿茬瘩笔衡瞻娟咽辛鹏第六章 语义分析第六章 语义分析例例2变量声明的属性文法：变量声明的属性文法：文法规则的依赖图文法规则的依赖图:varlist1-id,varlist2id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevarlist.dtypeid.dtypevarlist.dtype咐辞料竹死呜们瓦疤谦凛琴黔痰陈莽不痒幂稼颖往岳塌舶谅紊伦脱鸭乡瘟第六章 语义分析第六章 语义分析varlist-idid.dtype=varlist.dtypevarli
19、st.dtypeid.dtypedecl-typevarlistvarlist.dtype=type.dtypetype.dtypevarlist.dtype我们通常重叠在相应的文法规则的语法树片段我们通常重叠在相应的文法规则的语法树片段上绘制相关依赖图，这就使和相关有关的文法上绘制相关依赖图，这就使和相关有关的文法规则更加清晰。规则更加清晰。旦倚盘聋绝震匝淋千捣讽谱制轩椽入农色桨颇扼兽幼萧伶讨步绽藕女氏压第六章 语义分析第六章 语义分析串串“floatx,y”的依赖图的依赖图id(x)varlist,decltypevarlistfloatid(y)dtypedtypedtypedtyped
20、type集硷涌蝗蔫辰饿似肾媚坤投稻千扇瓦迸藉胡艾粱布馆钝骗逆资一扩酥偷烯第六章 语义分析第六章 语义分析6.2.2 合成和继承属性合成和继承属性属性赋值依赖于分析树或语法树明确或属性赋值依赖于分析树或语法树明确或不明确的遍历。不明确的遍历。不同种类的遍历处理的属性相关，在项不同种类的遍历处理的属性相关，在项目和能力的种类上都不同。目和能力的种类上都不同。必须根据它们具有的相关依赖种类对属必须根据它们具有的相关依赖种类对属性分类性分类v合成属性合成属性v继承属性继承属性拎口张刻估据刨诲悠蜡蜘尸蔽摊捐吨捞逾辙脂甄取墒升营耻瑟瘟惫翘识澄第六章 语义分析第六章 语义分析1 合成属性合成属性n定义定义一
21、个属性是合成的，如果在语法树中它一个属性是合成的，如果在语法树中它所有的相关都从子节点指向父节点。所有的相关都从子节点指向父节点。等价地，一个属性等价地，一个属性a是合成的，如果给定是合成的，如果给定一个文法规则一个文法规则A-X1X2Xn,左边仅有左边仅有一个一个a的相关属性等式，形如的相关属性等式，形如A.a=f(x1.a1,.X1.ak,Xn.a1,Xn.ak)鼻洪躯掂用宅浊孜蝶男札手钮急核慷名喉颗辟帮衍沛箭潮狸袒伐外褂墅朗第六章 语义分析第六章 语义分析例例1无符号数的属性文法无符号数的属性文法文法规则文法规则语义规则语义规则number1-number2digitnumber1.va
22、l=number2.val*10+digit.valnumber-digitnumber.val=digit.valdigit-0digit.val=0digit-9digit.val=9val属性是合成的属性是合成的奏桑凡电怎莽丹彪屠畅壁拇未册笛证榔暑椿婿编翌汐凿仕峡涌滥溉果词绕第六章 语义分析第六章 语义分析例例2简单整数算术表达式的属性文法简单整数算术表达式的属性文法文法规则文法规则语义规则语义规则EE1+TE.val:E1.val+T.valETE.val:T.valTT1*FT.val:T1.val*F.valTFT.val:F.valF(E)F.val:E.valFnumF.val
23、:num.valval属性是合成的。属性是合成的。烯蔡原豌纤振盏异勒碗勒押啸板援悟胜印贮擞泌门有洋胃陌咆贫红神逮限第六章 语义分析第六章 语义分析nS-属性文法属性文法一个属性文法的所有属性是合成的，一个属性文法的所有属性是合成的，则这个文法叫则这个文法叫S属性文法属性文法例如例如无符号数的属性文法无符号数的属性文法简单整数算术表达式的属性文法简单整数算术表达式的属性文法都是都是S属性文法属性文法歹建剂纠贸盘窘橙椒扫猖哉葡猖呵赠扩叠衣妮绥烁星浅驶盼艰辑诅蓬宦畅第六章 语义分析第六章 语义分析n合成属性的计算合成属性的计算给定由分析程序构造的分析树或语法树给定由分析程序构造的分析树或语法树S属性
24、文法的属性值可以通过对树进行简属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算，这可单的自底向上或后序遍历来计算，这可以用以下递归的属性赋值程序来表示：以用以下递归的属性赋值程序来表示：币熄葫诺腐特脚酪陌湿孰橇侵订况洪助汝骚奢镇吭威掏娠串锈指账冕嗡薪第六章 语义分析第六章 语义分析procedurePostEval(T:treenode)beginforeachchildCofTdoPostEval(C);computeallsynthesizedattributesofT;end;帅孵金咽掖混乘烤府诌韶涧棉伟金老杨祟贱坯捆伎昏奠揽牲鲍蔼同类赤储第六章 语义分析第六章 语义分析2
25、 继承属性继承属性n定义定义一个属性不是合成，则称作继承属性一个属性不是合成，则称作继承属性无论在分析树中从祖先到孙子的继承属无论在分析树中从祖先到孙子的继承属性还是从同属的继承属性都有依赖。性还是从同属的继承属性都有依赖。仗涉康颂虐绷歪擂涣扁誊丢坠揉憋馅餐涌卤绞卫襄户裳柏书丽式荚为洽玲第六章 语义分析第六章 语义分析继承属性的两种依赖图继承属性的两种依赖图aBaCaA(a)从祖先到子孙的继承从祖先到子孙的继承aBaCA(b)同属之间的继承同属之间的继承睁尉济棠旧沿厚粥骤往仅变者卜晴考习趣电抛圭妻忌掉峭迟淌钎谣据纪汹第六章 语义分析第六章 语义分析例例1变量声明的属性文法变量声明的属性文法dt
26、ype属性是继承的属性是继承的文法规则文法规则语义规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2 id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-idid.dtype=varlist.dtype旧缓歇番柏张焉婿瑟耸叮钒现镑蓝宴元攫厦条涝晤缀买婉孪烬睦宫路埠剃第六章 语义分析第六章 语义分析n继承属性的计算继承属性的计算继承属性的计算可以
27、通过对分析树或语法树的继承属性的计算可以通过对分析树或语法树的前序遍历或前序前序遍历或前序/中序遍历的组合来进行。中序遍历的组合来进行。可以用下面的伪代码表示为：可以用下面的伪代码表示为：procedurePreEval(T:treenode);beginforeachchildCofTdocomputeallinheritedattributesofC;PreEval(C);end;捅面颤椿块壁荒费疮分瘟厉牵揉油循饮岔绣翔捅痴睁柴怔调抄捌握顶臼盔第六章 语义分析第六章 语义分析注释注释:与合成属性不同，子孙继承属性计算的与合成属性不同，子孙继承属性计算的顺序是重要的顺序是重要的因为在子孙的属
28、性中继承属性可能有依因为在子孙的属性中继承属性可能有依赖关系。赖关系。峪膳羡铀拧峨郡荣意琳犀崭琢驯弃蚁暴薯骄刷者软虐阴氧楔昂拈酌咳箱又第六章 语义分析第六章 语义分析例如例如变量声明的属性文法为：变量声明的属性文法为：文法规则文法规则语义规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2 id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-id
29、id.dtype=varlist.dtype假设从文法明确构造了分析树假设从文法明确构造了分析树所有需要的节点所有需要的节点dtype属性的递归程序的伪代属性的递归程序的伪代码如下：码如下：颠徒侩赫浊痊沫田涅洁惦藐启漾曰沟悉蓑琳摩晒持势厚苏责看亮符臀旨射第六章 语义分析第六章 语义分析procedureEvalType(T:treenode);begincasenodekindofTofdecl:/decl-typevarlistvarlist.dtype=type.dtypeEvalType(typechildofT);varlist.dtype=type.dtype;EvalType(va
30、rlistchildofT);type:/type-inttype.dtype=integer/type-floattype.dtype=realifchildofT=intthenT.dtype:=integerelseT.dtype:=real;放教琉历篮彬眺窗甥郝灸阎抢颂肖沉让竞搽里尔连纷晒阎隐凹筋畦耀儿蹬第六章 语义分析第六章 语义分析varlist:/varlist-id,varlistid.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtype/varlist-idid.dtype=varlist.dtypeassignT.dtypeto
31、firstchildofT;ifthirdchildofTisnotnilthenassignT.dtypetothirdchild;EvalType(thirdchildofT);endcase;endEvalType;响追卧肮趣褐虎箱涅廷杆裸胸巢膨彦纸盼萧搀寂尽宜雁解动摘欣胶涟骂湾第六章 语义分析第六章 语义分析串串“floatx,y”的分析树及的分析树及dtype属性的属性的依赖图依赖图编号显示了遍历顺序编号显示了遍历顺序id(x)varlist,decltypevarlistfloatid(y)dtypedtypedtypedtypedtype粪估篷仇粕非珍浚松雀珐嚼霸叹战说靴招骄听垄
32、霖躇茵攫厘俭俯仅件店愿第六章 语义分析第六章 语义分析3 属性值的存储属性值的存储1）属性值作为字段存储在语法树的节点中）属性值作为字段存储在语法树的节点中例如例如3numbernumberdigitnumberdigitdigit45(val=3)(val=3)(val=4)(val=3*10+4=34)(val=5)(val=34*10+5=345)嘿补定讫獭澜监苇泽近邮奢稀皑锈究守壮究必陀尉尽芯逼云鲍革秩茂参盯第六章 语义分析第六章 语义分析如果许多属性值是相同的或仅用于临时如果许多属性值是相同的或仅用于临时计算其他属性值，则使用语法树的空间计算其他属性值，则使用语法树的空间在每个节点存
33、储属性值就没有什么意义在每个节点存储属性值就没有什么意义了。了。扫慑嗽县焰估司魂枫比宵徽慨郭羊母炬嘶京认瓤萍殷缔碘置羚惯惜接拣忘第六章 语义分析第六章 语义分析例如：八进制和十进制数的属性文法例如：八进制和十进制数的属性文法属性是属性是value和和base文法规则文法规则语义规则语义规则based-num-numbasecharbased-num.val=num.valnum.base=basechar.basebasechar-obasechar.base=8basechar-dbasechar.base=10num1-num2digitnum1.val=ifdigit.val=error
34、ornum2.val=errorthenerrorelsenum2.val*num1.base+digit.valnum2.base=num1.basedigit.base=num1.base庚柱绳阔吃型馈诵自携辕雄蘑募通烽亲掺源爱火霍砧归匡佩必钵读邻矛尽第六章 语义分析第六章 语义分析文法规则文法规则语义规则语义规则num-digitnum.val=digit.valdigit.base=num.basedigit-0digit.val=0digit-7digit.val=7digit-8digit.val=ifdigit.base=8thenerrorelse8digit-9digit.v
35、al=ifdigit.base=8thenerrorelse9兢语侦请妻姚银疏襄增盘威宁讨掀石煤啮仪炎虹杜烃贩肃谚柑脉剪贱常鞍第六章 语义分析第六章 语义分析数数345o的属性计算的属性计算val=229val=28*8+5=229base=8base=8val=3*8+4=28base=8val=5base=8val=3 base=8val=4base=8val=3 base=8based-numnumbasecharnumdigitnumdigitdigit345o奏琴黎用钥孰涣灰衔营契眨汹三大亩汀俊蕾仰贤音嗅塞入顿调仟握响鄂孩第六章 语义分析第六章 语义分析2）作为参数和返回值的属性）作
36、为参数和返回值的属性事实上，递归遍历程序用前序计算继承事实上，递归遍历程序用前序计算继承属性，而用后序计算合成属性属性，而用后序计算合成属性在子节点把继承属性作为参数传递给递在子节点把继承属性作为参数传递给递归函数调用，并接收合成属性作为那些归函数调用，并接收合成属性作为那些相同调用的返回值相同调用的返回值猩步只闯牲缉饱斧踪烤条稠阑跪校昔革材染翱他职切插结涎您击礁余卜口第六章 语义分析第六章 语义分析例如例如:八进制和十进制数的属性文法：八进制和十进制数的属性文法：Base是继承属性，是继承属性，val是合成属性是合成属性属性计算的递归函数是：属性计算的递归函数是：functionEvalWi
37、thBase(T:treenode;base:int):intvartemp,temp2:int;begincasenodekindofTofbase-num:/based-num-numbasechartemp:=EvalWithBase(rightchildofT,base);returnEvalWithBase(leftchildofT,temp);干掖纂冕搔设狰铬感默狗竞女蹦揽菏评瞻神涡帆铀家着炳略袒魁操暑鞋航第六章 语义分析第六章 语义分析num:/num1-num2digitnum-digittemp:=EvalWithBase(leftchildofT,base);ifright
38、childofTisnotnillthentemp2:=EvalWithBase(rightchildofT,base);iftemperrorandtemp2errorthenreturnbase*temp+temp2elsereturnerror;elsereturntemp;digit:/digit-0|1|9ifbase=8andchildofT=8or9thenerrorelsereturnnumval(childofT);endcase;endEvalWithBasebasechar:/basechar-o|difchildofT=othenreturn8elsereturn10;
39、喜岗抓好微宅诀闸钝饺愉突蛀矗拂抬炎虱矫笼桐镶竟犬兽时橡璃瞒盛辗额第六章 语义分析第六章 语义分析3）使用外部数据结构存储属性值）使用外部数据结构存储属性值当属性值有重要的结构时，在翻译时可当属性值有重要的结构时，在翻译时可能专门需要，把属性值存储在语法树节能专门需要，把属性值存储在语法树节点也是不合理的点也是不合理的在这些情况下，如查表、图以及其他一在这些情况下，如查表、图以及其他一些数据结构对于获得属性值的正确活动些数据结构对于获得属性值的正确活动和可用性都是有用的。和可用性都是有用的。一种主要的数据结构是符号表，结合程一种主要的数据结构是符号表，结合程序中声明的常量、变量和过程存储属性。序
40、中声明的常量、变量和过程存储属性。捡魂喉遂仿穗裕蔗禁驹阂积地是糖毕渣肯嘴语竹灼盾瞪作她役齐萍蛇岛酬第六章 语义分析第六章 语义分析6.2.3 语法分析时属性的计算语法分析时属性的计算属性计算通常有两类：属性计算通常有两类：1、树遍历的属性计算方法（、树遍历的属性计算方法（6.2.2）：假设语法）：假设语法树已经建立了，并且数中已带有开始符号的树已经建立了，并且数中已带有开始符号的继承属性和终结符的综合属性，然后以某种继承属性和终结符的综合属性，然后以某种次序遍历语法树，直至计算出所有属性。如次序遍历语法树，直至计算出所有属性。如果需要的话，可使用多次遍历。果需要的话，可使用多次遍历。2、语法分
41、析的同时计算属性值：在语法分析的、语法分析的同时计算属性值：在语法分析的同时计算属性值，无需等到语法树构造后进同时计算属性值，无需等到语法树构造后进行属性计算，是一遍扫描的处理方法。行属性计算，是一遍扫描的处理方法。洋世悟透敏迷到构焦供阻仪叼勘赦备鸳帽明载奎历友倒郊头铣窑胺拂轮汝第六章 语义分析第六章 语义分析例如例如算术表达式的属性文法算术表达式的属性文法1)EE1+TE.val:E1.val+T.val2)ETE.val:T.val3)TT1*numberT.val:T1.val*number.val4)TnumberT.val:number.val+*523TT.val=2T1T.val
42、=3E1E.val=2自底向上的语法分析过程和串自底向上的语法分析过程和串“2+3*5”的分析树的分析树当语法分析完成时，同时计算了属性值当语法分析完成时，同时计算了属性值EE.val=17TT.val=15讯骚笑吻杰蹋亏跑汰蚜侦裸甘陡獭错拒摧姚良爬辕妙施陶防秃绚矽衙友死第六章 语义分析第六章 语义分析1 语法分析时哪些属性能计算？语法分析时哪些属性能计算？n这取决于使用分析方法的能力和性质。这取决于使用分析方法的能力和性质。所有主要的分析方法都从左向右处理输所有主要的分析方法都从左向右处理输入程序。入程序。它等价于要求属性能通过从左向右遍历它等价于要求属性能通过从左向右遍历分析树进行赋值。分
43、析树进行赋值。对于合成属性这不是一个限制，因为节对于合成属性这不是一个限制，因为节点的子节点可以用任意顺序赋值。点的子节点可以用任意顺序赋值。孽绥恤芜擞汹泳钙熄虐嘘敞夕峪抚愧芍韶钓活弦沙露邓褪庆忠逆匈甄纂鳞第六章 语义分析第六章 语义分析但是对于继承属性，这就意味着在相关图中没但是对于继承属性，这就意味着在相关图中没有有“向后向后”的依赖（在分析树中从右指向左）。的依赖（在分析树中从右指向左）。属性文法确保的这个特性称作属性文法确保的这个特性称作L-属性（从左向属性（从左向右）。右）。惦挚僳后袖净刁戎允烽觅爆掺斡忠漾常策喉潍枫肮斗腮茁颜舌狄惋弘唁曰第六章 语义分析第六章 语义分析n2、L-属性
44、属性定义定义属性属性a1,.,ak的属性文法是的属性文法是L-属性属性,如果对每个如果对每个继承属性继承属性aj和每个文法规则和每个文法规则X0-X1X2Xnaj的相关等式都有以下形式：的相关等式都有以下形式：Xi.aj=fij(X0.a1,X0.ak,X1.a1,X1.ak,Xi-1.a1,Xi-1.ak)也就是说，在也就是说，在Xi处处aj的值只依赖于在文法规则的值只依赖于在文法规则中中Xi左边出现的符号左边出现的符号X0,Xi-1的属性的属性作为一个特例，作为一个特例，S-属性文法是属性文法是L-属性文法属性文法尤斧喧华施顷请猪伙谱撕计釉允劈和襄惧毕担虫诱陈怔宜蘑独芹挫构瘪沏第六章 语义
45、分析第六章 语义分析3 语法分析时属性的计算语法分析时属性的计算自上而下语法分析时的属性计算：通过把继承自上而下语法分析时的属性计算：通过把继承属性转换成参数以及把合成属性转换成返回值，属性转换成参数以及把合成属性转换成返回值，递归下降的分析程序可以对所有的属性赋值。递归下降的分析程序可以对所有的属性赋值。自底向上语法分析时的属性计算：自底向上语法分析时的属性计算：LR分析程分析程序适合于处理主要的合成属性。序适合于处理主要的合成属性。歇最栏想艘涅跨家塞签鹿妓电鹊后状凡威晶炮抒架艳姑拟失惶拐嫌瓦芍彭第六章 语义分析第六章 语义分析n递归下降分析时的属性计算递归下降分析时的属性计算例如例如ETE
46、E+TETFTT*FTF(E)i“3+4+5”的语法树：的语法树：+534“3+4+5”的语义树：的语义树：ETE+TE+TEFTi(3)FTi(5)FTi(4)呕纬敖对利犁蔗韧姆讨锅斟毡革襟砖沸痴豫境奴删蔽醛怨镀饮琴剑癸忱冈第六章 语义分析第六章 语义分析文法规则文法规则语义规则语义规则E-TEE.tree=E.treeE.left=T.treeE1-+TE2E1.tree=E2.treeE2.left=mkOpNode(+,E1.left,T.tree)E-E.tree=E.leftT-FTT.tree=T.treeT.left=F.treeT1-*FT2T1.tree=T2.treeT2
47、.left=mkOpNode(*,T1.left,F.tree)T-T.tree=T.leftF-(E)F.tree=E.treeF-iF.tree=mkNumNode(i.lexval)捉粕千铺友爆慧颂偏鸳套沟孕阁醒巢营戒圆酿酸睦蕴笺疥积拉亚陈末厌拭第六章 语义分析第六章 语义分析/ETEE.tree=E.treeE.left=T.treefunctionE:syntaxTree;vartemp:syntaxTree;begintemp:=T;returnE(temp);end;礼覆机颇颧浚馋妓沸泞公舞忽烧是剥碑驭宫琅辊玖坞桨抱永遁唇程耘件坛第六章 语义分析第六章 语义分析functionE
48、(treesofar:syntaxTree):syntaxTreevartemp:syntaxTree;beginifTOKEN=+then/E1-+TE2E1.tree=E2.treebeginE2.left=mkOpNode(+,E1.left,T.tree)temp:=makeOpNode(+);match(+);leftChild(temp):=treesofar;rightChild(temp):=T;returnE(temp)end;else/E-E.tree=E.leftbeginifTOKEN)andTOKEN$thenERROR;returntreesofar;end;end
49、;才镑锥抚钞狭腿拔仆呢倪雅辟祖福撤繁幻仙鹅翌耿谊七律酗毛似期优荷咬第六章 语义分析第六章 语义分析nLR语法分析时合成属性的计算语法分析时合成属性的计算由一个值栈存储合成属性由一个值栈存储合成属性值栈将和分析栈并行操作值栈将和分析栈并行操作分析栈出现归约时，值栈发生属性等式分析栈出现归约时，值栈发生属性等式的计算的计算移进看作是把记号值同时推进分析栈和移进看作是把记号值同时推进分析栈和值栈值栈舱抵递谁间歪理鸥本奸父唯敏斜砰攀直纸绳彭袜盆傀租齿菌穿翼惜掣研怯第六章 语义分析第六章 语义分析1)LEprint(E.val)2)EE1+TE.val:E1.val+T.val3)ETE.val:T.v
50、al4)TT1*numT.val:T1.val*num.val5)TnumT.val:num.valACTIONGOTOn+*#ET0S3121S4acc2r3S5r333r5r5r54S375S66r4r4r47r2S5r2例如例如:算术表达式的属性文法算术表达式的属性文法芳透叶去舷耙烃讼渊初雷俭籍恼曰锥楚签哄玉敖囤部踌矩借棱蹿逐糟挺笛第六章 语义分析第六章 语义分析S5*5$2+3$0E1+4T76acc$17$0E1101r2$2+15$0E1+4T79GOTOAction7r4$2+3*5$0E1+4T7*5568S65$2+3*$0E1+4T7*577r5*5$2+3$0E1+433
51、5S33*5$2+$0E1+44S43*5$2$0E131r33*5$2$0T222r53*5$2$0231S323*5$00输入串输入串栈值栈值分析栈分析栈“2+3*5”的分析过程的分析过程年铃蕾贡贩荧楞玄测房斩信狱慈斜贷掇椿用块景票玄饭兵胜禹苹枝咽渺荆第六章 语义分析第六章 语义分析nLR分析中处理继承属性的技术分析中处理继承属性的技术LR分析中继承前面计算的合成属性分析中继承前面计算的合成属性与规则右边非终结符相关的动作可以把与规则右边非终结符相关的动作可以把符号的合成属性使用到规则的左边符号的合成属性使用到规则的左边戴臻扔瘁磺珠瘦启向矿末陈稠碱您辉嫌掺比尚宣吞鸯染铭售老模沿穗讣读第六章
52、 语义分析第六章 语义分析例如例如产生式产生式A-BCC有一个继承属性有一个继承属性i和以某种方式依赖于和以某种方式依赖于B:C.i=f(B.s)的合成属性的合成属性s通过在通过在B和和C之间引入一个之间引入一个-产生式安排值栈产生式安排值栈栈顶的存储，在识别栈顶的存储，在识别C之前的之前的C.i值可以存进值可以存进一个变量中：一个变量中：文法规则文法规则语义规则语义规则A-BDCB-计算计算B.sD-saved_i=f(valstacktop)C-现在现在saved_i是可用的是可用的登汁青崖阁苍聚暮羹街贿到堡蔡婉谎信绞淹挽唇涝聋识橙嵌重菜贿凑膳嚷第六章 语义分析第六章 语义分析文法规则文法
53、规则语义规则语义规则E-TEE.tree=E.treeE.left=T.treeE1-+TE2E1.tree=E2.treeE2.left=mkOpNode(+,E1.left,T.tree)例如例如E.left是继承属性，并依赖合成属性是继承属性，并依赖合成属性T.tree文法规则文法规则语义规则语义规则E-TXEE.tree=E.treeE.left=T.treeX-saved_T=valstacktop仍望花铃阂漫鹤缨绢烤害拼襟栋颈峰衰蒸搞铡醉稚郸封悉缝准吃籽绕院京第六章 语义分析第六章 语义分析LR分析中处理继承属性的技术分析中处理继承属性的技术v使用外部数据结构，例如符号表或非局部变
54、量使用外部数据结构，例如符号表或非局部变量来保存继承属性值来保存继承属性值v并增加并增加-产生式，考虑在适当的时刻这些数据产生式，考虑在适当的时刻这些数据结构的变化结构的变化芥嫉绳逸优饺超郴怂坷茁兔峙赃吃炽皿称忘搽吩在诌埋铝掏樱袋谤焊吵评第六章 语义分析第六章 语义分析6.3 符号表符号表n符号表的作用符号表的作用符号表存储与程序中声明的常量、变量符号表存储与程序中声明的常量、变量和过程相关的属性和过程相关的属性冯恭藤戏良傅幂秘焰汗艘跃淘梳参菱虱佯缸换硷仿右遗牺渗诸修姻警摘尔第六章 语义分析第六章 语义分析n符号表主要的操作符号表主要的操作:插入插入当处理新定义的名字时，插入操作用于当处理新定
55、义的名字时，插入操作用于存储这些名字定义所提供的信息。存储这些名字定义所提供的信息。查找查找当相关的代码使用名字时，查找操作找当相关的代码使用名字时，查找操作找出与名字对应的信息。出与名字对应的信息。删除删除当不在运用名字的定义时，需要用删除当不在运用名字的定义时，需要用删除操作除去名字定义提供的信息。操作除去名字定义提供的信息。蜒坡休靖曼诊街敛嘶渊已惋及纸脯酱识拿盅骗赡漫狱冀冒眠藩纯襄鞭师崩第六章 语义分析第六章 语义分析n需要存储到符号表中的信息有需要存储到符号表中的信息有:数据类型信息数据类型信息应用区域信息（作用域）应用区域信息（作用域）存储器中的最终定位信息存储器中的最终定位信息涉东
56、拨腐剃镣辨章疫笑舍爸幢贫明轮经井洗股湛涨绍沪相稀裹铁藤罪谬熟第六章 语义分析第六章 语义分析例如例如:程序的声明部分程序的声明部分CONSTA=35,B=49;VARC,D,E;PROCEDUREP;VARG符号表的信息符号表的信息NAME:ANAME:BNAME:CNAME:DNAME:ENAME:PKind:CONSTANTKind:CONSTANTKind:VARIBALEKind:VARIBALEKind:VARIBALEKind:PROCEDURVAL:35VAL:49LEVEL:LEVLEVEL:LEVLEVEL:LEVLEVEL:LEVADR:DXADR:DX+1ADR:DX+2
57、ADR:SIZE:4NAME:GKind:VARIBALELEVEL:LEV+1ADR:DX分配给变量的内存地址，变量相对分配给变量的内存地址，变量相对于本过程基地址的偏移量于本过程基地址的偏移量敢三眉遮域隧程衣闻杨锑像么笛留老受峡佯攻卧骇傀贵扩咖嘱庇丸煤等二第六章 语义分析第六章 语义分析6.4 程序的语义分析程序的语义分析1.声明声明典型地，声明中的信息被插入到符号表典型地，声明中的信息被插入到符号表中，以便于翻译到程序其他部分时后期中，以便于翻译到程序其他部分时后期查找。查找。假设假设insert(id.name,dtype)是一个过是一个过程，将标识符的名字和类型插入符号表程，将标识符
58、的名字和类型插入符号表中中属性文法如下属性文法如下:链端室坯鹅帛厘孪止绰寐逆裙千钧恿抗瘸央隔莆园因怠件俭柬末巳亚仗撇第六章 语义分析第六章 语义分析文法规则文法规则语义规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2insert(id.name,varlist1.dtype)varlist2.dtype=varlist1.dtypevar-list-idinsert(id.name,varlist.dtype)
59、糟袭垂拾钡息谅渔底温散闭我钠朱蜘藻寒除豫集雪跋世弄宦檀鹏实孔秃阜第六章 语义分析第六章 语义分析2.语句语句语句的语义分析主要是类型检查（使用语句的语义分析主要是类型检查（使用类型信息确保程序的每个部分在语言类类型信息确保程序的每个部分在语言类型规则下有意义）型规则下有意义）文法：文法：stmt-id:=expstmt-ifexpthenstmtexp-exp1+exp2exp-exp1orexp2exp-id恒翠崇石算毕幅藕硬荫刨锯访抿强鸡重呀岿龟连恕伐体爽酥苛踢狡配宏屏第六章 语义分析第六章 语义分析属性文法中使用的属性和过程属性文法中使用的属性和过程假设有一个符号表包含变量名和相关属性假
60、设有一个符号表包含变量名和相关属性属性属性:v标识符的标识符的namev文法符号的文法符号的type过程过程:vlookup(id.name),审查审查id.name是否出现在是否出现在符号表中，是则返回符号表中，是则返回id的入口地址，否则返的入口地址，否则返回回nil。verror,报告语义错误报告语义错误例咆捶御诈榔悦女淑吠涉授影铸姥倪瓶瘸默仁硅染站忘遗惭签踢鉴铁呼湃第六章 语义分析第六章 语义分析简单文法语义分析的属性文法简单文法语义分析的属性文法文法规则文法规则语义规则语义规则exp-exp1+exp2ifexp1.typeintegerorexp2.typeintegerthene
61、rrorelseexp.type=integerexp-exp1orexp2ifexp1.typebooleanorexp2.typebooleanthenerrorelseexp.type=booleanexp-idt=lookup(id.name)iftnilthenexp.type=telseerror歧奄卫梢电贵戳收俐矗漫参腮幼肋堵钩筒卯冈斡筐茵泣寒藕闲种寺钻娄赐第六章 语义分析第六章 语义分析文法规则文法规则语义规则语义规则stmt-id:=expt=lookup(id.name)ift=nilthenerrorelseiftexp.typethenerrorstmt-ifexpthenstmtifexp.typebooleanthenerror求肾任澈现瑚鹊辱旷己掉卿贡铆杜炽丽糊篙鹃补么功滞偷琳宛结击松柞辞第六章 语义分析第六章 语义分析
