编译原理-第六章习题答案

1、编译原理电子教案 第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译 上一页下一页2 本章的主要内容本章的主要内容 属性文法和语法制导的翻译的概念 综合属性和继承属性的概念、特点 S-属性文法与L-属性文法的概念及分析方法 翻译模式 递归下降翻译器的设计 上一页下一页3 本章要求本章要求 知识点：语法制导定义，S-属性定义及其自底向上计算 属性，L-属性定义，自顶向下的翻译，自底向上计算继 承属性。 深刻理解：属性，综合属性，继承属性，依赖图，计算 顺序，语法树，语法制导定义，S-属性文法定义，L-属 性文法定义，翻译模式。 熟练掌握：对于已知文法G和翻译任务，构造其L-属性 定义，将

2、其改造成适于自顶向下分析或自底向上分析的 翻译模式。 上一页下一页4 本章教学线索本章教学线索 1 属性文法（属性翻译文法）属性文法（属性翻译文法） 1.1 属性文法的概念 1.2 属性的分类 1.3 属性的计算规则 2 基于属性文法的处理办法基于属性文法的处理办法 3 S-S-属性文法的自下而上计算属性文法的自下而上计算 4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译 5 自下而上计算继承属性自下而上计算继承属性 上一页下一页5 1 属性文法（属性翻译文法）属性文法（属性翻译文法） 语法制导翻译：通过给语法树上各个符号赋予一定的含义 并且将各个符号进行有结构的连接，可以形成语言的具

3、 体语句的含义。这给予我们以启示：可以通过扩充文法， 在文法符号上附着某些语义信息，并在这些语义信息间建 立相互计算关系，从而在语法分析的同时进行语义分析。 由于这种分析是在语法分析的控制下进行的，故称为语法 制导翻译。 上一页下一页6 1.1 属性文法的概念属性文法的概念 （1）属性文法的定义 在上下文无关文法的基础上，为每个文法符号（终 结符和非终结符）配备若干相关的“值”（也称： “属性”），对于文法的每个产生式都配备了一组属 性的计算规则（语义规则），这种文法称为属性文法。 1968年，Knuth首先提出。 说明：在一般情况下，整个属性文法是非常复杂的。但 属性的函数关系却通常非常简单

4、。属性也很少依赖于 大量的其它属性，因此可以将相互依赖的属性分割成 较小的独立属性集，然后单独对每一属性集写出一个 属性文法。 上一页下一页7 （2）属性（Attribute）是编程语言结构的任意特性。属性在其包含 的信息和复杂性等方面变化很大。属性的典型例子有： 变量的数据类型 表达式的值 存储器中变量的位置 程序的目标代码 数的有效位数 （3）属性文法一般表示方法： 上一页下一页8 例6.1 一个简单台式计算器的属性文法 上一页下一页9 例6.2：无符号整数的属性文法 上一页下一页10 1.2 属性的分类属性的分类 例6.3 属性文法为例6.1中的属性文法，输入：3*5+4n digitl

5、exval:=3 Fval:=3 Tval:=3 digitlexval:=5 Fval:=5 Tval:=15 * Eval:=15 + digitlexval:=4 Fval:=4 Tval:=4 Eval:=19L n 综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子 结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规 则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。 继承属性：用于自上而下传递信息；在语法树中，一个结点的继承属性由此结 点的父结点和/或兄弟结点的某些属性确定。 上一页下一页11 例6.4 继承属性的类型说明文法 D

6、T.type=real real L.in=real L.in=real , id3 L.in=real , id2 id1 real id1，id2，id3 上一页下一页12 1.3 属性的计算规则属性的计算规则 属性的计算规则：设有产生式A 定义 b= f（c1，c2，ck ）f是一个计算函数，并且 （1）b是A的一个综合属性，并且c1，c2，ck是产 生式右边文法符号的属性。或者： （2）b是产生式右边某文法符号的一个继承属性，并且 c1，c2，ck是A或产生式右边任何文法符号的属性。 上一页下一页13 注意： 如果同一文法符号在文法规则中出现不止一次，那么每次必须用合适 的下标与在其他

