《编译原理》练习题一一、填空题（每空1分）1．设G ［S ］是一个文法，我们把能由文法的 （1） 推导出来的符号串α称为G 的一个句型。

当句型α仅由 （2） 组成时 (即α∈V T *)，则将它称为G 产生的句子。

2．从某一给定的状态q 出发，仅经过若干条 (3) 的矢线所能达到的状态所组成的集合称为ε-CLOSURE(q)。

3．设G=(V N ,V T ,P,S)是一文法，我们说G 中的一个符号X ∈V N ∪V T 是有用的，是指X 至少出现在 （4） 的推导过程中，否则，就说X 是无用的。

我们将不含形如A→A 的产生式和不含无用符号及无用产生式的文法称为 （5） 。

4．我们常采用形如 (class, value)的二元式作为一个单词的 (6) 。

其中,class 是一个整数，用来指示该单词的 (7) ，value 则是单词之值。

5．一个文法G[S]可表示成形如 （8） 的四元式。

其中V N ,V T ,P 均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集， S ∈V N 为文法的开始符号。

此外，将出现在各产生式左部和右部的一切符号所组成的集合称为 （9） ，记作V 。

显然，V=V N ∪V T ,V N ∩V T =∅。

6．通常，可通过两种途径来构造词法分析程序。

其一是根据对语言中各类单词的某种描述或定义，用 (10) 构造词法分析程序；另外一种途径是所谓词法分析程序的 (11) 。

7．设G 为一文法，A→α是G 的一个产生式，如果α具有υA δ的形式，其中υ，δ不同时为ε，则称产生式A→α是 （12） 。

若存在推导δυαA A *⇒⇒，则称产生式A→α是 （13） 。

8．设M=(K,Σ,f,S 0,Z)为一DFA ，并设s 和t 是M 的两个不同状态，我们说状态s,t 为某一输入串w (14) ，是指从s,t 中之一出发，当扫视完w 之后到达M 的终态，但从其中的另一个状态出发，当扫视完同一个w 后而进入 (15) 。

9．把最右推导称为 （16） ，而把右句型称为 （17） 。

10．如果从状态转换图的初态出发，分别沿着一切可能的路径到达 (18) ，并将每条路径各矢线上的 (19) 依次连接起来，便得到状态转换图所能识别的全部字符串，这些字符串所组成的集合也就是该状态转换图所识别的语言。

二、选择题（每空2分）1. 下列文法中，不是产生语言 {ab n a∣n≥1} 的文法。

A．A→aBa B→b∣bBB．A→aB B→ba∣bBC．A→aB B→ba∣bBaD．A→aB B→bC C→bC∣a2. 设有文法G[S]：S→aAB A→bAc∣ε B→bB∣Ae∣ε则经消去ε-产生式后与G等价的文法G1[S]为。

A．S→aA∣aB∣aAB∣a A→bc∣bAc B→bB∣Ae∣b∣eB．S→aAB A→bAc B→bB∣AeC．S→aA∣aB A→bc B→b∣eD．S→aA∣aB∣a A→bc∣bAc B→bB∣Ae∣b∣e3. 文法 G 产生的的全体是该文法描述的语言。

A ．句型 B. 终结符集 C. 非终结符集 D. 句子4. 设M为一确定有限自动机，并设s 和t是M的两个不同状态。

如果s和t ，则称s和t等价。

A．不可区分 B．可划分 C．可区分 D．待区分5. 设有文法G[S]：S→aS∣W∣U U→a V→bV∣ac W→aW则经化简后与G等价的文法G1[S]为。

A．S→aS∣W V→bV∣ac W→aWB．S→aS∣U U→aC．S→aS∣W∣U U→a W→aWD．S→aS V→bV∣ac6. 若文法 G 定义的语言是无限集，则文法G必然是。

A．前后文无关的 B．递归的 C．二义性的 D．无二义性的7. 下列说法中正确的是 。

A ．一个确定的有限自动机实际上是相应的状态转换图的一种形式描述。

B ．一个状态转换图是由一组矢线连接的有限个结点所组成的无回路有向图。

C ．所谓一个DFA M 状态数的最小化，是指构造一个与之等价的DFA M ′，使它们有相同的接受集。

D ．对于有同一接受集的FA ，与之等价的DFA 在同构意义下是唯一的。

