资源描述：
《编译原理习题解答(第2-3章)_吴蓉》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》第2-3章习题解答版权所有：南京邮电大学计算机学院声明：希望同学们不要把此解答拷贝给他人，请大家保持诚信第二章习题2P387.设有文法G[S]：S∷＝AA∷＝B
2、IFATHENAELSEAB∷＝C
3、B+C
4、+CC∷＝D
5、C*D
6、*DD∷＝X
7、(A)
8、-D试写出VN和VT。解：VN＝{S，A，B，C，D}VT＝{IF，THEN，ELSE，+，*，X，(，)，-}P3910.给定文法：S∷＝aB
9、bAA∷＝aS
10、bAA
11、aB∷＝bS
12、aBB
13、b该文法所描述的语言是什么？解：L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}
14、。P3911.试分别描述下列文法所产生的语言（文法开始符号为S）：(2)S∷＝aaS
15、bc(4)S::=ABA::=aAb
16、abB::=cBd
17、ε解：(2)L(G)＝{a2nbc
18、n≥0}；(4)L(G)＝{anbncmdm
19、m≥0,n≥1}。P3912.试分别构造产生下列语言的文法：（1）{abna
20、n=0，1，2，3……}（3）{aban
21、n≥1}（5）{anbmcp
22、n，m，p≥0}解：（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aAa或S∷＝aBA∷＝bA
23、εB∷＝bB
24、a（3）G＝{VN，VT，
25、P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝abA或S∷＝Sa
26、abaA∷＝aA
27、a（5）{anbmcp
28、n，m，p≥0}解：G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，P：S∷＝ABCA∷＝aA
29、εB∷＝bB
30、εC∷＝cC
31、εP3915.设文法G规则为：S：：=ABB：：=a
32、SbA：：=Aa
33、bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（2）baabaab解：SABAaSbbBABabBaa句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄
34、aP4019.证明下述文法是二义的S::=iEtS
35、iEtSeS
36、aE::=b存在句子ibtibtaeibta或者ibtibtaea有两颗不同的语法树3)解：对于句子ababa可构造两棵不同的语法树，所以证明该文法是二义的。SAaCbAbaaSBBCCababaP4124.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S::=aBB::=cBB::=bC::=c2.S::=aBB::=bCC::=cC::=ε3.S::=aAbaA::=aBaA::=aaAB::=bA::=a4.S::=aCdaC::=BaC:
37、:=aaAB::=b5.S::=ABA::=aB::=bCB::=bC::=c6.S::=ABA::=aB::=bCC::=cC::=ε7.S::=aAS::=εA::=aAA::=aBA::=aB::=b8.S::=aAS::=εA::=bAbA::=a解：正规文法127或者1上下文无关文法568或者25678上下文有关文法3短语结构文法4P4126.给出产生下列语言L（G）={W
38、W∈{0，1}+且W不含相邻1}的正规文法。解：G=({S,A,B},{0,1},P,S)P:S::=0
39、1
40、0S
41、1AA::=0
42、0S解题思路一：写出满足要
43、求的符号串，例如0，1，00，01，10，000，101，010，001等，根据符号串从左至右的次序画出状态转换图，然后根据状态转换图来推导出文法。这将会得到S::=0
44、1
45、0S
46、1A
47、0Z
48、1ZA::=0
49、0S
50、0Z经过分析其中Z为多余状态可删去。SZA100001解题思路二：写出其正规表达式(0
51、10)*(10
52、0
53、1)【如果仅有(0
54、10)*的话推导不出1，因为是连接关系，后面缺了10的话就会以1结尾，同样的道理还要推导出0，所以得到此正规式】，画出转换系统，然后根据转换系统来推导出文法。也可以根据正规表达式直接写文法，例如正规表达式
55、(0
56、10)*(10
57、0
58、1)可以看成是a*b，推导出A::=(0
59、10)A
60、10
61、0
62、1，即A::=0A
63、1B
64、10
65、0
66、1，其中B::=0A，但是10此项不符合正规文法的选项，可以进行改写从而得到A::=0A
67、1B
68、0
69、1B::=0A
70、0。P4127.给出一个产生下列语言L（G）＝{W
71、W∈{a,b}*且W中含a的个数是b个数两倍的前后文无关文法。解：文法G=({S,A,B},{a,b},P,S)P:S::=AAB
72、ABA
73、BAA
74、εA::=aSB::=bS或者S::=Saab
75、aSab
76、aaSb
77、aabS
78、Saba
79、aSba
80、abSa
81、
82、abaS
83、Sbaa
84、bSaa
85、baSa
86、baaS
87、ε或者S::=aaB
88、aBa
89、Baa
90、εB::=SbSP4128.给出一个产生下列语言L(G)={w
91、w∈{a,b,c}+且w
