编译原理习题解答(第2-3章)

《编译原理》第2-3章习题解答 版权所有：南京邮电大学计算机学院 声明：希望同学们不要把此解答拷贝 给他人，请大家保持诚信 * 第二章习题 * P38 7.设有文法G[S]： S∷＝A A∷＝B | IF A THEN A ELSE A B∷＝C | B+C | +C C∷＝D | C*D | *D D∷＝X | (A) | -D 试写出VN和VT。 解： VN＝{S，A，B，C，D} VT＝{IF，THEN，ELSE，+，*，X，(，)，-} P39 10.给定文法： S∷＝aB | bA A∷＝aS | bAA | a B∷＝bS | aBB| b 该文法所描述的语言是什么？ 解： L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。 P39 11.试分别描述下列文法所产生的语言（文法开始符号为S）： (2) S∷＝aaS | bc (4) S:: =AB A:: =aAb | ab B:: =cBd | ε 解： (2) L(G)＝{a2nbc | n≥0}； (4) L(G)＝{anbncmdm | m≥0, n≥1}。 P39 12.试分别构造产生下列语言的文法： （1）{ abna | n=0，1，2，3……} （3）{ aban | n≥1} （5）{ anbmcp | n，m，p≥0} 解： （1）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}， P：S∷＝aAa 或 S∷＝aB A∷＝bA |ε B∷＝bB | a （3）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}， P：S∷＝abA 或 S∷＝Sa | aba A∷＝aA | a （5）{ anbmcp | n，m，p≥0} 解： G＝{VN，VT，P，S}，VN＝{S，A ，B，C }，VT＝{a，b，c}， P：S∷＝ABC A∷＝aA |ε B∷＝bB |ε C∷＝cC |ε P39 15. 设文法G规则为： S：：=AB B：：=a|Sb A：：=Aa|bB 对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 （2）baabaab 解： S A B A a S b b B A B a b B a a 句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a P40 19. 证明下述文法是二义的 S::=iEtS| iEtSeS|a E::=b 存在句子ibtibtaeibta或者ibtibtaea有两颗不同的语法树 3) 解： 对于句子ababa可构造两棵不同的语法树，所以证明该文法是二义的。 S A a C b A b a a S B B C C a b a b a P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？ 1.S::=aB B::= cB B::=b C::=c 2.S::=aB B::=bC C::=c C::=ε 3.S::=aAb aA::=aB aA::=aaA B::=b A::=a 4.S::=aCd aC::=B aC::=aaA B::=b 5.S::=AB A::=a B::=bC B::=b C::=c 6. S::=AB A::=a B::=bC C::=c C::=ε 7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b 8. S::=aA S::= ε A::=bAb A::=a 解：正规文法 1 2 7 或者 1 上下文无关文法 5 6 8 或者 2 5 6 7 8 上下文有关文法 3 短语结构文法 4 P41 26. 给出产生下列语言L（G）={W|W∈{0，1}+且W不含相邻1}的正规文法。 解： G=({S, A, B}, {0, 1}, P, S) P: S::=0|1|0S|1A A::=0|0S 解题思路一：写出满足要求的符号串，例如0，1，00，01，10，000，101，010，001等，根据符号串从左至右的次序画出状态转换图，然后根据状态转换图来推导出文法。这将会得到S::=0|1|0S|1A|0Z|1Z A::=0|0S|0Z 经过分析其中Z为多余状态可删去。 S Z A 1 0 0 0 0 1 解题思路二：写出其正规表达式(0|10)*(10|0|1)【如果仅有(0|10)*的话推导不出1，因为是连接关系，后面缺了10的话就会以1结尾，同样的道理还要推导出0，所以得到此正规式】，画出转换系统，然后根据转换系统来推导出文法。也可以根据正规表达式直接写文法，例如正规表达式(0|10)*(10|0|1)可以看成是a*b，推导出A::= (0|10)A|10|0|1，即A::= 0A|1B|10|0|1，其中B::=0A，但是10此项不符合正规文法的选项，可以进行改写从而得到A::= 0A|1B|0|1 B::=0A|0。 P41 27.给出一个产生下列语言 L（G）＝{W|W∈{a,b}*且W中含a的个数是b个数两倍的前后文无关文法。 解：文法G=({S, A, B}, {a, b}, P, S) P: S::=AAB|ABA|BAA|ε A::=aS B::=bS 或者 S::=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSaa|baSa|baaS|ε 或者 S::=aaB|aBa|Baa|ε B::=SbS P41 28. 给出一个产生下列语言L(G)={w | w∈{a, b, c}+且w由相同个数的a，b，c组成的前后文有关文法。 解: 文法G=({S, A, B}, {a, b, c}, P, S) P: S::= ABC A::=aS | a B::=bS | b C::=cS | c AB::=BA BC::=CB AC::=CA P41 29. 用扩充的BNF表示以下文法规则： (1) Z::=AB|AC|A (2) A::=BC|BCD|AXZ|AXY (3) S::=aABb|ab (4) A::=Aab|ε 解: (1) Z::=A（B|C|ε）::=A[B|C] (2) A::=BC（ε|D）|{X（Z|Y）}::= BC[D]|{X（Z|Y）} (3) A::=a((AB|ε)b) ::= a[AB]b (4) A::={ab|ε}::={ab} 第三章习题 P74 4. 画出下列文法的状态图： Z :: =Be B :: =Af A :: =e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。 解： 由状态图可知只有eefe是该文法的合法句子。 P74 6. 构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？ Z :: =A0 A :: =A0|Z1|0 解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z :: =A0 A :: =A0|B1|0 B :: =A0，具体为： A := Z1 A := B1 A := A01 Z := A0 B := A0 将所得的新左线性文法转换成右线性文法： 此时利用书上规则，其对应的右线性文法为：A :: =0A|0B|0 Z :: =0A B :: =1A 解2：先画出该文法状态转换图： NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}） 其中M： M（S，0）={A} M（S，1）=ø M（A，0）={A，Z} M（A，1）=ø M（Z，0）=ø M（Z，1）={A} 显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；也可以通过求解正规表达式得到A=0(0|01)*，Z=0(0|01)*0 那么如何构造其相应的有穷自动机呢？ 先构造其转换系统： Z’ Z A S S’ ε 0 1 0 0 ε 根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：(其中S’可以忽略，结果是一样的) I I0 I1 S 0 1 {S’, S} {A} Ф 0 1 Ф {A} {A, Z, Z’} Ф 1 2 Ф {A, Z, Z’} {A, Z, Z’} {A} 2 2 1 则其相应的DFA为： 2 1 0 0 0 0 1 P74 7. 构造一个DFA，它接受{0，1}上所有满足下述条件的字符串，其条件是：字符串中每个1都有0直接跟在右边，然后，再构造该语言的正规文法。 解(一)：其状态转换图为 (状态S表示空串开始，状态A表明串的末尾是1，状态Z表示串的末尾是0) DFA=（{S，A，Z}，{0，1}，M，S，{Z}） 其中M： M（S，0）=Z M（S，1）= A M（A，0）=Z M（Z，0）=Z M（Z，1）=A 该语言的正规文法G[Z]为： 右线性文法：//S :: =0|1A|0Z 左线性文法： A :: =0|0Z A :: =1|Z1 Z :: =0|1A|0Z Z :: =0|A0|Z0 若终止状态只引入不引出则适合构造右线性文法，若开始状态只引出不引入则适合构造左线性文法，若终态和初态均既有引入又有引出，则构造文法要注意。 解(二)：可以先写出该文法的正规表达式为(0 | 10)*，根据该正规式构造转换系统 对于该转换系统可以采用子集法将其转变为DFA，再根据DFA写出其正规文法；但是注意观察后，发现开始状态S通过ε到达A状态，可以直接删去S状态，由A状态作为新的开始状态，同理，只有A状态通过ε才能到达终止状 态Z，因此可以删去Z状态，由A状态作为终止状态。这样，A状态就既为开始状态又为终止状态。可画出化简后的转换图。可写出右线性文法为： A :: =0|0A|1B B :: =0|0S P74 8. 设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} )，其中M定义如下： M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B} 请构造相应确定有穷自动机(DFA) M’。 解：构造一个如下的自动机(DFA) M’， (DFA) M’={K’, {a, b}, M’, S’, Z’} K’的元素是[A] [B] [A, B] 由于M（A, a）={A, B}，故有M’（[A], a）=[A, B] 同样 M’（[A]，b）=[B] M’（[B]，a）= ø M’（[B]，b）=[A，B] 由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ø= {A，B} 故 M’（[A，B]，a）= [A，B] 由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B} 故 M’（[A，B]，b）= [A，B] S’=[A]，终态集Z’={[A，B]，[B]} 重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示： P74 9. 设有穷自动机M = ({S, A, E}, {a, b, c}, M, S, {E})，其中M定义为 M (S, c) = A M (A, b) = A M (A, a) = E 请构造一个左线性文法。 解：先求右线性文法 S→cA A→bA A→a | aE {A→aE实际上是多余的规则，应该去掉} 其左线性文法G=（VN, VT, P, S） VN = {A, S} VT = {a, b, c} 根据书上左右线性文法的转换规则，得到P: A→c A→Ab S→Aa {E→Aa实际上是多余的规则，应该去掉} 画出状态转换图之后就非常清晰。 P74 11. 构造下列正规式相应的DFA： （1）(0 | 11*0)* 【新课本】 解：先构造该正规式的转换系统： 由上述转换系统可得状态转换集K={S, 1, 2, 3, 4, Z}，状态子集转换矩阵如下表所示： I I0 I1 K 0 1 {S, 1, Z} {1, Z} {2, 3, 4} 0 1 2 {1, Z} {1, Z} {2, 3, 4} 1 1 2 {2, 3, 4} {1, Z} {3, 4} 2 1 3 {3, 4} {1, Z} {3, 4} 3 1 3 由状态子集转换矩阵可知，状态0和1是等价的，而状态2和3是等价的，因此，合并等价状态之后只剩下2个状态，也即是最少状态的DFA。 P74 12. 将图3.24非确定有穷自动机NFA确定化和最少化。 解：设(DFA)M = {K, VT, M, S, Z}，其中，K={[0], [0, 1], [1]}，VT ={a, b}，M： M ([1], a) =[0] M ([1], b) =Ф M ([0, 1], a) =[0, 1] M ([0, 1], b) =[1] M ([0], a) =[0, 1] M ([0], b) =[1] S=[1]，Z={[0], [0, 1]} 令[0, 1]=2，则其相应的状态转换图为： 现在对该DFA进行化简，先把状态分为两组： 终态组 {0, 2} 和非终态组 {1}，易于发现 {0, 2} 不可以继续划分，因此化简后的状态转换图如下： P74 15. 用两种方法将(NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z})，构造相应的DFA，其中： M (X, 0) = {Z} M (X, 1) = {X} M (Y, 0) = {X, Y} M (Y, 1) = Ф M (Z, 0) = {X, Z} M (Z, 1) = {Y} 第一种方法：先画出其状态转换图，利用非子集法： 假设(DFA) M’=(K’, VT’, M’, S’, Z’)， 其中K’={[X], [Y], [Z], [X,Y], [X, Z], [Y, Z], [X, Y, Z]}， VT’={0, 1}，M’的规则如下表： 其中[Y, Z]为不可到达状态，应该删去，所以S’={[X]}，Z’={[Z], [X, Z], [X, Y, Z]}，再进行化简，发现4和6两状态等价，最后其DFA如下所示： 第二种方法：先构造其对应的转换系统： 由上述转换系统可得状态转换集、状态子集转换矩阵如下表所示： 先化简，分为非终态集 {2, 4, 5, 0} 和终态集 {6, 1, 3}，易于发现可划分为{0, 2}，{1}，{3, 6}，{4}，{5}，其DFA如下所示： P74 18. 根据下面正规文法构造等价的正规表达式： S::=cC | a ……① A::=cA | aB ……② B::=aB | c ……③ C::=aS | aA | bB | cC | a ……④ 解：由③式可得 B= aB + c → B=a*c 由②式可得 A= cA + aB → A= c*aa*c 由①式可得 S= cC + a 由④式可得 C= aS + aA + bB + cC + a → C= c*( aS + aA + bB + a) → C= c*( aS + ac*aa*c + ba*c + a) → S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a) 另一种答案是S= c(ac | c)*( ac*aa*c | ba*c | aa | a) | a P75 20. 证明下列关系式成立，其中A、B是任意正规表达式。 （4）(AB)*A = A(BA)* 解： (AB)*A = ((AB)0 ∪(AB)1∪(AB)2∪……)A = A∪ABA∪ABABA∪…… = A((BA)0 ∪(BA)1∪(BA)2∪……) = A(BA)*。 *