2022年编译原理试题 3.pdf

《2022年编译原理试题 3.pdf》由会员分享，可在线阅读，更多相关《2022年编译原理试题 3.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟试题一一、选择题（每个选择题 2 分，共 20 分）1 文法 G 产生的 的全体是该文法描述的语言。A 句型 B. 终结符集 C. 非终结符集 D. 句子2 若文法 G 定义的语言是无限集，则文法必然是 ：A 递归的 B 前后文无关的 C 二义性的 D 无二义性的3 Chomsky 定义的四种形式语言文法中， 0 型文法又称为 文法； 1 型文法又称为 文法； 2 型语言可由 识别。A 短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法E 图灵机 F 有限自动机 G 下推自动机4 一个文法所描述的语言是 ；描述一个语言的文法是 。A 唯一的 B 不唯一的 C 可能唯一，好可

2、能不唯一5 数组的内情向量中肯定不含有数组的 的信息A维数 B. 类型 C. 维上下界 D. 各维的界差6 在下述的编译方法中，自底向上的方法有 ，自顶向下的分析方法有 。简单优先分析算符优先分析递归下降分析预测分析技术LR （ K）分析 SLR（ k）分析 LL （ k）分析LALR （ K）分析A. B. C. D. E. F. 二、简答题（每小题 5 分，共 20 分）1 LL （ 1 ）分析法对文法有哪些要求？2 常见的存储分配策略有几种？它们都适合于什么性质的语言？3 常见循环优化都有哪些项目？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

3、- - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 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

4、 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*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

5、 - - - - 第 2 页，共 5 页 - - - - - - - - - E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案：一、 D A A C G. A B A F A二、 1 对于 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

6、)= （ i 1,2, ,m ；i j ）2 有三种分配存储空间的方式：（ 1 ） 静态分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。（ 2 ） 栈式分配适用于允许递归调用的程序设计语言；（ 3 ）堆式分配对于允许程序在运行时为变量动态申请和释放存储空间的语言， 采用堆式分配是最有效的解决方案。3 不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。4 一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有

7、：（ 1 ） 临时变量域存放目标程序临时变量的值；（ 2 ）局部数据域存放过程本次执行时的局部数据、简单变量及数组内情向量等；（ 3 ）机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；（ 4 ）存取链为访问其它活动记录中所存放的非局部数据所提供的链地址；（ 5 ）控制链指向主调过程的活动记录；（ 6 ）实参存放主调过程为被调用过程所提供的实参信息；（ 6 ）返回值为主调过程存放被调过程的返回值三、化简后：S ASe|AC A Cb C bC | d四、 DFA 如图所示。相应的正规式为 (c|acc|bc)* 。名师资料总结 - - -精品资料欢迎下载 - -

8、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 五、改造后的文法：S PS S aPS| fS | e P qP P bP | e各候选式的 FIRST 集，各非终结符的 FOLLOW 集为产生式FIRST 集FOLLOW 集S PSq # S aPS fS ea f e # P qPq a,f,# P bP eb e a,f,# LL(1) 分析表为六、分析表如下图所示七、（ 1 ）逆波兰式：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

9、 - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - , 其中， BLE 表示汪或等于时的转向指令； 表示标号。（ 2 ）四元式：(1) ( j, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( )八、化简后的的四元式序列为A :=D+12 E :=E+F C :=28 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -