编译原理作业集－第七章 语义分析和中间代码产生
不需要一个临时单元存放结果，那么在编制后面的三元式时如果要用到这些运算结果，可以用这些三元式的编号来代替。
六、应用题：
1. 已知产生布尔表达式的语法定义如下： E→E1 or E2 E→E1 and E2 E→not E1
E→(E1)
E→id1 relop id2
E→id1
a写出翻译模式；
b画出语法树（语义动作也表示在其中）；
c通过对语法树的遍历，写出对布尔表达式a
1. 答案：见教材P187，图7.14。
E→E1 or E2 {E.place:=newtemp; emit(E.place ':=' E1.place 'or' E2.place)} E→E1 and E2 {E.place:=newtemp; emit(E.place ':=' E1.place 'and' E2.place)} E→not E1 {E.place:=newtemp; emit(E.place ':=' 'not' E1.place)} E→(E1) {E.place:= E1.place} E→id1 relop id2 {E.place:=newtemp; emit('if' id1.place relop.op id2.place 'goto' nextstat+3); emit(E.place ':=' '0'); emit('goto' nextstat+2); emit(E.place ':=' '1')} E→id1 {E.place:=id.place}
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 6 - - -
编译原理作业集－第七章 语义分析和中间代码产生
E 动作5 E or 动作1 E 动作4 id (a) relop (<) id (b) id (c) E or 动作2 E 动作3 id (e) relop (<) id (f) relop (<) id (d) 100: if a
104: if c 108: if e 112: T4:=T2 and T3 113: T5:=T1 or T4 2. 画出赋值语句a:=b*-c+b*-c的抽象语法树和DAG图，并写出它的后缀式表示法。 2. 答案：见教材P168，图7.3。 assign assign a * b uminus + * b uminus a + * b uminus c c c 后缀式表示法：a b c uminus * b c uminus * + assign 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 7 - - - 编译原理作业集－第七章 语义分析和中间代码产生 3. 翻译算术表达式a*- (b+c)为 a)：一棵语法树 b)：后缀式 c)：三地址代码 3. 答案：（1） （2） 后缀式： a b c + uminus * （3） 三地址代码序列为： t1:= b + c t2 := - t1 t3 := a* t2 4. 翻译算术表达式 –(a+b)*(c+d) +(a+b+c) 为 a)：四元式 b)：三元式 c)：间接三元式 4. 答案：（1）四元式序列为： op arg1 arg2 result (1) + a b t1 (2) + c d t2 (3) * t1 t2 t3 (4) uminus t3 t4 (5) + a b t5 (6) + t5 c t6 (7) + t4 t6 t7 （2）三元式序列为： op arg1 arg2 (1) + a b (2) + c d (3) * (1) (2) (4) uminus (3) (5) + a b 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 8 - - - 编译原理作业集－第七章 语义分析和中间代码产生 (6) + (5) c (7) + (4) (6) （3）间接三元式表示： statement op arg1 arg2 (1) (11) (11) + a b (2) (12) (12) + c d (3) (13) (13) * (11) (12) (4) (14) (14) uminus 13 (5) (11) (15) + (11) c (6) (15) (16) + (14) (15) (7) (16) 5. 已知数组翻译模式如下： (1) S ? L := E { if L.offset = null then // 简单变量 emit(L.place ?:=? E.place) else //数组元素 emit(L.place ?[? L.offset ?]? ?:=? E.place) } (2) E ? E1 + E2 { E.place := newtemp; emit(E.place ?:=? E1.place ?+? E2.place) } (4) E ? L { if L.offset = null then E.place := L.place else begin E.place := newtemp; emit(E.place ?:=? L.place?[? L.offset ?]?) end } (5) L ? Elist ] { L.place := newtemp; emit(L.place ?:=? Elist.array ?-?, ck); L.offset := newtemp; emit(L.offset ?:=? w ?*? Elist.place) } (6) L ? id { L.place := id.place; L.offset := null } (7) Elist ? Elist1, E { t := newtemp; m:= Elist1.ndim + 1; emit(t ?:=? Elist1.ndim ?*? limit(Elist1.array, m)); emit(t ?:=? t ?+? E.place); Elist.array := Elist1.array; Elist.place := t; 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 9 - - - 编译原理作业集－第七章 语义分析和中间代码产生 Elist.ndim := m } (8) Elist ? id [ E { Elist.place := E.place; E.ndim := 1; Elist.array := id.place } 利用该翻译模式对下面赋值语句：A[i,j] :=B[i,j] + C[A[k,l]] + D[i+j]。 （1）画出并注释语法分析树； （2）翻译成三地址代码； 5. 答案：对于C语言的数组，每维的下界约定为0。例如，对A[10,20]来说，A[0,0]是第一元素，A[i,j]的相对地址为：base + ( i * n2 + j ) * w 三地址序列如下： t11 := i * 20 t12 := t11+j t13 := A-84; t14 := 4*t12 t15 := t13[t14] //A[i,j] t21 := i*20 t22 := t21+j t23 := B-84; t24 := 4*t22 t25 := t23[t24] //B[i,j] t31 := k*20 t32 := t31+l t33 := A-84 t34 := 4*t32 t35 := t33[t34] //A[k,l] t36 := 4*t35 t37 := C-4 t38 := t37[t36] //C[A[k,l]] t41 := i+j t42 := 4*t41 t43 := D-4 t44 := t43[t42] //D[i+j] t1 := t25 +t38 t2 := t1 + t44 t23[t24] := t2 注：A,B,C,D分别表示数组A,B,C,D的基地址。 6. 试把下列C语言程序的可执行语句 main(){ int i; int a[10]; while (i<=10) a[i]=0; 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 10 - - -