资源描述：
《编译原理及实现课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2.3设有文法G[S]：S∷=SS*
2、SS+
3、a，写出符号串aa+a*规范推导，并构造语法树。S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*SSS*SS+aaa2.5已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。A∷=aA︱ε描述的语言:{an
4、n>=0}B∷=bBc︱bc描述的语言：{bncn
5、n>=1}L(G[S])={anbmcm
6、n>=0,m>=1}ETE+FTE+iFT*T2.7对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。短语：T+T*F+iT+T*FiiTT*F简单短语：iT*FT句柄：T2.8设有
7、文法G[S]：S∷=S*S
8、S+S
9、(S)
10、a，该文法是二义性文法吗？SSS*S+SaaaSSS+S*Saaa根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。2.10给出语言{anbm
11、n,m≥1}的文法。G[S]:S::=ABA::=aA
12、aB::=bB
13、b3.1有正则文法G[Z]：Z::=Ua
14、Vb，U::=Zb
15、b，V::=Za
16、a，画出该文法的状态图，并检查句子abba是否合法。解：该文法的状态图如下：SUVZaaabbb句子abba合法。3.2状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。SAZaba
17、b图3-35状态图解：左线性文法G[Z]:右线性文法G’[S]:Z::=Ab
18、bS::=aA
19、bA::=Aa
20、aA::=aA
21、bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vn={S,A}Vt={a,b}Vt={a,b}3.3构造下列正则表达式相应的NFA：1(1
22、0)*
23、01(1010*
24、1(010)*1)*0解：正则表达式：1(1
25、0)*
26、01、SZ1(1
27、0)*
28、02、SZ1(1
29、0)*03、SAZ01ε014、q0q1010,1q2正则表达式：1(1010*
30、1(010)*1)*001354621010107801011ε01a,baa3.4将图3.36的NFAM
31、确定化图3.36状态图解：aBq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}ΦDFA:q0q1q2ababa3.4将图3.37的DFA化简。014253aaaaaabbbbbb图3.37DFA状态图解：划分aB{0,1}{1}{2,4}{2,3,4,5}{1,0,3,5}{3,5,2,4}划分aB{0,1}{1}{2,4}{2,4}{0,1}{3,5}{3,5}{3,5}{2,4}q0={0,1}q1={2,4}q2={3,5}化简后的DFA：q0q1q2baaabb4.1对下面文法，设计递归下降分析程序。S→aAS
32、(A),A→Ab
33、c解：首先将左递归去
34、掉，将规则A→Ab
35、c改成A→c{b}4.4有文法G[A]：A::=aABe
36、ε，B::=Bb
37、b（1）求每个非终结符号的FOLLOW集。（2）该文法是LL(1)文法吗？（3）构造LL(1)分析表。解：（1）FOLLOW(A)=First(B)∪{#}={b,#}FOLLOW(B)={e,b}（2）该文法中的规则B::=Bb
38、b为左递归，因此该文法不是LL(1)文法（3）先消除文法的左递归（转成右递归），文法变为：A::=aABe
39、ε，B::=bB’，B’=bB’
40、ε，该文法的LL(1)分析表为：aeb#APOP，PUSH(eBAa)POPPOPBPOP，PUSH(B’b)B’POPPO
41、P，PUSH(B’b)aPOP,NEXTSYMePOP,NEXTSYMbPOP,NEXTSYM#ACCEPT更常用且简单的LL(1)分析表：aeb#AA→aABeA→εA→εBB→bB’B’B’→εB’→bB’4.5若有文法A→(A)A
42、ε（1）为非终结符A构造FIRST集合和FOLLOW集合。（2）说明该文法是LL(1)的文法。解：（1）FIRST(A)＝｛(,ε｝FOLLOW(A)＝｛)，#｝（2）该文法不含左递归；FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ，且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩FOLL
43、OW(A)=Φ，因此，该文法满足LL(1)文法的条件，是LL(1)文法。4.6利用分析表4-1，识别以下算术表达式，请写出分析过程。（1）i+i*i+i（2）i*(i+i+i)解：（1）i+i*i+i步骤分析栈余留输入串分析表元素所用产生式1#Ei+i*i+i#POP,PUSH(E’T)E→TE’2#E’Ti+i*i+i#POP,PUSH(T’F)T→FT’3#E’T’Fi+i*i+i#POP,PUSH(i)F→i4#E’T’ii+
