24-25-1-编译原理与技术-期末

一、请回答下面词法分析问题（10分）

1（3分）

请给出 C 语言中“标识符”的正则文法 RG（标识符必须以字母 az, AZ 或下划线开头，后面可跟任意个（可为0）字符，这些字符可以是字母、下划线和数字，其他字符不允许出现在标识符中）。

2（7分）

给出下面 C 语言代码的词法分析结果：

int max(int i, int j) /*return maximum of integer i and j */
{
	return i>j?i:j;
}

二（20分）

考虑下列文法 G，回答以下问题。

1. 构建该文法的拓广文法。（3分）
2. 构造 first 集和 follow 集。（3分）
3. 构造该文法的 LR(1) 项目集规范族及识别其所有活前缀的 DFA。（7分）
4. 构造该文法的 LR(1) 分析表。（7分）

三（15分）

下述语法制导定义完成算数表达式求值的翻译目标，请补充相应语义规则，并给出句子 $(4+7)*2n$ 的注释分析树。

四（10分）

有如下的 C 语言声明，写出变量 foo 和 bar 的类型表达式。

typedef struct{
	int *a, b[10];
}CEll, *PCELL;

CELL foo[100];
PCELL bar(int x, CELL y){...}

1. foo 的类型表达式

2. bar 的类型表达式

五（15分）

有如下程序，编译程序采用的参数传递方式不同，得到的变量结果也不同，请说明传值调用、引用调用、复制恢复（假定按从左到右的顺序把结果复制回实参）等参数传递方式的具体做法，并给出各种参数传递情况下下面程序的输出。

program main(input, output);
	var a, b: integer;
	procedure p(x, y, z: integer);
	begin
		y:=y+3;
		z:=z+x
	end;
begin
	a:=5;
	b:=6;
	p(a, a, b);
	writeln('a=', a, 'b=', b)
end.

1. 传值调用

a=5 b=6

2. 引用调用

a=8 b=14

3. 复制恢复

a=8 b=11

六（10分）

输出布尔表达式 x>2 or y=0 and z<=10 的两种三地址码中间代码翻译结果（and 优先级高于 or 优先级）。

1. 数值表示法（假设起始语句编号为 100）

2. 控制流表示法（假设语句起始编号为 200，假定语句的真出口为 x，假出口为 y）

七（20分）

语句 x[i]:=x[i]+y[i] 可以翻译为以下中间代码：

t1:=x-4
t2:=4*i
t3:=x-4
t4:=4*i
t5:=t3[t4]
t6:=y-4
t7:=4*i
t8:=t6[t7]
t9:=t5+t8
t1[t2]=t9

回答以下问题：

1. 对以上中间代码进行优化，并说明采用了哪些优化方法。

t1:=x-4
t2:=4*i
t5:=t1[t2]
t6:=y-4
t8:=t6[t2]
t9:=t5+t8
t1[t2]:=t9

2. 假设目标机器的指令形式为 OP DEST，SRC（OP 包含 MOV, SUB, MUL, ADD 等，DEST 表示目标操作数，SRC 表示源操作数），该机器有三个寄存器 R0, R1, R2（假定各寄存器初始均为空），将优化后的代码转换为目标代码（尽量提高资源利用率，并说明寄存器描述符及地址描述符内容）。