成都理工大学2012-2013软件代码开发技术（编译原理）考试试卷（

成都理工大学2012-2013学年第一学期《软件代码开发技术》考试试卷

一，填空题（每题2分，共30分）

1. 源程序的动态错误是源程序中的逻辑错误，它们发生在程序运行的时候，也被成为动态

语义错误。

2. 设计一个编译器，除了具有中间代码生成、代码生成和出错处理功能之外，还应具有哪

些功能：它们分别为_词法分析、语法分析、语义分析、中间代码优化、符号表管理_ 3. 设∑=｛0,1｝上的正规集S由倒数第二个字符为0的所有字符串组成，则该正规集对应

的正规式表示为(0|1)*0(0|1)

4. 假设G是一个文法，S是文法的开始符号，如果S=>x,则称x是该文法的一个句型 5. 中间代码生成器对语法树进行遍历，生成可顺序执行的中间的代码序列，最常用的中间

代码形式是四元式

6. 最右推导也成为规范推导，推导出的句型称为右 句型。

7. LR(k)文法所识别的语言称为LR(k)语言，其中L表示从左到右扫描输入序列，R表示逆

序的最右推导，k表示确定下一动作向前看的终结符个数

8. 将栈顶的符号和文法产生式的右部符号串进行比较，若相等，则用左部符号去替换栈顶

符号串，这种操作称为规约

9. 自上而下语法分析方法遇到的主要问题是回溯和无限循环（死循环） 10. 正规文法，正规表达式和有限自动机三者在某种意义下是 等价的

11. 若为文法G构造的预测分析表中不含多重定义的条目，则称G为回溯文法。 12. 文法符号的属性有两种，一种称为 综合属性，另一种称为几成属性。 13. 一个句型中的最左 直接短语称为该句型的句柄。

14. 如果一个问发的同一个句子存在两棵分析树，则该文法是二义性的

15. 不管任何类型的文法都包括四个组成部分，它们分别是 非终结符、终结符、产生式、

开始符号

二、判断题（每题1分，共10分）

1，确定的和不确定的有限自动机都能识别正规集。（√）

2，有些语言能被确定的有限自动机识别，但不能用正规表达式表示。（×） 3，设L = {a, b, c},M = {b, c, d} , L∪M = {b , c}.（×） 4，在预测分析器的转换图中，其箭弧上的标识必须是终结符。（×）

5，一个项目集中既可以有移进项目，又有可规约项目，使得分析无法进行，这种冲突称为移进/规约冲突。（√）

6，在使用自上而下分析法时，文法应该没有左递归。（√）

7，正规集都可以由一个状态数最少的DFA识别，这个DFA是唯一的。（√） 8，二义文法是SLR(l)文法。（×）

9，正规表达式的运算操作不具有优先级运算。（×） 10，文法G的产生式为 S->（L）|a L->L，S|S 是一个直接左递归文法。（√）

三、选择题（每题1分，共10分） 1，文法G所描述的语言是D的集合。

A．文法G的字汇表V中所有符号组成的符号串 B．文法G的字汇表V的闭包V*中的所有符号串 C．由文法的开始符号推出的所有符号串 D．由文法的开始符号推出的所有终结符号串

2，一个语言的文法是 B 。

A．唯一的 B. 不唯一的 C. 个数有限的

3，若一个文法是递归的，则它所产生的句子个数 A 。 A. 必定是无穷的 B. 是有限个的 C. 根据具体情况而定 4，文法的二义性和语言的二义性是两个 A 的概念。 A. 不同 B. 相同 C. 无法判断 D. 等价 5，巴克斯范式（BNF）是一种广泛采用的 C 的工具。 A. 描述规则 B. 描述语言 C. 描述文法 D. 描述句子 6， B 是两类程序语言处理程序。 A. 高级语言程序和低级语言程序 B. 解释程序和编译程序 C. 编译程序和操作系统 D. 系统程序和应用程序

7，乔姆斯基把文法分为四种类型：0型、1型、2型和3型，其中2型文法指的是 C 。 A．短语文法 B.上下文有关文法 C. 上下文无关文法 D. 正规文法 8，语法分析常用的方法是 A 。 A. 自顶向下、自底向上

B. 自顶向下、自底向上、自左向右

C. 自顶向下、自底向上、自左向右、自右向左 D. 自左向右、自右向左

9.编译程序中的语法分析器接受以 C 为单位的输入，并产生以有关信息供以后各阶段使用。

A. 表达式 B. 产生式 C. 单词 D. 语句 10.LR语法分析栈中存放的状态是识别 B 的DFA状态。 A. 前缀 B. 可规约前缀 C. 项目 D. 句柄 四，综合题（5小题，共50分） 1， 设文法G具有下列产生式：

E -> E Or T|T T -> T and F|F

F -> not F | (E) | true | false

请指出文法G的终结符号、非终结符号和开始符号。（4分） 解答：终结符：｛or,and,not,(,),true,false｝ 非终结符：｛E,T,F｝ 开始符号：｛E｝

2， 根据1中文法G写出句子 not(true and false) 的规范推导并确定句柄。（6分） 解答：规范推导为：

E =>T =>F =>not F =>not (E) =>not (T) =>not (T and F) =>not (T and false) =>not (F and false) =>not (true and false)

由分析树： 可知句柄为：true

3， 有NFA定义如下：

N = （S={0,1}，∑=｛a,b｝,s0 = 0，F = {0}， MOVE = {move(0,a) = 0，move(0,a) = 1，move(1,a) = 0}） (1) 画出N的状态转换图（4分） 解答：

