A.R1和R2都是定义在一个字母表上的正则表达式 B.R1和R2中使用的运算符相同 C.R1和R2代表同一正则集 D.R1和R2代表不同正则集
53． 已知文法G[S]:S→A1， A→A1|S0|0。与G 等价的正规式是(C)
A. 0(0|1)*
B. 1*|0*1
C. 0(1|10)*1
D. 1(10|01)*0
54． 与(a|b)*(a|b)等价的正规式是(C)。
A.a*| b*
B.(ab)*(a|b)
C. (a|b)(a|b)*
D.(a|b)*
55． (D)文法不是LL(1)的。
A. 递归
B. 右递归
C. 2型
D.含有公共左因子的
56． 给定文法A→bA|cc，则符号串①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc中，是该文法句子的
是(D) A. ①
B. ③④⑤
C. ②④
D. ①⑤
57． LR(1)文法都是()
A. 无二义性且无左递归 C. 无二义性但可能是左递归
B. 可能有二义性但无左递归 D. 可以既有二义性又有左递归
58． 文法E→E+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。
A. 1
B.3
C. 5
D.7
59． 文法 S→aaS|abc 定义的语言是(C)。
A.{a2kbc|k>0}
B.{akbc|k>0}
C.{a2k-1bc|k>0}
D.{akakbc|k>0}
60． 若B为非终结符，则 A→?.B?为(D)。
A.移进项目
B.归约项目
C.接受项目
D.待约项目
61． 同心集合并可能会产生新的(D)冲突。
A.二义
B.移进/移进
C.移进/归约
D.归约/归约
62． 就文法的描述能力来说，有(C)
A．SLR(1)? LR(0)
B．LR(1) ? LR(0)
C．SLR(1)?LR(1) D．无二义文法 ?LR(1)
63． 如图所示自动机M，请问下列哪个字符串不是M所能识别的(D)。
A. bbaa
B. abba
C. abab
D. aabb
64． 有限状态自动机能识别(C)
A.上下文无关语言
B.上下文有关语言
C.正规语言
D.0型文法定义的语言
65． 已知文法G是无二义的，则对G的任意句型α(A)
A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同
D.可能存在两个不同的最左推导，但他们对应的语法树相同 66． (B)不是DFA的成分
A.有穷字母表
B.多个初始状态的集合
C.多个终态的集合
D.转换函数
67． 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)
A. a+b+c*d
B. (a+b)* c+d
C. (a+b)* (c+d)
D. a+b*c+d
68． 后缀式abc?+?d+可用表达式(B)来表示。
A．(? (a+b)?c)+d
B．?(a+(b?c))+d
C．? (a?(b+c))+d
D．(a?(?b+c))+d
69． 表达式A*(B-C*(C/D))的后缀式为(B)。
A．ABC-CD/**
B．ABCCD/*-*
C．ABC-*CD/*
D．以上都不对
70． (D)不是NFA的成分。
A. 有穷字母表 二、 问答
1． 将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。 G[S]： S→bSAe | bA A→Ab | d 答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S→bB B→SAe | A
B. 初始状态集合
C. 终止状态集合
D. 有限状态集合
A→d A'
A' →bA' | ε
2． 将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。 G[S]： S→SAe|Ae A→dAbA|dA|d 答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S →AeS' S' →AeS'|ε A →dA' A' →AB|ε B →bA |ε
3． 将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。 G[S]： S→[A A→B]|AS B→aB|a 答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S →[A A →B]A′ A′→SA′|ε B →aB′
B′→B|ε
4． 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。 S→aH H→aMd | d M→Ab | ε A→aM | e 答：
首先计算文法的 FIRST集和FOLLOW集如下表。
文法的 FIRST集和FOLLOW集
非终结符 S H M A FIRST集 {a}......... {a ，d}..... {a ，e ，ε} {a ，e}..... FOLLOW集 {# }... {# }... {d ，b} {b}.... 由于predict（H→aMd）∩predict（H→d）={a}∩{d }= predict（M→Ab）∩predict（M→ε）={a ，e}∩{d ，b }= predict（A→aM）∩predict（A→e）={ a }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表。
S H M A a →aH. →aMd →Ab. →aM. d →d. →ε b →ε e →Ab →e. # 5． 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bH|H H→d|ε 答：
首先计算文法的 FIRST集和FOLLOW集如下表。
非终结符 S D T H {a} {a，ε} {b，d，ε} {d，ε} FIRST集 FOLLOW集 {#，b，d，e}. {#，b，d，e } {e} {e}
