( E .t r u e )
(1 ) 和 ( 5 ） 拉链（真）
c<d e<f
( 4 ) g o to ( 6 ) g o to „„ (p -1 ) (p + 1 ) „„ (q -1 ) (q )
( E .f a l s e )
( 4 ) 和 (6 ) 拉链（假）
(7 )( S 的 四 元 式 „„） (q )
While E do S
Begin: E 的代码
E.true: S 1 的代码
Goto begin
E.true E.false
E.false:
改写为： W->while Wd->W E do S->WdS L->L;S|S 改写为：L->S Ls->L; L->LsS;
3、翻译 C->if E then{backpatch(E.true,nextstat); C.chain:=E.false;} S->CS1 {S.chain:=merge(C.chain,S1.chain)} Tp->CS else {q:=nextstat;emit(‘goto’-); backpatch(C.chain,nextstat); Tp.chain:=merge(S.chain,q);} S->TpS2{S.chain:= merge(Tp.chain, S2.chain);} W->while{W.codebegin:=nextstat} Wd->W E do S->WdS{backpatch(S.chain,wd.codebegin) emit(‘GOTO’ W.codebegin) S.chain:=Wd.chain}
P→D；E D→D；|id:T T→char | integer | aray [num]of T| ↑T E→literal|num | id| E mod E| E [E]|E↑ P代表程序；D代表说明；E代表表达式。如程序语句： key: integer; key mod 1999 语言本身提供两种基本类型：char和integer。 除此之外还有缺省的基本类型type_ error和void。假定所有数组 都从下标1开始
二、控制语句中布尔表达式的翻译
控制语句 S if E then S E 的代码 E.true: S 的代码 goto out S 2 的代码 out:
1 1 2
else S E.true E.false
E.false:
. 把条件转移的布尔表达式E 翻译成仅含 条件真 转 和 无条件 转 的四元式 E：a rop b if a rop b goto E.true goto E.false
E->(E1) {E.true:=E1. true; E.codebegin:=E1.codebegin;E.false:=E1.false;} E-> id1rop id2 {E.true:=nextstat; E.codebegin:= nextstat; E.false:= nextstat+1; emit(‘if’id1.place’rop’id2.place’goto’-); Emit(‘goto’-)} E->true {E.true:=nextstat; E.codebegin:= nextstat; Emit(‘goto’-)}
8.6 控制语句的翻译
一条件转移 1、文法 S->if E then S| if E then S else S|while E do S|begin L end|A L->L;S|S S语句E布尔表达式 L语句串 A 赋值句
2、文法改写
控制语句 S if E then S E 的代码 E.true: S 1 的代码
S->A{S.chain=0;} L->S{L.chain:=S.chain} Ls->L;{backpatch(L.chain,nextstat)} L->LsS{L.chain:=S.chain} S->begin L end {S.chain:=L.chain}
例:将while(a<b)do if(c<d)then x:=y+z 翻译为四元式
语 句 if a < b o r c < d a n d e < f t h e n S e l s e S 的 四 元 式 ( 1 ) if a < b ( 2 ) g o to ( 3 ) if ( 5 ) if
1
1
2
g o to (7 ) (3 ) g o to (5 ) (p + 1 ) g o to (p + 1 ) (7 )
2
(p ) g o to
(S 的 四 元 式 „„）
自下而上分析中的一种翻译方案： (1) E→ E1 or E 2 { backpatch(E 1.false, E 2.Codebegin); E.Codebegin:= E 1.codebegin; E.true:=merge(E 1.true, E 2.true) E.false:= E 2.false} (2)E→ E1 and E 2 { backpatch(E 1.true, E 2.codebegin); E.Codebegin:= E 1.codebegin; E.true:= E 2.true; E.false:= merge(E 1.false, E 2false);} (3) E → not E 1 { E.true:= E 1.false; E.Codebegin:= E 1.codebegin; E.false:= E 1.true
语句 if a<b or c<d and e<f then S1 else S2 的四元式 (1) if a<b goto (7) //转移至(E.true ) (2) goto (3) (3) if c<d goto (5) (4) goto (p+1) //转移至(E.false) (5) if e<f goto (7) //转移至(E.true ) (6) goto (p+1) //转移至(E.false) 1 (7)( S 的四元式 // (E.true ) 入口 …… (p-1) ……） (p) goto (q) (p+1) (S2 的四元式 //(E.false)入口 …… (q-1) ……） 问题：有些地址在生成四元式时 无法确定。 (q)
为了记录需回填地址的四元式，使用“拉链”法。把需回填 Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａｌｓｅ 的四元式拉成一链，分别称做“真”链和“假”链 （１０） … ｇoｔｏ Ｅ．ｔｒｕｅ … （２０） … ｇｏｔｏ Ｅ．ｔｒｕｅ … （３０） … ｇｏｔｏ Ｅ．ｔｒｕｅ 则链成 （１０） … ｇｏｔｏ （０） … （２０） … ｇｏｔｏ （１０） … （３０） … ｇｏｔｏ （２０） 把地址（３０）称作“真”链链，０为链尾标志，即地址（１ ０）为“真”链链尾。
例如 a<b or c<d and e<f ： 可 翻译成如下四元式： (1) if a<b goto E.true (2) goto (3) (3) if c<d goto (5) (4) goto E.false (5) if e<f goto E.true (6) goto E.false
(翻译不是最优)
确定标识符类型的部分翻译模式 （1）P→D；E （2）D→D；D （3）D→id:T {addtype (id. Entry, T. type)} （4）T→char {T. Type:= char} （5）T→integer {T. Type:= integer} （6）T→↑T1 {T. Type:= pointer (T1. type)} （7）T→array [num]of T1 {T. Type: = array (num.Val, T1.type)}
S Wd S
W
E
do
C
S
while
a < b
if
E
then
A
c <
d
类型和声明（Types and declarations）
一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型: 基本类型：int, float, double, char, bool等等. 也可能允许在基本类型基础上用 户自己定义的类型，如枚举型. 复合类型：数组,指针，记录/结构/联合,类等等.这些类型由基本类型构成. 复杂类型：链表，栈，队，树，堆，表格等等.可以把它们组织成ADT. 一个语 言不一定支持这类高级的抽象。 声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传 给编译，声明的地方传递生命周期信息
语义描述使用的变量和过程： E.true ： “真”链， E.false ： “假”链 。 E.codebegin ： E 的第一个四元式 Nextstat： 下一四元式地址 过程： emit( ) 输出一条四元式，而 nextstat+1 merge(p1, p2) 把 p1 的链首填在 p2 的链尾 例： merge(p1, p2) (p10) goto ( 0) …… p1 链 (p100) goto (p10) ……` (p1) goto (p100) (p20) goto( 0) (p1) …… p2 链 (p200) goto (p20) …… (p2) goto (p200) 回填： backpatch(p,t) 把 链首p 所链接的每个四元式 的第四区段都填为 t
也有些语言允许声明初始化变量。如 double calculate(int a,
:
•
• • •
•
double b); // function prototype int x = 0; // global variables available throughout double y; // the program int main() { int m[3]; // local variables available only in main char *n;