a 0 a,b a 1

(2) 构造N的最小DFA D（7分） 解答：确定DFA ε_闭包（｛0｝）= ｛0｝*A ε_闭包（smove(｛0｝,a)） = ｛0,1｝*B ε_闭包（smove(｛0｝，b)） = ｛1｝*C ε_闭包（smove(｛0，1｝,a)）= ｛0,1｝B ε_闭包（smove(｛0，1｝,b)）= ｛1｝C ε_闭包（smove(｛1｝,a)）= ｛0｝A ε_闭包（smove(｛1｝,b)）=ε DFA为：

a A Ab a C CΠ = ｛｛A，B｝｝,｛C｝｝

B b

move(A,a)= B move(A,b)=｛c｝ move(B,a)= B move(B,b)= ｛c｝

故A,B不可分，将A为｛A,B｝编号0，C编号1,为｛c｝代表 最小DFA为

a 0 b a 1

(3) 给出串aaba,baa的识别过程（4分） 解答：

a a b a 0 0 0 1 0 b a a 0 1 0 0

识别aaba: 识别baa:

4， 设文法G具有下列产生式：

E -> E + T | T T -> T * F | F F –> id | (E)

(1) 消除文法的直接左递归：（4分） 解答：消除左递归后的文法为： E ->T E’

E’->+T E’/ε T ->F T’

T’ ->*F T’/ε F ->id/(E)

(2) 求消除左递归后文法的FIRST和FOLLOW函数：（6分） 解答：

First(F) = ｛id,(｝ First(T’) = ｛*,ε｝ First(T) = ｛id,(｝

First(E’) = ｛+，ε｝

First(E) = First(T) = First(F) =｛id,(｝

Follow(E) = ｛#,)｝

Follow(E’) =Follow(E) =｛#,)｝ Follow(T) =｛+,#,)｝

Follow(T’) =Follow(T) =｛+,#,)｝

Follow(F) = ｛*,+,#｝ (3) 构造其预测分析表。（4分） 解答：

first(TE’) = ｛id，(｝ first(+TE’) = ｛+,ε｝ first(FT’) = ｛id，(｝ first(*FT’) = ｛*,(｝ first(id) = id

first((E)) = ｛（｝ E * + ） （ id # TE’ TE’ ε ε E’ T +TE’ ε FT’ FT’ ε (E) id T’ *FT’ ε F

5，已知文法G3: S` -> E E -> aA|bB A -> cA|d B -> cB|d

(1) 写出句型bccB的所有短语、直接短语和句柄。（4分） 解答：

S’=>E =>bB =>bcB =>bccB

短语：bccB(S’E) ccB(B1) cB(B2) 直接短语：cB(B2) 句柄：cB(B2)

(2) 列出4个项目集I1、I2、I3、I4（如下图），请将这4个项目集补充完整。（7分）

a I1: S` ->.E E->.aA E->.bB I2:E->a.A A->.cA A->d E b I3:E. I4:E->b.B B->.cB B->.d

附加资料：

编译：高级语言可以直接转换成机器语言，也可以翻译成汇编语言，这两个过程称为编译。 解释器与编译器的主要区别：运行目标程序的控制权在解释器而不在目标程序。 解释器优点：（1）其具有较好的动态特性。（2）具有较好的可移植性。 缺点：在时间和空间上的损失较大，运行效率低。 文法的分类：

文法 产生式 语言 自动机 0型文法（短语） α->β 0型语言（短语结构语言，递归可枚举集） 图灵机 1型文法（CSG） 限制1 1型语言（CSL） 线性界线自动机 2型文法（CFG） 限制2 2型语言（CFL） 下推自动机 3型文法（正规） 限制3 3型语言（正规语言，正规集） 有限自动机

LR(1)与LALR(1)的关系：LR(1)与LALR(1)对于移进/规约冲突的解决二者是等价的，而对于规约/规约冲突，由于LALR(1)项目中合并了lookaheads可能会减弱它对规约/规约冲突的解决能力，具体有下述两个结论：

(1) LR(1) DFA中不发生的移进/规约冲突，LALR(1)DFA中也一定不会发生。 (2) 合并后的lookaheads可能会引起LALR(1)项目集中的规约/规约冲突。

a I1: S` ->.E E->.aA E->.bB I2:E->a.A A->.cA A->d E b I3:E. I4:E->b.B B->.cB B->.d

附加资料：

编译：高级语言可以直接转换成机器语言，也可以翻译成汇编语言，这两个过程称为编译。 解释器与编译器的主要区别：运行目标程序的控制权在解释器而不在目标程序。 解释器优点：（1）其具有较好的动态特性。（2）具有较好的可移植性。 缺点：在时间和空间上的损失较大，运行效率低。 文法的分类：

文法 产生式 语言 自动机 0型文法（短语） α->β 0型语言（短语结构语言，递归可枚举集） 图灵机 1型文法（CSG） 限制1 1型语言（CSL） 线性界线自动机 2型文法（CFG） 限制2 2型语言（CFL） 下推自动机 3型文法（正规） 限制3 3型语言（正规语言，正规集） 有限自动机

LR(1)与LALR(1)的关系：LR(1)与LALR(1)对于移进/规约冲突的解决二者是等价的，而对于规约/规约冲突，由于LALR(1)项目中合并了lookaheads可能会减弱它对规约/规约冲突的解决能力，具体有下述两个结论：

(1) LR(1) DFA中不发生的移进/规约冲突，LALR(1)DFA中也一定不会发生。 (2) 合并后的lookaheads可能会引起LALR(1)项目集中的规约/规约冲突。

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