第六章 属性文法和语法制导翻译 http://sei.nudt.edu.cn/cp 网上教学系统: 070606302: 编译原理

6.1 属性文法 属性文法（也称属性翻译文法） Knuth在1968年提出 6.1 属性文法 属性文法（也称属性翻译文法） Knuth在1968年提出 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等 属性可以进行计算和传递 语义规则：对于文法的每个产生式都配备了一组属性的计算规则 国防科技大学计算机系602教研室

在一个属性文法中，对应于每个产生式A→都有一套与之相关联的语义规则，每条规则的形式为： 综合属性：“自下而上”传递信息 继承属性：“自上而下”传递信息 在一个属性文法中，对应于每个产生式A→都有一套与之相关联的语义规则，每条规则的形式为： b:=f(c1,c2,…,ck) 这里，f是一个函数，而且或者 1. b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性，或者 2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck 是A或产生式右边任何文法符号的属性。 属性b依赖于属性c1,c2,…,ck。 国防科技大学计算机系602教研室

说明 终结符只有综合属性，由词法分析器提供 非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供 国防科技大学计算机系602教研室

语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。 例，考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式A→BC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c 而属性A.a和B.c在其它地方计算 国防科技大学计算机系602教研室

产 生 式 L→En E→E1+T E→T T→T1*F T→F F→ (E) F→digit 语 义 规 则 print(E.val) 语 义 规 则 print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval 国防科技大学计算机系602教研室

仅仅使用综合属性的属性文法称S－属性文法 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称S－属性文法 国防科技大学计算机系602教研室

产 生 式 L→En E→E1+T E→T T→T1*F T→F F→ (E) F→digit 语 义 规 则 print(E.val) 语 义 规 则 print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval 国防科技大学计算机系602教研室

3*5+4n的带注释的语法树 L E.val=19 n E.val=15 + T.val=4 T.val=15 F.val=4 产 生 式 语 义 规 则 L→En print(E.val) E→E1+T E.val := E1.val+T.val E→T E.val :=T.val T→T1*F T.val :=T1.val* F.val T→F T.val :=F.val F→ (E) F.val :=E.val F→digit F.val :=digit.lexval 3*5+4n的带注释的语法树 L E.val=19 n E.val=15 + T.val=4 T.val=15 F.val=4 T.val=3 F.val=5 digit.lexval=4 * F.val=3 digit.lexval=5 digit.lexval=3 国防科技大学计算机系602教研室

继承属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便 国防科技大学计算机系602教研室

L→id addtype(id.entry, L.in) 产 生 式 语 义 规 则 D→TL 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) 国防科技大学计算机系602教研室

句子real id1，id2，id3的带注释的语法树 T T.type=real L L.in=real real , L L.in=real id3 产 生 式 语 义 规 则 D→TL 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) L L.in=real id2 , id1 国防科技大学计算机系602教研室

6.2 基于属性文法的的处理方法 由源程序的语法结构所驱动的处理办法就是语法制导翻译法 语义规则的计算 6.2 基于属性文法的的处理方法 输入串 语法树 依赖图 语义规则计算次序 由源程序的语法结构所驱动的处理办法就是语法制导翻译法 语义规则的计算 产生代码 在符号表中存放信息 给出错误信息 执行任何其它动作 对输入符号串的翻译也就是根据语义规则进行计算的结果。 国防科技大学计算机系602教研室

6.2 基于属性文法的的处理方法 依赖图 树遍历 一遍扫描 国防科技大学计算机系602教研室

6.2.1 依赖图 在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述 6.2.1 依赖图 在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述 为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成 b:=f(c1,c2,…,ck) 的形式 依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。 国防科技大学计算机系602教研室

for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for语法树中每一个结点n do b:=f(c1,c2,…,ck ) do for i:=1 to k do 从ci结点到b结点构造一条有向边； 国防科技大学计算机系602教研室

E→E1＋E2 E.val:=E1.val+E2.val 国防科技大学计算机系602教研室

句子real id1，id2，id3的带注释的语法树的依赖图 产 生 式 语 义 规 则 D→TL 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) 句子real id1，id2，id3的带注释的语法树的依赖图 D 6 - addtype(id.entry, L.in) T 4 type L 5 in real , L 8 addtype id3 3 entry 7 in L 10 addtype , 9 in id2 2 entry id1 1 entry 国防科技大学计算机系602教研室

如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的 国防科技大学计算机系602教研室

