浙江工业大学之江学院 编译原理 试卷A 2009/2010(2)
课程：编译原理 姓名： 班级： 总分： 1 2 3 题序 总评 计分
一、选择题(20*2=40)
1、 两个有穷自动机等价是指它们的( )。
A．状态数相等 C．所识别的语言相等
B．有向弧数相等
D．状态数和有向弧数相等
2、 若状态k含有项目“A→α· ”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的
语法分析方法是( )。 A．LALR分析法
B．LR(0)分析法
C．LR(1)分析法 D．SLR(1)分析法
3、 若a为终结符，则A→α · aβ为( )项目。
A．归约
B．移进
C．接受
D．句柄
4、 在使用高级语言编程时，首先可通过编译程序发现源程序的全部和部分( )错误。
A. 语法
B. 语义
C. 语用
D. 运行
5、 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是( )
A. 非文法
B. 正则文法
C. 上下文有关文法
D. 上下文无关文法
6、 一个句型中的( )称为该句型的句柄。
A. 最左直接短语
B. 最右直接短语
C. 终结符
D. 非终结符
7、 一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组( )
A. 句子
B. 产生式
C. 单词
D. 句型
8、 编译程序是一种( )
A. 汇编程序
B. 翻译程序
C. 解释程序
D. 目标程序
9、 按逻辑上划分，编译程序第三步工作是( )
A. 语义分析
B. 词法分析
C. 语法分析
D. 代码生成
10、 在语法分析处理中，FIRST集合、FOLLOW集合均是( )
A. 非终结符集
B.终结符集
C. 字母表
D. 状态集
11、 识别上下文无关语言的自动机是( )
A. 下推自动机
B. NFA
C. DFA
D. 图灵机
12、 正则表达式R1和R2等价是指( )
A. R1和R2都是定义在一个字母表上的正则表达式 B. R1和R2中使用的运算符相同 C. R1和R2代表同一正则集 D. R1和R2代表不同正则集
13、 已知文法G[S]:S→A1， A→A1|S0|0。与G 等价的正规式是( )
A. 0(0|1)*
B. 1*|0*1
C. 0(1|10)*1
D. 1(10|01)*0
14、 给定文法A→bA|cc，则符号串①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc中，是该文法句子的是
( ) A. ①
B. ③④⑤
C. ②④
D. ①⑤
15、 文法 S→aaS|abc 定义的语言是( )。
A.{a2kbc|k>0}
B.{akbc|k>0}
C.{a2k-1bc|k>0}
D.{akakbc|k>0}
16、 若B为非终结符，则 A→.B 为( )。
A.移进项目
B.归约项目
C.接受项目
D.待约项目
17、 同心集合并可能会产生新的( )冲突。
A.二义
B.移进/移进
C.移进/归约
D.归约/归约
18、 如图所示自动机M，请问下列哪个字符串不是M所能识别的( )。
A. bbaa
B. abba
C. abab
D. aabb
19、 有限状态自动机能识别( )
A.上下文无关语言
B.上下文有关语言
C.正规语言
D.0型文法定义的语言
20、 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是( )
A. a+b+c*d
B. (a+b)* c+d
C. (a+b)* (c+d)
D. a+b*c+d
二、简答题(6*5=30)
1、 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示。
Abc*+ab+/d－
2、 简述DFA与NFA有何区别?
DFA与NFA的区别表现为：DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合(可能为空集)，而不是单个状态。
3、 已知文法： SaAB AbBb BA| 给出符号串abbbb的最左推导和最右推导。 Answer:
最左推导是：
SaABabBbBabAbBabbBbbBabbbbBabbbb 最右推导是：
SaABaAabBbabAbabbBbbabbbb 4、 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc
写出L(G[S])的全部元素。 答案： L(G[S])={abc}
5、 文法S→S(S)S|ε (1) 生成的语言是什么？
(2) 该文法是二义的吗？说明理由。 答案：
(1) 嵌套的括号
(2) 是二义的，因为对于()()可以构造两棵不同的语法树。 6、 设有文法： G[S]: S→aAbDe | d A→BSD | e B→Sac | cD | ε D→Se | ε 求Follw(S) Answer:
Follw(S)={a,b,d,e,$}
三、分析题(2*15=30)
1、 设有正规式r=1(0|1)*1，给出识别该正规式的NFA和DFA并最简化(要有计算过程)。
NFA
下面是将NFA转换成DFA： 状态 {q0} {q1,q2,q3,q5,q8} {q2,q3,q4,q5,q7,q8} {q2,q3,q5,q6,q7,q8,q9} 输入 0 {q2,q3,q4,q5,q7,q8} {q2,q3,q4,q5,q7,q8} {q2,q3,q4,q5,q7,q8} 1 {q1,q2,q3,q5,q8} {q2,q3,q5,q6,q7,q8,q9} {q2,q3,q5,q6,q7,q8,q9} {q2,q3,q5,q6,q7,q8,q9}
DFA
下面是将DFA最简化： 先分成两个状态集合： {q0,q1,q2}，{q3}
move({q0,q1,q2}, 0)={q2} move({q0,q1,q2}, 1)={q1,q3} q0可分离出来 {q0}，{q1,q2}，{q3} move({q1,q2}, 0)={q2} move({q1,q2}, 1)={q3}
最简化的DFA
2、 已知文法
A→aAd|aAb|
判断该文法是否是SLR(1)文法，若是则构造相应分析表，并对输入串ab给出分析过程。
Answer:
文法：
A→aAd|aAb|
拓广文法为G'，增加产生式S'→A 若产生式排序为： r0: S'→A r1: A→aAd r2: A→aAb r3: A→ 由产生式知： First (S' ) = {,a} First (A ) = {,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}
G'的LR(0)项目集族及识别活前缀的DFA 如下图所示：
在I0 中：
A →.aAd 和A →.aAb 为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I0、I2 中：
Follow(A)= {d，b，#}
由于：Follow(A) ∩{a}= {d，b，#} ∩{a}=φ
所以在I0、I2中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。 构造的SLR(1)分析表如下：
状态 0 1 2 3 4 5 Action a s2 b r3 r3 s5 r1 r2 d r3 r3 s4 r1 r2 $ r3 acc r3 r1 r2 Goto A 1 3
对输入串ab的分析过程：
状态栈 0 02 023 0235 01 四、
$ $a $aA $aAb $A 文法符号栈 剩余输入串 ab$ 移进 b$ 按A→归约 b$ 移进 $ 按A→aAb归约 $ 接受 动作 分析成功，说明输入串ab 是文法的句子。
