第六、七章属性文法、语法制导翻译和中间代码

Presentation on theme: "第六、七章属性文法、语法制导翻译和中间代码"— Presentation transcript:

1 第六、七章属性文法、语法制导翻译和中间代码
1语义处理 2语义形式化 3语法制导翻译 4中间代码 5一些语句的翻译

2 语义处理 程序设计 语言的语义 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，它可以分为类型规则和作用域/可见性规则两大类 类型相容性 变量先声明后引用 名称相关要求 动态语义 程序单位描述的计算 编译程序的语义处理工作 静态语义审查 解释执行动态语义（计算）生成代码... 语 法 分 析 后 的 源 程 序 Þ 语义处理

3 类型相容性 变量先声明后引用 名称相关要求 解释执行动态语义（计算）生成代码...

4

5 语义形式化 语义建模 文法模型---- 属性文法 命令式或操作式模型 ----- 操作语义学 应用式模型-----指称语义学
文法模型 属性文法 命令式或操作式模型 操作语义学 应用式模型-----指称语义学 公理式模型-----公理语义学 规格说明模型-----代数数据类型

6 属性文法 表达式文法 E—>T+T| T or T T—>n | b ET1 + T2 { T1.type = int
T2.type= T1.type E.type :=int} E T1 or T2 { T1.type = bool T2.type= T1.type E.type :=bool} T  n { T.type := int} T  b { T.type := bool}

7 操作语义 描述一段程序的含义是通过执行该段程序所改变的计算机（无论是真实计算机还是虚拟计算机）状态来反映。计算机里所有的寄存器的值和存储单元的值作为计算机的状态。 For (expr1;expr2;expr3){ expr1; Loop:if expr2=0 goto out } … expr3; goto loop out: ...

8 公理语义 公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。 一般的记号 {P} S {Q} 程序正确性的证明 给定P,什麽是它的规格说明S 给定规格说明S,开发实现此规格说明的程序P S和 P执行同样的功能吗

9 {x>3} x=x-3 {x>0}, (x>5)(x>3), {x>0}{x>0}
{x>5} x=x-3 {x>0} While 循环 (I and B) S {I} {I} while B do S end {I and (not B)} I是循环不变式。 if--then--else {B and P} S1 {Q}, {(not B) and P} S2 {Q} {P} if B then S1 else S2{Q}

10 指称语义 指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数
特点： 不但对全部程序赋予全文而且对程序设计语法 每一个语法成分短语（表达式，命令，声明…） 都给予含义。 每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。 即 语义结构 平行于语法结构。

11 语义函数： 程序设计语言的语义利用映射函数来证 明。
语义函数将短语映射到它的指称。

12 例： 二进制数语言 或 语法实体 指称（十进制数） 或 语义实体 二进制数文法 Numeral::=0 ::=1 ::= Numeral 0 ::=Numeral 1 自然数 Natrual={0,1,2,3,…} 语义函数 Valuation:NumeralNatural

13 Valuation[101] 表示把Valution施用于101
Valuation[N] 把它施用于N 定义: Valuation（用四个方程)因为有四个形式numeral Valuation[0] 0 Valuation[1] 1 Valuation[N0] 2Valution [N] Valuation[N1] 2Valution [N]+1 所以： Valuation[110]=2  Valuation[11] = 2  (2  Valuation[1]+1) =2 (2  1+1) =6

14 规格说明模型-代数数据类型 描述实现一个程序的各种函数间的关系。
如表明一个实现服从任何两个函数间的这种关系，则可以声明这个实现是此规格说明的正确实现。

15 语法制导的翻译 一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言） 设是输入字母表且是输出字母表。定义由语言 L1 *到语言L2  *的一个翻译是由*到 *的一个关系T,使得T的定义域为L1且T的值域为L2 。 使(x,y) ∈T的句子y叫做x的一个输出.

16 语法制导的翻译 直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。
例： 下列翻译模式，它定义翻译，即对每个输入x，其输出是x的逆转。定义此翻译的规则是 产生式 翻译成分 (1)s0s (1)s=s0 (2)s1s (2)s=s1 (3)s ε (3)s=ε