属性的计算次序 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的 输入串 语法树 依赖图 基础文法用于建立输入符号串的语法分析树 根据语义规则建立依赖图 从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序 输入串 语法树 依赖图 语义规则计算次序 国防科技大学计算机系602教研室

句子real id1，id2，id3的带注释的语法树的依赖图 , id2 id3 real T D 4 type 5 in 6 7 8 9 10 1 entry 2 3 a4:=real; a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9); 国防科技大学计算机系602教研室

6.2 基于属性文法的的处理方法 依赖图 树遍历 一遍扫描 国防科技大学计算机系602教研室

6.2.2 树遍历的属性计算方法 通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性 6.2.2 树遍历的属性计算方法 通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性 深度优先，从左到右的遍历 国防科技大学计算机系602教研室

VisitNode(S) /*S是开始符号*/ procedure VisitNode (N:Node) ; begin While 还有未被计算的属性 do VisitNode(S) /*S是开始符号*/ procedure VisitNode (N:Node) ; begin if N是一个非终结符 then /*假设它的产生式为N→X1…Xm*/ for i :=1 to m do if XiVN then /*即Xi是非终结符*/ 计算Xi的所有能够计算的继承属性； VisitNode (Xi) end; 计算N的所有能够计算的综合属性 end 国防科技大学计算机系602教研室

例 考虑属性的文法G。其中，S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g 产 生 式 语 义 规 则 S→XYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b X→x X.d :=2*X.c Y→y Y.f := Y.e*3 Z→z Z.g :=Z.h+1 国防科技大学计算机系602教研室

假设S.a的初始值为0，输入串为xyz 产 生 式 语 义 规 则 S→XYZ Z.h := S.a X.c := Z.g 产 生 式 语 义 规 则 S→XYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b X→x X.d :=2*X.c Y→y Y.f := Y.e*3 Z→z Z.g :=Z.h+1 S:a=0, b=0 S:a=0 X X:c=1 d=2 Y Z Y:e=0 f=0 Z:h=0 g=1 x y z 国防科技大学计算机系602教研室

6.2 基于属性文法的的处理方法 依赖图 树遍历 一遍扫描 国防科技大学计算机系602教研室

6.2.3 一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值 L－属性文法适合于一遍扫描的自上而下分析 6.2.3 一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值 所采用的语法分析方法 属性的计算次序 L－属性文法适合于一遍扫描的自上而下分析 S－属性文法适合于一遍扫描的自下而上分析 国防科技大学计算机系602教研室

所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则 语义规则就被计算的时机 在自上而下语法分析中，一个产生式匹配输入串成功时 在自下而上分析中，当一个产生式被用于进行归约时 国防科技大学计算机系602教研室

6.2.4 抽象语法树 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树(Abstract Syntax Tree) S→if B then S1 else S2 3*5+4 * 5 4 + 3 B S1 S2 if_then_else 国防科技大学计算机系602教研室

建立表达式的抽象语法树 mknode (op,left,right) 建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。 mkleaf (id,entry) 建立一个标识符结点，标号为id，一个域eutry指向标识符在符号表中的入口。 mkleaf (num,val) 建立一个数结点，标号为num，一个域val用于存放数的值。 国防科技大学计算机系602教研室

建立抽象语法树的语义规则 产 生 式 语 义 规 则 E→E1+T E.nptr := mknode( ‘+’, E1.nptr, T.nptr ) 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 := mknode( id, id.entry ) T→num T.nptr := mknode( num, num.val ) 国防科技大学计算机系602教研室

a－4＋c的抽象语法树 E nptr E nptr T nptr T nptr E - id T nptr id + - id num 4 To entry for c id num 4 id 国防科技大学计算机系602教研室 To entry for a

一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值 L－属性文法适合于一遍扫描的自上而下分析 所采用的语法分析方法 属性的计算次序 L－属性文法适合于一遍扫描的自上而下分析 S－属性文法适合于一遍扫描的自下而上分析 国防科技大学计算机系602教研室

6.3 S-属性文法的自下而上计算 S-属性文法：只含有综合属性 综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。 分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。 国防科技大学计算机系602教研室

在分析栈中使用一个附加的域来存放综合属性值 假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式A→XYZ的 国防科技大学计算机系602教研室

