习题解答(123章).ppt

思考题： 语言L(G[S])={b2i+1 | i=0}对应 的3型文法？ G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{b}， S∷＝ bbS |b ?? P：S∷＝ bA |b A∷＝ bS 解法二 构造出正规表达式 (0 | 10)* 转换系统 * * 《编译原理》习题解答（一） 第二次作业： P38 1、3、5、7、8(1)(3)(5)、10、11(1)(2)、12(1)(3)(5)、15 第1、3、5题 符号串集合的运算P19 第7题 文法的形式定义 P22 第8题 句型、句子的定义 P23 第10、11题 语言的形式定义，从文法－语言 P24 第12题 语言－文法 P25 第15题 推导语法树、句型短语、简单短语，句柄的概念 P26、P27 P38 1、设T1＝{11，010}，T2＝{0，01，1001}， 计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……} P38 3、令A＝{0，1，2}，写出集合A+和A*的七个最短符号串。 A+：0，1，2，00，01，02，10（有多种可能） A*：ε，0，1，2，00，01，02（有多种可能） P38 5、试证明：A+＝A A*＝A*A。 证明：A+＝A1∪A2∪……∪An∪…… A*＝A0（即{ε}）∪A+ A A*＝A（A0∪A+ ）＝A∪A+＝A+＝A+∪A ＝（A0∪A+ ）A＝A*A（证毕） 符号串集合的运算P19 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，(，)，-} 文法的形式定义 P22 P38-39 8、设有文法G[S]： S∷＝aAb A∷＝BcA | B B∷＝idt |ε 试问下列符号串（1）aidtcBcAb （3）ab （5）aidtcidtcidtb 是否为该文法的句型或句子。 S=aAb=aBcAb=aidtcAb=aidtcBcAb S=aAb=aBb=ab S=aAb=aBcAb=aidtcBcAb=aidtcidtcBb=aidtcidtcidtb 句型、句子的定义 P23 P39 10、给定文法： S∷＝aB | bA A∷＝aS | bAA | a B∷＝bS | aBB | b 该文法所描述的语言是什么？ L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。 P39 11、试分别描述下列文法所产生的语言（文法开始符号为S）： 1)S∷＝0S | 01 2)S∷＝aaS | bc 3) S:: =aSd | aAd A:: =aAc | bc 1)L(G)＝{0n1| n≥1}； 2)L(G)＝{a2nbc | n≥0}； 3)L(G)＝{aibcjdk | i, j, k≥1, i=j+k-1}。 语言的形式定义，从文法－语言 P24 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 A∷＝bA |ε （3）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}， P：S∷＝abA A∷＝aA | a （5）G＝{VN，VT，P，S}，VN＝{S，A ，B，C}， VT＝{a，b，c}， P：S∷＝ABC A∷＝aA |ε B∷＝bB |ε C∷＝cC |ε 语言－文法 P25 P39 15. 设文法G规则为： S：：=AB B：：=a|Sb A：：=Aa|bB 对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 （2）baabaab (3)bBABb 2)句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a 3)短语bB, AB, ABb，简单短语bB, A