《第五章 语法制导翻译(1)》由会员分享，可在线阅读，更多相关《第五章 语法制导翻译(1)（45页珍藏版）》请在金锄头文库上搜索。
1、1,第五章 语法制导翻译,编译原理,2,在文法中，文法符号通常都有明确的意义，文法符号之间也有确定的语义关系。 用属性描述语义信息，用语义规则描述属性之间的关系，将语义规则与语法规则相结合。 语法制导翻译(Syntax-Directed Translations)：在语法分析的过程中计算语义属性值。,编译原理,3,介绍一种形式化的语义描述方法：语法制导的翻译，包括两种具体形式 语法制导定义(Syntax-Directed Definitions, SDD)：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 翻译模式(translation schemes)： 给出语义规则的计算顺序。
2、介绍语法制导翻译的实现方法。,编译原理,4,语法制导翻译的一般过程,输入符号串,分析树,依赖图,语义规则的计算顺序,一个句子的翻译过程可以与语法分析过程并行。,编译原理,5,5.1 语法制导定义,语法制导定义是对CFG的推广，每个文法符号都有一个相关的属性集。 属性：语义信息。一个文法符号通常用一个或若干个属性来描述它的语义信息。典型例子： 变量的数据类型 表达式的值 变量的存储位置 程序的目标代码,编译原理,6,5.1.1综合属性和继承属性,综合属性：在分析树结点N上的非终结符A的综合属性是由N上的产生式所关联的语义规则来定义的。A是产生式的头。结点N上的综合属性只能通过N的子结点的属性值或
3、结点N本身的属性值计算得到。 继承属性：在分析树结点N上的非终结符B的继承属性是由N的父结点上的产生式所关联的语义规则来定义的。 B出现在产生式的体中。结点N上的继承属性只能通过N的父结点的属性值、结点N本身的属性值或N的兄弟结点的属性值计算得到。,编译原理,7,语义规则：描述产生式中各文法符号的属性之间的依赖关系。通常用函数或程序语句的形式表示。 依赖图：表示文法符号属性之间依赖关系的有向图。 注释分析树：每个结点都带有属性值的分析树。,编译原理,8,每个产生式A有一组形如b := f(c1, c2, , ck )的语义规则，其中f 是函数，并且满足下面两种情形之一： b是A的综合属性，c1
4、, c2 , , ck是产生式右部文法符号的属性。 b是产生式右部某个文法符号的继承属性，且c1 , c2 , , ck也是该产生式文法符号的属性。 称属性b依赖于属性c1, c2 , , ck。,编译原理,9,例5.1 简单台式计算器的语法制导定义,编译原理,10,综合属性： E.val, T.val, F.val, digit.lexval 在语法制导定义中，终结符号只有综合属性，它们的值由词法分析程序提供；digit.lexval 假设开始符号没有继承属性。,编译原理,11,5.1.2 对SDD求值,S属性定义：仅仅使用综合属性的语法制导定义称为S属性定义。 例5.1中的S属性定义详细说
5、明了一台计算器读入包含数字，括号，+和*运算符的算术表达式，随后再读入一个换行字符n，然后打印出表达式值的过程。 分析树各结点属性的计算可以自底向上地完成。,编译原理,12,8+5*2 n的注释分析树 (annotated parse tree),编译原理,13,例5.3,编译原理,14,T.val = 15,T.inh = 3 .syn =15,F.val = 3,digit.lexval =3,*,F.val = 5,digit.lexval = 5,T1.inh = 15 .syn =15,图5-4,编译原理,15,继承属性,一个结点的继承属性值由该结点的父结点和（或）兄弟结点的属性决定
6、。,编译原理,16,5.2 SDD的求值顺序,编译原理,17,5.2.1 属性依赖图,依赖图主要用于 确定属性的计算顺序； 设计语义规则。,编译原理,18,E E1 + E2,val val val,E.val是从E1.val和E2.val综合得出,产生式 语义规则 E E1+E2 E.val := E1.val + E2.val,例5.4,编译原理,19,图5-7,T,T,F,digit,*,F,digit,T1,val 9,syn 8,syn 7,val 4,lexval 1,lexval 2,val 3,inh 6,inh 5,编译原理,20,5.2.2 属性求值的顺序,拓扑排序：结点的
7、一种排序，若mimj是从mi到mj的边，那么在此排序中mi先于mj。 有向图变成线形排序 例：图5-7的一个拓扑排序 1，2，3，4，5，6，7，8，9 或1，3，5，2，4，6，7，8，9,编译原理,21,循环依赖Circular dependency,产生式 语义规则 A B A.s := B.i B.i := A.s + 1,编译原理,22,属性计算次序,构造输入的分析树， 构造属性依赖图， 对结点进行拓扑排序， 按拓扑排序的次序计算属性。,编译原理,23,5.2.3 S属性定义,如果一个SDD的每个属性都是综合属性，则它是S属性。可以按照分析树的自底向上顺序来计算各属性值。 后序遍历
8、postorder (N) for (从左边开始，对N的每个结点C) postorder (C); 计算N的属性值； S属性定义可以在自底向上语法分析过程中实现。,编译原理,24,5.2.4 L属性定义,一个语法制导定义是L属性定义，如果任意一条产生式A X1X2 . Xn，其右部符号Xj(1 j n)的继承属性仅依赖于 产生式中Xj的左边的符号X1, X2 ,. Xj-1的属性； A的继承属性。 对综合属性没有限制。显然，所有的S属性定义都是L属性定义。,编译原理,25,例5.8 L属性,编译原理,26,例5.9 非L属性,文法符号Q的继承属性依赖于它右边文法符号R的属性。,编译原理,27,
9、另一例 非L属性的语法制导定义,文法符号B的继承属性依赖于它右边文法符号C的属性。,编译原理,28,例5.10,编译原理,29,例5.10 简单类型声明的SDD,id.entry : 指向符号表的id表目的指针，由词法分析得到,编译原理,30,结点6、7、8是为addtype过程引入的虚属性,L.attr:=addtype(L.in, id.entry),图5-9 float id1, id2, id3的分析树的依赖图,编译原理,31,float id1, id2, id3的分析树的依赖图,编译原理,32,float id1, id2, id3的注释分析树,编译原理,33,5.3 语法树的构造
10、,应用语法制导定义来构造语法树,编译原理,34,5.3.1 语法树,语法树是分析树的压缩表示：算符和关键字作为内部结点。 语法制导翻译可以基于分析树，也可以基于语法树。 语法树的例子：,编译原理,35,5.3.2 构造表达式的语法树,三个函数： 1. mknode (op, left, right)：建立一个运算符结点； 2. mkleaf(id, entry)：建立一个标识符结点； 3. mkleaf(num, val)：建立一个数结点。,编译原理,36,构造语法树的语法制导定义,为表达式建立语法树的语法制导定义,编译原理,37,E node E node + T node E node -
11、 T node id T node num id,1,2,3,4,5,6,id to entry for a,+,-,num 4,id to entry for c,图5.11 a-4+c的语法树的构造,编译原理,38,下面函数调用建立表达式a-4+c的语法树。,(1) p1 := new Leaf(id, entrya); (2) p2 := new Leaf(num, 4); (3) p3 := new Node(-, p1, p2); (4) p4 := new Leaf(id, entryc); (5) p5 := new Node(+, p3,p4);,p1, p2, ., p5是指
12、向结点的指针，entrya和entryc分别是指向符号表中标识符a和c的指针。,编译原理,39,例5.12,+,-,id to entry for a,num 4,id to entry for c,id,i E s,T node,+,i E s,num,T node,-,i E s,E.node,T node,id,编译原理,41,5.3.2 类型的构造,编译原理,42,L属性的语法制导定义: The stucture of a Type,In C, the type int 23 means, “array of 2 arrays of 3 integers.” The corresponding type expression array(2, array(3, integer) can be represented by trees:,编译原理,43,T generates a basic type or an array type,B.t, T.t : 综合属性 C.t : 综合属性 C.b: 继承属性,编译原理,44,编译原理,45,习题,P190 5.2.3 5.2.4 P195 5.3.1 5.3.3,
