资源描述：
《编译原理复习题2017(含试卷).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理复习题库一、应用题1） 写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：文法G(N)： N→AB
2、B A→AC
3、D B→1
4、3
5、5
6、7
7、9 D→B
8、2
9、4
10、6
11、8 C→0
12、D 2）写一个文法，使其语言是无符号二进制实数（不含指数）。解答:文法G(N)： N→L.L
13、L L→LB
14、B B→0
15、13）给出上下文无关文法的定义。一个上下文无关文法G是一个四元式(VT，VN，S，P)，其中：VT是一个非空有限集，它的每个
16、元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∪VN=Φ；S是一个非终结符号，称为开始符号；P是一个产生式集合(有限)，每个产生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。4）．给出正规式与正规集的递归定义。(1)ε和Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ；(2)任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；(3)假定U和V都是∑上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U
17、V)、(U·V)和
18、(U)*也都是正规式，它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)(连接积)和(L(U))*(闭包)。仅由有限次使用上述三步骤而得到的表达式才是∑27上的正规式。仅由这些正规式所表示的字集才是∑上的正规集。5）．设文法G为：S→aAcB
19、BdSA→BaB
20、aBc
21、aB→aScA
22、cAB
23、b对于输入串aacabccb，给出最左推导。答：S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb6）设文法G为：S→BAA→BS
24、dB→aA
25、bS
26、c对于输入串adcc
27、d，给出最左推导。答：S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccdSFDAabab7）．给定正规文法G:S→aS
28、bA
29、bA→aS请构造与之等价的有限自动机。8）．给定正规文法G:S→aAA→bA
30、aB
31、bB→aAABDFbbaaSa请构造与之等价的有限自动机。24D3abaa1ba9）．对下面给出的NFA确定化。SFDAababa2710）.将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。 G[S]：S→bSAe
32、bA A→Ab
33、d答：文法
34、G[S]改写为等价的不含左递归和左公共因子的G'[S]为： S→bB B→SAe
35、A A→dA'A'→bA'
36、ε11）消除下列文法G[A]的左递归。A→AaB∣BB→BbC∣CC→eD∣DD→(A)∣d解答：消除文法G[A]的左递归后得到：A→BAˊAˊ→aBAˊ∣εB→CBˊBˊ→bcBˊ∣εC→eD∣DD→(A)∣d12）正规式（a
37、b）*a(a
38、b)构造一个等价的有限自动机。a,baabÞ012解答：13）将下图的NFA确定化为DFA。27答：用子集法确定化如下表IIaIb状态{X,1,2}{1,2}..{1,2,3
39、}{1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X123确定化后如下图：14）.已知文法G(E)E→T
40、E＋TT→F
41、T*FF→(E)
42、i(1)给出句型(T*F＋i)的最右推导；(2)给出句型(T*F＋i)的短语、简单短语、句柄、素短语、最左素短语。解：(1)最右推导：E->T->F->(E)->(E＋T)->(E＋F)->(E＋i)->(T＋i)->(T*F＋i)(2)短语：(T*F＋i)，T*F＋i，T*F，i简单短语：T*F,i句柄：T*F素短
43、语：T*F,i最左素短语：T*F15）.构造正规式1(0
44、1)*101相应的DFA。27解：先构造NFA：确定化：重新命名，令AB为B、AC为C、ABY为D得：所以，可得DFA为：16）.文法：S->MH
45、aH->LSo
46、ε27K->dML
47、εL->eHfM->K
48、bLM判断G是否为LL(1)文法，如果是，构造LL(1)分析表。解：各符号的FIRST集和FOLLOW集为：预测分析表由于预测分析表中无多重入口，所以可判定文法是LL(1)的17）.对下面的文法G：E->TE'E'->+E
49、εT->FT'T'->T
50、εF->PF'F'
51、->*F'
52、εP->(E)
53、a
54、b
55、^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(4分)(2)证明这个方法是LL(1)的。(4分)(3)构造它的预测分析表。(2分)解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRS
