编译原理ppt99

1、第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译编译程序的功能和组织结构编译程序的功能和组织结构表表 处处 理理词词法法分分析析源源程程序序目目标标程程序序错错 误误 处处 理理语语法法分分析析语义语义分析分析和和中间中间代码代码生成生成目目标标代代码码生生成成前前 端端后后 端端中中间间代代码码优优化化本章学习内容本章学习内容v本章介绍有关本章介绍有关语义描述语义描述及及语义处理语义处理的问题。的问题。其处理的方法主要是其处理的方法主要是属性文法属性文法和和语法制导翻译语法制导翻译。v掌握：掌握：属性文法属性文法,语法制导翻译的概念语法制导翻译的概念v理解：理解：如何在自下而上分析

2、中实现如何在自下而上分析中实现S-属性属性计算。计算。v 6.1 6.1 属性文法属性文法v 6.2 6.2 语法制导翻译的概述语法制导翻译的概述v 6.3 6.3 S-S-属性文法的自下向上的计算属性文法的自下向上的计算6.16.1 属性文法属性文法属性文法属性文法: : 是在是在上下文无关文法上下文无关文法的基础上为每个文法符的基础上为每个文法符号配备若干个相关的号配备若干个相关的 “值值”（称为（称为属性属性）; ;对于对于文法的每一个产生式配备一组文法的每一个产生式配备一组属性的属性的“计算规计算规则则”( (称为称为语义规则语义规则) )。属性和变量一样，可以进行计算和传递。属性和变

3、量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程代表与文法符号相关的信息，例如它的类型、代表与文法符号相关的信息，例如它的类型、值、代码序列值、代码序列 、符号表内容等等。、符号表内容等等。6.16.1 属性文法属性文法v属性：属性：综合属性综合属性: :用于用于“自下而上自下而上”传递信息传递信息 继承属性继承属性: :用于用于“自上而下自上而下”传递信息传递信息 继承属性和综合属性 例： E P P.env := E.env; E.val := P.val; E1 P+E2 P.env := E1.env E2.env := E1.env E1.

4、val :=P.val+E2.val P n P.val :=n.val P id P.val :=Lookup(P.env,) P (E) E.env := P.env P.val := E.val6.16.1 属性文法属性文法v语义规则语义规则: : 对应于每个产生式对应于每个产生式A A都有一套与之相关联都有一套与之相关联的语义规则，每条语义规则的形式为：的语义规则，每条语义规则的形式为： b:=f(cb:=f(c1 1,c,c2 2, ,c,ck k) )这里这里f f是一个函数，并满足下面的条件之一是一个函数，并满足下面的条件之一: :（1 1）b b是是A A的一个的

5、一个综合属性综合属性并且并且c c1 1,c,c2 2, ,c ck k是产生式是产生式右边文法符号的属性；右边文法符号的属性；（2 2）b b是产生式右边某个文法符号的一个是产生式右边某个文法符号的一个继承属性继承属性并且并且c c1 1,c,c2 2, ,c ck k是是A A或产生式右边任何文法符号的或产生式右边任何文法符号的属性属性在这两种情况下，我们都说属性在这两种情况下，我们都说属性b b依赖依赖于属性于属性c c1 1,c,c2 2,c,ck k. .用于用于“自下而上自下而上”传递信息传递信息 用于用于“自上而下自上而下”传递信息传递信息 6.16.1 属性文法属性文法特别强调

6、：特别强调：终结符终结符只有综合属性，由词法分析器提供；只有综合属性，由词法分析器提供；非终结符非终结符既可有综合属性也可有继承属性，文法开始符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。号的所有继承属性作为属性计算前的初始值。v属性计算规则中只能使用属性计算规则中只能使用相应相应产生式的文法符号的产生式的文法符号的属性。属性。一般而言：一般而言：v出现在出现在产生式右边的继承属性产生式右边的继承属性和出现在和出现在产生式左边产生式左边的综合属性的综合属性都必须提供一个计算规则都必须提供一个计算规则. .v出现在出现在产生式左边的继承属性产生式左边的继承属性

7、和出现和出现在产生式右边在产生式右边的综合属性的综合属性由其它产生式的属性规则计算或由属性由其它产生式的属性规则计算或由属性计算器的参数提供计算器的参数提供产生式产生式 语义规则语义规则6.16.1 属性文法属性文法 例例 6 .2 输入：输入：3*5+4ndigitlexval:=3F val:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19例例 6 .2 输入：输入：3*5+4nLn对于对于s-属性定义属性定义通常使用通常使用自下而上的分析方法自下而上的分析方法在在建立建