8. 下列文法中， 不是产生语言}1{12≥+n a n 的文法。

A ．A →aBaB →a ∣aBaB ．A →aB B →aa ∣BaaC ．A →aAA A →aD ．A →aBB B →a ∣aBB9. 如下的表示形式中，不能表示程序语言中单词结构的是 。

A ．左线性文法B ．形如（Class ，Value ）的二元式C ．正规式D ．正规文法三、证明题1．试证明文法S →aB ∣bA A →aS ∣bAA ∣a B →aBB ∣bS ∣b为二义性文法。

（10分）2． 试证明文法: S →a AB A →aA ∣a B →aB ∣b 为二义性文法。

（10分）四、简答题1．试构造一文法，使其描述如下语言： （15分）L(G)={ a n b m c m d n ∣m,n ≥1 }2．消除下列文法中的单产生式。

（10分）S→AbB∣A A→AB∣caB∣B B→Aa∣b3．对正规式((a∣b) *∣ab*)b ，构造与其相应的状态转换图。

（15分）4．消除下列文法中的ε-产生式。

（10分）S→ABb∣a A→aB∣caB∣ε B→aA∣b∣ε5．试描述由下列文法所产生的语言。

（10分）S→aAd A→aAd∣bBc B→bBc∣e6．消除下列文法中的单产生式。

（10分）S→aFbM∣F F→M∣abc M→abF∣c7．化简下列文法：（10分）S→B ab∣cC B→bS∣b C→Da D→Cb∣CDa 8．对正规式(a∣ab)*ab*，构造与其相应的状态转换图。

（15分）9．试构造一正规文法，使其描述如下语言：（10分）L(G)={ ab m cb n a∣m≥1, n≥0 }10．试描述由下列文法所产生的语言。

（15分）S→aAbB A→A ab∣ε B→aA∣aC C→cC∣d 五、应用题1．对于如下的状态转换矩阵(1) 分别画出相应的状态转换图；（10分）(2) 写出相应的3型文法。

（10分）2．将如图所示的NFA确定化。

（20分）3．将如图所示的具有ε动作的NFA确定化。

（20分）4．将如图所示的DFA最小化。

（20分）5．将如图所示的DFA最小化。

（25分）6．对于如下的状态转换矩阵(1) 画出相应的状态转换图；（10分）(2) 写出相应的3型文法。

（10分）7．设有如下正规文法G[S]：S→aA∣aB A→bB∣b B→bB∣bC C→bC∣a （1）构造与文法G[S]相应的状态转换图；（10分）（2）将所得的NFA确定化。

（15分）8．将如图所示的NFA确定化。

（15分）《编译原理》练习题二一、填空题（每空1分，共10分）1．所谓递归下降法，是指对文法的每一非终结符号，都根据相应产生式各候选式的结构，为其编写一个 (1) ，用来识别该非终结符号所表示的 (2) 。

2．在每一LR(0)项目［A→α·β］中放置一个 (3) a，使之成为［A→α·β,a］的形式，我们将此种项目称为一个 (4) 。

3．所谓 (5) ，就是对文法中的 (6) 都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的 (7) 外，还要执行相应的语义动作或调用相应的语义子程序。

4．LL(1)分析表可用一个 (8) 表示，它的每一行与文法的一个非终结符号相关联，而其每一列则与文法的一个终结符号或 (9) 相关联。

5．若在一个文法G中，不含有形如 (10) 的产生式，其中A,B∈V N，则称G 为算符文法。

6．将每一运算符都置于其 (11) 的表达式称为后缀表示，也称为逆波兰表示。

7．把流程图中具有如下性质的一组结点称为程序中的一个循环：(ⅰ) 在这组结点中，有惟一的 (12) ，使得从循环外到循环内任何结点的所有通路，都必通过此结点；(ⅱ) 这一组结点是 (13) 。

8．语法分析的基本任务是：根据语言的语法规则 (即根据描述该语言的前后文无关文法)，分析源程序的 (14) ，即分析如何由这些单词组成各种语法范畴，并在分析过程中，对源程序进行 (15) 。

9．所谓句型的素短语，是指一个句型中具有这样性质的短语：短语中至少含有一个(16) ，且除它自身外，不再包含其它的 (17) 。

10．一个文法符号X的 (18) 我们称之为语义属性或简称为属性，用形如X.ATTR的记号来表示文法符号X的相关语义属性。

11．表示流程图中各结点间控制关系的一种直观而有效的方法是用树形结构，称之为(19) 。

12．目前，已存在许多语法分析方面的方法。

但就产生语法树的方向而言，可大致把它们分为 (20) 和 (21) 两大类。

13．将形如A→αX·β的项目称为A→α·Xβ的 (22) 。

14．记录和一个数组有关的信息，如维数n、各维的上、下界l k和u k的数据结构称为数组的 (23) 。

15．基本块是程序中具有下述性质的 (24) ：它有惟一的入口和惟一的出口，它们分别是块中的第1个操作和最末一个操作，且块中的各个操作按顺序执行，不出现(25) 。

16．若一文法G的任何两个符号之间 (26) 一种优先关系，且任意两个不同的产生式均无 (27) ，则称G为简单优先文法。

17．把在数据区给变量分配的存储单元地址称为 (28) ，而把在目标程序运行时存放在相应单元中的值称为 (29) 。

18．如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的 (30) ，记作 (31) 。

二、选择题（每空2分）1. 下列文法中，是LL(1)文法。

A．S→bBS′a S′→aBS′∣ε A→S∣a B→AcB．S→bS∣bA∣b A→aA∣aC．E→E+T∣T T→T*F∣F F→(E)∣iD．S→bBS′ S′→aBS′∣ε A→S∣a B→Ac2. 下列文法中，是简单优先文法。

A．E→E+T∣T T→T*F∣F F→(E)∣iB．S→A/ A→aA∣AS∣/C．E→E+E∣E*E∣(E)∣iD．E→E1 E1→E1+T1∣T1 T1→T T→T*F∣F F→(E)∣i3. 当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。

为了便于引用，通常是把上述内容存放于数组相应的之中。

A．信息向量 B．内情向量 C．地址向量 D．指针向量4. 下列说法中正确的是。

A. 所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。

B. 如果一个文法具有二义性，则它必然不是LL(1)文法。