系别___________________ 专业_____________________年级_____________________姓名_________________学号
┈┈┈┈┈┈┈┈┈┈┈┈┈┈密┈┈┈┈┈┈┈┈┈┈┈┈┈┈封┈┈┈┈┈┈┈┈┈┈┈┈┈线┈┈┈┈┈┈┈┈┈┈┈┈┈┈
计算机学院编译原理课
期中测试题
1.文法G所描述的语言是的集合。

A.文法G的字母表V中所有符号组成的符号串
B.文法G的字母表V的闭包V*中的所有符号串
C.由文法的开始符号推出的所有符号串
D.由文法的开始符号推出的所有终结符串
2．有文法G[I]：I→I1|I0|Ia|Ib|Ic|a|b|c ,下列符号串中是该文法的句子的有
①ab0 ②a0c01 ③aaa ④bc10 可选项有：。

A.②③④
B.①
C.③
D.①②③④
3.词法分析所依据的是。

A.语义规则
B.构词规则
C.语法规则
D.等价变换规则
4.如果L(M) = L(M’)，则M与M’。

A.等价
B.M与M’都是二义的
C.M与M’都是无二义的
D.它们的状态数相等
5．下面状态转换图接受的字集为。

1
A.以0开头的二进制数组成的集合
B.以0结尾的二进制数组成的集合
C. 含奇数个0的二进制数组成的集合
D.含偶数个0的二进制数组成的集合
6.文法G[E]：
E→T|E+T T→F|T*F F→a|(E)
该文法句型E+F*(E+T)的直接短语是下列符号串的。

①(E+T) ②E+T ③F ④F*(E+T)
可选项有：
A.①③
B.②③
C.③④
D.③
7. 有限状态自动机能识别。

A.上下文无关文法
B.上下文有关文法
C.正规文法
D.短语文法
8. 如果文法G是无二义的，则它的任何句子 。

A.最左推导和最右推导对应的语法树必定相同
B.最左推导和最右推导对应的语法树可能不同
C.最左推导和最右推导必定相同
D.可能存在两个不同的最左推导，但他们对应的语法树相同
9．产生正规语言的文法为文法
A ． 0型
B .1型 C.2型 D.3型
10、素短语是指_______的短语。

①至少包含一个非终结符号 ②至少包含一个终结符号
③除自身外不再包含其它终结符号 ④除自身外不再包含其它非终结符号 ⑤除自身外不再包含其它短语 ⑥除自身外不再包含其它素短语 可选项有：
A.①⑥
B.②⑤
C. ③④
D.②⑥
1．简述编译过程的五个阶段及各个阶段的任务。

2．简述自上而下语法分析方法基本思想及自上而下分析方法面临的问题？
一、1．(10分)写一个文法使其语言为L(G)={a n b n c m | m,n≥1，n 为奇数，m 为偶数}。

2．(10分) 设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构
造一个识别该正规集的DFA 。

3． 对文法G(S)：
S → S ∨ a T | a T | ∨ a T T → ∧ a T | ∧ a
(1) 消除该文法的左递归和提取左公因子；
(2) 构造各非终结符的FIRST 和FOLLOW 集合；
(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。

4．(9分) 设已构造出文法G(S)：
(1) S → BB (2) B → aB (3) B → b
的LR 分析表如下
假定输入串为abab ，请给出LR 分析过程(即按照步骤给出状态，符号，输入串的变化过程)。

二、简答题：
三、推导计算题：（共60分）。