7、地方出现的符号区分开来。 终结符只有综合属性，它们由词法分析器提供。 非终结符既可有综合属性也可有继承属性，文法开始符的所有继承属 性为属性计算前的初始值。 属性计算规则中仅能使用相应产生式中文法符号的属性（封装性）。 产生式左边的继承属性和产生式右边的文法符号的综合属性由其它产 生式的属性规则计算。 一个句型的语法树可以加以扩充，用来表示句型分析中得到的各个符 号的属性间的关系： u语法树中，一个结点的综合属性的值由其子结点的属性值确定 u语法树中，一个结点的继承属性的值由该结点的父结点和（或）兄 弟结点的某些属性值确定 上一页下一页14 本章教学线索本章教学线索 1 属性文法（属性翻译文法

8、）属性文法（属性翻译文法） 2 基于属性文法的处理办法基于属性文法的处理办法 2.1 语法制导翻译 2.2 依赖图 2.3 树遍历的属性计算方法 2.4 一一遍扫描的处理办法 2.5 抽象语法树(Abstract Syntax tree) 3 S-S-属性文法的自下而上计算属性文法的自下而上计算 4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译 5 自下而上计算继承属性自下而上计算继承属性 上一页下一页15 2.1 语法制导翻译语法制导翻译 基于属性文法的处理过程通常是：对单词符号串进行 语法分析，构造语法分析树，然后根据需要遍历语法树， 并在语法树的各结点处按语义规则进行计算。 输入

9、串分析树依赖图语义规则的计算 图6.1 语法制导翻译的概观 在具体实现时，一般都是随语法分析的进展，识别出一 个语法结构，就对它的语义进行分析和翻译。也就是语义 分析是伴随语法分析的过程进行。 上一页下一页16 2.2 依赖图依赖图 a依赖图：一种有向图，在一颗语法树中表示结点的继承属性和综合属性之间 的相互依赖关系（这种属性之间的依赖关系由文法的语义规则确定）。 b依赖图的构造方法： for 语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 语法树中每一个结点n do for 结点n所有产生式对应的每一条语义规则 bf（c1，c2，

10、ck ) do for i1 to k do 从结点ci到结点b构造一条有向边； 注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义。 b C1C2Ck-1Ck 上一页下一页17 例6.5 EE1+E2 E.val=E1.val+E2.val E.val E1.valE2.valD T real L L , id3 L , id2 id1 4 type in 5 in 7 in 9 10 8 6 1 entry 3 entry 2 entry 例6.4中带继承属性文法对于real id1，id2，id3 上一页下一页18 c属性的计算顺序 l拓扑排序 一个有向非循环图的拓扑排

11、序是图中结点的任何顺序m1，m2， mk，使得边必须是从序列中前面的结点指向后面的结点，也就是 说,如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj 前面。 若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排 序，它就是属性值的计算顺序。 l计算语义规则的方法 1）分析树法：输入串分析树依赖图计算次序 2）基于规则的方法：在构造编译器时，用手工或专门的工具来分 析语义规则，确定属性值的计算顺序。 3）忽略语义规则的方法：在语法分析过程中翻译，那么计算顺序 由分析方法来确定而表面上与语义规则无关。实际上，要求限制 语法制导定义，使属性值的计算顺序能和语法分析过程同步进行

12、。 上一页下一页19 2.3 树遍历的属性计算方法树遍历的属性计算方法 前提：1）假设语法树已经建立 2）且树中已带有开始符号的继承属性和终结符的综合属性； 方法：深度优先，从左到右进行（也是一种分析树的方法） 具体算法： While 还有未被计算的属性 do VisitNode(S) /S是开始符号 Procedure VisitNode (N：Node)； begin if NVN then /假设它的产生式NX1Xm for i = 1 to m do if XiVN then begin 计算计算Xi的所有能够计算的继承属性；的所有能够计算的继承属性； VisitNode（Xi）； e

