编译原理模拟试卷
说明向学生提供这门课程的4份模拟考试试题与答案。试题最好分开放题 和客观题两类,客观题提供答案,开放题提供解题思路。如果期末的评估要求学 员提交论文或作品,教师需提供评价标准。 模拟试卷 模拟试卷A 一、处于/*和*/之间的串构成注解,注解中间没有*/,请根据词法分析基本方 法,画出接受这种注解的DFA的状态转换图。 二、根据自上而下的语法分析方法,构造下面文法的LL 1分析表。 D ML T - int | real Lt id R R r , id R | 8 三、根据自下而上的语法分析方法,为下面文法构造规范LR1分析表,画出状 态转换图就可以了。然后说明它是否有动作冲突。 SVE\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 J0 LI J J I read I if I 100 goto L2 write J halt L2 1 I * I goto LI 模拟试卷B 一、叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换 图。 1 | 01 * 0* 二、1通过构造识别活前缀的DFA和构造分析表,来证明文法ErE id|id 是SLRl文法。 2下面左右两个文法都和1的文法等价 E t E M id | idE - M E id | id M T 8M T 8 请指出其中有几个文法不是LR1文法,并给出它们不是LR1文法的理由。 三、为下面的算术表达式文法写一个语法制导的翻译方案,它将每个子表达式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”, il, i2, i3; printf Addresses of jl, J2, j3 o, o, o\n”,jl,j2,j3; } 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 0B.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 flint x long x; x 1; } f2int x long x; x 1; } } 某编译器编译时报错如下 s.c In function fT s.c3 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