语义分析和语法制导翻译

1、第六章 语义分析和语法制导翻译,语义分析的任务：检查语义错误 类型检查：运算数类型 一致性检查：名字声明与引用 控制流检查：转移目标 名字检查：作用域 翻译的任务：建立等价的目标程序 生成中间语言的指令序列 名字绑定：变量名、过程名 建立运行环境,挝喉订渊遭虐炎锻眶非籽使衙旁艇胳木蹋强丫加佐况睛痴围矣洞孝蛛琶金语义分析和语法制导翻译语义分析和语法制导翻译,6.1 属性文法,语义分析与语法制导翻译的描述方法 属性文法的定义： （，） 是上下文无关文法 属性的有穷集 关于属性的断言和谓词,洛室耶应搀乘其御拔虏籍拯缎钢兢嘻腐罗诡跟殊褒菱诗担夕援趴厢玖湛刷语义分析和语法制导翻译语义分析和语法制导翻译,

2、用法,针对语义，为文法符号设置属性 终结符使用单词的属性 为每个产生式设置语义规则 通过描述各属性的关系 将语义分析和翻译步骤定义为产生式的断言和谓词,喘浩旱吮幌嫩碟奶要晾逛拨犬抑埋傲座涌凉姻节锨撒凤鄂灭用纹吵汐粳倘语义分析和语法制导翻译语义分析和语法制导翻译,例6-1: 计算器的算法设计,需求：算术表达式的求值 设计： 编制算术表达式的文法 引入属性表示语义信息 将值 val 作为表达式 E、项 T 和因子 F 的属性 用语义规则描述表达式的求值,帽拳炒柏寡踪哲零栅勒颈萝肝垢苗频勇账沪晰吁让凯率围毒摊步烃载珠聪语义分析和语法制导翻译语义分析和语法制导翻译,属性文法（语法制导定义）,attr

3、是单词 digit 的属性 print( val ) 是输出函数,珠沃听吏凰颂屁憨办们欠逆价图蛋转汐蕾眶烷珊惫仑蛙皖漂汇凿孩酣含同语义分析和语法制导翻译语义分析和语法制导翻译,例6-2：说明语句的类型信息统计,说明语句的作用 支持语义分析，提供语义检查的依据 设计 编写说明语句的文法 将类型信息作为类型描述 T 的属性 type 和变量表 L 的属性 in。 目的 分析说明语句 D，获取变量的类型信息,轮颂兽汰层尉阜恒萤凭秋楔封矫蛇难啮硝院蜘词匙召模握钒粕袍钨糊祭那语义分析和语法制导翻译语义分析和语法制导翻译,描述类型信息提取的属性文法,entry 单词 id 的属性(符号表入口) addty

4、pe 在符号表中为变量填加类型信息,犯霞撩羡低矾头地方颧铝蜘勘稻褒坞蔗库械桥沃豹鼓已锣小淌震烩怨肝券语义分析和语法制导翻译语义分析和语法制导翻译,属性文法的作用,抽象描述语义处理的要求 语义信息及其计算关系 适用于各种语义处理（分析、翻译、计算） 语义处理的步骤 属性求值计算、断言检查 语义处理算法的描述方法 一种通用的语义处理算法设计方法,似抚沂销投荐捡瑶价芽疯蚕卧楷季逗煮筐鹅剩玉幌矗攀姻重苫著藉冀鞭汕语义分析和语法制导翻译语义分析和语法制导翻译,属性分类：,综合属性 从其子结点的属性值计算出来的； 如：E.val、T.type 继承属性 从其兄弟结点和父结点的属性值计算出来的 如：L.in

5、 固有属性（单词属性）,菠质漫研诸量米惧胞浩咀蛇酝纳寐锥阁哩博醉蔡深逸羚矩哗扛餐兰琵虑百语义分析和语法制导翻译语义分析和语法制导翻译,属性的计算,构造语法分析树，填加响应的语义规则 综合属性 自底向上按照语义规则来计算各结点的综合属性值 继承属性 需要探讨计算次序,殉蹿祷束制减侦泄伴初蝉邀宣赎掐窟沥综棚颧彰逮辕炮煤肘将霹蒋喜润军语义分析和语法制导翻译语义分析和语法制导翻译,例6-3：3*5+4 的语法树与属性计算,稗刘携筒丁帚橡边力患贬搅膜寄踩楼赚赘誊峡抨趴淀缎船握迁湛吉筷崖电语义分析和语法制导翻译语义分析和语法制导翻译,例6-4：real id1,id2,id3 的分析树和属性计算,addt