17 输入输出对可由(,)表示，其中是输入句子形式而是输出句子形式。
(S,S)开始用产生式s0s来扩展得到(0S,S0). 再用一次规则(1)，得到(00S,S00)。 再用规则(2)，就得到(001S,S100). 然后应用规则(3)并得到(001,100)。

18 把下述产生式定义的算术表达式映射到后缀波兰表示：
例： 把下述产生式定义的算术表达式映射到后缀波兰表示： 产生式 翻译成分 EE+T E=ET+ E T E=T T TF T=TF T=F T F F (E) F=E F a F=a

19 确定输入a+aa的输出： (E,E)(E+T,ET+) (T+T,TT+) (a+T,aT+) (a+TF,aFF+)
(F+T,FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+)

20 定义： 一个语法制导的翻译模式是一个五元组T=(N,,， R,S),其中 (1) N是非终结符的有限集。 (2) 是有限的输入字母表。 (3) 是有限的输出字母表。 (4) R是形如A,的规则的有限集,其中 ∈(N∪ )*,∈(N∪ )*且中那组非终结符是中那组非终结符的置换。 (5) S是N中一个特别的非终结符，即起始符。

21 定义： 若T= (N,,, R,S)是SDTS,(T)则称为语法制导的翻译(SDT)，文法Gi=(N, ,P,S)，其中P={A|A,属于R)，称为SDTS T的基础（或输入）文法。文法G0=( N, ,P,S), ，其中P ={A | A,属于R} ，称为T的输出文法。 把语法制导的翻译方法看成是将输入文法Gi中的推导树变换成输出文法G0中的推导树。给了输入句子x，可以按如下方式得到x的一个翻译：先为推导x构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为x的一个翻译。

22 最简单的翻译程序---有限变换器 … a1 a2 an 只读输入磁带 有限控制器 b1 b2 b3 只写输出磁带

23 一个有限变换器M是一个六元组(Q,,, ,q ,F),其中 (1) Q是状态的有限集. (2) 是有限的输入字母表.
定义： 一个有限变换器M是一个六元组(Q,,, ,q ,F),其中 (1) Q是状态的有限集. (2) 是有限的输入字母表. (3) 是有限的输出字母表. (4) 是从Q ∪{})到Q * 的一些有限子集的映射。 (5) q ∈Q是初始状态。 (6) FQ是终态集。 *

24 (4) 由下面的转移图定义。在由qi 结点到qj 结点的一条边上，标记x/y表示 (qi ,x)含有(qj ,y)。
例： 设计一个有限变换器来识别由产生式 Sa+S | a-S | +S | -S | a 生成的算术式，并从这些算术式中去掉多余的一元运 算符。例如，我们会把- a + - a a翻译成- a - a +a . 令M=（Q, ,, ,q ,F), 其中 (1)Q={q0 ,q1 ,q2 , q3 ,q4 }. (2)={a,+,–}. (3)= . (4) 由下面的转移图定义。在由qi 结点到qj 结点的一条边上，标记x/y表示 (qi ,x)含有(qj ,y)。 (5)F={q1 }.

25 +/e -/e a/-a a/a a/+a q4 q0 q1 q2 q3

26 (2)x∈ 是输入磁带上尚存的输入符号串，且x的最左边那个符号在输入头底下。 (3)y∈* 是到此时为止已发出的输出符号串。
M的一个组态为三元组(q,x,y)，其中 (1)q∈Q是有限控制器的当前状态 (2)x∈ 是输入磁带上尚存的输入符号串，且x的最左边那个符号在输入头底下。 (3)y∈* 是到此时为止已发出的输出符号串。 * *

27 以- a + - a - + - a为输入，M会作下列移动序列：
(q0,- a + - a + - a,)|—(q4, a+ -a a, ) |—(q1, + - a a, - a) |—(q2, - a a, - a) |—(q3, a a, - a) |—(q1, a, - a - a) |—(q3, + - a, - a - a) |—(q3, - a, - a - a) |—(q2, a, - a - a) |—(q1, , - a - a + a)

