编译原理模拟试卷
说明:向学生提供这门课程的4份模拟考试试题与答案。试题最好分开放题 和客观题两类,客观题提供答案,开放题提供解题思路。如果期末的评估要求学 员提交论文或作品,教师需提供评价标准。 模拟试卷 模拟试卷A 一、处于/*和*/之间的串构成注解,注解中间没有*/,请根据词法分析基本方 法,画出接受这种注解的DFA的状态转换图。 二、根据自上而下的语法分析方法,构造下面文法的LL (1)分析表。 D ML T -> int | real Lt id R R r , id R | 8 三、根据自下而上的语法分析方法,为下面文法构造规范LR(1)分析表,画出状 态转换图就可以了。然后说明它是否有动作冲突。 S^V=E\E V^*E\id EtV 四、何谓语法制导的定义?为下面文法写一个语法制导的定义,它完成一个句子 的while-do最大嵌套层次的计算并输出这个计算结果。 StE E t while E do E | id := E | E + E | id | (E) 五、请根据数据流分析方法,对下面的程序片段作出其程序流图并计算: (1) 各基本块的到达—定值集IN[B]; (2) 各基本块中各变量引用点的ud链; I:= 1 J:=0 LI: J:= J + I read I if I M E + id | id M T 8M T 8 请指出其中有几个文法不是LR(1)文法,并给出它们不是LR(1)文法的理由。 三、为下面的算术表达式文法写一个语法制导的翻译方案,它将每个子表达式E 的符号(即值大于零还是小于零)记录在属性砺加中(属性值分别用POS或 NEG表示)。你可以假定所有的整数都不为零,这样就不用担心零的符号。 E T E *E | +E | —E | unsigned_integer 四、一个C语言程序如下: func (il, i2, i3) long il, i2, i3; ( long jl, j2, j3; printf (“Addresses of il, i2, i3 = %o, %o, %o\n”, printf (“Addresses of jl, J2, j3 = %o, %o, %o\n”, } main () { long il, i2, i3; func (il, i2, i3); 该程序在某种机器的Linux上的运行结果如下: Addresses of il, i2, i3 = 27777775460, 27777775464, 27777775470 Addresses of jl, j2, j3 = 27777775444, 27777775440, 27777775434 从上面的结果可以看出,func函数的3个形式参数的地址依次升高,而3 个局部变量的地址依次降低。试说明为什么会有这个区别。 五、考虑下面的三地址语句序列: b := 1 b :=2 if w <= x goto L2 e := b goto L2 LI: gotoL3 L2: c := 3 b :=4 c := 6 L3: if y <= z goto L4 goto L5 L4: g := g + 1 h := 8 goto LI L5: h := 9 (1) 在该代码中用水平的横线将代码分成基本块,并给每个基本块一个序 号。 (2) 画出该代码的控制流图,每个基本块就用(1)的序号表示。 (3) 若有循环的话,列出构成每个循环的结点。 模拟试卷C 一、下面是用正规式表示的变量声明: (int | float) id (, id )* ; 请改用上下文无关文法表示,也就是写一个上下文无关文法,它和该正规式等价。 二、下面的文法产生代表正二进制数的0和1的串集: B T B0|B 1 | 1 下面的翻译方案计算这种正二进制数的十进制值: B T Bi 0(B.val := Bi.val x 2 ) I Bi 1{B.val := Bi.val x 2 +1) |1 {B.val := 1 ) 请消除该基础文法的左递归,再重写一个翻译方案,它仍然计算这种正二进 制数的十进制值。 三、为下面文法写一个语法制导的定义,用S的综合属性逾/给出下面文法中S 产生的二进制数的值。例如,输入101.101时,S. v«/:= 5.625o (不得修改文法。) StL.R|L LtLB I B RtB R| B B t0| 1 四、对于下面C语言文件s.c fl(int x) long x; x = 1; } f2(int x) long x; x = 1; } } 某编译器编译时报错如下: s.c: In function fT: s.c:3: warning: declaration of x shadows a parameter 请回答,对函数f2为什么没有类似的警告错误。 五、考虑一个简单语言,其中所有的变量都是整型(不需要显式声明),并且仅 包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法(其中lit 表示整型常量;0P的产生式没有给出,因为它和下面讨论的问题无关)。 Programs StmtList StmtList T Stmt StmtList | Stmt Stmt T id := Exp; | read (id ); | write (Exp ); Exp T id | lit | Exp OP Exp 我们把不影响write语句输出值的赋值(包括通过read语句来赋值)称为无 用赋值,写一个语法指导定义,它确定一个程序中出现过赋予无用值的变量集合 (不需要知道无用赋值的位置)和没有置初值的变量集合(不影响write语句输 出值的未置初值变量不在考虑之中)o 非终结符StmtList和Stmt用下面3个属性(你根据需要来定义其它文法符号 的属性): (1) usesjn:在本语句表或语句入口点的引用变量集合,它们的值影响在 该程序点后的输出。 (2) uses.out:在本语句表或语句出口点的引用变量集合,它们的值影响在 该程序点后的输出。 (3) useless:本语句表或语句中出现的无用赋值变量集合。 模拟试卷D 一、描述由正规式b*(abb*)*(a| £)定义的语言,并画出接受该语言的最简DFA。 二、证明文法ErE + id|id是S