编译原理第二次习题课 王静

(a) array(0..99, pointer(real)) (b) array(0..9, array(0..19, integer) 5.4 为下列类型写类型表达式 （a）指向实数的指针数组，数组的下标从0到99 （b）两维数组，它的行下表从0到9,列下标从0到19. （c）函数，它的定义域是从整数到整数指针的函数，它的值域是 由一个整数和一个字符组成的纪录。 (a) array(0..99, pointer(real)) (b) array(0..9, array(0..19, integer) (c) 假定作为值域的记录类型的两个值域分别叫做i和c， 那么该函数的类型表达式为 (integer  pointer(integer))  record((i*integer)*(c*char)

5. 6 下列文法定义字面常量表的表。符号的解释和图5 5.6 下列文法定义字面常量表的表。符号的解释和图5.2文法的那些相同，增加 了类型list， 它表示类型T的元素表。 P  D; E ｜ T  list of T | char | integer D  D; D | id : T ｜ E  (L) | literal | num | id ｜ L  E, L | E 写一个类似5.3节中的翻译方案，以确定表达式(E)和表(L)的类型 P  D; E D  D; D D  id : T { addtype(id.entry, T.type) } //addtype函数将id的 T  char { T.type := char } //类型添到符号表中 T  integer { T.type := integer } T  list of T1 { T.type := list (T1.type) } E  literal { E.type := char } E  num { E.type := integer } E  id { E.type := lookup(id.entry) } // 取符号表中id指向的条目 E  (L) { E.type := list (L.type) } //的类型 L  E { L.type := E.type } L E | L1 { L.type := (L1.type = E.type)? L1.type : E.type

(a) ref :∀α.α  pointer(α) (b) arrayderef: 5.14 使用类型变量表示下列函数的类型 （a）函数ref，它取任意类型的对象作为变元，返回这个对象的指针 （b）函数arrayderef，它以一个数组为变元，数组的下标是整型，数组 的元素是某类型的指针，返回一个数组，它的元素是变元数组的元素 所指向的对象。 (a) ref :∀α.α  pointer(α) (b) arrayderef: ∀α.array(integer,pointer(α) array(integer,α)

6.3 考虑下面的c语言程序： (a)该程序经先前某些C编译器的编译，其目标程序的运行结果是： cp1 = abcdefghij cp2 = ghij 试分析，为什么cp2所指的串被修改了 (b)在x86／Linux机器上经gcc编译后，该程序运行报告段错误，请分析原因。 main() { char * cp1,* cp2; cp1 = "12345"; cp2 = "abcdefghij"; strcpy(cp1,cp2); printf("cp1 = %s \n cp2 = %s \n", cp1,cp2); } (a) 1 2 3 4 5 \ 0 a b c d e f g h i j \ 0 ↑ cp1 ↑ cp2 执行了串拷贝操作后，上面变为 a b c d e f g h i j \0 f g h i j \0 ↑ cp1 ↑ cp2 而cp2的地址没有改变，所以cp2所指的串被修改了 (b)编译器把程序中的字符串常量分配在一个段中，该 段内容在运行中不能被修gi啊。

6. 4 typedef struct _a{ typedef struct _b{. char c1;. char c1; 6.4 typedef struct _a{ typedef struct _b{ char c1; char c1; long i; char c2; char c2 ; long i; double f; }a; double f; }b; 该程序在SPARC／Solaris工作站上的运行结果：Size of a,b = 24, 16 在x86／Linux机器上运行时，结果是： Size of a,b = 20,16 结构体类型a和b的域都一样，仅次序不同，为什么他们需要的存储空间不一样？ 这是由于数据的对齐问题的影响。 SPARC/Solaris上以8对齐 对于a ： （1 ＋ 4）取 8 ＋（1）取8 ＋ 8 ＝ 24 对于b ： （1＋1＋4） 取 8 ＋ 8 ＝ 16 x86／Linux 上以4对齐 对于a ： （1）取4 ＋ 4 ＋（1）取4 ＋ 8 ＝ 20 对于b： （1＋1）取4 ＋ 4 ＋ 8 ＝ 16

f1的声明不做类型检查，f2的声明会做类型检查 6.12下面是一个C语言程序： long f1(i) long I;{ return (i*10); } long f2(long i){ return (i*10); } main() { printf(“f1=%d,f2=%d\n”, f1(10.0), f2(10.0)); 其中函数f1和f2仅形式参数的描述方式不一样。该程序在x86／Linux机器上的运行结果为：f1＝0,f2＝100.请解释原因 f1的声明不做类型检查，f2的声明会做类型检查 在编译函数调用f1（10.0）时，会把浮点数10.0转换 成双精度型，并将其压栈，其低地址的4个字节看成 整数时正好时0. 在编译函数调用f2（10.0）时，会把浮点数10.0转换 成整数10，并将其压栈，于是结果是100.

a ：array(2,array(4,char)) p ：array(2, pointer(char)) 6.14 一个C文件array.c仅有下面两行代码： char a[][4] = {“123”, “456”}; char *p[] = {“123”, “456”} 写出数组a和指针p的类型表达式 a ：array(2,array(4,char)) p ：array(2, pointer(char))

main(){ long I; （a）sizeof（a） ＝ 0 ＊ 4 ＝ 0； （b）a[0][0]指向的实际还是i； 6.18 下面是一个C语言程序 虽然出现long a[0][4]这样的声明，在x86／Linux机器上的该程序还是能通过编译并生产目标代码。请回答下面两个问题： （a） sizeof（a）的值是多少？ （b） a[0][0]的值是多少？ main(){ long I; long a[0][4]; long j; I = 4; j = 8; printf(“%d,%d\n”, sizeof(a), a[0][0]);} （a）sizeof（a） ＝ 0 ＊ 4 ＝ 0； （b）a[0][0]指向的实际还是i；

参数是逆序计算进栈的，因此 先调用f（f），此时，n变为0, 因此再打印n的时候，打印的 结果为0. 6.23 一个C语言程序如下 该程序的运行结果不是所期望的 5 factorial is 120 而是 0 factorial is 120 试说明原因。 int n; Int f(g) int g();{ int m; m = n; if (m == n) return 1; else { n = n -1; return m*g(g); }} main(){ n = 5; printf(“%d factorial is %d\n”, n, f(f));} 参数是逆序计算进栈的，因此 先调用f（f），此时，n变为0, 因此再打印n的时候，打印的 结果为0.

7.4 修改图7.5中计算声明的类型和相对地址的翻译方案，允许名字 表而不是单个名字出现在形式为D->id: T的声明中 D → L:T { L.type = T.type ; L.width = T.width } L→ id,L 1 { enter ( id.name , L.type , offset ) ; offset = offset + L.width ; L1.type = L.type ; L1.width = L.width } L→id { enter ( id.name , L.type , offset ) ; offset = offset + L.width }

需要修改 E→ E1 or E2 和 E→ id1 relop id2 两个产生式的 语法 制导定义。 7.8 表7.3的语法制导定义把B-> E1< E2翻译成一对语句 if E1.place< E2.place goto … goto ... 可以用一个语句 if E1.place>= E2.place goto... 来代替，当B是真时执行后继代码。修改表7.3的语法制导定义，使之产生这种性质的代码。 需要修改 E→ E1 or E2 和 E→ id1 relop id2 两个产生式的 语法 制导定义。 E→ E1 or E2 E1.true = E.true ; E1.false = newlable ; E2.true = E.true ; E2.false = E.false ; E.code = E1.code || gen ( ‘goto’ E1.true ) || gen (E1.false ‘:’ ) || E2.code E→ id1 relop id2 E.code = gen ( ‘if’ id1.place conreop id2.place ‘goto’E.false) conrelop 为原 relop 关系运算符的‘非’关系运算符。

（a）编译器每次遇到可能会跳转到此处的地方会预 7.10 题目略 （a）编译器每次遇到可能会跳转到此处的地方会预 留一个标记，当后面的代码需要跳转时又会在相应 的 地方添加标记，所以会有多条。 （b） L1 是预留给返回的， 本函数没有return，所以 没用L1