28 翻译程序----下推变换器 定义P的一个组态为四元组(q,x,,y)，其中q,x和与PDA的情形一样，而y是此刻为止已发出的输出符号串。
一个下推变换器(PDT)是一个八元组(Q,,,, ,q ,Z0,F)，其中除是有限的输出字母表及是由Q ∪ 到Q**的一些有限子集的映射以外，其余所有符号与PDA的符号含意相同。 定义P的一个组态为四元组(q,x,,y)，其中q,x和与PDA的情形一样，而y是此刻为止已发出的输出符号串。

29 例： 设P是下推变换器 （{q},{a, +, },{+,  ,E},{a, +, }, , q, E,{q}) 其中的定义如下： (q,a,E)={(q, ,a)} (q,+,E)={(q,EE+, ) (q,,E)={(q, EE*,+)} (q,e,+)={(q, , )} (q,e, )={(q,  , )}

30 以+aaa为输入，P作如下移动序列: (q, +aaa ,E, ) |—(q, aaa, EE+, ) |—(q, aaa, EEE+, ) |—(q, aa, EE+, a) |—(q, a,  E+,aa ) |— (q, a, E+,aa) |—(q, ,+,aaa) |—(q, , , aaa+)

31 语义制导翻译中的规则A, 属性文法(attribute grammar)是一个三元组:A=(G,V,F)
编译实现: (LR分析）：增加语义栈 归约时进行语义动作

32 文法 E—>T+T| T or T T—>n | b
ET1 + T2 { if T1.type = int and T2.type= int then E.type :=int else error} E T1 or T2 { if T1.type = bool and T2.type=bool then E.type :=bool T  n { T.type := int} T  b { T.type := bool}

33

34 w =n + n 4 n int o # -- 2 T 5 + --- 6 T int 5 + --- 2 T int o # -- 1 E int 2 T int o # -- 4 n 5 + --- o # --

35

36 属性文法 属性文法(attribute grammar)是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法

37 属性有两种 继承的和综合的属性 AX1 X2 …Xn A的综合属性 断言,计算 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性 断言,计算 T(Xj):=f(I(A),... I(Xn)) 1)开始符号没有继承属性. 2)终结符只有综合属性.

38 一个简单台式计算器的语法制导定义 综合属性val 产 生 式 语 义 规 则 Print(E.val) E E1+T E T
产 生 式 语 义 规 则 L E 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

39 惟独只使用综合属性. L 3*5+4的带注释的分析树 E.val=19 E.val=15 T.val=4 T.val=15 F.val=4
digit.lexval=4 F.val=3 digit.lexval=5 digit.lexval=3 3*5+4的带注释的分析树

40 继承属性 一个结点的继承属性值是由此结点的父结，点和/或兄弟结点的某些属性来决定的。 继承属性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)

41 Real id1,id2,id3 D L.in= real T.type=real real id2 id1 id3 .

42 例：定义定点二进制数的CFG: (1) NS•S (2) SSB (3) SB (4) B0 (5) B1

43 非终结符N表示整个二进制数的数值，综合属性v附加在N上：N v 非终结符B 表示一个二进制数字，它有自己的值v ，但该值分配给N的值与它的位置有关，是与2成比例，比例因子f是从S继承的属性,所以：B v f 非终结符S 表示一个二进制数字串，它也有值，但该值与串的位置有关，与f有关与串的长度l有关: S f v l

44 构造数值的属性断言可以如下: N v——>S f1 v 1 l1 • S f 2 v 2 l2
[v=v1+v2; f 1 =1; f2=2-l2] S f v l——> S f1v1 l 1B f 2v2 [f1=2f ; f 2=f; v=v 1+v2;l=l1+1] ——> B f v [l=1] B f v——>0 [v=0] ——>1 [v=f]

45 S  i  l  S  i1  l 1 Bi2 [ i =2 i1+ i2; ;l=l1+1]  B  i [l=1]
N v S  i1  l1 “•” S  i2  l2 [v= i1+ 2-l2 • i2 ] S  i  l  S  i1  l 1 Bi [ i =2 i1+ i2; ;l=l1+1]  B  i [l=1] B  i “0” [i =0] “1” [i =1]

