2011-2012（二）编译原理B卷

院系：_____________ 专业：_______________ 班级：_________ 学号：___________ 姓名：_____________ 山西师范大学期末考试试题（卷） 2011—2012学年第二学期 院系：__数计学院__ 专业：__计算机__ 考试科目：_ _编译原理___ 试卷号： B卷 山 西 师 范 大 学 2011——2012 学 年 第 二 学 期 期 末 考 试 试 题 （卷） 题 号 分 数 密 封 线 密 封 线 以 内 不 准 作 任 何 标 记 密 封 线 评卷人 复查人 一 二 三 四 五 六 七 八 总分 一、选择题（每题3分，共30分） 1、唯一能被计算机直接识别和执行的语言是（ ）。 A．机器语言 B．汇编语言 C．高级语言 D．低级语言 2、下列属于编译综合阶段的是（ ）。 A．词法分析 B．语法分析 C．语义分析 D．中间代码生成 3、文法 G 产生的（ ）的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 4 ．一个语言的文法是 （ ） A ．有限的 B 不唯一的 C唯一的 5、程序基本块是指（ ）。 A．一个子程序段 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组语句顺序组成的程序段，仅有一个入口和一个出口 6、文法 S→aaS|abc 定义的语言是( )。 A．{a2kbc|k>0} B．{akbc|k>0} C．{a2k-1bc|k>0} D．{akakbc|k>0} 7、给定文法, A::= bA | cc, 下面哪些符号串可由其推导出_____。 ① cc ② b*cc 可选项有： A．① B．①③④⑤ C．①⑤ D．①②⑤ E．①②③④⑤ 8、下列文法是（ ）型文法。 E－> iT|T T－> +iF|iF|F F—> * E |( A．0 B．1 C．2 D．3 ③ b*cbcc ④ bccbcc ⑤ bbbcc

第 1 页 共 2 页

9．如果一个文法是二义的，则必然存在某个句子对应（ ）。

A．恰好两棵相同的推导树 B．恰好两棵不同的推导树 C．两棵或两棵以上不同的推导树 D．最左推导和最右推导的推导树相同 10．下列不属于局部优化的方法有（ ）。

A．多余表达式的删除 B．常量合并 C．删除无用表达式 D．强度削弱 二、（10分）已知文法G[E]：

E→T|E+T T→F|T*F F→(E)|i

画出句型T+T*F+i的语法树，并找出该句型所有短语、直接短语、句柄、素短语和最左素短语。

三、(10分) 设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 四、(10分)考虑文法

S→(S)S |ε

1. 求非终结符S的First集合和Follow集合；（5分）

2. 构建该文法的LL(1)分析表，判断该文法是否是LL(1)文法？为什么？（5分） 五、（20分）有如下文法

S→E

E→bEa | aEb | ba

1. 求该文法的LR(0)项目集规范族及识别活前缀的DFA；（10分） 2. 构建该文法的LR(0)分析表；(5)

3. 该文法是否是SLR(1)文法？为什么？（5分） 六、（20分）考虑下述的语法制导定义

产生式 S→AB A→a B→b

语义规则 B.i:=S.i A.i:=2*B.s S.s:=A.s A.s:=A.i+3 B.s:=B.i+4

1. 画出字符串ab的分析树；(5分)

2. 根据语义规则画出分析树的依赖图；(5分) 3. 根据依赖图写出语义规则的计算顺序；(5分) 4. 假设S.i的初值为3，计算S.s的初值；(5分)

第 2 页 共 2 页

本文来源：https://www.bwwdw.com/article/hvzp.html