2022年编译原理阶段测试题 .pdf-淘文阁

资源描述

《2022年编译原理阶段测试题 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理阶段测试题 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、学而不思则惘，思而不学则殆第一阶段测试卷考试科目 : 编译原理第 1 章至第 4 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择与填充（30）1. 一个正则语言只能对应( )？A. 一个正则文法 B. 一个最小有限状态自动机C. 一个自然语言 D. 一个上下文有关文法2. 对于编译程序而言，输入数据是源程序，输出数据是_。3. 给出在字母表0,1上的“所有以00 结尾的符号串的集合”的语言的正则表达式：_。4. 一个句型中最左的（）称为该句型的句柄。A. 简单短语 B. 短语 C. 非终结符号 D. 终结符号5. Micro

2、语言只有三种语句：（）、输入语句和输出语句。A. GOTO语句 B.赋值语句 C. 条件语句 D.循环语句6. 描述高级语言语法的常用方法有_和 BNF 范式。二、给出与正规式R（ab）*（a|b*）ab 等价的 NFA。（16）三、简述 DFA 与 NFA 有何区别。（14）四、判断下列文法是否具有二义性：GP: PPaP|PbP|cP|Pe|f(18) 五、对于下面的文法GZ，构造句子 (i*i+i)*i的最左和最右推导及相应的语法树。（22） (1) Z:=E (2) E:=T+E (3) E:=T (4) T:=F*T (5) T:=F (6) F:=(E) (7) F:=i 附：

3、参考答案：一、选择与填充（30）1.一个正则语言只能对应( B )？A. 一个正则文法 B. 一个最小有限状态自动机精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 10 页学而不思则惘，思而不学则殆C. 一个自然语言 D. 一个上下文有关文法2. 对于编译程序而言，输入数据是源程序，输出数据是_目标程序 _。3. 给出在字母表0,1上的“所有以00 结尾的符号串的集合”的语言的正则表达式：_(0|1)*00_。4. 一个句型中最左的（ A ）称为该句型的句柄。A. 简单短语 B. 短语 C. 非终结符号 D. 终结符号5. Micro

4、语言只有三种语句：（B ）、输入语句和输出语句。A.GOTO语句 B.赋值语句 C.条件语句 D.循环语句6. 描述高级语言语法的常用方法有_语法图 _和 BNF 范式。二、给出与正规式R（ab）*（a|b*）ab 等价的 NFA。（16）三、简述 DFA 与 NFA 有何区别。（14）解： DFA与 NFA的区别主要有两点：1 是 NFA可以若干个开始状态，而DFA仅只一个开始状态。2 是 DFA的映象 M是从 K 到 K，而 NFA的映象 M是从 K到 K的子集，即映象 M将产生一个状态集合（可能为空集），而不是单个状态。四、判断下列文法是否具有二义性：GP: PPaP|PbP|cP

5、|Pe|f(18) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 10 页学而不思则惘，思而不学则殆解：因为文法存在句型fbfbf ，此句型有两棵不同的语法树，所以文法具有二义性。五、对于下面的文法GZ，构造句子 (i*i+i)*i的最左和最右推导及相应的语法树。（22）(1) Z:=E (2) E:=T+E (3) E:=T (4) T:=F*T (5) T:=F (6) F:=(E) (7) F:=i 解：最左：Z=E=T=F*T=(E)*T=(T+E)*T=(F*T+E)*T=(i*T+E)*T=(i*F+E)*T=(i*i+E

6、)*T =(i*i+T)*T=(i*i+F)*T=(i*i+i)*T=(i*i+i)*F=(i*i+i)*i 最右： Z=E=T=F*T=F*F=F*i=(E)*i=(T+E)*i=(T+T)*i=(T+F)*i=(T*i)*i=(F*T+i)*i =(F*F+i)*i=(F*i+i)*i=(i*i+i)*i 第二阶段测试卷精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 10 页学而不思则惘，思而不学则殆考试科目 : 编译原理第 4 章至第 7 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：

7、姓名：得分：一、选择与填充（30）1. 有限状态自动机能识别( )。A. 上下文无关文法 B. 上下文有关文法 C. 正则文法 D. 短语文法2在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT集合都是 ( )。A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中，分析的关键是( )。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 消除公共前缀4_是这样一种动作文法，即动作符只出现于产生式的末尾。5文法要满足两个条件：_和_才可以使用自顶向下的语法分析方法。6. 文法 GE: E E+T|T, T T*P|P, P(E)|I, 则句型

9、答案：一、选择与填充（30）1.有限状态自动机能识别（C ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 10 页学而不思则惘，思而不学则殆A. 上下文无关文法 B. 上下文有关文法 C. 正则文法 D. 短语文法2在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT集合都是 ( B )。A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中，分析的关键是( A )。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 消除公共前缀4_尾动作文法 _是这样一种动作文法，即动作符只出现于

