新疆大学：《编译原理》课程教学资源（习题解答）Chapter5_2

5.18假如有下面的Pascal说明： TYPE atype=ARRAY[.-10.10]OF integer a,b:integer END: pcell=fcell: foo=ARRAY [1.100]OF cell FUNCTION ar(rinteger.y:cell):pcell. BEGIN END 写出aype,cell,pcel,foo和bar的类型表达式。 atype:ARRAY(0.9.ARRAY(-10.10.integer ) cell:RECORD(a*integer)产(b*integer)方 pell:POINTER() POINTER(RECORD((ainteger)(binteger))): foo:ARRAY(1.100,cell ) ARRAY(1.100.RECORD((a*integer)*(b*integer))): :integer"cellPOINTER(RECORD((a*integer)(b*integer))) 5.19文法GP1及其产生式如下： P→D:E DD:DIid:T E-(L)|Literal num id L→E,LE 这个文法产生由字面常量组成的表。符号的解释和文法(5.10)相同，增加类型L, 它表示类型T的元素表。写一个类似5.82中图5.33的翻译模式，以确定表达式(E)和(L) 的类型（注：表中每个元素的类型是一样的）。 Did:T{addtype (id.enery,T.TYPE) T-char T.type :char T-integer Ttvpe:=integer Tlist of TTtype:=list (TLtype E→num{E.type nteger E-id E.type:=lookup(id.entry)) E-Literal E.type:=char E-(L){E.type:=list (L.type)) LE.Li{L.type:=IF(E.type-Litype) THEN E.type ELSE type_error L→E{L.type=E.type; 5.20修改图5.34的翻译方案，使之能够处理：

5.18 假如有下面的 Pascal 说明： TYPE atype = ARRAY [0.9, -10.10] OF integer; cell = RECORD a, b : integer END; pcell = ↑cell; foo = ARRAY [1.100] OF cell; FUNCTION bar(r:integer; y:cell) : pcell; BEGIN.END; 写出 atype, cell, pcell, foo 和 bar 的类型表达式。 atype : ARRAY( 0.9, ARRAY( -10.10, integer ) ); cell : RECORD( (a*integer)*(b*integer) ); pcell : POINTER(cell); : POINTER( RECORD( (a*integer)*(b*integer) ) ); foo : ARRAY( 1.100, cell ); : ARRAY( 1.100, RECORD( (a*integer)*(b*integer) ) ); bar : integer*cell → pcell; : integer*cell → POINTER( RECORD( (a*integer)*(b*integer) ) ); 5.19 文法 G[P]及其产生式如下： P→D; E D→D; D | id : T T→ list of T | char | integer E→(L) | Literal | num | id L→E , L | E 这个文法产生由字面常量组成的表。符号的解释和文法（5.10）相同，增加类型 List， 它表示类型 T 的元素表。写一个类似 5.8.2 中图 5.33 的翻译模式，以确定表达式（E）和（L） 的类型（注：表中每个元素的类型是一样的）。 D→ id : T { addtype ( id.enery, T.TYPE) } T→ char { T.type := char } T→ integer { T.type := integer } T→ list of T1 { T.type := list ( T1.type ) } E→ num { E.type := integer } E→ id { E.type := lookup( id.entry ) } E→ Literal { E.type := char } E→ (L) { E.type := list ( L.type ) } L→ E, L1 { L.type := IF (E.type=L1.type) THEN E.type ELSE type_error } L→ E { L.type := E.type } 5.20 修改图 5.34 的翻译方案，使之能够处理：

)语句有值。赋值语句的值是赋值号右边的表达式的值。条件语句或当语句的值是语 句体的值，语句表的值是表中最后一个语句的值。 B) 布尔表达式。加上逻辑算符and,or和not,还有关系算符的产生式，然后给出适当 的翻译规则，计算出这些表达式的类型。 (a: Sid:-E(S.type:=IF id.type=E.type THE void ELSE type_error; S.val:=IF id.type=E.type THEN E.val ELSEval_error S-IF E THEN S(S.type=IF E.type-boolean THEN S1.type ELSE type error S.val :=IF E.type=boolean THEN SLval S-WHILE EDOS(S.type=IF E.type=boolean THEN S1.type ELSE type error S.val :=IF E.type=boolean THEN Sval ELSE S-S1;S2{S.type:=IF(S1.type-void)AND(S2.type-void) THEN void ELSE type_error S.val:=IF(S1.type d)AND(S2.type=void) THEN S2.val ELSE val error (b: E-Ei AND E2 E.type:=IF(E1.type=boolean)AND(E2.type=boolean) THEN boolean ELSE type EOR EEype:-1F (E.typebocan)AND (Epeboocm) THEN boolean ELSE type error E-NOT EE.type:=IF (E1.type=boolean) THEN boolear ELSE type_error E-E1op E2 (E.type:=IF(E1.type=E2.type) THEN boolean ELSE type error 注：叩为关系运算符，包括二，⊙，<>，<

a）语句有值。赋值语句的值是赋值号右边的表达式的值。条件语句或当语句的值是语 句体的值，语句表的值是表中最后一个语句的值。 b）布尔表达式。加上逻辑算符 and,or 和 not, 还有关系算符的产生式，然后给出适当 的翻译规则，计算出这些表达式的类型。 (a): S→ id := E { S.type := IF id.type = E.type THEN void ELSE type_error; S.val := IF id.type = E.type THEN E.val ELSE val_error } S→ IF E THEN S1 { S.type := IF E.type = boolean THEN S1.type ELSE type_error S.val := IF E.type = boolean THEN S1.val ELSE val_error } S→ WHILE E DO S1 { S.type := IF E.type = boolean THEN S1.type ELSE type_error S.val := IF E.type = boolean THEN S1.val ELSE val_error } S→ S1; S2 { S.type := IF (S1.type = void) AND (S2.type = void) THEN void ELSE type_error S.val := IF (S1.type = void) AND (S2.type = void) THEN S2.val ELSE val_error } (b): E→ E1 AND E2 { E.type := IF (E1.type = boolean) AND (E2.type = boolean) THEN boolean ELSE type_error } E→ E1 OR E2 { E.type := IF (E1.type = boolean) AND (E2.type = boolean) THEN boolean ELSE type_error } E→ NOT E1 { E.type := IF (E1.type = boolean) THEN boolean ELSE type_error } E→ E1 op E2 { E.type := IF (E1.type = E2.type) THEN boolean ELSE type_error } 注：op 为关系运算符，包括 =, <>, , =

5.21假定类型各1ik和cell如(5.9)中的定义，下面哪些表达式结构等价？哪些名字等价？ (1)Link (2pointer(cell)(3)pointer(Link)(4)pointer(record(info*integer)(next*pointer(cell)) (1(2(4)结构等价，无名字等价

5.21 假定类型各 link 和 cell 如（5.9）中的定义，下面哪些表达式结构等价？哪些名字等价？ （1）Link（2）pointer(cell)（3）pointer(Link)（4）pointer(record(info*integer)*(next*pointer(cell))) (1)(2)(4)结构等价，无名字等价