编译原理作业题范例.doc

第二章 2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1 ∪ A2 ∪ …. ∪ A n ∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪ A2 ∪ …. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S = SS* = Sa* = SS+a* = Sa+a* = aa+a* 2.4 已知文法G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=U0=Z10=U010=1010 Z=U0=Z10=V110=0110 Z=V1=Z01=U001=1001 Z=V1=Z01=V101=0101 2.5 已知文法G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {an|n=0} B∷=bBc︱bc描述的语言：{bncn|n=1} L(G[S])={anbmcm|n=0,m=1} 2.6 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。 开始符号：E Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T} 2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T 2.8 设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA N::=0|1|2|3|4|5|6|7|8|9 2.10给出语言{anbm|n,m≥1}的文法。 G[S]: S::=AB A::=aA|a B::=bB|b 第三章 3.1 有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，画出该文法的状态图，并检查句子abba是否合法。 解：该文法的状态图如下： 句子abba合法。 3.2 状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。 解： 左线性文法G[Z]: 右线性文法G’[S]: Z::=Ab|b S::=aA|b A::=Aa|a A::=aA|b V={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|0)*|0 1(1010*|1(010)*1)*0 解：正则表达式：1(1|0)*|0 1、 2、 3、 4、 正则表达式：1(1010*|1(010)*1)*0 将图3.36的NFA M确定化 解： a b q0={0} {0,1} {1} q1={0,1} {0,1} {1} q2={1} {0} Φ DFA: 将图3.37的DFA化简。 解： 划分 a b {0,1} {1} {2,4} {2,3,4,5} {1,0,3,5} {3,5,2,4} 划分 a b {0,1} {1} {2,4} {2,