13、nd； 计算计算N的所有能够计算的综合属性；的所有能够计算的综合属性； end 例子：6.6 P143 上一页下一页20 2.4 一遍扫描的处理办法一遍扫描的处理办法 在语法分析的同时计算属性值，无需构造实际的语法树；这种方 法同下面两个因素有关： 所采用的语法分析方法 属性的计算次序 使用一遍扫描的语义分析方法，就是为文法中的每个产生式配上 一组语义规则，并且在语法分析的同时执行这些语义规则。在自 上而下的分析中就是在产生式匹配输入串成功，或者在自下而上 的分析中，当一个产生式被用于进行规约时，此产生式相应的语 义规则就被计算，完成有关的语义分析和代码产生的工作。 语法分析过程中完成翻译有许

14、多优点，但也有一些不足： u适于语法分析的文法可能不完全反映语言成分的自然层次结构； u语法分析方法限制，对语法树结点的访问次序和翻译需要的访问 次序不一致。 上一页下一页21 2.5 抽象语法树抽象语法树(Abstract Syntax tree) （1）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉， 是语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常 用的一种中间表示形式。 （2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点 中出现。 产生式Sif B then S1 else S2 赋值语句的语法树 if-then-else assignment

15、 | B S1 S2 variable expression （3）建立表达式的抽象语法树 建立表达式的抽象语法树使用的函数 1）mknode（op，left，right）建立一个运算符号结点，标号是op，两个 域left和right指向运算分量结点的指针。 2）mkleaf(id，entry) 建立一个标识符结点，由标号id标识，一个域entry指 向标识符符号表中相应的项。 3）mkleaf（num，val）建立一个数结点，标号为num，域val用于存放数 的值。返回新建立结点的指针。 上一页下一页22 产生式 语义规则 EE1+T E.nptr:=mknode(+,E1.nptr,T.n

16、ptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val) id to entry a num 4 id to entry c + a-4+c的语法树 上一页下一页23 本章教学线索本章教学线索 1 属性文法（属性翻译文法）属性文法（属性翻译文法） 2 基于属性文法的处理办法基于属性文法的处理办法 3 S-S-属性文法的自下而上计算属性文法的自下而上计算

17、 4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译 5 自下而上计算继承属性自下而上计算继承属性 上一页下一页24 3 S-属性文法的自下而上计算属性文法的自下而上计算 s-属性文法：只含有综合属性 s-属性文法通常借助于LR分析器来实现，在分析栈中使用一个附加的域来存放文 法符号的综合属性值。 state val . ZZ.z Y . Y.y . XX.z top 一个带有综合属性值域的分析栈 A b=f（c1，c2，ck） b是A的综合属性，ci(1 ik)是中符号的属性。综合属性的值在自底向上的分 析过程中，每步归约时，计算相应的属性值。 上一页下一页25 例如：AXYZ Aa

18、f(Xx，Yy，Zz) Aa X x Y y Z z X X.x Y Y.y Z Z.z A A.a state val top top state val 定义式 A.a=f（X.x，Y.y，Z.z）（抽象）变成： valntopf（valtop-2，valtop-1，valtop）（具体可执行代码）。在执行代码 段之前执行：ntoptop - r + 1（r是句柄的长度） 执行代码段后执行：topntop； 总总 结：结： 采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变 成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约 处有一个“挂钩”，

19、语义分析和翻译的代码段（语义子程序）就挂在这个钩子上 。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。 上一页下一页26 例6.9 用LR分析器实现台式计算器 产生式 代码段 LEn printf(valntop) E E+T valntop:=valtop-2+valtop E T T T*F valntop:=valtop-2*valtop T F F (E) valntop:=valtop-1 F digit 输入 state val 产生式 3*5+4n - - *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3-