11、ViFi( 的短语，简单(直接 )短语 ,句柄。解: 句型 ViFi( 的语法树如下: F 是句型 ViFi( 相对于 T 的短语、简单短语、句柄（是句型 ViFi( 相对于 F 的短语、简单短语（是句型 ViFi( 相对于 T 的短语ViF 是句型 ViFi( 相对于 V 的短语精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 10 页学而不思则惘，思而不学则殆ViFi( 是句型 ViFi( 相对于 V 的短语ViFi( 是句型 ViFi( 相对于 S 的短语四、写出表达式 (ab*c)/(ab)d 的逆波兰表示和三元式序列。（15

12、）解：逆波兰表示：abc*ab/d三元式序列：(1) (* ，b，c) (2) (， a， (1) (3) (， a， b) (4) (/，(2)， (3) (5) (， (4)，d) 五、下面的文法是不是LL(1) 文法？若是，请构造相应的LL(1) 分析表。（25）S aD D STe | T bH | H H d | 解: Predict(S aD)=first(aD)=a Predict(D STe)=first(STe)=a Predict(D )=follow(D)=#,b,d,e Predict(T bH)=first(bH)=b Predict(T H)=first(H) fo

13、llow(T)=d,e Predict(H d)=first(d)=d Pridict(H )=follow(H)=e 所以该文法是LL(1) 文法， LL(1) 分析表如下表: a e b d # S 1 D 2 3 3 3 3 T 5 4 5 H 7 6 第三阶段测试卷考试科目 : 编译原理第 8 章至第 10 章（总分 100 分）时间： 90 分钟学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择与填充（30）1. 四元式之间的联系是通过( )来实现的。A指示器 B临时变量 C符号表 D程序变量精选学习资料 - - - - - - - - - 名师归纳总结 - -

14、 - - - - -第 6 页，共 10 页学而不思则惘，思而不学则殆2. 优化可生成 ( )的目标代码。A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用存储空间较小 D. 运行时间短且占用存储空间小3. 下列 ( )优化方法不是针对循环优化进行的。A. 强度削弱 B删除归纳变量 C删除多余运算 D代码外提4. 在目标代码生成阶段，符号表用于( )。A目标代码生成 B语义检查 C语法检查 D地址分配5语法分析是依据语言的_规则进行的，中间代码产生是依据语言的_规进行的。6优化可分为局部优化、_和全局优化三种。二、写出表达式A*(B/C-D)+E/F 的逆波兰中间代码。(15) 三

15、、什么是活动记录？它主要由哪些内容构成？(15) 四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。 (15) 五、文法 GM 及其 LR 分析表如下，请给出对串dada#的分析过程。(30) GM: 1) S VdB2) V e3) V 4) B a 5) B Bda 6) B 状态ACTION GOTO d e a # S B V 0 r3 S3 1 2 1 acc 2 S4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 附：参考答案：一、选择与填充（30）1. 四元式之间的联系是通过( B )来实现的。精

16、选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 10 页学而不思则惘，思而不学则殆A指示器 B临时变量 C符号表 D程序变量2. 优化可生成 ( D )的目标代码。A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用存储空间较小 D. 运行时间短且占用存储空间小3. 下列 ( C )优化方法不是针对循环优化进行的。A. 强度削弱 B删除归纳变量 C删除多余运算 D代码外提4. 在目标代码生成阶段，符号表用于( D )。A目标代码生成 B语义检查 C语法检查 D地址分配5语法分析是依据语言的_语法 _规则进行的，中间代码产生是依

17、据语言的_语义 _规进行的。6优化可分为局部优化、_循环优化 _和全局优化三种。二、写出表达式A*(B/C-D)+E/F 的逆波兰中间代码。(15) 解：ABC/D-*EF/+ 三、什么是活动记录？它主要由哪些内容构成？(15) 解：一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：(1) 临时变量域存放目标程序临时变量的值；(2) 局部数据域存放过程本次执行时的局部数据、简单变量及数组内情向量等；(3) 机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；(4) 存取链为访问其它活动记录中所存放的非局部数据所提供的链地

18、址；(5) 控制链指向主调过程的活动记录；(6) 实参存放主调过程为被调用过程所提供的实参信息；(7) 返回值为主调过程存放被调过程的返回值四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15) 解：该表达式的四元式序列为：(1) (*, b, c, T1 ）(2)(+, a, T1, T2) (3)(*, c, b, T3) (4)(+, T3, a, T4) (5)(-, T4, e, T5) (6)(*, b, c, T6) (7)(+, T6, d, T7) (8)(/, T5, T7, T8) (9)(-, T2, T8, T9) 可以对该表达

19、式进行删除公共子表达式的优化。优化后的四元式序列为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 10 页学而不思则惘，思而不学则殆(1) (*, b, c, T1 ）(2)(+, a, T1, T2) (3)(-, T2, e, T5) (4)(+, T1, d, T7) (5)(/, T5, T7, T8) (6)(-, T2, T8, T9) 五、文法 GM 及其 LR 分析表如下，请给出对串dada#的分析过程。(30) GM: 1) S VdB2) V e3) V 4) B a 5) B Bda 6) B 状态ACTION

20、GOTO d e a # S B V 0 r3 S3 1 2 1 acc 2 S4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 S7 r1 7 S8 8 r5 r5 解：状态栈符号栈输入流动作S0 # dada# r3 S0S2 #V dada# S4 S0S2S4 #Vd ada# S5 S0S2S4S5 #Vda da# r4 S0S2S4S6 #VdB da# S7 S0S2S4S6S7 #VdBd a# S8 S0S2S4S6S7S8 #VdBda # r5 S0S2S4S6 #VdB # r1 S0S1 #S # acc 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 10 页学而不思则惘，思而不学则殆精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 10 页

展开阅读全文