期末考试编译原理试题
A 、Z →aZb|aAb|b A →aAb|b
B 、A →aAb A →b
C 、Z →AbB A →aA|a B →bB|b
D 、Z →aAb A →aAb|b
10、若一个句型中出现了某一产生式的右部，则此右部________是句柄。 A 、一定 B 、不一定 11、考虑文法G[A]：A →A ∨B|B C →∧D B →BC| D →（A ）|i, 该文法 LL(1)文法。
A 、是
B 、不是
12、简单优先分析法每次都是对 进行归约
A 、最左短语
B 、直接短语
C 、句柄
D 、素短语
E 、最左素短语 13、下列文法G[S]：S →AA A →Aa|a 不是LR （1）文法，理由是
A.、FIRST(S)∩FIRST （A ）≠? B 、FIRST （A ）∩FOLLOW （A ）≠? C 、FIRST （Aa ）∩FIRST （a ）≠? D 、都不是
14、设有文法G[E]：E →E*E|E+E|（E ）|a 该文法 LR （1）文法 A 、是 B 、不是 C 、无法判断 15、对于文法G[A]
A →ABe|Ba
B →dB|ε
有人说，因为FIRST （aABe ）∩FOLLOW （A ）≠? 并且FIRST （Ba ）∩FOLLOW （A ）≠?，所以文法G[A]不是LL （1）文法。这种说法 A 、正确 B 、不正确
16、下列正规表达式中________与(a|b)*(c|d)等价。 A 、（a*|b*）(c|d) B 、（a*|b*）*(c|d) C 、(ab)*(d|c) D 、（a*b*）(cd) 17、若一个句型中出现了某一产生式的右部，则此右部_______是该句型的句柄 A 、一定 B 、不一定
18、前后文无关文法和正规文法所产生的语言类相比_______
A 、前后文无关文法产生的语言类大
B 、正规文法产生的语言类大
C 、两者产生的语言类一样大
D 、无法比较 19、编译过程中，比较常见的中间语言有___________。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式 ⑤树形表示
可选项有：A 、①③④ B 、②③④ C 、③④①⑤ D 、②③④⑤ 20、LL （1）文法的条件是_______________。
A 、对形如U →X1|X2|…|Xn 的规则，要求FIRST （Xi ）)∩FIRST (Xj)=? (i ≠j)
B 、对形如U →X1|X2|…|Xn 的规则 若Xi ?* ε 则要求FIRST(Xj) ∩FOLLOW (U)=?
C 、a 和b
D 、都不是 二、综合题：（共35分）
1、(10分)对于文法G(S):
）Ma L a |(L M bMb S →→→
(1)写出句型b(Ma)b 的最右推导并画出语法树。
(2)写出上述句型的短语，直接短语和句柄。
2、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aabca 是否是该文法接受的句子：
S →Aa S →B A →Cc A →Bb B →Bb B →a C →D C →Bab D →d 3、(10分)将下面具有ε的NFA 确定化
4、 (5分)求出下列文法所产生语言对应的正规式。
S →aS S →bA S →b A →aS 5、 (5分)构造识别下面正规式的NFA
ab （a|b ）*
四、综合题（共45分）
1、(10分)计算文法G(M)的每个非终结符的FIRST 和FOLLOW 集合，并判断该文法是否是LL(1)的，请说明理由。 G(M)：
a) M → TB b) T → Ba | ε
c) B → Db | eT | ε d) D → d | ε
2、(15分)对文法G(S)： S → a | ^ | (T) T → T ，S | S
(1) 构造算符优先表;
(2) 判断是算符优先文法吗? (3) 构造优先函数。 3、（10分）将表达式A-B*(C+D)+E/F ↑G 分别表示为三元式、四元式、逆波兰式序列 4、（10分）设有文法G[S]
S →Ba|Bb|c B →Bd|Se|f
判断该文法是哪一类LR 文法，说明理由，并构造相应的分析表
德州学院期末考试试题
（ 9 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟
一、选择题（本大题共20小题，每小题1分，共20分） 1、文法的二义性和语言的二义性是两个____________概念。 a 、不同 b 、相同 c 、无法判断