《编译原理》模拟试题六

1、编译原理模拟试题六一、是非题（请在括号，正确的划，错误的划 ）（每个2 分，共 20 分）1设 r 和 s 分别是正规式，则有L(r|s)=L(r)L(s) 。 ( )2确定的自动机以及不确定的自动机都能正确地识别正规集。( )3词法分析作为单独的一遍来处理较好。( )4构造 LR 分析器的任务就是产生LR 分析表。( )5规归约和规推导是互逆的两个过程。( )6同心集的合并有可能产生新的“移进 ” /归“约 ”冲突。( )7 LR 分析技术无法适用二义文法。( )8树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。( )9程序中的表达式语句在语义翻译时不需要回填技术。( )10对中

2、间代码的优化依赖于具体的计算机。( )二、选择题 (请在前括号选择最确切的一项作为答案划一个勾，多划按错论)( 每个 4 分，共40 分 )1编译程序绝大多数时间花在_ 上。A ( ) 出错处理B( ) 词法分析C ( ) 目标代码生成D ( ) 表格管理2 编译程序是对_。A ( ) 汇编程序的翻译C ( ) 机器语言的执行B( )D()高级语言程序的解释执行高级语言的翻译3 采用自上而下分析，必须_。A ( ) 消除左递归B ( ) 消除右递归C ( ) 消除回溯D ( ) 提取公共左因子4在规归约中，用_来刻画可归约串。A ( )直接短语B( )句柄C ( )最左素短语D ( )素短语5

3、 若 a 为终结符，则A- a为 _项目。A ( )归约B( ) 移进C( ) 接受D( ) 待约6间接三元式表示法的优点为_。A ( ) 采用间接码表，便于优化处理B ( ) 节省存储空间，不便于表的修改C ( ) 便于优化处理，节省存储空间D ( ) 节省存储空间，不便于优化处理7基本块的优化为_。A. ( )代码外提，删除归纳变量B ( ) 删除多余运算，删除无用赋值C ( ) 强度削弱，代码外提D ( ) 循环展开，循环合并8. 在目标代码生成阶段，符号表用_。A ( ) 目标代码生成B( ) 语义检查C ( ) 语法检查D ( ) 地址分配9若项目集 Ik 含有 A- a FOLLO

4、W(A) 时，才，则在状态 k 时，仅当面临的输入符号采取 “A-”动作的一定是_。A. ( ) LALR文法B( ) LR(0) 文法C ( ) LR(1) 文法D ( ) SLR(1) 文法10堆式动态分配申请和释放存储空间遵守_原则。A.()先请先放B( )先请后放C( )后请先放D.()任意三、填空题 (每空 1 分，共 10 分 )1词法分析基于_正则 _文法进行，即识别的单词是该类文法的句子。2语法分析基于 _上下文无关 _文法进行， 即识别的是该类文法的句子。语法分析的有效工具是 _语法树 _。3分析句型时， 应用算符优先分析技术时，每步被直接归约的是LR 分析技术时，每步被直接

5、归约的是_句柄 _。_最左素短语_，而应用4语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰 _、 _四无式表示_与 _三元式表示 _等。5按 Chomsky 分类法，文法按照_规则定义的形式_进行分类。6一个文法能用有穷多个规则描述无穷的符号串集合（语言） 是因为文法中存在有_递归_定义的规则。四、简答题（ 20 分）1. 文法 GS 为：S-Ac|aBA-abB-bc写出L(GS)的全部元素。解： S=Ac=abc或 S=aB=abc所以 L(GS)=abc2. 构造正规式 1(0|1)*101 相应的 DFA 。解：先构造 NFA ：确定化：重新命名，令AB 为 B、 AC

6、为 C、 ABY 为 D 得：所以，可得DFA 为：3. 文法S-a|(T)T-T,S|S对 (a,(a,a) 和 (a,a),(a),a) 的最左推导。解：对 (a,(a,a)的最左推导为：S=(T) =(T,S) =(S,S) =(a,S)=(a,(T) =(a,(T,S) =(a,(S,S)=(a,(a,S) =(a,(a,a)对(a,a),(a),a) 的最左推导为：S=(T) =(T,S) =(S,S) =(T),S)=(T,S),S) =(T,S,S),S) =(S,S,S),S)=(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S)=(a,S),S,

7、S),S) =(a,a),S,S),S) =(a,a),S),S)=(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S)=(a,a),(a),a)4. 文法：S-MH|aH-LSo|K- dML|L-eHfM-K|bLM判断G 是否为LL(1)文法，如果是，构造LL(1)分析表。解：各符号的FIRST 集和 FOLLOW集为：预测分析表为：由于预测分析表中无多重入口，所以可判定文法是LL(1) 的。五.计算题（ 10 分）已知文法GS为：S-a|(T)T- T,S|S(1) 计算 GS 的 FIRSTVT 和 LASTVT 。(2) 构造 GS 的算符优先关系表并说