20、 +4n T* 5 3-5 +4n T* F 3-5 F digit +4n T 15 TT*F +4n E 15 ET 4n E+ 15- n E+4 15-4 n E+F 15-4 Fdigit n E+T 15-4 T F n E 19 EE+T En 19 L 19 L En 上一页下一页27 本章教学线索本章教学线索 1 属性文法（属性翻译文法）属性文法（属性翻译文法） 2 基于属性文法的处理办法基于属性文法的处理办法 3 S-S-属性文法的自下而上计算属性文法的自下而上计算 4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译 4.1 L-属性文法的定义 4.2 翻译模式 4.

21、3 自顶向下的翻译 4.4 递归下降翻译器的设计 5 自下而上计算继承属性自下而上计算继承属性 上一页下一页28 4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 在语法分析过程中进行语义分析和翻译，属性的计算 顺序受到语法分析建立分析树结点顺序的限制。一种 自然的计算属性的顺序是按深度优先访问分析树结点 的顺序，它适应多种自底向上和自顶向下的翻译方法。 L-属性文法可用按深度优先顺序计算属性值。 上一页下一页29 4.1 L-属性文法的定义属性文法的定义 如果AX1X2XnP，其每一个语义规则中的每一个 属性都是一个综合属性，或是Xj(1j n)的一个继承属 性，这个继承属性仅依赖于：

22、a产生式中Xj的左边符号X1，X2，Xj-1的属性； bA的继承属性。 每一个每一个S-属性文法都是属性文法都是L-属性文法属性文法 上一页下一页30 4.2 翻译模式翻译模式 1）翻译模式的概念： 翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符 号相对应，语义规则或语义动作用花括号 括起来，可以被插入到产生 式右部的任何合适的位置上。 这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分 析树的过程中何时执行语义动作。 翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译 的注释。 翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。翻译模式保证

23、了按深度优先次序一次扫描就能完成属性的计算。 例 一个简单的翻译模式 ETR Raddop T print(addop.lexeme) R1| Tnum print(num.val) E T 9print(9) R - T 5 print(5) print(-) R + T print(2) print(+) 2 R 9-5+2翻译成后缀式95-2+ 上一页下一页31 2）翻译模式的构造 条件：属性文法是L-属性文法； 保证语义动作不会引用还没有计算的属性值。 a. 只需要综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生 式右边的末尾。 例如： TT1*F

