编译原理期末复习题(含有答案)

编译原理复习题及答案

一、 选择题

1． 一个正规语言只能对应( B )

A 一个正规文法 B 一个最小有限状态自动机

2． 文法G[A]：A→ε A→aB B→Ab B→a是( A )

A 正规文法 B 二型文法

3． 下面说法正确的是( A )

A 一个SLR（1）文法一定也是LALR（1）文法

B 一个LR（1）文法一定也是LALR（1）文法

4． 一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A )

A 必要条件 B 充分必要条件

5． 下面说法正确的是( B )

A 一个正规式只能对应一个确定的有限状态自动机

B 一个正规语言可能对应多个正规文法

6． 算符优先分析与规范归约相比的优点是( A )

A 归约速度快 B 对文法限制少

7． 一个LR（1）文法合并同心集后若不是LALR（1）文法( B )

A 则可能存在移进/归约冲突

B 则可能存在归约/归约冲突

C 则可能存在移进/归约冲突和归约/归约冲突

8． 下面说法正确的是( A )

A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器

9． 下面说法正确的是( A )

A 一个正规文法也一定是二型文法

B 一个二型文法也一定能有一个等价的正规文法

10． 编译原理是对(C)。

A、机器语言的执行 B、汇编语言的翻译

C、高级语言的翻译 D、高级语言程序的解释执行

11． (A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL

12． 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器 B. 汇编器 C. 解释器 D. 预处理器

13． 用高级语言编写的程序经编译后产生的程序叫(B)

A．源程序 B．目标程序 C．连接程序 D．解释程序

14． (C)不是编译程序的组成部分。

二、概念题1、设有文法：P→P+Q|Q

Q→Q*R|RR→(P)|i

（1）证明Q*R+Q+Q是它的一个句型。（3分)

（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)

（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)（4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)2、设有文法：E→E+T|T T→T*F|F F→(E)|i

（1）证明E+T*F是它的一个句型。（3分)

答案：EETETF*

（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语: E+T*F, T*F,直接短语: T*F句柄: T*F（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)

3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。

答案：逆波兰式：(abcd-*+)

三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2)

三、词法分析题给出下面语言的相应文法

L1={anbnambm|n,m≥0}

答案：S→AB|A|B|∑A→aAb|ab B→aBb|ab给出下面语言的相应文法

L2={anbnci|n≥1,i≥0}

答案：S→AB|B

A→a|aA B→bBc|bc给出下面语言的相应文法

L3={anbncm| m,n≥1，n为奇数，m为偶数}。答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc四、词法分析题

1、构造下面正规式相应的DFA

((0|1)*|(11)*)*

（要求：先将正规式转化为NFA，再将NFA确定化，最小化）

2、构造下面正规式相应的DFA

1(0|1)*101

答案：

I I0 I1

{X} Ф{A,B,C} {A,B,C} { B,C} { B,C,D}

{B,C} { B,C} { B,C,D}

{B,C,D} { B,C,E} { B,C,D}

{B,C,E} { B,C} {B,C,D,y}

{B,C,D,y} {B,C,E} { B,C,D}3、构造一个DFA，它接受S={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) ①与此正规式对应的NFA为

.

. 3.2 是非判断，对下面的述，正确的在述后的括号写T，否则写F。

(1)有穷自动机接受的语言是正则语言。（）

(2)若r1和r2是Σ上的正规式，则r1|r2也是。（）

(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（）

(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（）

(5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）

(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）

答案

(1) T (2) T (3) F

(4) F (5) T (6) T

3.3 描述下列各正规表达式所表示的语言。

(1) 0(0|1)*0

(2) ((ε|0)1*)*

(3) (0|1)*0(0|1)(0|1)

(4) 0*10*10*10*

(5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

答案

(1) 以0开头并且以0结尾的，由0和1组成的符号串。

(2) {α|α∈{0,1}*}

(3) 由0和1组成的符号串，且从右边开始数第3位为0。

(4) 含3个1的由0和1组成的符号串。 {α|α∈{0,1}+，且α中含有3个1 }

(5) {α|α∈{0,1}*,α中0和1为偶数}

3.4 对于下列语言分别写出它们的正规表达式。

(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。

(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。

(3) Σ={0,1}上的含偶数个1的所有串。

(4) Σ={0,1}上的含奇数个1的所有串。

(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。

(6) 不包含子串011的由0和1组成的符号串的全体。

(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。

第1页共6页 《编译原理》期末试题（一）

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）

1．编译程序是对高级语言程序的解释执行。(× )

2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)

3．一个算符优先文法可能不存在算符优先函数与之对应。 (√ )

4．语法分析时必须先消除文法中的左递归 。 (×)

5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√)

6．逆波兰表示法表示表达式时无须使用括号。 (√ )

7．静态数组的存储空间可以在编译时确定。 (×)

8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×)

9．两个正规集相等的必要条件是他们对应的正规式等价。 (× )

10．一个语义子程序描述了一个文法所对应的翻译工作。 (×)

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

1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码 B．( ) 单词在符号表中的位置

C．( ) 单词的种别编码和自身值 D．( ) 单词自身值

2． 正规式 M 1 和 M 2 等价是指_____。

A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等

C．( ) M1和M2所识别的语言集相等 D．( ) M1和M2状态数和有向边条数相等

3． 文法G：S→xSx|y所识别的语言是_____。 第2页共6页 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*

4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同

B．( ) 最左推导和最右推导对应的语法树可能不同