E→E1+T val[ntop] := val[top-2]+val[top] E→T 产 生 式 语 义 规 则 L→En print(E.val) E→E1+T E.val := E1.val+T.val E→T E.val :=T.val T→T1*F T.val :=T1.val* F.val T→F T.val :=F.val F→ (E) F.val :=E.val F→digit F.val :=digit.lexval 产生式 代 码 段 L→En print(val[top]) E→E1+T val[ntop] := val[top-2]+val[top] E→T T→T1*F val[ntop] := val[top-2]*val[top] T→F F→ (E) val[ntop] :=val[top-1] F→digit 国防科技大学计算机系602教研室

输入 state sym val 用到的产生式 3*5+4n 0 # - *5+4n 05 #3 -3 产生式 代 码 段 L→En print(val[top]) E→E1+T val[ntop] := val[top-2]+val[top] E→T T→T1*F val[ntop] := val[top-2]*val[top] T→F F→ (E) val[ntop] :=val[top-1] F→digit 输入 state sym val 用到的产生式 3*5+4n 0 # - *5+4n 05 #3 -3 *5+4n 03 #F -3 F→digit *5+4n 02 #T -3 T→F 5+4n 027 #T* -3 - +4n 0275 #T*5 -3 - 5 国防科技大学计算机系602教研室

输入 state sym val 用到的产生式 +4n 0275 #T*5 -3 - 5 产生式 代 码 段 L→En print(val[top]) E→E1+T val[ntop] := val[top-2]+val[top] E→T T→T1*F val[ntop] := val[top-2]*val[top] T→F F→ (E) val[ntop] :=val[top-1] F→digit 输入 state sym val 用到的产生式 +4n 0275 #T*5 -3 - 5 +4n 02710 #T*F -3 - 5 F→digit +4n 02 #T -15 T→T*F +4n 01 #E -15 E→T 4n 016 #E+ -15- n 0165 #E+4 -15- 4 国防科技大学计算机系602教研室

输入 state sym val 用到的产生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4 F→digit 产生式 代 码 段 L→En print(val[top]) E→E1+T val[ntop] := val[top-2]+val[top] E→T T→T1*F val[ntop] := val[top-2]*val[top] T→F F→ (E) val[ntop] :=val[top-1] F→digit 输入 state sym val 用到的产生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4 F→digit n 0169 #E+T -15- 4 T→F n 01 #E -19 E→E+T #En -19- #L -19 L→En 国防科技大学计算机系602教研室

一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值 L－属性文法适合于一遍扫描的自上而下分析 所采用的语法分析方法 属性的计算次序 L－属性文法适合于一遍扫描的自上而下分析 S－属性文法适合于一遍扫描的自下而上分析 国防科技大学计算机系602教研室

6.4 L-属性文法和自顶向下翻译 通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值 LL(1)：自上而下分析方法，深度优先建立语法树 国防科技大学计算机系602教研室

一个属性文法称为L-属性文法，如果对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于： (1) 产生式Xj的左边符号X1，X2，…，Xj-1的属性； (2) A的继承属性。 S-属性文法一定是L-属性文法 国防科技大学计算机系602教研室

产 生 式 语 义 规 则 A→LM L.i := l(A.i) M.i :=m(L.s) A→QR R.i := r(A.i) 产 生 式 语 义 规 则 A→LM L.i := l(A.i) M.i :=m(L.s) A→QR R.i := r(A.i) Q.i :=q(R.s)   A.s :=f(Q.s) 国防科技大学计算机系602教研室

6.4.1 翻译模式 翻译模式：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来 6.4.1 翻译模式 翻译模式：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来 在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号{ }括起来，插入到产生式右部的合适位置上 国防科技大学计算机系602教研室

翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式 E→TR R→addop T {print(addop.lexeme)} R1 |  T→num {print(num.val)} 例：9-5+2 E T R - {print(‘9’)} T {print(‘-’)} R 9 {print(‘5’)} 5 + T {print(‘+’)} R 2 {print(‘2’)}  国防科技大学计算机系602教研室

设计翻译模式的原则 设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。 L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。 国防科技大学计算机系602教研室

建立翻译模式 当只需要综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾 产生式 语义规则 产生式 语义规则 T→T1*F T.val:=T1.val×F.val 建立产生式和语义动作： T→T1*F {T.val:=T1.val×F.val} 国防科技大学计算机系602教研室

建立翻译模式 如果既有综合属性又有继承属性，在建立翻译模式时就必须保证： 1. 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 S→A1A2 {A1.in:=1; A2.in:=2} A→a {print(A.in)} 国防科技大学计算机系602教研室