24、Tval = T1 val*F val TT1*F Tval = T1 val*F val b. 既有综合属性又有继承属性: 产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的综合属性。( 因为综合属性是在该符 号所有分析动作结束后计算） 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后 才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 上一页下一页32 4.3 自顶向下的翻译自顶向下的翻译 用翻译模式构造自顶向下翻译。 从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提 取公共左因子，在改写

25、基本文法时考虑属性值的计算。 例例 图6.13的带左递归的文法的翻译模式被转换成图6.14的带右递 归的文法的翻译模式。 EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val 图6.13 带左递归的文法的翻译模式 上一页下一页33 ET R.i:=T.val RE.val:=R.s R T R1.i:=R.i+T.val R1R.s:=R1.s R- T R1.i:=R.i-T.val R1R.s:=R1.s RR.s:=R.i T

26、（ E ）T.val:=E.val Tnum T.val:=num.val 图6.14经过转换的带有右递归文法的翻译模式 R.s=R.i E T.val=9 num.val=9 R.i=9 - T.val=5 num.val=5 R.i=4 + T.val=2 num.val=2 R.i=6 R.s=R1.s R.s=R1.s E.val=R.s 计算表达式计算表达式9-5+2 上一页下一页34 关于左递归翻译模式更一般化的讨论关于左递归翻译模式更一般化的讨论 左递归翻译模式 AA1YA.a:=g(A1.a，Y.y) AX A.a:=f(X.x) （6.2） 每一个文法符号都有一个综合属性，用

27、相应的小写字母表示，g和f是任意函数。 消除左递归，文法转换成 AX R RY R| （6.3） 再考虑语义动作，翻译模式变为： AX R.i := f(X.x) R A.a := R.s RY R1.i := g（R.i，Y.y） R1 R.s := R1.s R R.s := R.i （6.4） 经过转换的翻译模式与图6.14中一样,使用R的继承属性i和综合属性s。（6.2）和 （6.4）的结果是一样的 上一页下一页35 A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=g(g(f(X.x),Y1.y),Y2.y) Y2 A.a=g(f(X.x),Y1.y)A.a=g(f(X.x

28、),Y1.y) A.a=f(X.x)A.a=f(X.x)Y1 X X A X XR.i=f(X.x)R.i=f(X.x) Y1R.i=g(f(X.x),Y1.y)R.i=g(f(X.x),Y1.y) Y2R.i=g(g(f(X.x),Y1.y),Y2.y)R.i=g(g(f(X.x),Y1.y),Y2.y) 输入：XY1Y2 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （6.2） AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i，Y y） R1 R s:=R1 s R R s:=R i （6.4） 上一页下一页36 建立表达式的抽象

29、语法树的翻译模式：建立表达式的抽象语法树的翻译模式： EE1+T E nptr :=mknode( + ,E1 nptr,T nptr) EE1-T E nptr :=mknode( - ,E1 nptr,T nptr) ET E nptr :=T nptr 从从翻译模式中消除左递归，变成以下翻译模式：翻译模式中消除左递归，变成以下翻译模式： ET R i:=T nptr R E nptr:=R s R T R1 i:=mknode(+,R i,T nptr) R1 R s:=R1 s R- T R1 i:=mknode(-,R i,T nptr) R1 R s:=R1 s R R s:=R

30、i T(E) T nptr:=E nptr Tid T nptr:=mkleaf(id, id entry) Tnum T nptr:=mkleaf(num,num val) 上一页下一页37 使用继承属性构造a-4+5的语法树 E T id nptr id to entry for a R - T num nptr num 4 i - R + T id nptr id to entry for c + i R s i 上一页下一页38 4.4 递归下降翻译器的设计递归下降翻译器的设计 算法6.1 预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法的语法制导翻译模式。 输出：一个语

31、法制导翻译器的代码。 方法：在预测分析器中加入语义动作代码。 A VN,建立一个可递归调用的函数过程建立一个可递归调用的函数过程 A。为。为A的每一个继承属性都的每一个继承属性都 设置设置 一个形式参数，函数的返回值是一个形式参数，函数的返回值是A的综合属性值。的综合属性值。 函数过程函数过程A的代码（指用符号形式表示的数据和程序）要根据当前的的代码（指用符号形式表示的数据和程序）要根据当前的 输入符号来决定使用哪一个产生式。输入符号来决定使用哪一个产生式。 与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、 非终结符号还是

32、语义动作，分别是：非终结符号还是语义动作，分别是： （a）对于带有综合属性）对于带有综合属性x的单词符号的单词符号X，x存放在存放在X.x中，中，Match(X)。 （b）对于）对于B VN，编写一个赋值语句，编写一个赋值语句c:= B（b1, b2, ，bk) 其中，其中， b1， b2， ，bk是继承属性，是继承属性， c是综合属性。是综合属性。 （c）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替 对属性的每一次引用。对属性的每一次引用。 上一页下一页39 例例: Raddop T R1i:=mknode（addop lexeme，R i， T nptr） R1 R.s:=R1.s R R.s:=R.i 递归下降构造语法树递归下降构造语法树 function R(in:AST-node):AST-node; var nptr,i1,s1,s:AST-node; addoplexeme:char; begin if sym=addop then begin addoplexeme=l