资源描述：
《编译原理作业20150515(答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章作业【编辑人：陈芳芳】1.写一文法，使其语言是偶正整数的集合。要求：（1）允许0打头；（2）不允许0打头。【解】：(1)允许0打头且含0的偶正整数集合的文法为：N—>(0
2、D
3、E)N
4、(E
5、0)D—>1
6、3
7、5
8、7
9、9E—>2
10、4
11、6
12、8(2)不允许0打头的偶正整数集合的文法为：R—>(D
13、E)N
14、EN—>(0
15、D
16、E)N
17、(E
18、0)D—>1
19、3
20、5
21、7
22、9E—>2
23、4
24、6
25、8(3)允许0打头的偶正整数集合的文法为：S—>0S
26、RR—>(D
27、E)N
28、EN—>(0
29、D
30、E)N
31、(E
32、0)D—>1
33、3
34、5
35、7
36、9E—>2
37、4
38、6
39、82.
40、一个上下文无关文法生成句子abbaa的推导树如下：SABSaSBBAa11Ɛbba（1）给出该句子的相应的最左推导，最右推导。（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语，简单短语，句柄。【解】：（1）最左推导：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)产生式集合P：S—>ABS
41、Aa
42、ƐA—>aB—>SBB
43、b(3)短语：a,Ɛ,
44、b,bb,aa,abbaa直接短语：a,Ɛ,b句柄：a3、给出生成下述语言的上下文无关文法：(1){anbnambm
45、n,m>=0}(2){1n0m1m0n
46、n,m>=0}【解】：（1）S—>AAA—>aAb
47、Ɛ（2）S—>1S0
48、AA—>0A1
49、Ɛ11第4章课后作业1.构造一个状态数最小的DFA，它接受∑={0,1}上所有倒数第二个字符为1的字符串。（编辑：张超）解：①构造正规式：（0│1）*1（0│1）②由正规式构造NFA：③NFA转化为DFA：T0=ε－closure（{0}）={0}用子集构造法求DFA状态，T0为初态，T2，T3
50、为终态。状态ε－closure（move（Ti，0））ε－closure（move（Ti，1））T0={0}{0}{0,1}T1={0,1}{0,2}{0,1,2}T2={0,2}{0}{0,1}T3={0,1,2}{0,2}{0,1,2}用0,1,2,3代表T0，T1，T2，T3，得到如下DFA：11④最小化DFA：P0=（{0,1}，{2,3}）P1=（{0}，{1}，{2}，{3}）∴无等价状态。∵没有找到多余状态，∴无多余状态。∴上图为最小化的DFA。2、将下图的NFA确定化为DFA，并最小化。（编辑：张超）解：用子集构造法求DF
51、A状态，T0为初态，T3为终态。状态ε－closure（move（Ti，a））ε－closure（move（Ti，b））T0={X，1，2}{1，2}{1，2，3}T1={1，2}{1，2}{1，2，3}11T2={1，2，3}{1，2，Y}{1，2，3}T3={1，2，Y}{1，2}{1，2，3}用0,1,2,3代表T0，T1，T2，T3，得到如下DFA：最小化：①{0，1，2}{3}②{0，1}{2}{3}③{0，1}{2}{3}0和1是等价的，∴得到最小化的DFA如下：11第5-7章课后作业（含答案）1、将文法G[S]改写为等价的G
52、′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe
53、bAA→Abd
54、dc
55、a【解】：G[S]：S→bS’S’→SAe
56、AA→(dc
57、a)A’A’→bdA’
58、ε2、有文法G[S]：S→ABfA→BbS
59、eB→dAg
60、ε证明文法G是LL(1)文法，并构造预测分析表【解】：①计算FIRST、FOLLOW、SELECT集产生式FIRSTFOLLOWSELECT左部右部SABfdbe#gdfdbeABbSdbgdfdbeeeBdAgdbfdεεbf由上表可知：该文法中，所有相同左部不同右部的产生式SELECT集两两相交均为空集，所
61、以该文法为LL(1)文法。②构造预测分析表fbedg#SABfABfABfABbSeBbSBεεdAg113、已知文法G[S]：S→(A)│a│bA→AcS│S构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。【解】：①拓展该文法：S’→#S#S→(A)│a│bA→AcS│S②计算FIRSTVT与LASTVT:FIRSTVTLASTVTS’##S(ab)abAc(abc)ab③计算算符优先关系：#=#(=)##LASTVT(A)>)LASTVT
62、(A)>c④构造算符优先矩阵（注：按终结符出现顺序列表）:()abc#(<=<<<)>>>a>>>b>>>c<><<>#<<<=⑤因为该文法G为2型文法，且不含空产生式，没有形如U®…VW…的
