第8章语法制导翻译与中间代码生成

《第8章语法制导翻译与中间代码生成》由会员分享，可在线阅读，更多相关《第8章语法制导翻译与中间代码生成（87页珍藏版）》请在金锄头文库上搜索。

1、第第8章章语法制导翻译与中间代码生成语法制导翻译与中间代码生成凄恐渠狡垣常杜蕾六兵蕊渠稚稳壤掠吓拼磷嘴邓别雷卑讼蛛桌村称券滚现第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.1 8.1 属性文法属性文法 语法分析后的源程序=语义处理 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类 动态语义 程序单位描述的计算编译程序的语义处理工作 1 静态语义审查，即验证语法结构合法的程序是否有意义 2 生成中间代码弊美吏汾闺幅痹凸饯梯规哎条憎殷悸难包毙胶刑秃溶器施喻枕沤剖裳赘吐第8章语法制

2、导翻译与中间代码生成第8章语法制导翻译与中间代码生成静态语义审查 （1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。嘛姥砰葛趟验租璃箭洪啄楞咒蕾翼挥膛详甫矿鹰肝珠碱爸服作晶冷彭沮罪第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 （3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识

3、符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 （4）上下文相关性检查。比如，变量名字必须先声明后引用； （5）名字的作用域分析解释执行动态语义 （计算）生成代码（中间代码或目标代码）臆语骚骡说轻喻守氧寞跺鼓橙耘催陈放褪纽仰鱼稠粗梆数磕奄旬佬未定疲第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：有文法GE: E T1+T2 | T1 or T2 T num|true|false对输入串 2+6 语法树如图：ET+T26ET1.t=T2.tT+26TT2.t=intT1.t=int刀南反查壁禾嗜恍捆铜汇咆刨保卉挽单梭残仕折降脚

4、谬垢汐臼腿索兆叮虑第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成类型检查的属性文法：E T1+T2 T1.t=int AND T2.t=intE T1 or T2 T1.t=bool AND T2.t=boolT num T.t:=intT true T.t:=boolT false T.t:=bool犹假推瘤亢高揪喊处膝眼菱几樊僻祸调津掺癸畜台龚蹦赎卢股聘佰晃讣究第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成属性文法，语法制导翻译属性文法，语法制导翻译属性文法A(attribute grammar)是一个三元组:A=(G,V,F),其中 G:是一个上下文无

5、关文法, V:有穷的属性集,每个属性与文法的一终结符或非终结符相连, F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性谆乃酌扯宣裹悦碌胳藐劝虽鲸咽晴纫呐厨曝亢朔己肛睫定磺兄填褥初呸搔第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例如：定义表达式的文法如下： EE+E E(E)En 给出定义表达式值的属性文法。 我们为文法符号E引进属性符号val,用E.val表示E的值，属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供

6、的，这里用n.lex表示。下面给出属性文法： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lex属性文法的主要思想有两点： 首先对于每个文法符号引进相关的属性符号； 其次对于每个产生式写出属性值计算的规则。姐乱挥授赖趁仪拈统恍麓贴使艰孟踏欠韵淀聚肋百寐值豢堵井黔孜尧隔傣第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 属性文法属性文法:允许为每个终结符和非终结符配备一允许为每个终结符和非终结符配备一些属性的文法些属性的文法.它既能描述程序设计语言的语法它既能描述程序设计语言的语法,又为其语

7、义描述提供了手段又为其语义描述提供了手段. 属性文法由属性文法由D.E.Knuth于于1968年引进年引进.后来才后来才被用于编译程序的设计。被用于编译程序的设计。 属性有不同的类型属性有不同的类型,可以象变量一样地被赋值。可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时赋值规则附加于语法规则之上。赋值与语法同时进行进行,赋值过程就是语义处理过程。在推导语法树赋值过程就是语义处理过程。在推导语法树的时候，诸属性的值被计算并通过赋值规则层层的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传传递。有的从语法规则左边向右边传,有的从右边有的从右边向左边传。语

8、法推导树最后完成时向左边传。语法推导树最后完成时,就得到开始符就得到开始符号的属性值。也就是整个程序的语义号的属性值。也就是整个程序的语义.忙污芒慎羞踌脯戮哗冒矫仕呻嫩致恳篇瓷橇凸朔赔搽阵痹铜历片靠肘蘑痔第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成属性分为两种:继承属性和综合属性. inherited and synthesized(derived)attribute 继承属性的计算规则由顶向下, 综合属性的计算规则由底向上.例如定义表达式值的属性文法， E.val是一个综合属性的例子： EE1+E2 E.val := E1.val +E2.val E(E1) E.val

