编译原理模拟试卷

1、说明： 向学生提供这门课程的4 份模拟考试试题与答案。试题最好分开放题和客观题两类，客观题提供答案，开放题提供解题思路。如果期末的评估要求学员提交论文或作品，教师需提供评价标准。模拟试卷模拟试卷A1、 处于 /* 和 */之间的串构成注解，注解中间没有*/，请根据词法分析基本方法，画出接受这种注解的DFA 的状态转换图。2、 根据自上而下的语法分析方法，构造下面文法的LL（ 1）分析表。D TLTint | realLid RR , id R |三、根据自下而上的语法分析方法，为下面文法构造规范LR（1）分析表，画出状态转换图就可以了。然后说明它是否有动作冲突。S V = E | EV E |

2、 idE V何谓语法制导的定义？为下面文法写一个语法制导的定义，它完成一个句子while-do 最大嵌套层次的计算并输出这个计算结果。S EE while E do E | id := E | E + E | id | （E）五、 请根据数据流分析方法，对下面的程序片段作出其程序流图并计算：（ 1）各基本块的到达_定值集INB ；（ 2）各基本块中各变量引用点的ud 链；I := 1J := 0II : J := J + Iread Iif I 100 goto L2write JhaltIII : I := I * Igoto L1模拟试卷B1、 叙述下面的正规式描述的语言，并画出接受该语言

3、的最简DFA 的状态转换图。( 1 | 01 )* 0*2、 ( 1)通过构造识别活前缀的DFA 和构造分析表，来证明文法E E + id | id是SLR(1)文法。( 2)下面左右两个文法都和(1)的文法等价E E + M id | idE M E + id | idMM请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。3、 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号(即值大于零还是小于零)记录在属性 E.sign中(属性值分别用POS或 NEG 表示) 。你可以假定所有的整数都不为零，这样就不用担心零的符号。E E *E | +E

4、| E | unsigned_integer四、一个C语言程序如下：func(i1,i2,i3) long i1,i2,i3;long j1,j2,j3;printf(Addresses of i1,i2,i3 = %o,%o,%on,&i1,&i2,&i3);printf(Addresses of j1,j2,j3 = %o,%o,%on,&j1,&j2,&j3); main()long i1,i2,i3; func(i1,i2,i3);该程序在某种机器的Linux 上的运行结果如下：Addresses of i1,i2,i3 = 27777775460,27777775464,277777

5、75470Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434从上面的结果可以看出，func 函数的 3 个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。五、 考虑下面的三地址语句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1: goto L3L2: c := 3b := 4c := 6L3: if y = z goto L4goto L5L4: g := g + 1h := 8goto L1L5: h := 9（ 1）在该代码中用水平的横线将代码分

6、成基本块，并给每个基本块一个序号。（ 2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（ 3）若有循环的话，列出构成每个循环的结点。模拟试卷C1、 下面是用正规式表示的变量声明：（ int | float ） id （, id ）* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。2、 下面的文法产生代表正二进制数的0 和 1 的串集：B B 0 | B 1 | 1下面的翻译方案计算这种正二进制数的十进制值：BB1 0B. val:=B1.val2|B1 1B. val:=B1.val2+1|1 B. val:= 1 请消除该基础文法的左递归，再重写一个翻译

7、方案，它仍然计算这种正二进制数的十进制值。3、 为下面文法写一个语法制导的定义，用S 的综合属性val 给出下面文法中S产生的二进制数的值。例如， 输入 101.101 时， S. val := 5.625。（不得修改文法。）SL . R| LLL B |BRB R |BB0 | 14、 对于下面C 语言文件s.cf1(int x)long x;x = 1;f2(int x)long x;x = 1;某编译器编译时报错如下：s.c: In function f1 :s.c:3: warning: declaration of x shadows a parameter 请回答，对函数f2 为什

8、么没有类似的警告错误。五、 考虑一个简单语言，其中所有的变量都是整型(不需要显式声明)，并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法(其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关)。Program StmtListStmtList Stmt StmtList | StmtStmt id := Exp; | read (id ); | write ( Exp );Exp id | lit | Exp OP Exp我们把不影响write语句输出值的赋值(包括通过read语句来赋值)称为无用赋值， 写一个语法指导定义，它确定一个程序中出现过赋予无用值

9、的变量集合(不需要知道无用赋值的位置)和没有置初值的变量集合(不影响write 语句输出值的未置初值变量不在考虑之中)。非终结符StmtList和Stmt用下面3个属性(你根据需要来定义其它文法符号的属性) ：(1) uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。(2) uses_out在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。(3) useless本语句表或语句中出现的无用赋值变量集合。模拟试卷D描述由正规式b*(abb*)*(a| )定义的语言，并画出接受该语言的最简DFA。、证明文法E E + id | id是SLR(1

10、)文法。三、考虑一个类Pascal的语言，其中所有的变量都是整型(不需要显式声明)，并且仅包含赋值语句、读语句、写语句，条件语句和循环语句。下面的产生式定义了该语言的语法(其中lit 表示整型常量；OP 的产生式没有给出，因为它和下面讨论的问题无关)。定义Stmt的两个属性：MayDef表示它可能定值的变量集合，MayUse表示它可 能引用的变量集合。写一个语法制导定义或翻译方案，它计算 Stmt的MayDef和MayUse属性。Program StmtStmtid := ExpStmtread (id )Stmtwrite ( Exp )StmtStmt ; StmtStmt if ( Ex

11、p ) then begin Stmt end elsebegin Stmt endStmtwhile(Exp ) do begin Stmt endExpidExplitExpExpOP Exp四、在C语百中，3+和(id + id )+这样的表达式被编译时，编译器都会报告如 下的错误：invalid lvalue in increment现有如下简化的C 语言表达式文法：E E + E | ( E ) | E + |id | num请写一个语法制导定义或翻译方案，它检查+的运算对象是否合法。一个 C 语言程序如下：typedef struct _a short i; short j; short k;a;typedef struct _b long i; short k;b;main() printf(Size of short, long, a and b = %