8、明GS 是否未算符优先文法。(3) 计算 GS 的优先函数。(4) 给出输入串 (a,a)# 的算符优先分析过程。解：（ 1）各符号的FIRSTVT 和 LASTVT ：（2）算符优先关系表：（3）对应的算符优先函数为：（4）句子 (a,a)#分析过程如下：一、选择题（每个选择题 2 分，共 20分）1文法 G 产生的 的全体是该文法描述的语言。A 句型 B. 终结符集 C. 非终结符集 D. 句子2若文法 G 定义的语言是无限集，则文法必然是 ：A 递归的 B 前后文无关的 C 二义性的 D 无二义性的3 Chomsky 定义的四种形式语言文法中， 0 型文法又称为 文法；1型文法又称为 文

9、法； 2 型语言可由 识别。A 短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法E 图灵机 F 有限自动机 G 下推自动机4一个文法所描述的语言是 ；描述一个语言的文法是 。A 唯一的 B 不唯一的 C 可能唯一，好可能不唯一5 数组的情向量中肯定不含有数组的 的信息A维数 B. 类型 C. 维上下界 D. 各维的界差6在下述的编译方法中， 自底向上的方法有 ，自顶向下的分析方法有 。简单优先分析 算符优先分析 递归下降分析 预测分析技术 LR （K）分析 SLR（ k）分析 LL （ k）分析LALR（ K）分析A. B. C. D. E. F.二、简答题（每小题5分，共

10、20分）1 LL（ 1）分析法对文法有哪些要求？2 常见的存储分配策略有几种？它们都适合于什么性质的语言？3 常见循环优化都有哪些项目？4 什么是活动记录？它主要由哪些容构成？三、（ 8分）化简文法 GS：S ASe | BCaD | aD | ACA Cb | DBSC bC | dB AcD aD四、（ 12 分） 设 L a,b,c*是满足下述条件的符号串构成的语言：(1) 若出现 a ，则其后至少紧跟两个 c ；(2) 若出现 b ，其后至少紧跟一个 c 。试构造识别 L的最小化的 DFA ，并给出描述 L的正规表达式。五、（ 12 分） 已给文法 GS： S SaP | Sf | P

11、 P qbP | q将 GS改造成 LL（ 1）文法，并给出LL（ 1）分析表。六、（ 12 分） 给定文法 GS： S Aa|dAb|Bb|dBa A c B c构造文法 GS的 LR （ 1）分析表。七、（ 8分） 将下面的条件语句表示成逆波兰式和四元式序列：if ab then x:=a+b*c else x:=b-a;八、（ 8分） 给定基本块：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案：一、D A A C G.A B A F A二、 1 对

12、于 G 中的每个产生式 A 1 | 2 | | m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FIRST( i ) FIRST( j )=（1 i， j m ； i j）（2）若有 j ，则其余候选式 i所能推出的符号串不能以FOLLOW(A)中的终结符号开始，即有FIRST( i ) FOLLOW(A)=（i 1,2,m ； i j）2 有三种分配存储空间的方式：（ 1 ） 静态分配 若在编译阶段就能确定源程序中各个数据实体的存储空间大小， 则可以采用较简单的静态存储管理。 适合 静态管理 的语言应具备条件： 数组上下界是常数、 过程调用不允许递归、不允许

13、动态建立数据实体。 （ 2 ） 栈式分配 适用于允许递归调用的程序设计语言 ；（ 3 ） 堆式分配 对于允许程序在运行时为变量 动态申请和释放存储空间 的语言 ， 采用 堆式分配 是最有效的解决方案 。3 不变运算外提；运算强度削弱； 消除归纳变量； 下标变量地址计算优化。4 一个过程的一次执行所需信息的管理，是通过称为 活动记录 的连续存储块来实现的。活动记录的主要容有： （ 1 ） 临时变量域 存放目标程序临时变量的值； （ 2 ）局部数据域 存放过程本次执行时的局部数据、简单变量及数组情向量等； （ 3 ）机器状态域 保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；

14、 （ 4 ）存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址； （ 5 ）控制链 指向主调过程的活动记录；（ 6 ）实参 存放主调过程为被调用过程所提供的实参信息；（ 6 ）返回值 为主调过程存放被调过程的返回值三、化简后：S ASe|AC A Cb C bC | d四、 DFA 如图所示。相应的正规式为(c|acc|bc)*。五、改造后的文法： S PS S aPS| fS | e P qP P bP | e各候选式的 FIRST 集，各非终结符的 FOLLOW集为产生式FIRST 集FOLLOW集SPSq#S aPSa# fSf e e P qPqa,f,#P bPba,f,# e e LL(1) 分析表为六、分析表如下图所示七、（ 1）逆波兰