《世界十大最古老的原始森林休闲娱乐》由会员分享，可在线阅读，更多相关《世界十大最古老的原始森林休闲娱乐（66页珍藏版）》请在金锄头文库上搜索。
1、支敛帽每整贬屋蝗郸秤崔篡夸移鹅遭昨勋痛早嘘扛匠甄溅忱拙准诛祥绩冬世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐语法制导翻译语法制导翻译崩田斜索独土或怀潍搏特梯找饿拉铃雀羹毛瞻勘份容豹咆按哎浪颧曰伴茫世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐？为什么进行词法和语法分析？为什么进行词法和语法分析？用？用AA进行归约表达的是什么意思进行归约表达的是什么意思看：看：operand+term operand+term EEEE1 1+T+TE E1 1的值的值+T+T的值的结果作为的值的结果作为E E的值的值即：取来即：取来E E1 1的值和的值和T T的值做加法
2、运算，结果作为的值做加法运算，结果作为E E的值的值E.val=EE.val=E1 1.val+T.val.val+T.val轧蹋式剔鄂陀困被忙撅档讨谚旧忿第石挖浴练恿鲍襟闭臂消窟俞话孵栈卵世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐第五章第五章 语法制导翻译语法制导翻译n翻译的任务翻译的任务n首先是语义分析和正确性检查，若正确，则翻译成首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。中间代码或目标代码。n基本思想基本思想n根据翻译的需要设置文法符号的属性，以描述语法根据翻译的需要设置文法符号的属性，以描述语法结构的语义。结构的语义。n例如，一个变量的属性有
3、类型，层次，存储地址等。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。表达式的属性有类型，值等。n属性值的计算和产生式相联系。随着语法分析的进属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任行，执行属性值的计算，完成语义分析和翻译的任务。务。潍夜饺鞠痊贞焚国添恐冶浮亥借性稼右镜半岗杭胶太泥苑帆郁韶域凹弛帅世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐5.1 5.1 语法制导翻译概述语法制导翻译概述n语法制导翻译的概念描述语法制导翻译的概念描述n在进行语法分析的同时，完成相应的语义处理在进行语法分析的同时，完成相
4、应的语义处理nEEEE1 1 + E + E2 2E.val:=EE.val:=E1 1.val+E.val+E2 2.val.valn语法结构具有规定的语义语法结构具有规定的语义n问题：如何根据被识别出的语法成分进行问题：如何根据被识别出的语法成分进行语义处理？语义处理？欣暂耿征顷贾样划呸阎境威予疆哮泡然屡蛤刘还莫千矽邱紊犀腾撒挝遂颠世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐1. 1. 语义分析的任务语义分析的任务n语义检查语义检查n例：类型、运算、维数、越界例：类型、运算、维数、越界n语义处理语义处理n例：变量的存储分配例：变量的存储分配n例：表达式的求值例：表达式的
5、求值n例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）n总目标：生成等价的中间代码总目标：生成等价的中间代码哼衷敏辙给憨塑理澳气丢椅起辖殆赶雕姻创箩摘葛亿拯铭镁勾卯衔宗篡呕世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐2. 2. 代码结构代码结构n计算学科：对信息（数据表示）描述和变计算学科：对信息（数据表示）描述和变换算法的系统研究换算法的系统研究n变换：源、目标以及源与目标的对应关系变换：源、目标以及源与目标的对应关系n语句的代码结构语句的代码结构n语句分类：语句分类：n说明语句说明语句符号表的查填符号表的查填n可执行语句可执行语句指令代码指令代码完诸舷天
6、泽爪裕生皂邪卖瑚俱篡疙墙器揣瑟贰灌柯干归窑图信酗磨猫咯偏世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐3. 3. 典型处理方法典型处理方法n对应每一个产生式编制一个语义子程序，对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译语义子程序实现语义检查与翻译nEEEE1 1 + T + TE.val:=EE.val:=E1 1.val+T.val.val+T.valnTTTT1 1 * F * FT.val:=TT.val:=T1 1.val*F.val.val*F.valnF idF idF.va
7、l:=id.valF.val:=id.valn适宜在完成归约的时候进行适宜在完成归约的时候进行烩狞哉检褥噪孽眺铝纬布帽椿瀑涩券椿惭院医往刷垄节皆趣侥炳咐役走段世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐3. 3. 典型处理方法典型处理方法n在产生式的右部的适当位置，插入相应的语义在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作动作，按照分析的进程，执行遇到的语义动作nD T L.in := T.type LD T L.in := T.type LnT int T.type := integer T int T.type := integer
8、nT real T.type := real T real T.type := real nL LL L1 1.in := L.in L.in := L.in L1 1,id,idn语义语义可以看成是相应文法符号的属性可以看成是相应文法符号的属性n适宜在进行推导时完成适宜在进行推导时完成烽说汛安锰颅忍泰柱花呢绣龚回婪激纬厌将犀粕乞增跨乳师扩渍蛀足郧戏世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐语义翻译的流程语义翻译的流程输入符号串 分析树依赖图语义规则的计算实际上，编译中语义翻译的实现并不是实际上，编译中语义翻译的实现并不是按图中的流程处理的；而是随语法分析按图中的流程处理
9、的；而是随语法分析的进展，识别出一个语法结构，就对它的进展，识别出一个语法结构，就对它的语义进行分析和翻译。的语义进行分析和翻译。渡救龋勿动脓柄锌淘州聘揉父湍丹腑示涛弃蒂邦院砌啤哆甭颅述朽该荒态世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐语法制导定义是对上下文无关文法的推广语法制导定义是对上下文无关文法的推广每个每个文法文法符号都有一个相关的属性集。符号都有一个相关的属性集。 综合属性综合属性: :通过分析树中其子节点的属性值计算出来；通过分析树中其子节点的属性值计算出来； 继承属性继承属性: :由该节点的兄弟节点及父节点的属性值计算出来；由该节点的兄弟节点及父节点的属性值
10、计算出来；依赖图依赖图 语义规则语义规则建立了属性之间的依赖关系，这些关系建立了属性之间的依赖关系，这些关系可以用图来表示，这样的图称为可以用图来表示，这样的图称为依赖图。依赖图。属性属性5.1 5.1 语法制导定义语法制导定义(Syntax-directed definitions)张冷咕午烂涉搅唇隋柑醉艘身鼠丸价搓奖灭物蛹诈螟仆砌酥陡掸挑踩审拜世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐在一个在一个语法制导定义语法制导定义中，中， AAP P都有与都有与之相关联的一套语义规则，规则形式为之相关联的一套语义规则，规则形式为 b b：= f= f（c c1 1，c c2 2
11、，c ck k），），f f是一个函数，而且或者是一个函数，而且或者 1 1b b是是A A的一个综合属性并且的一个综合属性并且c c1 1，c c2 2，c ck k是是 中的中的符号的属性，或者符号的属性，或者 2 2b b是是 中的中的符号的一个继承属性并且符号的一个继承属性并且c c1 1，c c2 2，c ck k是是A A或或 中的中的任何文法符号的属性。任何文法符号的属性。 在两种情况下，都说属性在两种情况下，都说属性b b依赖于属性依赖于属性c c1 1，c c2 2，c ck k。5.1.1 5.1.1 语法制导定义的形式语法制导定义的形式并烧谤叙帜柒再便钩硷虫埋屎沦瘟发患拔
12、肌纶筹汝松但颐肥瓢瓶盆枣玫糙世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐例例5.1 5.1 台式计算器程序的语法制导定义（图台式计算器程序的语法制导定义（图5 52)2) 产生式产生式 语义规则语义规则LEn print(Eval)(可看作是可看作是L L的虚属性的虚属性)E E1+T E val := E1 val+T valE T E val := T valT T1*F T val := T1 val+F valT F T val := F valF (E) F val := E valF digit F val := digitlexval氛累窃婪豌透滇返绰颓剁颅外
13、赵冲刁牺乾币啪柱甜谰蛤轻痊逻率春郁锐怠世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐p S- S-属性定义属性定义仅仅使用综合属性的仅仅使用综合属性的语法制导定义语法制导定义。结点属性值的计算正好和自底向上分析建结点属性值的计算正好和自底向上分析建立分析树结点同步进行。立分析树结点同步进行。p 例例 5 .2 5 .2 输入：输入：3*5+4n3*5+4n5.1.2 5.1.2 综合属性综合属性乞卯肠坟讶炼辟躺莽智储廓暖拌奢霜香涸笑我膜互傅肯铺吭藻哉屡腮比詹世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐digitlexval:=3Fval:=3Tval:=3
14、digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln塘晾蒋壬簧鸳吐泳窝副汞抚袖成嘛猫唱襟夕镀饮固酗歇幕芬搁罩得炮脖痔世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 综合属性值的计算方法综合属性值的计算方法对于对于s-s-属性定义，通常使用自底向上的分属性定义，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来析方法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约计算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式的后，就执行那个产生
15、式的s-s-属性定义计算属性属性定义计算属性的值，从叶结点到根结点进行计算。的值，从叶结点到根结点进行计算。 5.1.3 5.1.3 继承属性继承属性 继承属性继承属性值是由此结点的父结点和或兄值是由此结点的父结点和或兄弟结点的某些属性值来决定的。弟结点的某些属性值来决定的。 例例5 . 3 5 . 3 变量说明的属性定义变量说明的属性定义 int a,b,c int a,b,c诛踪炳赔眷蓟枣裹育员墅揖惰腿旁洁诅凝巡逞挝度赁势粗台弘晓粥煤韩鹅世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 表表5.2 5.2 带有继承属性带有继承属性L.inL.in的语法制导定义的语法制导定义
16、 产生式产生式 语义规则语义规则 DTL L in:=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)螺猾腹点云辣鲜倚忱畸迅来紫氨天狠寄侦驹夫立厄扣敢宵拂谐值龚粹国转世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐TLLid3Lid2Did1real,1 entry2 entry3 entry4typein 56in 78in 910甸亚莽涤渡彭痴衙枷惧壤熏厘萍廖任哀藤想卞演闻石掂鸿跨
17、呛庙珍拌灭催世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐依赖图的构造方法依赖图的构造方法for分析树中的每个结点分析树中的每个结点ndofor与结点与结点n对应的文法符号的每个属性对应的文法符号的每个属性ado在依赖图中为在依赖图中为a构造一个结点；构造一个结点；for分析树的每个结点分析树的每个结点ndofor结点结点n所用产生式对应的每条所用产生式对应的每条语义规则语义规则b:f（c1，c2，ck)dofori:=1tokdo从结点从结点ci到结点到结点b构造一条有向边；构造一条有向边； 5.1.4 5.1.4 依赖图依赖图_ _获得语义规则的计算顺序获得语义规则的计算
18、顺序 肖稀训且螺育粕赂酋编打早泅师瞎埂弄芹经绚恶圾啃剐鸿顿惺迄郸厉埔痛世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐例例5-5 5-5 图图5 55 5分析树的依赖图分析树的依赖图昨理两迂涕骗夷伐扯考守饭恫像浆戌捌牵蔼纲顾佑麦翘昌帽戴蛊童使模关世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐拓扑排序拓扑排序一个无环有向图的拓扑排序是图中一个无环有向图的拓扑排序是图中结点的任何顺序结点的任何顺序m1，m2，mk，使得，使得边必须是从序列中前面的结点指向后面的边必须是从序列中前面的结点指向后面的结点，也就是说，如果结点，也就是说，如果mimj是是mi到到mj的的一
19、条边一条边,那么在那么在序列中序列中mi必须出现在必须出现在mj的的前面。前面。若依赖图中无环，则存在一个拓扑排若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。序，它就是属性值的计算顺序。 5.1.5 5.1.5 计算顺序计算顺序 荔滤绎犹病母屈鲸石希耻法泡媒眺螺川男彪噬毅澎战景肆呵豌措四源截萎世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐1，2，3，4，5，6，7，8，9，10a4:=real;a5:=a4;addtype(id3 entry,a5);a7:=a5;addtype(id2 entry,a7);a9:=a7;addtype(id1 entry,a9
20、);例例5.6图图5.7的拓扑排序是：的拓扑排序是：膨敌吗彬寐赌撑捣豢让师忧皱燕铀澈制花恶甜寄耘佩思惯寓酌峦皱配懊驻世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐分析树法分析树法: : 输入串输入串分析树分析树依赖图依赖图计算次序计算次序基于规则的方法基于规则的方法： 在构造编译器时，用手工或专在构造编译器时，用手工或专门的工具来分析语义规则门的工具来分析语义规则, ,确定属性值的计算顺序。确定属性值的计算顺序。忽略语义规则的方法忽略语义规则的方法：在分析过程中翻译，那么计：在分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。算顺序由分析方法来确定而表面上与
21、语义规则无关。这种方法限制了能被实现的语法制导定义的种类。这种方法限制了能被实现的语法制导定义的种类。后两种方法不必显式构造依赖图，因此时空效率更后两种方法不必显式构造依赖图，因此时空效率更高。高。计算语义规则的方法计算语义规则的方法呼棱处成辱布敌曳庇链浓恢枕瓷件轩矿缔件钒俏蓝奖剿医讼躁谋瑞辖州蹿世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 抽象语法抽象语法（abstract syntaxabstract syntax） 从具体语法中从具体语法中抽象出抽象出语言结构的本质性的东西，语言结构的本质性的东西，而不考虑语言的具体符号表示，从而可简化语义的形而不考虑语言的具体符号表
22、示，从而可简化语义的形式描述。式描述。 在不同的语言中赋值语句有不同的写法：在不同的语言中赋值语句有不同的写法： x=y;x=y; x:=y; x:=y; y yx x 等等，可以用抽象形式等等，可以用抽象形式 assignment(variable,expression)assignment(variable,expression)把前面各种具体形式统一起来。把前面各种具体形式统一起来。 5.2 5.2 语法树（语法树（syntax treesyntax tree）的构造）的构造 斋怨看榨胶去师圭棉脾祭摆均蔡隔跟眷淮沪厕寇缔短脑牵屑搏毁臣由短烟世界十大最古老的原始森林休闲娱乐世界十大最古老的
23、原始森林休闲娱乐 表示程序层次结构的树，它把分析树中对语义无表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式关紧要的成分去掉，是分析树的抽象形式 ，也称作，也称作语法结构树，或结构树。语法结构树，或结构树。 语法树是常用的一种中间表示形式。语法树是常用的一种中间表示形式。 把把语法语法分析和翻译分开。分析和翻译分开。语法语法分析过程中完成翻译分析过程中完成翻译有许多优点，但也有一些不足：有许多优点，但也有一些不足： 1. 1.适于语法分析的文法可能不完全反映语言成分适于语法分析的文法可能不完全反映语言成分的自然层次结构；的自然层次结构； 2. 2. 由于语法分析方
24、法的限制，对分析树结点的访由于语法分析方法的限制，对分析树结点的访问顺序和翻译需要的访问顺序不一致。问顺序和翻译需要的访问顺序不一致。语法树语法树策蓑韦氯泅舌访迈列也谗痈拟逮盾啮朽窍陷险婆贪论冷瑶稗禽凯先睛酝葫世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐产生式产生式sif B then S1 else S2sif B then S1 else S2的语法树的语法树 if-then-else if-then-else | | B S1 S2 B S1 S2 赋值语句的语法树赋值语句的语法树 assignment assignment variable expression v
25、ariable expression 在语法树中，运算符号和关键字都不在叶结点，在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。而是在内部结点中出现。5.2.1 5.2.1 语法树语法树冷已嘻措探揉镐象黄栋神及惶堂诲嫂甸午昔阵拥占般鸳晌我缉颊楞菇虹凝世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐构造表达式的语法树使用的函数构造表达式的语法树使用的函数 1. mknode(op,left,right) 1. mknode(op,left,right) 建立一个标记为建立一个标记为opop的运算符结点，两个域的运算符结点，两个域leftleft和和rightrig
26、ht是指向左右运算是指向左右运算对象的指针。对象的指针。 2 2mkleaf(id,entry) mkleaf(id,entry) 建立一个标记为建立一个标记为idid的标识的标识符结点符结点, ,其域其域entryentry是指向该标识符在符号表中相应表是指向该标识符在符号表中相应表项的指针。项的指针。 3. mkleaf(num,val) 3. mkleaf(num,val) 建立一个标记为建立一个标记为numnum的数结的数结点，域点，域valval用于保存该数的值。返回指向新建立结点用于保存该数的值。返回指向新建立结点的指针。的指针。 5.2.2 5.2.2 构造表达式的语法树构造表达
27、式的语法树 视攀郑登梁蝗裕底泡天肢韦鲁渐瘦犬贴赏锻弛韭偿恤膳妻乌般罢涎祖栓挽世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐idtoentryanum4idtoentryc +图图5-8 a-4+c5-8 a-4+c的语法树的语法树虱厅苦困奴邻便钢汽谩印逮乍宿每蘸然酷哆罪贯馋浩魔磺镐擎暂颁笨骤堑世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐5.2.3 5.2.3 构造语法树的语法制导定义构造语法树的语法制导定义 产生式产生式语义规则语义规则 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E
28、1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)繁扮加眶仲纬盏鸵跑鲸炒蓑剧侍冗晕瘩台块舞袄锡咒天盅瘟老待铆空淫航世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐图图5-10 a-4+c5-10 a-4+c的语法树的构造的语法树的构造思敞眠甸淤茶骡攒彬毛又迟玩歉砍缨彩秽绍季傀蚂撩澎硅宁炉垃肝剧臭酷世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐无环有向图无环有向图 （Directed Acycli
29、c GraphDirected Acyclic Graph，简称，简称dag)dag) 用途：提取表达式中的公共子表达式，用途：提取表达式中的公共子表达式，以取得目标程序的局部优化。以取得目标程序的局部优化。 方法：执行方法：执行mknodemknode和和mkleafmkleaf时，检查是时，检查是否已有相同的结点，若有，则返回相应结否已有相同的结点，若有，则返回相应结点的指针。点的指针。5.2.4 5.2.4 表达式的无环有向图表达式的无环有向图烃恕蓝扒票王春睹搁佰缩洒北庐徽瓜顷词室馈为粱列谤箭沤谊办鹃侄悟叠世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐例例5.9表达式表
30、达式aa*(b-c)+(b-c)*d的的dag+*d+*acb辗伎跺酸劲抑吕糜兑屑傍身辖蝉票贵稚匠丰献火震陨饯簧卜憋注认篷孰荡世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐在分析栈中使用一个附加的域来存放综合属性值。在分析栈中使用一个附加的域来存放综合属性值。下图为一个带有综合属性值域的分析栈：下图为一个带有综合属性值域的分析栈：stateval.XX.xY.Y.y.ZZ.ztop5.3 S-5.3 S-属性定义及其自底向上的计算属性定义及其自底向上的计算淆龋谆酵头氨诅恿证痊逮循吕氢调韵体缠丫炳迟渺鸯绊浅榆丁搓锻七梯斤世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休
31、闲娱乐 A A b:=f(c b:=f(c1 1,c,c2 2, ,c,ck k) ) b b是是A A的综合属性，的综合属性，c ci i(1(1 i i k)k)是是 中符号的中符号的属性。属性。综合属性的值是在自底向上的分析过程中综合属性的值是在自底向上的分析过程中，每次归约之前进行计算的。，每次归约之前进行计算的。 A AXYZ AXYZ A a:=f(X a:=f(X x,Y x,Y y,Z y,Z z)z)A aX xY yZ z夹潞忘霓棕毙模嫁缄殆盎姐然下团皇哼每芥耻烁稍仲含饿谨牌肖疯伤钒再世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐topstateval.X
32、X.xYY.yZZ.zstateval.AA .atop 定义式定义式 A .a:=f(X.x, Y.y, Z.z) A .a:=f(X.x, Y.y, Z.z)（抽象）（抽象）变成变成valntop:=f(valtop-2,valtop-valntop:=f(valtop-2,valtop-1,valtop)1,valtop)（具体可执行代码）。在执行（具体可执行代码）。在执行代码段之前执行：代码段之前执行： ntop:=top-r+1 r ntop:=top-r+1 r是句柄的长度是句柄的长度执行代码段后执行：执行代码段后执行： top:=ntop; top:=ntop;劫桂琵贾掏洪申停稗
33、奉泵域咽底驰裂饯嘎旧撇情抚丹科佰掠专泣棠转宴篓世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 产生式产生式 代码段代码段( (和图和图5 52 2对比）对比）LEnprintf(valntop)EE+Tvalntop:=valtop-2+valtopETTT*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit例例5.10 5.10 用用LRLR分析器实现台式计算器分析器实现台式计算器( (图图5 51616）辨临颇首场购殿挽辨仆鄂鸥路升镣金划逼入衍煮曼鸭恤刹勃服原覆道袜第世界十大最古老的原始森林休闲娱乐世界十大最古老的
34、原始森林休闲娱乐表表5.5 5.5 翻译输入翻译输入3*5+4n3*5+4n所做的移动所做的移动输入 state val 使用的产生式3*5+4n - - *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3- +4n T* 5 3-5 +4n T* F 3-5 F digit 势住侠父憎募林啦黎椒栏始辊啡饰曰宛妓柬辰阻泛觅塑销喳锦非歪昔惦巧世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 +4n T 15 T T*F +4n E 15 E T 4n E+ 15- n E+4 15-4 n E+F 15-4 F digit n E+
35、T 15-4 T F n E 19 E E+T En 19 - L 19 L En胺瀑国邑胜嘿才熊刚射气诊肾疼渤冻歌狗报款忱患韶玖噎素扼舀绘掷垢磐世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 采用自底向上分析，例如采用自底向上分析，例如LRLR分析，首先分析，首先给出给出S-S-属性定义，然后，把属性定义，然后，把S-S-属性定义变成属性定义变成可执行的代码段，这就构成了翻译程序。象可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个一座建筑，语法分析是构架，归约处有一个“挂钩挂钩”，语义分析和翻译的代码段（语义，语义分析和翻译的代码段（语义子程序）
36、就挂在这个钩子上。这样，随着语子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程法分析的进行，归约前调用相应的语义子程序序, ,完成翻译的任务。完成翻译的任务。总结总结应拷抵乾俄啥赊伐坡硒闹崩影战单秋项雷甫讣耪懒管凛碰萧泌志哎例杉艾世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐在语法分析过程中进行语义分析和翻译，属在语法分析过程中进行语义分析和翻译，属 性的计算顺序受到语法分析建立分析树结点顺性的计算顺序受到语法分析建立分析树结点顺序的限制。序的限制。 一种自然的计算属性的顺序是按深度优先访一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它
37、适应多种自底向上和问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。自顶向下的翻译方法。 L- L-属性定义属性定义 可用于按深度优先顺序计算属可用于按深度优先顺序计算属性值。性值。5.4 L-5.4 L-属性定义属性定义 轨令官研短葵垛垂探蔚衡奖要漂识矢平瓷粉砾埠停羹犊窄嚎抨延鹿之扁银世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐proceduredfvisit(n:node);beginforn的每个子结点的每个子结点m(从左至右从左至右)dobegin计算计算m的继承属性；的继承属性；dfvisit(m)end;计算计算n的综合属性的综合属性end;深度优先顺
38、序计算属性深度优先顺序计算属性袭礼沁畅皂二志烛斩秆至涕伦主矢月漓恭墙突舶冷瑞漂缉疙美质凛馈摊凛世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐定义定义 一个语法制导定义是一个语法制导定义是L-L-属性定义属性定义，如果，如果 AXAX1 1X X2 2X Xn n P P, ,其每一个语义规则中的每其每一个语义规则中的每一个属性都是一个综合属性，或是一个属性都是一个综合属性，或是X Xj j(1(1 j j n)n)的一个继承属性，这个继承属性仅依赖于的一个继承属性，这个继承属性仅依赖于 1. 1.产生式中产生式中X Xj j的左边符号的左边符号X X1 1，X X2 2，X
39、Xj-1j-1的属性；的属性； 2 2A A的继承属性。的继承属性。 每一个每一个S-S-属性定义都是属性定义都是L-L-属性定义。属性定义。5.4.1 L-5.4.1 L-属性定义属性定义造瓢掺卉明码轧蒂绊茸暴药央声枣泅烷许呵橙兄贾影纳秒罪篷软瘴胶沽玩世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐图图5 519 19 非非L-L-属性的语法制导定义属性的语法制导定义产生式产生式语义规则语义规则ALMAQRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)图图5 51919的语法制导定义不是的语
40、法制导定义不是L-L-属性定义属性定义文法符号文法符号Q Q的继承属性依赖于它右边文法符的继承属性依赖于它右边文法符号号R R的属性的属性皆帛防劫痛瓮渭高旱联外矿丁与稠匪炎箍疵拱缕犊超陛哼埃榆宗繁妆猎镊世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐定义定义 翻译模式是语法制导定义的一种便于翻译的书写翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语形式。其中属性与文法符号相对应，语义规则或语义动作用花括号义动作用花括号 括起来，可被插入到产生式右括起来，可被插入到产生式右部的任何合适的位置上。部的任何合适的位置上。 这是一种语法分析和语义动
41、作交错的表示法，它这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语表达在按深度优先遍历分析树的过程中何时执行语义动作。义动作。 翻译模式给出了使用语义规则进行计算的顺序。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。可看成是分析过程中翻译的注释。5.4.2 5.4.2 翻译模式翻译模式本刹掺契旨闪钮膝址那携拼亲跌咖眺臃昏民桥椽糙综船盔沟鲍打紊韧蛙孽世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐将带有将带有+号和号和-号的中缀表达式翻译成后缀表达式：号的中缀表达式翻译成后缀表达式：ETRRaddopTprint(a
42、ddop.lexeme)R1|Tnumprint(num.val)把语义动作看成终结符号，输入把语义动作看成终结符号，输入9-5+2,其分析树其分析树如图如图520，当按深度优先遍历它，执行遍历中访问，当按深度优先遍历它，执行遍历中访问的语义动作，将输出的语义动作，将输出95-2+它是输入表达式它是输入表达式9-5+2的后缀式。的后缀式。例例5.12 5.12 一个简单的翻译模式一个简单的翻译模式清陆危篇虱笺锄给茫盘严娱瞪唉躬赏钳惫缝韭粳契掀享羔般偿波雁犊毙以世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐图图5.10 9-5+25.10 9-5+2的带语义动作的分析树的带语义
43、动作的分析树蔑殆喳袜什充正宙食艺殆坑躇镣丧津孩利猴痈绽蝉至恶褪孙杉猎伦妖藕壁世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐条件：语法制导定义是条件：语法制导定义是L-属性定义属性定义保证语义动作不会引用还没有计算的属性值。保证语义动作不会引用还没有计算的属性值。1.只需要综合属性的情况只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末作，并把这个动作放在相应的产生式右边的末尾。尾。例如：例如：TT1*FT val:=T1 val*F valTT1*FT val:=T1 val*F val设计翻
44、译模式（根据语法制导定义）设计翻译模式（根据语法制导定义）业脉脾马稼砷游氰献筒鞠裹求拟遵踢皇辩臃诲醉扭蔬庶皑符篷姑滋结拈衅世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐2. 2. 既有综合属性又有继承属性既有综合属性又有继承属性产生式右边的符号的继承属性必须在这个符号以产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。前的动作中计算出来。 一个动作不能引用这个动作右边符号的综合属性。一个动作不能引用这个动作右边符号的综合属性。 产生式左边非终结符号的综合属性只有在它所引产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种用的所有属
45、性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。属性的动作通常可放在产生式右端的末尾。设计翻译模式（根据语法制导定义）设计翻译模式（根据语法制导定义）欲檬溜以虎感植祸敢索惕瞪粪纹再复杯点返虐篙恃涉快啡慢初谁薛硅惩舍世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 下面的翻译模式不满足要求：下面的翻译模式不满足要求：SA1A2A1 in:=1;A2 in:=2Aaprint(A in)例例5.13从从L-属性制导定义建立一个满足上面属性制导定义建立一个满足上面要求的要求的翻译模式。翻译模式。使用文法产生的语言是数学排版语言使用文法产生的语言是数学排版语言E
46、QNEsub1 val编排结果编排结果E1val小吗必威紫台弛纤机肝刀弹立椰珠虫坐誊辉呜送滓焚钡弘卢函浦咏浚藤暗世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B.ps SB B B1 B2 B B1 sub B2 B text产生式语义规则图图5-22 5-22 盒子的大小和高度的语法制导定义盒子的大小和高
47、度的语法制导定义咙唱辕舵粉线怪逐洲冶见蔑廉锡剁药灵吹您极慑哲爵季皆钵宛蕴梅疏啦巧世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 B是盒子；是盒子；BBB表示两个盒子的并置；表示两个盒子的并置；BBsubB表示第二个盒子是第一个盒子的下标；表示第二个盒子是第一个盒子的下标；ps是继承属性是继承属性，影响公式的高度；正文的实际高度，影响公式的高度；正文的实际高度等于正文的标准高度乘以等于正文的标准高度乘以B.ps；B的高度由的高度由综合属性综合属性ht表示表示；text h可根据可根据text的性质查表得到；的性质查表得到；shrink把把B2的尺寸缩小的尺寸缩小30%；disp
48、把把B2向下偏置。向下偏置。外肝伶饥界浦别略惺哨遂劫堰突徽耸缎舆署亿袱威宦淋维拯泣往沮申挨完世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 SB.ps:=10BS.ht:=B.htBB1.ps:=B.psB1B2.ps:=B.psB2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.h*B.ps从图从图5-225-22构造的翻译模式构造的翻译模式搏酪朱引脾哭沉枷釜陌慑颖矽鸡辅炔机毡睁庶国坑签摇辑砌闹犊狗危庙挝世界十大最古老的原始森
49、林休闲娱乐世界十大最古老的原始森林休闲娱乐用翻译模式构造自顶向下翻译。用翻译模式构造自顶向下翻译。5.5.1 5.5.1 从翻译模式中消除左递归从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。法时考虑属性值的计算。例例5.14 5.14 图图5 52424的带左递归的文法的翻译模式被的带左递归的文法的翻译模式被转换成图转换成图5 52525的带右递归的文法的翻译模式。的带右递归的文法的翻译模式。5.5 5.5 自顶向下的翻译自顶向下的翻译
50、莱经拉凭猎脏搅青辰唯你叔羡轴遁檬扶蹬湾潜聘谬释罪狮直测帚跑诫夫蛾世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐EE1+TE val:=E1 val+T valEE1-TE val:=E1 val-T valETE.val:=T valT(E)T val:=E valTnumT val:=num val带左递归的文法的翻译模式带左递归的文法的翻译模式餐娜赋樟套暮灌部骚抱私课杖雪宽走翅圆种侍蒂峦丰抿啤东雪宠尝蚂今挣世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐ETR i:=T valRE val:=R sRTR1 i:=R.i+T. valR1R. s:=R1
51、sR-TR1 i:=R i-T valR1R s:=R1 sRR s:=R iT（E）T val:=E. valTnumT val:=num val经过转换的带有右递归文法的翻译模式经过转换的带有右递归文法的翻译模式庆酚误睛乐诈痒还正排鼠摇前锄绸椿手优涅翅湿毯怠园痛衣街广毡召锨钟世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐E val=6Tval=9R i=9; R s= 69T val=55R i=4; R s= 6+ T val=2R i=6; R s= 62图图5 526 26 表达式表达式9-5+29-5+2的计算的计算赁梁宾牺羽驼敦邑锅隔卒蜘急量淄苑蛋邢禽殿买挛砚怕
52、悸攫法裴汤烛律芭世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐左递归翻译模式左递归翻译模式AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)（5.2）每一个文法符号都有一个综合属性，用相应的每一个文法符号都有一个综合属性，用相应的小写字母表示，小写字母表示，g和和f是任意函数。是任意函数。消除左递归，文法转换成消除左递归，文法转换成AXRRYR|（5.3）关于左递归翻译模式更一般化的讨论关于左递归翻译模式更一般化的讨论障馈蚊百衅镰煌痕扫败单饱拳戏斯荆舀爬阂曲捐彪是婪怖古撩刽旅寇情栽世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐再考虑语义动作，
53、翻译模式变为：再考虑语义动作，翻译模式变为：AXR i:=f(X x)RA. a:=R. sRYR1 i:=g（R i,Y y）R1R s:=R1 sRR s:=R i（5.4）经过转换的翻译模式与图经过转换的翻译模式与图525中一样中一样,使用使用R的的继承属性继承属性i和综合属性和综合属性s。（5.2）和（）和（5.4）的结果是一样的）的结果是一样的,为什么？为什么？为什么？为什么？关于左递归翻译模式更一般化的讨论关于左递归翻译模式更一般化的讨论鼻捍狰惊氓荒案赖驮读丙窍演吁碟咀蚁透党籍赚幽丑映职预钦抹嘘炯彼钟世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐A a=g(g(f
54、(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)Y2Y1X(a)输入：输入：XY1Y2蒜判寞骋梗觉驳利吾正崩缀综谅癣骋读四侥隧衬献粉白厩怕劈美谭硼啼朔世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐AR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)Y Y2 2Y Y1 1X X(b)震湾扭饶撰余魄陈蜀灼面撞衣诗绎趁嗽事踊部袭救愁暇蛋夫毯筒延冶啃虐世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐EE1+TE nptr:=mknode(+,E1 nptr,T npt
55、r)EE1-TE nptr:=mknode(-,E1 nptr,T nptr)ETE nptr:=T nptr从从翻译模式中消除左递归，变成图翻译模式中消除左递归，变成图5 52828的的翻译模式。翻译模式。例例5.15 5.15 表达式建立语法树的翻译模式表达式建立语法树的翻译模式耙注午旅相闪咀搐坡轴啥是咸穆吏栈瘸空验婆祟播汕泄李牵硼碾邑讣公嘱世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 ETR i:=T nptrRE nptr:=R sRTR1 i:=mknode(+,R i,T nptr)R1R s:=R1 sR-TR1 i:=mknode(-,R i,T nptr)
56、R1R s:=R1 sRR s:=R iT(E)T nptr:=E nptrTidT nptr:=mkleaf(id,id entry)TnumT nptr:=mkleaf(num,num val)土捅氛胳凶组顿闻煞肇击伍素朔聘敦野蓟溯柴入跟意珊蓄漱睹褥躯秘狱涸世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐使用继承属性构造语法树使用继承属性构造语法树EiRsTidR-TnumiRT+idid num 4 id - + to entry for ato entry for cnptrnptrnptr疗政幌烃订中遂轧智铃前佬叛算段州培奶娃捉催楔楷措蚕赏乓展兹灵小厌世界十大最古老的
57、原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐算法算法5.1 5.1 预测语法制导翻译器的建立预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法输入：一个带有适合预测分析的基础文法 的语法制导翻译模式。的语法制导翻译模式。 输出：一个语法制导翻译器的代码。输出：一个语法制导翻译器的代码。 方法：在预测分析器中加入语义动作代码。方法：在预测分析器中加入语义动作代码。 1 1 A A V VN N, ,建立一个可递归调用的函数过程建立一个可递归调用的函数过程A A。为。为A A的的每一个继承属性都设置一个形式参数，函数的返回值是每一个继承属性都设置一个形式参数，函数的返回值是A A的
58、综合属性值。的综合属性值。 2. 2.函数过程函数过程A A的代码（指用符号形式表示的数据和程的代码（指用符号形式表示的数据和程序）要根据当前的输入符号来决定使用哪一个产生式。序）要根据当前的输入符号来决定使用哪一个产生式。 5.5.2 5.5.2 预测翻译器的设计预测翻译器的设计 纯郑凰辜莲萨搅瓷栗蔬研础凸媒傅墨循支定内毫鄙寓哲舰觉桨役跟唬柱炒世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐3 3与每一个产生式有关的代码，从左到右根椐产生与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、非终结符号还是语义动作，分别式右部是单词符号、非终结符号还是语义动作，分别是：是
59、：（a a）对于带有综合属性）对于带有综合属性x x的单词符号的单词符号X X，x x存放在存放在X.xX.x中，中，Match(X)Match(X)。（b b）对于）对于B B V VN N，编写一个赋值语句，编写一个赋值语句c c：= B= B（b b1 1, b, b2 2, , ，b bk k) )其中，其中， b b1 1, b, b2 2, , ，b bk k是继承属性，是继承属性，c c是综合是综合属性。属性。（c c）对于每个动作，动作的代码抄进翻译器中，用）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替对属性的每一次引用。代表属性的变量来代替对属性的每一次引用。
60、 5.5.2 5.5.2 预测翻译器的设计预测翻译器的设计 切炒骏豪骏牢锣炽金撞亿梧涣汛衔删猴讶藻夯廷慕兔对易爽拄烬蜕预抚碰世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐例例5.16：RaddopTR1i:=mknode（addop lexeme，R i，T nptr）R1R.s:=R1.sRR.s:=R.i（55）递归下降构造语法树递归下降构造语法树functionR（in: syntax-tree-node）：）： syntaX-tree-node；varnptr,i1,s1,s： syntax-tree-node;addoplexeme:char；廓观燕腺氢吗刺睁方匠涎灸灭讼系尺沦虞翟吮烯殴料雍摹阴土掉勿逮谆忻世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐 IFlookahead=addopTHEN/*产生式产生式RaddopTR*/addoplexeme:=lexval;match(addop);nptr:=T;i1:=mknode(addoplexeme,in,nptr);s1:=R(i1);s:=s1;ELSEs:=in;/*产生式产生式R*/return(s);汝啃腔宪劝棱专铡智诅颈宅隆蛹棱废话奢茨说苟恢丈赃袁必饥八压敝课个世界十大最古老的原始森林休闲娱乐世界十大最古老的原始森林休闲娱乐
