02-编译原理课程测试第二套卷(附解析)-编译原理试题-中国科技大学.doc

编译原理课程测试第二套卷（附解析）
1．（20分）写出字母表S = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。

2．（15分）说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。
S ® M a | b M c | d c | b d a
M ® d

3．（10分）为下面的语言写一个无二义的文法：
ML语言中用分号分隔语句的语句块，例如：
( (s ; s ) ; ( s ; s ; s ) ; s ) ; ( s ; s )

4．（20分）考虑一个类Pascal的语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句、写语句，条件语句和循环语句。下面的产生式定义了该语言的语法（其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。
定义Stmt的两个属性：MayDef表示它可能定值的变量集合，MayUse表示它可能引用的变量集合。
（1）写一个语法制导定义或翻译方案，它计算Stmt的MayDef和MayUse属性。
（2）基于MayDef和MayUse属性，说明Stmt1;Stmt2和Stmt2;Stmt1在什么情况下有同样的语义。
Program ® Stmt
Stmt ® id := Exp
Stmt ® read (id )
Stmt ® write ( Exp )
Stmt ® Stmt ; Stmt
Stmt ® if ( Exp ) then begin Stmt end else begin Stmt end
Stmt ® while ( Exp ) do begin Stmt end
Exp ® id
Exp ® lit
Exp ® Exp OP Exp

5．（10分）下面是一个C语言程序：
main()
{
long i;
long a[0][4];
long j;

i = 4; j = 8;
printf(“%d, %d\n”, sizeof(a), a[0][0]);
}
虽然出现long a[0][4]这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：
（1）sizeof(a)的值是多少，请说明理由。
（2）a[0][0]的值是多少，请说明理由。

6．（15分）考虑下面的三地址语句序列：
b := 1
b := 2
if w <= x goto L2
e := b
goto L2
L1: goto L3
L2: c := 3
b := 4
c := 6
L3: if y <= z goto L4
goto L5
L4: g := g + 1
h := 8
goto L1
L5: h := 9
（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。
（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。
（3）若有循环的话，列出构成每个循环的结点。

7．（5分）如果
（1）用编译命令cc test.c会报告有未定义的符号；
（2）用编译命令cc test.c –lusr.a会得到可执行程序（–lusr.a表示连接库libusr.a）。
那么，用编译命令cc test.c –lusr.a –lusr.a是否会报告有多重定义的符号？请说明理由。

8．（5分）C++中的对象声明语句应如何翻译成C语句？如书上图11.11程序中的
Point _center;
应翻译成什么？

编译原理课程测试第二套卷参考答案
1．语言L的正规式是：
(a|b)*(aa|bb)

1
start

3
a
a
b
b
2
0

4
a
a
a
b
b
b
接受该语言的最简DFA是：

S’ ® .S
S ® .M a
S ® .b M c
S ® . d c
S ® . b d a
M ® .d
S ® b .M c
S ® b .d a
M ® .d
S ® b d .a
M ® d .
b
d

2． S’ ® S S ® M a | b M c | d c | b d a M ® d
因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。
等价的SLR(1)文法是
S ® d a | b d c | d c | b d a

3． SL ® S | SL ; S
S ® s | ( SL )

4．（1） Program ® Stmt
Stmt ® id := Exp
{ Stmt.MayDef := {id.name} ;
Stmt.MayUse:= Exp.MayUse }
Stmt ® read (id )
{ Stmt.MayUse := f ; Stmt.MayDef := {id.name} }
Stmt ® write ( Exp )
{ Stmt.MayDef := f ; Stmt.MayUse:= Exp.MayUse }
Stmt ® Stmt1 ; Stmt2
{ Stmt.MayUse := Stmt1.MayUse È Stmt2.MayUse ;
Stmt.MayDef := Stmt1.MayDef È Stmt2.MayDef }
Stmt ® if ( Exp ) then begin Stmt1 end else begin Stmt2 end
{ Stmt.MayUse := Stmt1.MayUse È Stmt2.MayUse È Exp.MayUse;
Stmt.MayDef := Stmt1.MayDef È Stmt2.MayDef }
Stmt ® while ( Exp ) do begin Stmt1 end
{ Stmt.MayUse := Stmt1.MayUse È Exp.MayUse;
Stmt.MayDef := Stmt1.MayDef }
Exp ® id { Exp.MayUse := {id.name} }
Exp ® lit { Exp.MayUse := f }
Exp ® Exp1 OP Exp2
{ Exp.MayUse := Exp1.MayUse ÈExp2.MayUse }
（2） Stmt1.MayDef Ç Stmt2.MayUse = f and
Stmt2.MayDef Ç Stmt1.MayUse = f and
Stmt1.MayDef Ç Stmt2. MayDef = f
5． （1）按照数组size的计算公式，sizeof(a)的值一定是0。
（2）a[0][0]的值是4。虽然a的size是0，但它仍然有起始地址，并且a[0][0]的地址等于a的起始地址。由于X86/Linux机器上，活动记录栈向低地址方向增长，另外由于低地址放低位字节，因此a[0][0]的地址和i的地址一致，其值和i的值一样，等于4。
6．（1） （2）
1
4
2
3
7
8
6
5

b := 1
b := 2
if w <= x goto L2 （1）
e := b
goto L2 （2）
L1: goto L3 （3）
L2: c := 3
b := 4
c := 6 （4）
L3: if y <= z goto L4 （5）
goto L5 （6）
L4: g := g + 1
h := 8
goto L1 （7）
L5: h := 9 （8）
（3）结点5、7和3构成一个循环，其中5是入口结点。

7．不会。连接时，第一次遇到库libusr.a便能解决所有的外部引用。这样在第二次遇到库libusr.a时什么东西也不会加入目标程序。

8．C++语言中类的对象声明不加翻译就成了C语言中相应结构类型的变量声明，不管对象声明出现在程序中的什么地方。