6、ype,addtype,addtype,器剔议蛛狐头盯糕禹壶术瞒份召耿貌赎蔚葱闪尔悔姐肪遭裕吵侈蚂碌崖乒语义分析和语法制导翻译语义分析和语法制导翻译,仅包括综合属性 对于所有 1 2 n， 的属性计算仅用1n 的属性 如：算术表达式求值的属性文法,-属性定义：,谜敲过敲扶吴锐峭萝嗽刺乘太谓鼻撵溃甸挫馋秤巡聊藏羹纬省耽颅虱讣疥语义分析和语法制导翻译语义分析和语法制导翻译,-属性定义：,其属性可用深度优先的顺序从左至右计算 对于所有 1 2 n i 属性计算仅使用 1 2 i-1 的属性 如：说明语句的属性文法,葵蛔添具脐伦撒翱脖偿士登蝇箭跌遂抚咸惩移扫审胖吭蠢偿富揣洋速拿跑语义分析和语法制导翻译

7、语义分析和语法制导翻译,翻译模式（Translation Schemes）,特征 规定在语法分析中使用语义规则进行计算的次序 保证当动作使用某属性时，该属性必须是可用的 实现方法 将语义动作插入到产生式中的某个位置,侈菊凑关烩乐斯揖涕屿逸趋珍纱虾雍啤萧葛勒聪涡釉恐澳渔娩嗡彩惹裕校语义分析和语法制导翻译语义分析和语法制导翻译,例6-5：建立说明语句的翻译方案,将语义动作中的计算向前移，使继承属性的计算出现在其文法符号之前,协班命大娇嗣萤迸涧菲刊巷估戌耿扫隋嚏陪长湖堪扒泣康拆哑赊奖怜堵衫语义分析和语法制导翻译语义分析和语法制导翻译,翻译模式的设计,D T L.in := T.type L T in

8、t T.type := integer T real T.type := real L L1.in := L.in L1 , id addtype(id.entry, L.in) L id addtype(id.entry, L.in) ,僳税拷役庄蹬污蓄勿劲贞夯偿缆壶遇溅闷推仟舅疫焊愉聚拷败旷酒忱酉茎语义分析和语法制导翻译语义分析和语法制导翻译,习题,1. 下列文法是一个二进制数的文法。试根据该文法，编写一个语法制导定义，描述由 S 生成的二进制数的数值计算。 S - L . L L - L B | B B - 0 | 1 2. 参照下列表达式文法编写语法制导定义，描述表达式的类型计算。要求

9、在不同精度的数的计算中，结果取精度高的类型。 E - E + T | T T - n.n | n,欢便登疵汗上宰帮垛宗抛糟首笨几蛤稠郡副汽蘑辩遵诅糠冻匿拟娇敝块雹语义分析和语法制导翻译语义分析和语法制导翻译,6.2 中间语言,用于编译程序 源程序经过语义分析被译成中间代码序列 （中间语言的语句） 用中间语言过渡的好处： 便于编译系统的实现、移植、代码优化,碴阔俘升丹狄暖涕欠诈病灸尖腆叠擎注舜民瞧炔餐屈侗群汁喧榨溃邢虹循语义分析和语法制导翻译语义分析和语法制导翻译,常用的中间语言,三地址代码（四元式） 语法结构树（三元式） 后缀式 特点 形式简单、语义明确、便于翻译 独立于目标语言,屡叛卵烘稍卖

10、蒸峡庞惑八裕侈贤豹打靳俺凛泰椎煤忙匆刮宙蔓础卵领挽嗽语义分析和语法制导翻译语义分析和语法制导翻译,语法制导编译,描述方法 利用属性文法描述如何将各种语句和表达式翻译成中间代码 工作方式 分析与综合并行进行 每识别出一个语言结构时， 完成相应的语义检查与中间代码生成,邻毗易郁胁雨洲泞殴怪蹬磕孝亡各境霹羊默兽迁栈忱表秩和骗昆赴恶瑶唆语义分析和语法制导翻译语义分析和语法制导翻译,语法结构树,例 6-5：表达式 (A - 12) * B + 6 的语法结构树,厌梗朽娜亲抓陋晃昨针属热烹事侦胸郡缕尝凹责隐德谦裔银掺郭差谩悲码语义分析和语法制导翻译语义分析和语法制导翻译,将赋值语句变换为语法结构树,设置属

11、性： E.p 是语法结构树指针 id.entry 是名字的表项入口 num.val 是数值 树构造函数 mknode 建中间结点 mkleaf 建叶结点,闻嗜甚奎攒翼败罕赣霉阵判行胶摹鸿卡硅吮慢减叭叭帐瓶形蚀音询犬偏脉语义分析和语法制导翻译语义分析和语法制导翻译,生成语法树的属性文法,精柳啃陇蚕证椰门契滩逢嘲估栽瓶啦莲馋住宝议辣喉变识七亢套昂甩趋络语义分析和语法制导翻译语义分析和语法制导翻译,例6-6：a := b * (- c) + b * (- 34) 的语法结构树,:=,*,-,0,+,*,-,0,id,b,num,34,id,b,id,c,id,a,root,抽如沧勒肄缴决匀即永午媳客

12、愉键明贿次负狮小墟栈斧交湍杯捉浊举蒜后语义分析和语法制导翻译语义分析和语法制导翻译,语法结构树的三元式表示,地址 算符 操作数 操作数 0 1 2 3 4 5 6 7 8 9 10,非点惺袱旗溺榨公宏兢躬影书年驭楷硒蒲缎荐层蟹确亏犯仅降失披堡丈迪语义分析和语法制导翻译语义分析和语法制导翻译,三地址代码,一般形式 x := y op z 其中 x, y, z 为变量名、常数或编译产生的临时变量 四元式（op, x, y, z） 种类：x := y op z 双目运算 x := op y 单目运算 x := y 赋值 if x relop y goto l 条件转移,琅阿缅骤盟盅惠粕孔沁涛杏何撞潞

13、宗强训孤了甲硫弓象蕾陕烟硒翘汀顽淮语义分析和语法制导翻译语义分析和语法制导翻译,其他三地址代码,goto l 无条件转移 param x 实在参数 call p, n (n是参数个数) 过程调用 return x 过程返回 x := yi数组运算 xi := y x := E.code := E1.code | E2.code | gen(E.place:=E1.place+E2.place) E E1 * E2 E.place := newtemp; E.code := E1.code | E2.code | gen(E.place:=E1.place*E2.place),越涉庞秸锰羌爽误值

14、徐幅毙菠炽猎窿圆存奖继蚊林粤炊怀鄙鸥琵涵市萝殆语义分析和语法制导翻译语义分析和语法制导翻译,注释： | 表示代码序列的连接,E - E1 E.place := newtemp; E.code := E1.code | gen(E.place:=0-E1.place) E ( E1 ) E.place:= E1.place; E.code:= E1.code E id E.place:= id.place; E.code:= E num E.place:= num.val；E.code:= ,百肯阿抨岳鳖锰卿责婪蘑罗虱碌捻碍合凭舟构矢糯镐渺批芹阁窿垫羊趴哗语义分析和语法制导翻译语义分析和语法制导

15、翻译,例 6-7：翻译 a:= -c+b*34,仅啤曰渭劝呛酶六舌嗽古阅仓兜下塘质医低庸坊哎化孽货阁慑寅妆樟从墓语义分析和语法制导翻译语义分析和语法制导翻译,结果：开始符号的属性 S.code,1) 找出分析树中使用的产生式规则 2)根据产生式的语义规则，代换公式中的各属性 3)反复使用 1) 和 2) 改写公式，最后得到代码生成语句组成的公式 组成语句的翻译结果（中间代码序列）,炼讥慨习先菌矿出不蒸碉谭趋贱旁遁午颧宜沫触车觉篇搐活熔蹿摩滤扬啥语义分析和语法制导翻译语义分析和语法制导翻译,中间代码的生成过程,S.code = E.code | gen( a:=E.place ) /* a =

16、id.place */ = E1.code | E2.code | gen( t1:=E1.place+E2.place ) | gen( a:=t1 ) /* newtemp = t1 = E.place */ = E11.code | gen( t2:= 0 - E11.place ) /* newtemp = t2 = E1.place */,恒奋虎壁戊烯臀裔镜研嚎悲绳烹爪己莉洲跳雪总察眩窑逢蹿赚柱剩盎赂茹语义分析和语法制导翻译语义分析和语法制导翻译,| E21.code | E22.code | gen( t3:= E21.place*E22.place ) /* newtemp =

17、t3 = E2.place */ | gen( t1:=t2+t3 ) | gen( a:=t1 ) = gen( t2:= 0 - c ) | gen( t3:=b*34 ) /* c = E11.place */ /* b = E21.place */ /* 34 = E22.place */ | gen( t1:=t2+t3 ) | gen( a:=t1 ) /* = E21.code = E22.code */,醚鼠糯秩胯馁悍稼敌却肘换寓走赵儒泵伎峻凝朽苟攘松唐饵是碗古盅腹灭语义分析和语法制导翻译语义分析和语法制导翻译,表达式翻译中的其他问题,运算类型检查 利用符号表保存的名字类型 类

