1．cc 2.bcbc 3.bcbcc 4.bc 可选项有：
a.1 b.1 2 c.1 4 d.1 2 4
7．一个句型中的最左 称为该句型的句柄。
可选项有：
a.短语 b.简单短语 c.素短语 d.终结符号
8．乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。3型文法也称为（1） ，2型文法是（2） 。 可选项有：
a.上下文无关文法 b.上下文有关文法. c正则文法 d.短语文法
9．乔姆斯基的3型语言是这样一种语言，其产生式限制为 。
可选项有：
a.A→a b.A→a A→aB c. a→d.
10．.一个文法G包括四个组成部分依次为：一组（1），一组（2），一个（3），以及一个（4）
可选项有：
a.字符串 b.字母数字串 c.产生式 d.结束符号 e.开始符号 f.文法 g.非终结符号 h.终结符号 11．设有文法G[S]：
S：：=S*S|S+S|（S）|a 该文法 二义性文法。 可选项有：
a.是 b.不是 c.无法判断 12．正则式的“|”读作 ，“．”读作 ，“*”读作 。可选项有：
a．并且 b．或者 c．连接 d．闭包
13．G[E]为: E->E+T|E-T T->T*F|T/F|F F->(E)|i
存在推导序列: E=>E+T=>E+T*F 则E+T*F是一个
a． 句型 b．句子 14．已知文法G[E]：
E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 该文法的句型T+T*F+i的直接短语为（ ① ），该文法的句型T+T*F+I句柄为（ ② ）。
（1）句型中第一个T （2）句型中第二个T （3）T+T （4）T*F
（5）F （6）i （7）T+T*F （8）T*F+i （9）T+T*F+i 可选项有： ① a．（1）b．（1）（2） c．（1）（4）（6） d．（1）（4）（6）（9） ② a．（4） b．（2） c．（1） d．（6）
四、思考题
1． 文法G=({A,B,C},{a,b,c},P,S) 其中 P：
S→Ac|aB A→ab B→bc
写出L(G[S])的全部元素。
2．为只包含数字、加号和减号的表达式，例如9-2+5，3-1，7等构造一个文法。 3．已知文法G[Z]: （1）Z::=aZb （2）Z::=ab
写出L(G[Z])的全部元素。
4．写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头 (2) 不允许0打头 5．已知文法G:
〈表达式〉∷=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉 〈项〉∷=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉 〈因子〉∷=（〈表达式〉）|i
试给出下述表达式的推导及语法树。 （1）i*i （2）i+(i+i) 6．证明下述文法［〈表达式〉］是二义的。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/7．令文法G［E］为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 8．一个上下文无关文法生成句子abbaa的推导树如下：
（1） 给出该句子相应的最左推导，最右推导。
（2） 该文法的产生式集合P可能有哪些元素？找出该句子的所有短语，简单短语，句柄。9．给出生成下述语言的上下文无关文法：(1) { anbnambm| n，m>=0} (2) { 1n0m 1m0n| n，m>=0}10．给出生成下述语言的三型文法：(1) { an|n=0} (2) { anbm|n,m>=1 }(3){anbmck|n,m,k>=0 }
第四章
一．填空题
1. 引入有穷自动机，为词法分析程序的自动构造寻找特殊的方法和工具，有穷 自动机分两类： ① 和 ② 。 2．确定的有穷自动机是一个 组。
3. 确定有穷自动机的化简，是指 ① ，并且它的状态中 没有两个是 ② 。 4. 编译过程的第一个阶段是 。
5. 扫描器的任务是从 ① 中识别出一个个 ② 。
6．如下有穷自动机：
0,1 1 1 0 1
X A B C
Y 该有穷自动机为一个： ① （DFA/NFA），从图中可看出初态集为{ ② }，终态集为：{ ③ }，有 ④ 个状态。10011101 ⑤ （能/不能）被该有穷自动机M所识别。 f(A,1)= ⑥ 。
二 判断题
（ ）1．一个确定的有穷自动机（DFA）M是一个五元组：M=（K，∑，f , S , Z ） 其中之一K是有穷集，每个元素称为一个状态，∑为字母表，S∈K是唯 一的一个初态，f是转换函数为一个单值函数，若字母表∑含有n个 输入符，任何一个状态最多有n条弧射出，而且每条弧以一个不同的
输入字符标记。
（ ）2．一个确定的有穷自动机（DFA）M是一个五元组：M=（K，∑，f , S , Z ） 其中之一K是有穷集，每个元素称为一个状态，∑为字母表，S∈K是唯 一的一个初态，f是转换函数可为一个多值函数，若字母表∑含有n个
输入符，任何一个状态可有n条以上的弧射出，而且每条弧以一个不同
的输入字符标记。
（ ）3．DFA是NFA的特例，对于每个NFA M,存在一个DFA M’,使得L(M)=L(M’)) （ ）4．如下有穷自动机是一个DFA.
三．选择题
1．无符号常数的识别和拼数工作通常都在（ ）阶段完成。
可选项有：
a.词法分析 b. 语法分析 c. 语义分析 d. 代码生成 e.代码优化 f. 表格管理 g. 出错管理
2．通常高级语言的词法规则可用正则式描述，词法分析器可用（ ）来实现。
可选项有：
a. 语法树 b.有穷自动机 c.栈 d. 堆 3. xyxxy是自动机 接受的。
a.可以 . b. 不可以
4.yyxy是自动机 接受的。
a.可以 b. 不可以
5.指出正规式(ab|b)c 与后面的 串不匹配
a.ababbc b.abab c. babc d.c 6.指出正规式(a|b)a(ba) 与后面的 串不匹配 a.ba b.baa c.aa d.bba
+
*
*
四．思考题
1．构造正规式1(0|1)*101相应的DFA. 2． 将书中P66图4.16确定化：
3． 把下图最小化(书中P66图4.17)：
4． 构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在
右边。并给出该语言的正规式。
第五章
一．填空题
1． ① 是编译程序的核心部分。目前常用的方法有 ② 和 ③ 分析法。 2.若有文法G[S]:
S→pA S→qB A→cAd A→a
则FIRST{S}={① } FOLLOW{A}={② }
3．LL（1）文法的含义：第一个L表明 ① 第二个L表 明 ② ，1表明 ③ 。
4．当文法不满足LL（1）时不能用 ① 自顶向下分析分析，但可用 ②
自顶向下分析。
5．文法G[S]：S→Ac|aB A→ab B→bc描述的语言L（G[S]）= { }。 6．已知文法G[E]：
E：：=T|E+T T：：=F|T*F F：：=（E）|i
改写该文法以消除直接左递归，改写后的文法为：
E→ ① E’， E’→ ② E’|ε。
二、判断题
（ ）1. 由LL（1）文法的定义可知若文法中含有间接左递归，该文法肯定是LL
（1）文法。
（ ）2. 若文法是LL（1）文法，该文法肯定能采用确定的自上向下的语法分析。
三．选择题
1．已知文法G（S）：
S→AB|bC A→b|ε B→aB|ε C→ABa|b