第二章2.构造产生下列语言的文法（2）{a n b m c p|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{a n # b n|n≥0}∪{cn # dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# }（5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应文法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全为零}该语言特点是：产生的句子中，0、1 个数相同，并且若干相接的1 后必然紧接数量相同连续的0。
（5）S→aSS S→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5. (1) 解：由于此文法包含以下规则：AA→ε，所以此文法是0 型文法。
7.解：(1)aacb 是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是文法G[S]中的句子aacbccb 不能从S推导得到时，它仅是文法G[S]的一个句型的一部分，而不是一个句子。
11.解：最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上面推导中，下划线部分为当前句型的句柄。
对应的语法树为：第三章3 假设M:人 W:载狐狸过河，G:载山羊过河，C:载白菜过河6 根据文法知其产生的语言是L={a m b n c i| m,n,i≧1}可以构造如下的文法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性文法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输入串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9．对于矩阵(iii)(1) 状态转换图：(2) 3型文法（正规文法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)用自然语言描述输入串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b 所组成的任意串结尾。
12 (1)-----------------------------------------------------以上为第一次作业最小化：≡0≡ {S,A} {B,C}因为 {S}b=φ {A}b={B} 所以{S,A}=>{S}{A}因为 {C}b=φ {B}b={B} 所以{B,C}=>{B}{C}≡1≡{S}{A}{B}{C}原DFA已为最小DFA。
10 （1）G1 的状态转换图：或(2) G1 等价的左线性文法G1’[F]：F→Dd|Bb, D→C, B→S|ε|Ab|Db, A→Sa|a, C→Bc, S→Eb, E→Aa或G1’[F]：F→Dd|Bb, D→C, B→S|ε|Ab|Db, A→Sa|a, C→Bc, S→Aab21 求出描述习题3-12中图（2）（3）所给出有限自动机所识别语言的正规式（2）a(ba)*b 或 (ab)*ab （3）a （b|aa)*a-----------------------------------------------------以上为第二次作业 22(1) ((0*|1)(1*0))*第四章1 (2)将间接左递归转换成直接左递归，将A->SA A->a 代入S->AS 由原文法得S->SAS|aS|b消除左递归：S->aSS ’|bS ’ S ’->ASS ’|ε 4又ε属于First(S)，First(S) ⋂ Follow(S)= ∅又ε属于First(A)，First(A) ⋂ Follow(A)= ∅又ε属于First(B)，First(A) ⋂ Follow(A)= ∅所以此文法为LL(1)文法。
8.（1）(a)消除左递归：S->Sb|Ab|b => S->AbS’|bS’S’->bS’|εA->Aa|a => A->aA’A’->aA’ |ε文法G’：S->AbS’|bS’S’->bS’|εA->aA’A’->aA’ |ε补充题：若有文法G[S]:S ->AB|cCA ->b|εB ->aC|εC ->aS|c判断文法G是否为LL（1）文法，写出理由；分别求所有非终结符的First和Follow集；若为LL（1）文法，给出其预测分析表；分析句子caac是否符合该文法。
答案：无左递归，无左公因子。
First(A)=(b, ε), First(B)={a, ε}因First(A)含ε，First(AB)=First(A) ⋃First(B)={a,b，ε}, First(cC)={c} Follow(S)={#} ⋃ Follow(C)={#}Follow(A)=First(B) ⋃ Follow(S) -{ ε}={a,#}Follow(B)=Follow(S) ={#}Follow(C)=Follow(B) ⋃ Follow(S) ={#}对S，First(AB) ⋂ First(cC)= ∅对A，First(b) ⋂ First(ε)= ∅,因First(A)含ε,First(A) ⋂ Follow(A)={b, ε}⋂{a,#}= ∅对B，First(aC) ⋂ First(ε)= ∅,因First(B)含ε,First(B) ⋂ Follow(B)={a, ε}⋂{#}= ∅对C，First(aS) ⋂ First(c)= ∅所以，文法G是LL（1）文法栈输入缓冲区动作#S caac##Cc caac# S ->cC#C aac##Sa aac# C ->aS#S ac##BA ac# S ->AB#B ac# A ->ε#Ca ac# B ->aC#C c##c c# C ->c# # 成功-----------------------------------------------------以上为第三次作业16．对于如下文法G[<变量说明>]：<变量说明>->VAR<变量表>：<类型>;<变量表>-><变量表>,<变量>|<变量><变量>->i<类型>->real|integer|Boolean|char(1)将G改造为等价的算符优先文法G’;令<变量说明>：S，VAR：v, <变量表>：A，<类型>：B，<变量>：Creal：r integer:g Boolean:b char:c文法G 可改写为：S->vA:B;A->A,C|CC->iB->r|g|b|c该文法是算符文法(2)求出G’的全部优先关系。
35.对于以下文法，试构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。
（2）S->cA S->ccB A->cA A->a B->ccB B->b解：拓展文法得文法列表：(0)S’->S (1) S->cA (2)S->ccB (3)A->cA (4)A->a (5)B->ccB (6)B->b37．判断下面的文法是哪一类LR文法，并构造LR分析表。
S->(SR S->a R->,SR R->)解：拓展文法得文法列表：(0)S’->S (1)S->(SR (2)S->a (3) R->,SR (4) R->)项目集规范族:分析表：补充题1：对下列文法G:S →D(R) R →R; P|P P →S|i D →i求出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系矩阵。
解：文法G每个非终结符的FIRSTVT集合FIRSTVT(S)={ (, i }FIRSTVT(R) ={;, (, I }FIRSTVT(P) ={i, ( }FIRSTVT(D) ={i }文法G的每个非终结符的LASTVT集合LASTVT(S) ={ ) } LASTVT(R) ={;, ) ,i }LASTVT(P) = {i , ) } LASTVT(D) = {i }优先关系矩阵（）； i # ( <· =· <· <·) ·> ·> ·>; <··> ·> <·i ·> ·> ·># <· <· =·补充题2:对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法，若是LR(1)方法，分析符号串abab的分析过程。
S→A A→AB A→ε B→aB B→b解：扩展后文法为：0.S’->S 1.S→A 2.A→AB 3.A→ε 4.B→aB 5.B→b构造LR(1)项目集族：-------------------------------------------------以上为第四、五次作业5.4 解：（1）A-BC+*DE-^（2）ad*c+d/e+f*g+（3）ax+4 ≤ cd3*>∨（4）abcdef^*<∧∨（5）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 245.5 解：(1)a+b*c(2)a*(b-c)-(c+d)/e(3)a≤b+c∧a>0∨a+b≠0∧a<0(4)if(a<b) x=(a-b)^c ;else g=h5.8 解：(1)①(+,B,C,T1)②(*,A,T1,T2)③(+,T2,D,T3)④(=,T3,_,X)(2)①(jnz, A,_, ③)②(j,_,_, f )③(jnz,B,_,t)④(j,_,_, ⑤)⑤(jnz, C,_,t)⑥(j,_,_, ⑦)⑦(jnz, D,_, ⑨)⑧(j,_,_,f)⑨(jnz, F,_,f)⑩(j,_,_,t)t:…………f:……(3)①(j<,A,C, ③)②(j,_,_, ⒃)③(j>,B,0, ⑤)④(j,_,_, ⒃)⑤(j=,a,1, ⑦)⑥(j,_,_, ⑩)⑦(+,C,1,T1)⑧(:=,T1,_,C)⑨(j,_,_, ⒂)⑩(j<=,A,D, ⑿)⑾(j,_,_, ⒂)⑿(+,A,2,T2)⒀(:=,T2,_,A)⒁(j,_,_, ⑩)⒂(j,_,_, ①)⒃-------------------------------------------------以上为第六次作业。