《编译原理》练习题一 一、填空题（每空 1 分）1．设 G［S］是一个文法，我们把能由文法的 （ 1 ） 推导出来的符号串 α 称为 G 的一个句型。当句型 α 仅由 （ 2 ） 组成时 (即 α∈VT*)，则将它称为 G 产生的句子。 2．从某一给定的状态 q 出发，仅经过若干条 (3) 的矢线所能达到的状态所组成的集合称为 ε-CLOSURE(q)。3．设 G=(VN,VT,P,S)是一文法，我们说 G 中的一个符号 X∈VN∪VT是有用的，是指 X 至少出现在 （ 4 ） 的推导过程中，否则，就说 X 是无用的。我们将不含形如 A→A 的产生式和不含无用符号及无用产生式的文法称为 （ 5 ） 。4．我们常采用形如 (class, value)的二元式作为一个单词的 (6) 。其中,class 是一个整数，用来指示该单词的 (7) ，value 则是单词之值。5．一个文法 G[S]可表示成形如 （ 8 ） 的四元式。其中 VN,VT,P 均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集， S∈VN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为 （ 9 ） ，记作 V。显然 ，V=VN∪VT,VN∩VT=。 6．通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用 (10) 构造词法分析程序；另外一种途径是所谓词法分析程序的 (11) 。7．设 G 为一文法，A→α 是 G 的一个产生式，如果 α 具有 υAδ 的形式，其中 υ，δ 不同时为 ε，则称产生式 A→α 是 （ 12 ） 。若存在推导，则称产生式 A→α 是 （ 13 ） 。 8．设 M=(K,Σ,f,S0,Z)为一 DFA，并设 s 和 t 是 M 的两个不同状态，我们说状态 s,t 为某一输入串 w (14) ，是指从 s,t 中之一出发，当扫视完 w 之后到达 M 的终态，但从其中的另一个状态出发，当扫视完同一个 w 后而进入 (15) 。9．把最右推导称为 （ 16 ） ，而把右句型称为 （ 17 ） 。10．如果从状态转换图的初态出发，分别沿着一切可能的路径到达 (18) ，并将每条路径各矢线上的 (19) 依次连接起来，便得到状态转换图所能识别的全部字符串，这些字符串所组成的集合也就是该状态转换图所识别的语言。二、选择题（每空 2 分） 1. 下列文法中， 不是产生语言 {abna∣n≥1} 的文法。 A．A→aBa B→b∣bB B．A→aB B→ba∣bB C．A→aB B→ba∣bBaD．A→aB B→bC C→bC∣a2. 设有文法 G[S]...
