CH6.属性文法语法制导翻译 《程序设计语言编译原理》 陈火旺等编著 2000年第3版

Presentation on theme: "CH6.属性文法语法制导翻译 《程序设计语言编译原理》 陈火旺等编著 2000年第3版"— Presentation transcript:

1 CH6.属性文法语法制导翻译 《程序设计语言编译原理》 陈火旺等编著 2000年第3版
程 序 设 计 语 言 编译原理参考答案 CH6.属性文法语法制导翻译 《程序设计语言编译原理》 陈火旺等编著 2000年第3版

2 CH.6.练习题1(P164.) 1.按照表6.1 (P137.)所示的属性文法, 构造表达式(4*7+1)*2的附注语法树。
L Eval=58 n 1.按照表6.1 (P137.)所示的属性文法, 构造表达式(4*7+1)*2的附注语法树。 Tval=58 Tval=29 * Fval=2 Fval=29 digitlexval=2 ( Eval=29 ) Eval=28 + Tval=1 Tval=28 Fval=1 Tval=4 * Fval=7 digitlexval=1 Fval=4 digitlexval=7 digitlexval=4

3 CH.6.练习题2(P164.) 2(1). 对表达式 ((a)+(b)) 按照表6.4 (P146.)
E.nptr 2(1). 对表达式 ((a)+(b)) 按照表6.4 (P146.) 所示的属性文法, 构造该表达式的抽象语法树。 T.nptr ( E.nptr ) E.nptr T.nptr + T.nptr ( E.nptr ) ( E.nptr ) T.nptr T.nptr id + id id id to entry a to entry b

4 CH.6.练习题5(P164.) 5.下列文法对整型常数和实型常数施用加法运算符+生成表达式; 当两个整型数相加时, 结果仍为整型数, 否则结果为实型数: E→E+T|T T→num.num|num (1) 给出确定每个子表达式结果类型的属性文法。 解: 设置综合属性E.typt,T.type表示E和T的结果类型, 类型值分别用int和real表示整型和实型。 属性文法如下：

5 CH.6.练习题5(P164.) 解5. (1) 给出确定每个子表达式结果类型的属性文法(翻译模式)。
E→E1+T { if E1.type=int and T.type=int then E.type:=int else E.type:=real; } E→T { E.type:=T.type; } T→num.num { T.type:=real; } T→num { T.type:=int; }

6 CH.6.练习题7(P164.) 7. 下列文法由开始符号S产生一个二进制数, 令综合属性val给出该数的值, 试设计求S.val的属性文法, 其中, 已知B的综合属性c, 它给出由B产生的二进制位的结果值。例如, 输入 时, S.val=5.625, 其中第一个二进制位的值是4, 最后一个二进制位的值是0.125。。 S→L . L | L S 表示可带小数点的二进制 数串 L→LB | B L 表示二进制数串 B→0 | B 表示二进制位

7 CH.6.练习题7(P164.) 解7: 题意是要求把二进制数串(可以带小数点)翻译为等值的十进制数值。
用综合属性S.val, L.val, B.c表示S, L和B的十进制值。 整数部分的转换规则是：从最高位开始往低位, 开始时val:=最高位值; 以后val:=val*2+下一位的值。 小数部分的转换规则是：从末位开始到十分位, 开始时val:=末位值; 以后val:=val/2+下一位值。 解法1 考虑结合自下而上的语法分析, 只使用综合属性, 可以改写文法。

8 CH.6.练习题7(P164.) 解法1. 属性文法，M表示小数部分的二进制数串: S→L . M S.val:=L.val+M.val
S→L S.val:=L.val L→L1B L.val:=L1.val*2+B.c L→B L.val:=B.c B→ B.c:=0 B→ B.c:=1 M→AM M.val:=A.c+M1.val/2 M→A M.val:=A.c A→ A.c:=0 A→ A.c:=0.5

9 CH.6.练习题7(P164.) 解法1.二进制数串101.101的语法树及自下而上翻译过程,归约时执行语义规则。 S.v= 5.625
L.v= M.v= 0.625 L.v= B.c=1 A.c= M.v=0.25 L.v= B.c=0 1 1 A.c= M.v=0.5 B.c=1 A.c= 0.5 1 1

10 CH.6.练习题7(P164.) 解法2. 综合属性S.val, L.val, B.c表示S, L和B的十进制值, 综合属性L.length计二进制数串的位数, 用L2.val/2L2.length得到小数部分的十进制值。属性文法: S→L1 . L S.val:=L1.val+L2.val /2L2.length S→L S.val:=L.val L→L1B L.val:=L1.val*2+B.c; L.length:=L1.length+1 L→B L.val:=B.c; L.length:=1 B→ B.c:=0 B→ B.c:=1

11 CH.6.练习题7(P164.) 解法2.二进制数串101.101的语法树及自下而上翻译过程,归约时执行语义规则。
S.v= 5.625(=5+5/8) L.v= 5 ; L.l= L.v=5; L.l=3 L.v=2 ; L.l= B.c=1 L.v=2; L.l= B.c=1 L.v= 1 ; L.l=1 B.c=0 1 L.v=1; L.l= B.c=0 1 B.c=1 B.c=1 1 1

12 CH.6.练习题11(P165.) 11. 设下列文法生成变量的类型说明:
文法的句子如 a, b, c : integer 解(1). 翻译模式如下: D → id L { addtype(id.entry, L.type) } L → , id L1 { L.type:=L1.type addtype(id.entry, L.type) } L → :T { L.type:=T.type } T → integer { T.type:=int } T → real { T.type:=real }

13 CH.6.练习题(补充题) 设下列文法生成配对的圆括号: S → (L) S → a L → L , S L → S
(1) 建立一个属性文法, 输出配对括号的个数, 例如符号串 (a,(a,a)) 将输出2; (2) 构造一个翻译模式, 打印每个a的嵌套深度, 例如符号串 ((a),a) 将打印2, 1。

14 CH.6.练习题(补充题) 解(1). 设综合属性S.n, L.n计配对括号的个数, 属性文法如下: S’ → S print( S.n)
S → (L) S.n :=L.n+1 S → a S.n :=0 L → L1,S L.n :=L1.n+S.n L → S L.n :=S.n 符号串 (a,(a,a))的分析和翻译, 见图 ⑩ S.n=2 ⑨ ( L.n=1 ) ⑧ , S.n=1 L.n=0 ⑦ ② S.n=0 ( L.n= ) ⑥ ① L.n=0 , S.n=0 a ④ ⑤ S.n=0 a ③ a

15 CH.6.练习题(补充题) 符号串((a),a)的分析和翻译, 见图:
S’ 解(2). 设继承属性S.d, L.d计a的嵌套深度, 遍历到a结点时打印S.d值, 翻译模式如下: S’ → { S.d :=0 } S S → ( { L.d :=S.d+1 } L ) S → a { print( S.d) } L → {L1.d :=L.d } L1 , { S.d :=L.d } S L → { S.d :=L.d } S {S.d=0} S ( {L.d=1} L ) {L1.d=1} L1 , {S.d=1} S a {pt(S.d=1)} {S.d=1} S ( {L.d=2} L ) {S.d=2} S a {pt(S.d=2)}