基于数学格式语言EQN En.val 给定输入 E sub n .val E n .val 国防科技大学计算机系602教研室

E sub n .val 识别输入并进行格式安放的L-属性文法 E n .val 产生式 语义规则 S→B B.ps :=10 产生式 语义规则 S→B B.ps :=10 S.ht :=B.ht B→B1B2 B1.ps :=B.ps B2.ps :=B.ps B.ht := max(B1.ht, B2.ht) B→B1 sub B2 B1.ps :=B.ps B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B2.ht) B→text B.ht :=text.h×B.ps 国防科技大学计算机系602教研室

翻译模式 S → {B.ps:=10} B {S.ht:=B.ht} B → {B1.ps:=B.ps} 1. 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。 翻译模式 S → {B.ps:=10} B {S.ht:=B.ht} B → {B1.ps:=B.ps} B1 { B2.ps:=B.ps } B2 {B.ht:=max(B1.ht,B2.ht)} B1 sub {B2.ps:=shrink(B.ps)} B2 {B.ht:=disp(B1.ht,B2.ht)} B → text{B.ht:=text.h×B.ps} 国防科技大学计算机系602教研室

6.4.2 自顶向下翻译 动作是在处于相同位置上的符号被展开（匹配成功）时执行的。 6.4.2 自顶向下翻译 动作是在处于相同位置上的符号被展开（匹配成功）时执行的。 为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归 当消除一个翻译模式的基本文法的左递归时同时考虑属性——适合带综合属性的翻译模式 国防科技大学计算机系602教研室

关于算术表达式的左递归文法相应的翻译模式 E→E1+T {E.val:=E1.val+T.val} E → T R R → + T R1 R → - T R1 R →  T → ( E ) T → num 关于算术表达式的左递归文法相应的翻译模式 E→E1+T {E.val:=E1.val+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} 国防科技大学计算机系602教研室

消除左递归，构造新的翻译模式 E → T {R.i:=T.val} R {E.val:=R.s} R → + T {R1.i:=R.i+T.val} R1 {R.s:=R1.s} R → - T {R1.i:=R.i-T.val} R →  {R.s:=R.i} T → ( E ) {T.val:=E.val} T → num {T.val:=num.val} E → T R R → +TR1 R → -TR1 R →  T → ( E ) T → num R.i: R前面子表达式 的值 R.s: 分析完R时子表 达式的值 国防科技大学计算机系602教研室

计算表达式9－5＋2 E E.val=6 R.i=9 R R.s=6 T T.val=9 num num.val=9 - T.val=5 T E → T { R.i:=T.val } R { E.val:=R.s } R → + T { R1.i:=R.i+T.val } R1 { R.s:= R1.s } R → - T { R1.i:=R.i-T.val } R1 { R.s:= R1.s } R →  { R.s:=R.i } T → ( E ) { T.val:=E.val } T → num { T.val:=num.val } 计算表达式9－5＋2 E E.val=6 R.i=9 R R.s=6 T T.val=9 num num.val=9 - T.val=5 T R.i=4 R R.s=6 R.s=6 num num.val=5 + T T.val=2 R R.i=6  num.val=2 num 国防科技大学计算机系602教研室

一般方法 假设有翻译模式： A→A1Y {A.a:=g(A1.a,Y.y) } A→X {A.a:=f(X.x)} 它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。 消除左递归： A→XR R→YR |  翻译模式变为 ： A → X {R.i:=f (X.x)} R {A.a:=R.s} R → Y {R1.i:=g(R.i,Y.y) } R1 {R.s:=R1.s} R →  {R.s:=R.i} R.i: R前面子表达式 的值 R.s: 分析完R时子表 达式的值 国防科技大学计算机系602教研室

XYY A→A1Y {A.a:=g(A1.a,Y.y)} A→X {A.a:=f(X.x)} A.a=g(g(f(X.x),Y1.y), Y2.y) A A.a=g(f(X.x),Y1.y) A Y2 A.a=f(X.x) A Y1 X 国防科技大学计算机系602教研室

XYY A A.a= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y) X R A → X {R.i:=f (X.x)} R {A.a:=R.s} R → Y {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s} R →  {R.s:=R.i} XYY A A.a= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y) X R R.i=f(X.x) R.s= g(g(f(X.x),Y1.y), Y2.y) Y1 R R.i= g(f(X.x),Y1.y) R.s= g(g(f(X.x),Y1.y), Y2.y) Y2 R R.i= g(g(f(X.x),Y1.y), Y2.y)  国防科技大学计算机系602教研室