46 对应于每一个文法产生式A  都有与之相关联的一套语义规则，规则形式为b:=f(c1,c2,c3,…,ck)，在这里，f是一个函数而且或者
1. b是A的一个综合属性并且c1,c2,c3,…,ck是产生式右边文法符号的属性，或者 2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,c3,…,ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2, c3,…,ck.

47 语法制导翻译 语义规则和产生式联系起来： 对翻译给出高级说明 进行语义计算 输入符号串 分析树 属性依赖图 语义规则的计算顺序

48 依赖图 由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。 依赖图的构造算法： for分析树中每一个结点n do
for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n do for结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,…ck) do for i :=1 to k do 从ci结点到b结点构造一条有向边

49 . . 分析树的依赖图 D L 6 5 T 4 7 L 8 L 9 10 1 in type 3 entry id3 Real in

50 计算顺序 一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。
语法制导定义说明的翻译可以是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。 具体的实现希望在单遍扫描中完成翻译

51 适用于自底向上的计算 只含有综合属性的语法制导定义 s-属性定义
L-属性定义：如果对于每一个产生式A X1X2Xn，其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1j n)的一个继承属性，这个继承性仅依赖于 1. 产生式中Xj的左边符号的属性； 2. A的继承属性。 适用于自顶向下的分析，也可用于自底向上。 注意，每一个S属性定义都是L属性定义，因为限制1和2仅对继承性使用。

52 描述自顶向下和自底向上多种翻译方法中的属性计算顺序
属性计算的自然顺序 ---深度优先的顺序 procedure dfvisit(n:node); begin for n 的每一个子结点m，从左至右do begin 计算m的继承属性； dfvisit(m) end; 计算n的综合属性 end

53 中间代码 . 何谓中间代码 ( Intermediate code ) ( Intermediate representation ) (
Intermediate language ) 源程序的一种内部表示，不依赖目标机的结构，易于机械生成 目 标代码的中间表示。 . 为什麽要此阶段 逻辑结构清楚；利于不同目标机上实现同一种语言； （ 参考第 12 章的 275,276页 页， ） 利于进行与机器无关的优化 ；这些内部形式也能用于解释。 . 中间代码的几种形式 逆波兰 四元式 三元式 间接三元式 树

54 例 : A + B * ( C - D ) + E / ( C - D ) ^N

55 例 : A + B * ( C - D ) + E / ( C - D ) ^N

56 例 : A + B * ( C - D ) + E / ( C - D ) ^N

57

58 (2) EE1+E2 {E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place)} (3) E - E1 { E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)} (4) E( E1) { E.place:= E1.place} (5) Eid {E.place:=newtemp; P:=lookup(id.name); if Pnil then E.place:=P else error}

59 8.4 控制语句中布尔表达式的翻译 控制语句 S ® if E then S else S E 的代码 .true .true:
1 else S 2 E 的代码 .true .true: goto out E.false: out: E.false

60 ( 不是最优 ) 1 . 把条件转移的布尔表达式 E 翻译成仅含 条件真 转 和 无条件 的四元式 ： a rop b ? if a
goto E.true E.false 如 a<b or c<d and e<f 可 翻译成如下四元式： (1 ) if a<b (2) goto (3) (3) if c<d goto (5) (4) (5) if e<f (6) ( 翻译 不是最优 )

61

62

63 (1) if a<b goto ( E.true ) (2) goto (3) (3 ) if c<d goto (5) (4
E.false) (5 ) if e<f goto ( (6 E.true)( S 1 的四元式序列 …… ……） p (q) S 2 (q-1)

64

65 自下而上分析中的一种翻译方案： (1) E → or E { backpatch(E .false, E .Codebegin);
2 { backpatch(E .false, E .Codebegin); E.Codebegin:= E .codebegin; E.true:=merge(E .true, E .true) E.false:= E .false} (2) and E .codebegin); E.true:= E .true; E.false:= merge(E false);} (3) E not E { E.true:= E .false; .true

66