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

编译原理课程测试第二套卷（附解析） 1．（20分）写出字母表( = {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) 接受该语言的最简DFA是： 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 := ( ; Stmt.MayDef := {id.name} } Stmt ( write ( Exp ) { Stmt.MayDef := ( ; Stmt.MayUse:=