1、编译原理模拟试题六一、是非题（请在括号内，正确的划，错误的划）（每个 2 分，共 20 分）1设 r 和 s 分别是正规式，则有 L(r|s)=L(r)L(s)。()2确定的自动机以及不确定的自动机都能正确地识别正规集。()3词法分析作为单独的一遍来处理较好。 ( )4构造 LR 分析器的任务就是产生 LR 分析表。 ()5规范归约和规范推导是互逆的两个过程。 ( )6同心集的合并有可能产生新的“移进”/“ 归约”冲突。 ( )7LR 分析技术无法适用二义文法。 ( )8树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 ()9程序中的表达式语句在语义翻译时不需要回填技术。 ()10
2、对中间代码的优化依赖于具体的计算机。 ( )二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)( 每个 4 分，共 40 分)1编译程序绝大多数时间花在_ 上。A( ) 出错处理 B( ) 词法分析 C( ) 目标代码生成 D ( ) 表格管理2 编译程序是对_。 A( ) 汇编程序的翻译 B( ) 高级语言程序的解释执行 C( ) 机器语言的执行 D ( ) 高级语言的翻译 3 采用自上而下分析，必须_。A( ) 消除左递归 B( ) 消除右递归C( ) 消除回溯 D ( ) 提取公共左因子 4在规范归约中，用_来刻画可归约串。A( ) 直接短语 B( ) 句柄 C( )
3、最左素短语 D ( ) 素短语 5 若 a 为终结符，则 A- a 为_项目。A( ) 归约 B( ) 移进 C ( ) 接受 D ( ) 待约 6间接三元式表示法的优点为_。 A( ) 采用间接码表，便于优化处理 B( ) 节省存储空间，不便于表的修改 C( ) 便于优化处理，节省存储空间 D( ) 节省存储空间，不便于优化处理 7基本块内的优化为_。A. ( ) 代码外提，删除归纳变量 B( ) 删除多余运算，删除无用赋值 C( ) 强度削弱，代码外提 D ( ) 循环展开，循环合并 8. 在目标代码生成阶段，符号表用_。A( ) 目标代码生成 B( ) 语义检查C( ) 语法检查 D (
4、 ) 地址分配9若项目集 Ik 含有 A- ，则在状态 k 时，仅当面临的输入符号 aFOLLOW(A)时，才采取“A- ”动作的一定是_。A. ( ) LALR 文法 B( ) LR(0)文法 C( ) LR(1)文法 D ( ) SLR(1)文法10堆式动态分配申请和释放存储空间遵守_原则。 A. ( ) 先请先放 B( ) 先请后放 C( ) 后请先放 D. ( ) 任意三、填空题(每空 1 分，共 10 分)1词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。 2语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。3分析句型时，应用算
5、符优先分析技术时，每步被直接归约的是_最左素短语_，而应用 LR 分析技术时，每步被直接归约的是 _句柄_。4语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰_、_四无式表示_与_三元式表示_等。5按 Chomsky 分类法，文法按照_规则定义的形式_进行分类。 6一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归_定义的规则。 四、简答题（20 分）1. 文法 GS 为： S-Ac|aB A-ab B-bc 写出 L(GS) 的全部元素。解：S=Ac=abc 或 S=aB=abc 所以 L(GS)=abc2. 构造正规式 1(0|1)*101 相应的 D
6、FA。解：先构造 NFA： 确定化： 重新命名，令 AB 为 B、AC 为 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
7、),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S) =(a,S),S,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|a H-LSo| K-dML| L-eHf M-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 的算符优先关系表并说明 GS 是否未算符优先文法。 (3) 计算 GS 的优先函数。 (4) 给出输入串 (a,a)# 的算符优先分析过程。解：（1）各符号的 FIRSTVT 和 LASTVT：（2）算符优先关系表： （3）对应的算符优先函数为： （4）句子(a,a)# 分析过程如下：