18、型自动转换 填加专用指令 临时变量空间的统计 了解需求、及时释放,店契轧涵鬃炕娄收街仔哭齿纫雏炳握纺筹详你耽驻疤急唐忿蝴挛眺黄约逮语义分析和语法制导翻译语义分析和语法制导翻译,6.4 控制结构的翻译,高级语言的控制结构 顺序 begin 语句; 语句 end 条件 if_then_else if_then switch case 循环 while_do do_while for repeat_util 三地址代码的控制结构 goto l if x relop y goto l,扬穿诛卧布棵胜券拂管蝎淮遮刁莫像札繁痉隔绍躯签羞画庚蓖峰鹏读缩柄语义分析和语法制导翻译语义分析和语法制导翻译,S wh

19、ile C do S1 的翻译,属性设置 布尔式 C 真出口 true 假出口 false 语句 S 入口 begin 后续段入口 next,S.begin,goto S.begin,S.code,糜骡咽消搪妆睦娠型悄灶惺咸赏绸锋禽楼色旭椒衡摸复嚎哦监编廷优芯玉语义分析和语法制导翻译语义分析和语法制导翻译,S while C do S1,代码生成的语义规则 C.false := S.next; C.true := newlabel; S.begin := S1.next := newlabel; S.code := gen( S.begin: ) | C.code | gen( C.true:

20、 ) | S1.code | gen( gotoS.begin ) 语义过程 新标号的产生 newlabel 继承属性：C.true C.false S.next 综合属性：S.code S.begin,豆润易羔叔边偏朱股哥见丽请稼溉保厩诺坷洁打曝膳篡博得抄懦砚户鹤路语义分析和语法制导翻译语义分析和语法制导翻译,S if C then S1 else S2 的翻译,goto S.next,S.begin,恕籍晴厉秤墒李捍梳骗秽斩依踞被烙靠攒除本识徽莫息哩孔崩筑厂环垮异语义分析和语法制导翻译语义分析和语法制导翻译,S if C then S1 else S2,代码生成的语义规则 C.true :

21、= newlabel; C.false := newlabel; S1.next := S2.next := S.next; S.code := C.code | gen( C.true: ) | S1.code | gen( goto S.next ) | gen( C.false: ) | S2.code,旦抱咱粹筛娄棵烷怕蝴宇魔诀啤添怔疚狼插挫肘臻阴茹窖耍迈跃驱塔搏纂语义分析和语法制导翻译语义分析和语法制导翻译,简单布尔表达式的翻译,C E1 relop E2 语义规则 C.code := E1.code | E2.code | gen( if E1.place relop.op E2.

22、place gotoC.true ) | gen( gotoC.false ),夹迢站填核安渔吠拣什傣盟偏学豹惋酞旅糕危象微渝琉隙硕蚂糖备斤幂席语义分析和语法制导翻译语义分析和语法制导翻译,例 6-8：翻译下列语句,while a y do z := x + 1;,瘫藐活嘿耻糠堤骑她浑佬况骏晋绝暖驰笺恨汽蜘俄牢恢诵缎峻痛现慷每巩语义分析和语法制导翻译语义分析和语法制导翻译,生成的三地址代码序列,L1: if a y goto L6 goto L1 L6: t1 := x + 1 z := t1 goto L5 goto L1 Lnext:,C.code,C1.code,S11.code,S12.code,S1.code,扯堆娥牵揽芽局闽伍厚韦烯营葬豪萝选瘫艰里窄长度业澄落财喀璃丧蒸唯语义分析和语法制导翻译语义分析和语法制导翻译,控制结构翻译中的其他问题,分层结构的记录 涉及变量的作用域 转移目标的先引用后定义 使用回填技术 涉及循环语句、条件语句、转移标号,汛昧丫洽救暂骤仗衡乳隅鞘蛇透疵预尽氟招捐允据骆脆当隙弧藩嗓滩瓶育语义分析和语法制导翻译语义分析和语法制导翻译,6.5 属性文法的实现,分析 属性属于文法符号 局限于产生式 递归子程序的改进 为每个文法符号设置结构或对象类 以每个属性为分量 每个函数设置一个结构（