《编译原理》模拟试题六

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)

2．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 3．词法分析作为单独的一遍来处理较好。 (× ) 4．构造LR分析器的任务就是产生LR分析表。 (√) 5．规范归约和规范推导是互逆的两个过程。 (× )

6．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× ) 7．LR分析技术无法适用二义文法。 (× )

8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 (×) 9．程序中的表达式语句在语义翻译时不需要回填技术。 (√) 10．对中间代码的优化依赖于具体的计算机。 (× )

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1．编译程序绝大多数时间花在_____ 上。

A．( ) 出错处理 B．( ) 词法分析 C．( ) 目标代码生成 D．( ) 表格管理 2． 编译程序是对_____。

A．( ) 汇编程序的翻译 B．( ) 高级语言程序的解释执行 C．( ) 机器语言的执行 D．( ) 高级语言的翻译

3． 采用自上而下分析，必须_____。

A．( ) 消除左递归 B．( ) 消除右递归 C．( ) 消除回溯 D．( ) 提取公共左因子 4．在规范归约中，用_____来刻画可归约串。 A．( )直接短语 B．( )句柄 C．( )最左素短语 D．( )素短语 5． 若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->α · ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α · ”动作的一定是_____。

A. ( ) LALR文法 B．( ) LR(0)文法 C．( ) LR(1)文法 D．( ) SLR(1)文法 10．堆式动态分配申请和释放存储空间遵守_____原则。

A. ( ) 先请先放 B．( ) 先请后放 C．( ) 后请先放 D. ( ) 任意 三、填空题(每空1分，共10分)

1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。

2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。

3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。

4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。

5．按Chomsky分类法，文法按照___规则定义的形式__进行分类。

6．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。 四、简答题（20分） 1. 文法 G[S] 为： S->Ac|aB A->ab B->bc

写出 L(G[S]) 的全部元素。 解：S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}

2. 构造正规式 1(0|1)*101 相应的DFA。 解：先构造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),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分） 已知文法 G[S] 为：

S->a|^|(T) T-> T,S|S

(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。

(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 计算 G[S] 的优先函数。

(4) 给出输入串 (a,a)# 的算符优先分析过程。

解：（1）各符号的FIRSTVT和LASTVT：

（2）算符优先关系表：

（3）对应的算符优先函数为：

（4）句子(a,a)#分析过程如下：