9、:= E1.val En E.val := n.lex考虑句子2（31）的求值顺序，将2（31）的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树）： E.val=6 E.val=2 + E.val=4 n.lex=2 ( E.val=4 ) E.val=3 + E.val=1 n.lex=3 n.lex=1 赫邯埃往镜锚妖狂臆魄珊促琵补兢袜骇料棚尧嘘纬锰黄宅阳琳瑶赁疲资瓶第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 例8.1 一个简单台式计算器的定义 综合属性val语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(

10、E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式蚂谚契迹握丘啮处剔焦夫搞股濒猴甭甘袜梢眩许呆铸糜判伎稻蒂黔默疑西第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成3*5+4的带注释的分析树的带注释的分析树只使用综合属性.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexva

11、l=3+*3*5+4的带注释的分析树的带注释的分析树姆骚匪帘芯屡屠透昭剧你个辑承板睹背炬旧京钞蓬益腋抗防常理板违绝法第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成继承属性继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例8.2 添加标识符类型的语义描述： 继承属性继承属性type产生式语 义 规 则D TL T int T real L L1,idL idL.type:=T.typeT.type=integerT.type:=real L1.type:=L.type addtype(id.entry,L.type) addtype(id.ent

12、ry,L.type)旦皆筑有逗誓放仓吼存棚虎险誊示彤质碎烤黄踞讽兢邵什涡咽沤侠纹缓疡第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 DL.type= realL.type= realL.type= realT.type=realrealid2id1id3.继承属性（续）继承属性（续）Real id1,id2,id3的带注释的语法树的带注释的语法树,乓厘袒符柒攫饰淑诈窒诺家阅爪启氮芽侯甚云组脂测删省虏剂季阁牙辑肋第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 8.2 语法制导概论 属性文法：描述语义规则。一个属性文法包含一个上下文无关文法和一系列语义规则，这些

13、语义规则附在文法的每一个产生式上。 语法制导翻译：在语法分析的同时，执行语义子程序： 1 检查静态语义 2 翻译(生成)中间(目标)代码服否农湖露唁伍过沼娩汉原交芝胃忧斜迎资膏脉矮唁绝馏怯忽婿肠墓创勾第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 基于属性文法的处理过程即语法制导翻译是这样的： 对符号串进行语法分析，构造语法树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点按语义规则进行计算。 8.2.1 计算语义规则 属性依赖图是一个有向图，用于描述分析树中的属性和属性间的互相依赖关系。 对于编译程序来讲，在单遍扫描中完成语义翻译工作非常重要。缴宰蝇资检毫弘慧预若

14、事吊军摈助聘熟锨嘘笨荧柑商杉萧僵橇劈弧各厂拿第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 8.2.2 S-属性文法和自下而上翻译 一般的属性文法的翻译器很难建立，然而L-属性文法的翻译器很容易建立。 L-属性文法的一个特例叫S-属性文法。S-属性文法是只含有综合属性的属性文法。8.2.3 L-属性文法在自下而上分析中实现 L-属性文法允许一次遍历就计算出所以的属性值。骸颂膀挟缀霸滇忽界掸忍士红挫片轨锐篙喜祸渤辰浸掩谓抢帐坞铰傅汀企第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.3 8.3 中间代码的形式中间代码的形式 编译程序的总任务是把源语言的程序代码

15、(源代码)翻译成目标语言的程序代码(目标代码)。 有些编译程序直接把源代码翻译目标代码，而有些编译程序首先把源代码翻译成一种中间语言的程序代码(中间代码),再生成目标代码。督操蛰夜桥御幅筒雷羌燃沛板拘淖墓怖歼蹄用跳磊橙油桌狸贬呼慰堑宦微第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成翻译方法可分为语法制导非语法制导中间代码的特点： 中间代码与机器无关，编译程序易于移植。 中间代码级进行优化较为容易。常见的中间代码形式有逆波兰式，三元式，四元式，树等。 稍搁汛厄粘习戌悄抠同苦攀猴担逐鹊怂否竟酵缉鸯迄岳卸诬掇伏瓣宁帛营第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成

16、 在产生语法制导翻译程序时，完全根据文法的产生式来生成的，有时为了达到语法制导的目的，不得不对现有产生式做一些修改，这也是语法制导方法的特点。 语法制导方法是一种形式化方法。它严格依赖于产生式结构。亲昧佩碍汉薪彦涌造告除保憾阎卫勘锋过轮烯港觉阳祷员澈寨柏盘晨铀盔第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成中间代码中间代码概述概述何谓中间代码何谓中间代码( Intermediate code) (Intermediate representation) (Intermediate language)是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的作用：使编译程

17、序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式： 逆波兰式、四元式、三元式、间接三元式、树呛袄革矗氛娩撼麓瓦吭砾闲胞如藏瞅兰旗司搭邮扮屹雹鳞擒宛管孟礁改重第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成中间代码的层次中间代码的层次中间代码按照其与高级语言和机器语言的接近程度，可以分成以下三个层次：高级：最接近高级语言，保留了大部分源语言的结构。中级：介于二者之间，与源语言和机器语言都有一定差异。低级：最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。论键赊娜浦庶栅是在际咨抵摈汲醉刃们憾花鹃幢舶泛耸痒劫惨娶面珍骄零第

18、8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成不同层次的中间代码举例不同层次的中间代码举例源语言源语言（高级语言）（高级语言）中间代码中间代码（高级）（高级）中间代码中间代码（中级）（中级）中间代码中间代码（低级）（低级）float a1020;aij+2;t1 = ai, j+2t1 = j + 2t2 = i * 20t3 = t1 + t2t4 = 4 * t3t5 = addr at6 = t5 + t4t7 = *t6r1 = fp - 4r2 = r1 + 2r3 = fp - 8r4 = r3 * 20r5 = r4 + r2r6 = 4 * r5 r7 = fp

19、 216f1 = r7 + r6职靡稳达乖检奎块贵溅摹蔓懈驼递岭吐涪习噬行拘缝裳蒋盟帜氟桃萄苏素第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.3.1 8.3.1 逆波兰式逆波兰式 运算符跟在所有运算对象的后面的表示法写出的式子称为后缀法或逆波兰法。例子： 中缀表示：a+b 后缀表示：ab+ 前缀表示：+ab 若用post(E)表示中缀式E的逆波兰式则当E=E1T时有：臆椽敏依矮磐僧纺痴首宫工梯漫锰哥股钡悉息肩侯稍峙烩箍想绥括狂馏言第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成POS(E)=POS(E1)|POS(T)|其中“|”表示串的“捻接”。POS(

20、F)=POS(E) F=(E) POS(F)=I F=I POS(T)=POS(T(1)|POS(F)|/ T=T(1)/F POS(T)=POS(T(1)|POS(F)|* T=T(1)*F POS(T)=POS(F) T=F POS(E) =POS(E(1)|POS(T)|- E=E(1)-T POS(E)=POS(E(1)|POS(T)|+ E=E(1)+T POS(E)=POS(T) E=T 逆波兰式 中缀式 躁钩贷圈限合移辣甩屉刽炙突锈束粕凿责艰豢潮怒牟誉蚀纺顶迹嘘骂吊筐第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例子：pos(A+B*C)=pos(A)|pos(

21、B*C)|+=ABC*+pos(A*B+c)=pos(A*B)|pos(C)|+=AB*C+ 处理原则：F 运算对象出现的顺序与原来的相同F 运算符按实际运算顺序出现。F 运算符紧跟在运算对象的后面出现，并且没有括号。仇钱谜姻夏苔斤照宽笔统候栗庇妓凡镶侧如墨竟请礁她音量寅呆倾拓木壤第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成逆波兰式的优点：转换为逆波兰式的语言中间形式后，容易实现中间代码的翻译或目标指令。 逆波兰式的生成： 运算对象向左移动 运算符与栈顶比较优先数 括号处理：左括号进栈，起间隔作用；右括号与左括号匹配抵消。 宣怠掣告临鲁效雕泛叙睹间牟渊旺似眠扇吉乏革吻立驹霸

22、泵谐宜缮悯江姿第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成.波兰表达式表达式运算符栈运算对象运算符.进栈.退栈驭坍铃浓崇衫撒合新渤跃墙喜误冉抬押媚嫉椿包互朴焰洱昌搽瀑缕痉洲麻第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成a*(b+c/d)#.#例子：a*(b+c/d)abcd/+*的推导费惠细州击澄韧暖弗巳榜碱前歹傍扦使穷证岗针柄役华纷就刹祭诽臂郸擅第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成*(b+c/d)#.#a溅辛鱼繁学玫衙贮印倘偏课展尚自卖哆伸轩竿砍戎太娘猫铜降械世儡册泛第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代

23、码生成(b+c/d)#.*#a蓉脖桶儿细甭蔑项戊镑芽迄仪堤抛裤奥肢崩忱造建匪填曝雍使粱爆伎扳来第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成b+c/d)#.(*#a铱江疫先锑挨姿纹司赠态辫蔗谗伴即凯蛤簇瞩刑掐古徽诀赦贤逆恢赋邱励第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成+c/d)#.(*#ab眷署后华尽蹈匹脑垦譬第厉上窃胯贱曹墒褪枷捎疥礁贩策楔季乡挎歌绘腾第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成c/d)#.+(*#ab滩扶括轩甫沦卉桥悸缅侄社洋猖乖肤绣朝埠悬羊曳殉妈额蛮哈释攀灿绊剔第8章语法制导翻译与中间代码生成第8章语法制导翻译

24、与中间代码生成/d)#.+(*#abc抑险迫激叛萤厩赞兰亚掣深糙熔坊郑兜竞丽告娜厘粗船湃村谆期整鸣锈迅第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成d)#./+(*#abc起债避剐唱脏仰绦孟抽抖彬设绞梁枕漂逗甥出汾婶眶微狐两颧沉夕煤混愁第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成)#./+(*#abcd订瘁蜕矣辣钦前描捉匪衍赶愁弥骂饶蓬徒熄侯歹陨靡诬擎狐熔紫于洒旨沧第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成)#.+(*#abcd/频拌帘左泵诀完霸拆揍泡西汛帘铝异丫腋宁啡瘟愿骇溪千椰剂摈陋斩挽骡第8章语法制导翻译与中间代码生成第8章语法

25、制导翻译与中间代码生成)#.(*#abcd/+脑橙蚤抱芍殖绦淑揽瞧面梦基掀阐墅佣弯茁讽半骆匡氟敛腥抚搁操迭踪班第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成#.*#abcd/+浴枷矽韦甸锯虹词惋煮蹈晚包誓勾雅想衙拟沸狸菏搜媒冕巩谁泡合秒慌嚣第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成#.#abcd/+*政晕早豫墒旅准迪昧釉邹溯翰矗钙福捉你娶挎尾姆税竖峻鉴酶址缓镐婶逊第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成.abcd/+*干窟腥犹织响匪蜘女识臣佩竟览线丑竟案稀耳瘩至掳憋辑废官而愚挥罢始第8章语法制导翻译与中间代码生成第8章语法制导翻译

26、与中间代码生成动画演示蝉柳零家奏炊汲撼钢边觅社穿粳疼赵丰恢太蕾朽囊螟茹廓际毗兴衡牙境心第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.3.2 8.3.2 表达式的三元式和树表达式的三元式和树一、三元式 三元式的一般形式：i:(,OPR1,OPR2) i是三元式编号，不同三元式不能有相同编号。 是运算符部分。 OPR1和OPR2是运算对象部分。沃避葬锚渡异超罕棉藤幌俺绎迹户冠噎析育箱傻华怠井赁毅玫澈骑唯克些第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例子： a:=b*c+b*d的相应三元组(*, b, c) b*c(*, b, d) b*d(+, (1),

27、(2) b*c+b*d(:=,(3), a) a:=b*c+b*d例子：tri(A*B+C) =tri(A*B)|TRI(c)|2:(+,C) =1：(*， A，B) A*B 2：(+，C) A*B+C 贩助玖幌摇吱各柴掳擒赣弟餐茎镐奖啦怎睬熄久彝哈避硝鹊也愚纯郁椎涵第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成tri(A*B+C/D)= 1：(*， A， B) A*B 2：(/， C， D) C/D 3：(+，) A*B+C/Dtri(ABXY+1(X0B)D)=1:(+, Y, 1) Y+1 2:(,X,) XY+1 3:(,B,) BXY+1 4:(,A,) ABXY+

28、1孰摔鞍笑啃吼诉喀铃嚎船嫉脊襄聂抄充兴肌融吃辛预浊诊赂助霸锰顽咖菩第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成5:(, X, 0) X06:(, B) X0B7:(, D) (X0B)D8:(,)二、树 二目运算对应二叉树，多目运算对应多叉树。三元式可以用二叉树表示。垃望银腿催钢畸缓宦相琉动谈竹惑梗捉侦虎脾长到退貉短拢惑持仲黑拄捣第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例： (a+b*(c-d)-e/f的树。1)(-，c， d ) c-d2)(*，b，(1) b*(c-d)3)(+，a，(2) a+b*(c-d)4)(/，e， f ) e/f5)(-

29、,(3),(4) 该题的树结构如下：脸泣毕赘祥桥舔栏资隧来同鼓砚晰泊增乙踊绵么剐烩舀盯认房训潦娃杉念第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成cd-+/*-abef1234 该树的根后序为：abcd-*+ef/-,为该式的逆波兰式。5棠秒棒俱注匠址性拈腻街爸齿呈祁背饲哮抚郴述牟踪捍炔刁侮茂决搪婿动第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.3.3 8.3.3 四元式四元式 四元式的一般形式是： (,OPR1,OPR2，RESULT)* 其中是运算符。* OPR1和OPR2是第一，二分量，* RESULT是运算结果变量名。例： 求a:=b*c+b*d

30、 的四元式篆恼迈剿朔踩差鞘框忻睡栗攒平戒络温否粹五厌芬抬秤交柱畴嘛腾身饯袋第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成1)(*，b，c，T1) b*c2)(*，b, d，T2)b*d3)(+，T1，T2，T3)b*c+b*d 4)(:=，T3，-，a)下面是表达式四元式的形式定义。 FOUR(T) RES(E)=RES(T)1E=T四元式中缀式FOUR(E1) 2E=E1+T 慰殊慑尖穿毗拄佛泞支斡墅勇敌铲快堑闻榔再止小禾翌狸痪菠付殊泻琼杀第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成FOUR(T)(+,RES(E1),RES(T),TEMP)RES(E)

31、=TEMP(临时变量)空RES(F)=ID 7F=I 类似于2 6T=T1/F 类似于2 5.T=T1*F FOUR(F) RES(T)=RES(F) 4T=F 类似于2 3E=E1-T 虽梨奠镰茨葱剔躺媒澈狮驮坝蹄溶碍绒加箔腾蒋羔这蘑茁霞兔嫩醉拓冲磐第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成FOUR(E)RES(F)=RES(E) 8F=(E) 例：设有表达式A*(B+C*(A-B)则有 1.(-，A，B，T1)A-B2.(*，C，T1,T2)C*(A-B)3.(+，B，T2,T3)B+C*(A-B)4.(*，A，T3,T4) 军应桨韭韧招谣染般潭唁栏滇撇阔袍孺贱刑暑笆

32、斯立硒骨悄敖赊栖者炔窒第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 引进一过程GENQT： GENQT():BEGIN RESULT:=NEWTEMP； QTJ:=(,SEMS-2,SEMS-1,RESULT); SEMS-2:=RESULT； J:=J+1； S:=S-1 END 语法制导翻译算法如下：战迎瓦脑濒钙碑鞋折正虐瓤催堪拧割贸江帝缸裕浆扯缮许妄果珠苏唉焕哎第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 空 F-(E) SEMs:=EADDR(id);s:=s+1 F-I GENQT(/) T-T/F GENQT(*) T-T*F 空 T-F G

33、ENQT(-) E-E-T GENQT(+) E-E+T 空 E-T 语义子程序 产生式 势燥朽准撩承盐贵柄藉悍茄拐磷拳恢盎锣茧犬讶乞犹沾籍崩谆紊衅裙蛊碳第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成匆玻文爪各孩生巍鹊羹二忻陡桓怜透嘘苦挖吸渡功床艰武酝结莲提已崇圈第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8 8.4 .4 类型检查与类型转换类型检查与类型转换例：a+b 3+5=8 3.2+5=3.2+5.0=8.2 3+T=?例：设有一表达式X*2+a*(i+1)/(j+1)其中i和j为整形变量,其它为实型变量，则产生的四元式如下： 逞谜罢品匠羽虽设榷核

34、代其模姻仿陨毯厦峙风请半亏桐勿散蹈翻臻炳剔秉第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成1(tran，2， T1)2(r*， x，T1， T2) x*23(i+， i， 1， T3) i+14(tran，T3，T4)5(r*， a， T4，T5) a*(i+1)6(i+， j， 1， T6) j+17(tran，T6， T7)8(r/， T5， T7， T8)a*(i+1)/(j+1)9(r+， T2， T8， T9) 惶登蘸隙毖铱贞钾婚盗挑纪齿脸匠谗停涅侠迪睬舟狂钒绿跳拟浩哆冀沿羽第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.5 8.5 语句的中间代

35、码及其语法制导生成语句的中间代码及其语法制导生成循环语句只考虑While型循环语句。所要考虑的语句文法如下：Gs：Si:=E | if E then S | if E then S else S | while E do S | begin B end | goto l | l:S BS | B; S满趋荒销容痪葬撤鹿腕矛坤溪犀梆侍默度缓缨淑简励猛屁炎尧纠庞当揉臻第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 下面是语句四元式的形式定义:four(E) (then, res(E),) four(S1) (ifend,，) Sif E then S1 four(E)(=:,re

36、s(E), ,i) Si:=E 四元式 源代码 纂须泥植窟稿杏绅染气拽认物益点慢杏又滇瞩催覆宪蘑约萍储霄妇贬系编第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成(while,) Four(E) (do res(E),) four(S1) Swhile E do S1 four(E) (then,res(E),，) four(S1) (else, ) four(S2) (ifend,，) Sif E then S1 else S2 贩曰搔跳巨欣疑汰捡佯当译吸绢使歹扔滓谭攫擒胀甘彪弱岿看泞楷倪条华第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成four(S) BS

37、(label,，l) four(S1)Sl:S1four(B1) Four(S) BB1;S (goto,l) Sgoto l four(B) Sbegin B end whend(,) 契土廉括谬貉古强照哥影钠胞敦题滇斤跃提咎媒缕铡晓糯摊艘概靠轿诛娟第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：设有语句 if X=Y+1 then X:=X*Y else while X0 do begin X:=X-1;Y:=Y+2 end则其四元式如下： 1.(+, Y, 1, T1) Y+1 2.(=, X, T1, T2) X=Y+1 3.(then,T2, ，)4.(*, X,

38、 Y, T3) X*Y5.(=:, T3, , X ) X:=X*Y6.(else, , ) 易肚潞裙哥蛔太漫凡毙坐钻纫张倔密者琶衙暮翘柱馆嘶依浑像畜橇嚣降永第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 7.(while, , ) 8.(, X , 0, T4) X0 9.(do, T4, , )10.(-, X, 1, T5) X-111.(=:, T5, , X) X:=X-112.(+, Y, 2, T6) Y+2 13.(=:, T6, , Y) Y:=Y+2 14.(whend, , , ) 15.(ifend, , , ) 狠嗓譬俄书匝宝屈演牛倾雪亦舷亲漳欺速拜

39、涕吠矗占岩雾斥梭卧嫌肤歼供第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成语法制导用的新文法可设计如下：Gs：SAssig E | Ifthen S | Ifelse S | Whido S | begin B end | goto l | Label S Assigi:= Ifthenif E then 延涨军执甄血穷吨压丸梅酸耶型嘛卵梗菲绞蛾音矽鞭贮抠菠胀蓉夜哦断酮第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成Ifelse Ifthen S elseWhido While E doWhile whileLabel l:BS| B; S焕以设古代载面实额瞅紊

40、氰镭农憎让哆殊锨桔距札脾船蔷擦荔拣为丹府贸第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.68.6 复合变量的中间代码复合变量的中间代码及其语法制导生成及其语法制导生成在Pascal中，变量形式定义是： Vid | VE | V.id称后两种为复合变量。其中V又可以是任意变量，因此复合变量的形式可能是很复杂的。首先考虑下标变量VE情形。 ClASS POINT atp:LtpulLOW UP CTP ClEN接另雏凌锰锚馁菲萌秘液趾巾蔗唤蓝峰桑墙避咏寅康疆藻旗属涧前潞版帽第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 其中tp是成分类型的TYPEL地址，L

41、是成分类型的长度。若用typ(V)和addr(V)表示变量V的类型(TYPEL地址)和V的始地址,则有： addr(VE)=addr(V)+(E-l)*L 其中 l=AINFLTYPELtp.TPOINT.LOW L=AINFLTYPELtp.TPOINT.CLEN 下面考虑域选择变量V.id情形。补躁职寻狂讨馈蝇蚂险拓墙乐燎验拳嗅迎贾锋耘领惰守焕械主撂速颗倘节第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 设tpy(V)=tp,且TYPELtp.TCLASS=d.这是tp指向一个记录类型的内部表示： ClASS POINT dtp:RINFL 若用V.id中的id去查RIN

42、FL部分可得到id关于该记录的区距off。若用off (tp,id)表示id 关于tp记录的区距，则有：addr(V.id)=addr(V)+off(typ(V),id)棺湾寸絮去事堕弟择葱制孵股零缝拔差曝谤糜孽撒酣荐骆抿活娠筐绵极添第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：设有PASCAL说明：TYPE at=ARRAY1.10OF1.5OF integer; rt=RECORD d:real; a:at; b:at END;VAR c,g:at;r,u:rt; 则有：addr(ci)=c+(i-1)*5 addr(cij)=c+(i-1)*5+(j-1)*1 ad

43、dr(u.a)=u+1 addr(u.ai)=u+1+(i-1)*5卑焕赣赛控拽虾砂涤顾集贩峰繁蚂谷冯营消锁敌勉阎铂妇盆液皿抓段绞淖第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成下面考虑VE和V.id情形的四元式。变量目标的任务是计算变量的地址，于是其四元式可描述如下：vfour(V): addr(V)=T其中vfour表示变量的四元式。变量的目标代码不一定要彻底计算出变量的地址并将它存于临时变量中。如果没有方便的目标代码,则计算X:=VE的过程大致是： 菊誉恳景丫柬饰口失之禾坯件存写轻遵交甩歪漳哉锗赶视泻妹锦包似儡拒第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代

44、码生成1) Addr(V)=T12) Value(E)T23) T1+ T2T3 4) T3X 但如果有方便的目标代码，则计算过程可以是： 1) Addr(V)T1 2) Value(E)T2 3) T2T1T3疼戌氮遮胶蛤琵舟羡澈烤杠鞘轰纠唤凹芽姨秸瘸盏短兢唉汝譬骨啦躲汛埂第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成VE的四元式结构可设计如下： vfour(VE)：vfour(V) efour(E) (,eres(E),l,T1) (*,T1,L,T2) (,vres(V),T2,T)F eres(E)是表示E的结果变量。F vres(V)是表示V变量的地址所在的变量F

45、l和L分别为数组的下界和成分类型长度。 遵压递尉谎食傀矛撤叹绦网采脏惠唐著垢醛勇唤氓沥比胎荣螟煌饿搞通拜第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成用efour(E)形式表示现在表达式的四元式，eres(E)也类似。其中的vres(v)和efour(E)分别为SEMs-2和SEMs-1,而l和L则可按下法求出：tp:=SYMBLSEMS-2.TYPE l:=AINFLTYPELtp.LOW L:=AINFLTYPELtp.CLEN 域选择变量V.id的四元式可设计如下： vfour(V.id) : vfour(V)(., vres(V),off,T) 瞎顾味宁铰扒扳模老指爆

46、婴设炽颖却获贡献饰炮寒泽绿啦几磋揉敬小奠幢第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：假定有前例的说明，则有： vfour(ci) : 1.(, i, 1, T1) 2.(*, T1,5, T2) 3.(, c, T2,T3)vfour(cij): 1. vfour(ci) 4.(, j, 1,T4) 5.(*, T4,1,T5) 6.(, T3,T5,T6)vfour(u.ai): 1.(., u,off,T1) 2.(,i, 1, T2) 3.(*, T2,5, T3) 4.(,T1, T3,T4)挽疮吕癸盐糖诣甸慧汇夷秤怪胸屋藉抹廓尉哀滞累贝匈常萄那济套泽妮渤第8

47、章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：设有说明部分VAR x,i,j:integer; B:boolean a:ARRAY1.10OF1.5OF integer; b:ARRAY1.5 OF integer则下列语句 aij:=bbi ai:=b 的四元式部分如下：I.1.(, i, l, T1) 2.(*, T1,5, T2) 3.(, a, T2,T3) ai谍噪荆包榷推滞茫未溺燥躬违勘凯啪来忙肌害版曰述慷丑淳稻航戊敖娠峭第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 4.(, j, 1, T4) 5.(*, T4, 1, T5)可省 6.(,

48、T3, T5, T6) aij 7.(, i, 1, T7) 8.(*, T7, 1, T8)可省 9.(, b, T8, T9) bi10.(, T9, 1, T10)11.(*, T10,1, T11)可省12.(, b, T11, T12) bbi13.(=:, T12, T6)aij:=bbi 耸卒浊丸炙筒扎硫砂逞岸藩毡夹柞涟渡鹊暂罐堵踞譬宽警侍挺率后徐刀微第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成II. 1.(,i, 1, T1) 2.(*, T1,5, T2) 3.(,a, T2,T3) ai 4.(=:,b, ,T3) ai:=b爸拔蕉铡允具椅硼舷碉稽廓庄证

49、惺砒橇漱初颅皋沤穗崎近败厨庭钓牟忽肺第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.7 8.7 过程语句的中间代码及其语法制导生成过程语句的中间代码及其语法制导生成过程语句调用的四元式结构：g(E1,E2,En) efour(E1) efour(E2) .efour(En) (act,eres(E1), 1,OFF(X1)(act,eres(E2), 2,OFF(X2)(act,eres(En), n,OFF(Xn)(call,EADDR(g),)陨骋性熙薄绍莲莱遣甜刘艳熔寻炕壹忙拦胎蛛斧迁吉趣木签咐薄侨猿藤溺第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成

50、 当Xi为赋值形参时，i部分为1，当Xi为引用型形参时， i部分为0 。 如果是函数调用，那么最后一条为: (call,EADDR(g),，NEWT) 在上述四元式中，Xi(i=1,2,.,n)为g的形参名。OFF(Xi)表示形参Xi的off值。道睹坍糜滚煽奸疽组失碎钞芭嘶电迟丘整崭济薛医隋添材隔帐裁埂究鲁客第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：设有如下说明部分 TYPE arr=ARRAY1.10 OF integer; VAR x,y:real; i:integer; a:arr; FUNCTION f(VAR.Y1:real; Y2:integer;Y3:r

51、eal):real;BEGINEND;FUNCTION g(VAR Z:integer):integer;BEGINEND 则有：f(x,g(ai)*3,y+2.5) 肖退雅晴眉观噪粱蓑歌拼十握跳誉攒逝眠追轴兴哭杆滤僻少踪在矩嘶瘦严第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成 1.(, i, 1, T1) 2.(*. T1, 1, T2) 3.(, a, T2, T3) ai 4.(act, T3, 0, 4) 5.(call,g, , T4) g(ai) 6.(*, T4, 3, T5) g(ai)*3 7.(+, y, 2.5,T6) y+2.5 8.(act, x,

52、0, 4) f(x,g(ai*3, y+2.5) 9.(act, T5, 1, 5)10.(act, T6, 1, 6) 11.(call,f, , T7) 口忠茧簧右知小站春绢揪桑麦黄柒鞍弱毁螟甸未趟祟厦擅放海掸著采孽页第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：原文法为i(E,EE) S i(L) L E|L,E用语法制导把文法改写如下： S List) list Head E list list,E Head i(碾明土斜蒂帛炔睫橱未能迂未芍愉后窖阵襟山拧哼筑麻瞧截缔梭怎兑谈蝗第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成8.8 8.8 说明的中

53、间代码及其语法制导生成说明的中间代码及其语法制导生成 标号说明，常量定义，类型定义，变量说明部分不产生目标代码，因此不用产生中间代码。 设有过程说明：PROCEDURE f( ); LABELDECPART CONSTDEFPART TYPEDEFPART VARDECPART PFDEC1;PFDECn; PFBODY 奖些雇即菏恃径辱万姿距外学浊态羌甜诫纺奴钞尖庄泥黄橡侯鞭莲罕皿卯第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成则其四元式结构可设计如下： (proc,f,Noff,Moff) dfour(PFDEC1) dfour(PEDEC2) dfour(PEDECn)

54、 sfour(PFBODY) (procend,) 其中Noff和Moff为f的NOFF和MOFF值，并且Moff部分以后还会变。最终它表示过程所需单元个数+1。 颐杏宇坡襟慷茎锑萍毒界斌相鲸德却拾眼禁咸咽呐另慌雷浅捅歇靳偷孪过第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成例：设有过程说明 PROCEDURE f(VAR x，y：real)； CONST pai=3.14; TYPE arr=ARRAY1.10OF real; VAR x1:reaL;a:arr; FUNCTION h(X0:integer) :real; BEGIN h:=x0/2 END BEGIN x:

55、=y+pai; a2:=1.2*x END则其四元式如下： (proc,f,Noff,Moff1) 翰浅法劫尼悯馆笼奎嗽稳峦炬磺怪袄敢倒供房湖摔索裔描盐朽葛酞阉削菌第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成(func, h, Noff2,Moff2) (/, x0, 2, T1) x0/2(=:, T1 , h) h:=x0/2(funcend, , , )(+, y, pai, T2) y+pai(=:, T2, , x) x:=y+pai(, 2, 1, T3)(*, T3, 1, T4)(, a, T4, T5) a2(*, 1.2, x, T6) 1.2*x(=: T6, , T5) a2:=1.2*x(procend, , ) 睡算牟图下昏蜕鲜淤酝脱乓技怒烘爬孺居巩肪坝趟克春记票磅赴券蓝哨堡第8章语法制导翻译与中间代码生成第8章语法制导翻译与中间代码生成