构造抽象语法树的属性文法定义转化成翻译模式 E→E1+T {E.nptr:=mknode(‘+’,E1.nptr,T.nptr)} E→E1-T {E.nptr:=mknode(‘-’,E1.nptr,T.nptr)} E→T {E.nptr:=T.nptr} 国防科技大学计算机系602教研室

构造抽象语法树的属性文法定义转化成翻译模式 E → T {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:=R.s} R →  {R.s:=R.i} T → ( E ) {T.nptr:=E.nptr} T → id {T.nptr:=mkleaf(id,id.entry)} T → num {T.nptr:=mkleaf(num,num.val)} 国防科技大学计算机系602教研室

使用继承属性构造 a－4＋c的抽象语法树 E.nptr E R. s T T.nptr R R. i R. s - T.nptr T R E → T {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:=R.s} R →  {R.s:=R.i} T → ( E ) {T.nptr:=E.nptr} T → id {T.nptr:=mkleaf(id,id.entry)} T → num {T.nptr:=mkleaf(num,num.val)} E.nptr E R. s T T.nptr R R. i R. s - T.nptr T R R. i id R. s R R. i + num T T.nptr + - id  num 4 To entry for c id To entry for a id 国防科技大学计算机系602教研室

6.4.3 递归下降翻译器的设计 如何在递归下降分析中实现翻译模式，构造递归下降翻译器 国防科技大学计算机系602教研室

设计递归下降翻译器的方法 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数 1. 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数 函数的返回值为A的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性 A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。 国防科技大学计算机系602教研室

设计递归下降翻译器的方法 2. 非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。 国防科技大学计算机系602教研室

设计递归下降翻译器的方法 3. 每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作： i) 对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。 ii) 对于每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…,bk)，其中，b1,b2,…,bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。 iii) 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。 国防科技大学计算机系602教研室

构造抽象语法树的属性文法定义转化成翻译模式 E → T {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:=R.s} R →  {R.s:=R.i} T → ( E ) {T.nptr:=E.nptr} T → id {T.nptr:=mkleaf(id,id.entry)} T → num {T.nptr:=mkleaf(num,num.val)} 国防科技大学计算机系602教研室

非终结符E、R、T的函数及其参数类型 用oddop代表＋和－ R → oddop function E:↑AST-node; function R(in:↑AST-node): ↑AST-node; function T: ↑AST-node;  用oddop代表＋和－ R → oddop T {R1.i:=mknode(addop.lexme, R.i,T.nptr)} R1 {R.s:=R1.s} R→  {R.s:=R.i} 国防科技大学计算机系602教研室

产生式R→addop TR|的分析过程 procedare R; begin if sym=addop then begin advance;T; R end else begin /*do nothing*/ end;   国防科技大学计算机系602教研室

function R (in:↑AST-node): ↑AST-node; var nptr, i1,s1,s: ↑AST-node; R → oddop T {R1.i:=mknode(addop.lexme, 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 /*产生式 R→addop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode (addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:= in; return s end; 国防科技大学计算机系602教研室

6.5 自下而上计算继承属性 在自下而上的分析过程中实现L-属性文法的方法 6.5 自下而上计算继承属性 在自下而上的分析过程中实现L-属性文法的方法 可实现任何基于LL(1)文法的L-属性文法，还可以实现许多（不是所有）基于LR(1)文法的L-属性文法 国防科技大学计算机系602教研室

6.5.1 从翻译模式中去掉嵌入在产生式中间的动作 要求把所有的语义动作都放在产生式的末尾 6.5.1 从翻译模式中去掉嵌入在产生式中间的动作 要求把所有的语义动作都放在产生式的末尾 转换方法，它可以使所有嵌入的动作都出现在产生式的末尾 加入新的产生式M→ 把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M→的末尾 国防科技大学计算机系602教研室

翻译模式 转换为 E → TR R → ＋T {print (‘＋’)} R | －T {print (‘－’)} R |  T → num {print (num.val)} 转换为 R → ＋TMR | －TNR |  M →  {print (‘＋’)} N →  {print (‘－’)} 国防科技大学计算机系602教研室

作业 P164 - 1，2，5，7 P164 - 11，12（选作） 国防科技大学计算机系602教研室