8、立每一个每一个结点处结点处综合综合属性值属性值使用使用语义规则语义规则来计算来计算 即在即在 用用后，就执行那后，就执行那个产生式的个产生式的s-属性规则定义计算属性的值，从属性规则定义计算属性的值，从进行计算进行计算。 例例 文法文法 DTL T int | real L L1,id | id 描述说明语句中各种变量的类型信息的描述说明语句中各种变量的类型信息的语义规则如下语义规则如下: 产生式产生式 语义规则语义规则 DTL L in:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addty

9、pe(id entry,L in) L id addtype(id entry,L in)分析分析real i1, i2, i3 产生式产生式 语义规则语义规则 v 翻译的任务翻译的任务：对对语法结构语法结构进行进行静态静态语义分语义分析和正确性检查，若正确，则翻译成中间代码或析和正确性检查，若正确，则翻译成中间代码或目标代码。目标代码。v 使用的方法使用的方法: :语法制导翻译。语法制导翻译。 语法制导翻译语法制导翻译: : 由源程序的语法结构所驱由源程序的语法结构所驱动的翻译方式。动的翻译方式。6.2 语法制导翻译概述语法制导翻译概述6.2 语法制导翻译的概述语法制导翻译的概述 语法制导翻

10、译把语言的一些属性附加到代表语法结构的文法符号上，这些属性值是由附加到文法产生式的“语义规则”中计算的，也就是为每个产生式配备翻译子程序，即语义子程序。对输入串的翻译也就是根据语义规则进行计算得出结果。 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。 语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。 6.3 S-属性文法属性文法的自下向上的计算的自下向上的计算v综合属性值的计算正好可以和自下而上分析综合属性值的计算正好可以和自下而上分析建立分析树结点的过程同步。建立分析树结点的过程同步。v因此因此,S-属性文法属性文法的翻译器通常可借助于的翻译器通常

11、可借助于LR分分析器实现。在析器实现。在S-属性文法属性文法的基础上，将的基础上，将LR分分析器改造为一个翻译器，在对输入串进行语析器改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算（语法分析的法分析的同时对属性进行计算（语法分析的同时进行语义分析）同时进行语义分析） 。只含有综合属性的属性文法只含有综合属性的属性文法增加属性值栈，属性值放到与符号栈同步操作的属性值栈中，当Si对应的符号为Xi时，Vali中就存放与Xi对应的属性值。分析栈结构为：状态栈符号栈 属性值栈SmXmXm.valS1X1X1.valS0#-将LR分析器能力扩大，增加在归约前调用语义规则的功能 6.3 S-属

12、性文法属性文法的自下向上的计算的自下向上的计算产生式产生式 语义规则语义规则例例 考虑一下前面台式计算器的考虑一下前面台式计算器的属性文法的具体实现属性文法的具体实现。 状态栈符号栈属性值栈SmXmXm.valS1X1X1.valS0#-用第五章中的技术用第五章中的技术来为上述文法构造来为上述文法构造LR分析器。分析器。 产生式产生式 语义规则语义规则 为了实现方便，对语为了实现方便，对语义规则稍做改动义规则稍做改动: 用用val数组中的一个数组中的一个位置来代替规则中的位置来代替规则中的每一个属性。每一个属性。 修改分析程序，修改分析程序，使其在作相应的使其在作相应的归约归约以前执行表以前执

13、行表6.5所示的代码所示的代码段。段。符号栈符号栈例 简单算术表达式求值的属性文法1)L E print(E.val)2)EE1+T E.val :E1.val +T.val 3)ET E.val :T.val 4)TT1*digit T.val :T1.val * digit.lexval 5)Tdigit T.val :digit.lexval 状态ACTION GOTO d+*#ET0S3 12 1S4 acc2r3 S5r3 33r5r5 r54S3 75S6 6 r4r4 r47r2S5r2步骤 状态栈语义栈 符号栈剩余输入串ActionGOTO00-#23*5S3103- -#23

14、*5r52202-2#T3*5r31301-2#E3*5S44014-2-#E+3*5S350143-2- -#E+3*5r5760147-2-3#E+T*5S5701475-2-3-#E+T*5S68014756 - 2-3-#E+T*5r4790147-2-15#E+T#r211001-17#E#acc分析并计算分析并计算23*5的过程如下的过程如下:L E print(E.val)EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval 6.3 S-属性文法属性文法的自下向上的计算的自下向上的计算练习 在一个移进归约的分析中采用以下的属性文法，在某产生式归约时，立即执行括号中的动作。 AaB pri