一.填空题:
2-01.所谓最右推导是指： 任何一步α?β都是对α中最右非终结符进行替换的 。
2-02.一个上下文无关文法所含四个组成部分是 终结符号集、非终结符号集、一个开始符号、产生式的集合 。
2-03.产生式是用于定义 语法成分 的一种书写规则。
2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S2-05.设G是一个给定的文法，S是文法的开始符号，如果S2-06.设G是一个给定的文法，S是文法的开始符号，如果S
二.单选题:
2-07．文法G所描述的语言是 C 的集合。
A.文法G的字母表V中所有符号组成的符号串 B.文法G的字母表V的闭包V中的所有符号串 C.由文法的开始符号推出的所有终结符串 D.由文法的开始符号推出的所有符号串
2-08．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是 B 。
A.短语文法 B.正则文法 C.上下文有关文法 D.上下文无关文法 2-09.文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是
C 。
A. L(G[N])={b│i≥0} B. L(G[N])={b│i≥0} C. L(G[N])={b可选项有：
A. 短语 B. 简单短语 C. 素短语 D. 终结符号 2-11．设G是一个给定的文法，S是文法的开始符号，如果S
x(其中x∈V),则称x是文法G的一个 B 。
*
2i+1i
2i
*
**
x,x∈VT} 。
*
x（其中x∈V），则称x是文法的一个句型 。 x(其中x∈VT),则称x是文法的一个句子。
│i≥0} D. L(G[N])={b
2i+1
│i≥1}
2-10．一个句型中的最左 B 称为该句型的句柄。
A. 候选式 B. 句型 C. 单词 D. 产生式
2-12．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符
号，以及一组 D 。
A. 句子 B. 句型 C. 单词 D. 产生式 2-13.文法G[E]：
E→T∣E＋T T→F∣T﹡F
F→a∣（E）
该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的 B 。 ①（E＋T） ②E＋T ③F ④ F﹡(E＋T) 可选项有：
A) ①和③ B) ②和③ C) ③和④ D) ③ 2-14．若一个文法是递归的，则它所产生的语言的句子 A 。
A.是无穷多个 B.是有穷多个 C.是可枚举的 D.个数是常量
三、是非题(下列各题，你认为正确的，请在题干的括号内打“ √”，错的打“×”。) 2-15.正则文法其产生式为A?a，A?Bb, A,B∈VN，a、b∈VT。 （√）
四、名词解释
2-16.短语——设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z ② U
xUy； u；
则称句型xuy 中的子串u是句型xuy的短语。
2-17.简单短语——设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z
xUy；
② U ? u；
则称句型xuy 中的子串u是句型xuy的简单短语（或直接短语）。 2-18.句柄——一个句型中的最左简单短语称为该句型的句柄。 五、简答题：
2-19什么是句子？ 什么是语言?
答：设G是一个给定的文法，S是文法的开始符号，如果S2-20.已知文法G[E]为：
E→T|E+T|E-T T→F|T*F|T/F F→（E）|i
① 该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。 解：① 该文法的开始符号（识别符号）是E。
②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、T、T+T*F、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。
2-21.已知文法G[S]为：
S→dAB A→aA|a B→Bb|ε
① G[S]产生的语言是什么？ ② G[S]能否改写为等价的正规文法？
解：① G[S]产生的语言是L(G[S])={dab│n≥1,m≥0}。
② G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为： Sˊ→dA A →aA|aB|a B →bB|b
2-22.设有语言L(G)={ada| a∈(a,b),a为a之逆}，试构造产生此语言的上下文无关文法G。
解：根据题义，可知a为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现；由于a∈(a,b)，所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]为：S→aSa|bSb|d
R
*
R
*
R nm
x(其中x∈VT),则称x是文法的一个句子。
x,x∈VT} 。
*
*
设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S
编译原理第二章语法分析试卷
