资源描述:
《词法分析作业及答案》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、词法分析1.写一个文法,使其语言是奇数集,且每个奇数不以0开头。—■■・9I5V/I0【分析】泌是希望构造-个文法,由它产生的句子是奇数,并且不以0开头。也就是说,它的毎是以1、3、5、7、9中的某个数结尾。如果数字只有-位,则满足要求,如果有多位,则-位不能是0,而中间有多位、每位是什么数字(必须是数字)则没有要求一—丢二■我们町以把这个文法分3部分来完成。分别用3个非终结符产生句子的第一位中和最后-位。引人几个非终结符,其中,-个用来产生句子的开头,可以是1〜9之间的鱼括0;-个用来产生句子的结尾,为奇数;另一个则用来产生以。
2、〜9之间的任意整数组成的任意长度的数字串。进行分解后,这个文法就很好写了。【解答】解法一:文法G=({S,A}JO,1,2,3・4・5,6,7,8,9},P,S)其中,P为:S~d]A
3、d3d,代表1~9中的数字;A—d2A
4、d3dz代表O~9中的数字;d3代表1,3,5,7,9中的任虑一个数字。解法二:文法G=({N,A,B,C,D},{0,1,2,3,4,567,8,9I,P,N),其中,P为:N—ABIBA—ACID・B-*ll3l5l7
5、91>*2
6、4
7、6
8、8
9、BC-*O
10、D解法三:文法g=({S,W,F,N,D},{0,
11、1,2,3,4・5,6,7,8・9I,P,S),其中P为:S-*W
12、FW
13、FNWN~DlNDI>*0
14、l
15、3
16、5
17、7
18、9
19、2
20、4
21、6
22、8Wf1
23、3
24、5
25、7
26、9F-*l
27、3
28、5
29、7
30、9
31、2
32、4
33、6
34、8Gi:2•给出下列正规表达式:以01结尾的二进制数串。3.给出下面语言的上下文无关文法:L^bVln^1,1^0}求b和c的个数-样多,因此可使用一个非终结符去生成旳•而使用另外一驚警囂分成两段考虑,即旳和也,然后使用两个非终结符分别去它们。,对于L3,将语言句子的描述稍作变形•得fl2mabb,n和abbbmo这样一来,发现句子中削后
35、的8和b的个数就有倍数关系了。【解答】1EFF—bFcIbcE-*hE
36、eAABA-^aAbltB—aBbleZfaaZbZ—bb4.为正规式(a
37、b)*a(a
38、b)(a
39、b)构造NFA,将其变换成DFA,并将该DFA最小化。答:NFA如下:a图3-20正^A(alb)-a(a
40、b)(a
41、b)的DFA*3-4状态转换表状杰lalb070110,1}lolr:iotii'0.1.2110.212*:
42、OJ.2
43、0.1.2.31{023}3':
44、0・2
45、10,1.3110,314#:
46、0Jt2t3
47、I0.123}102315TO.2.
48、3II0U.3I10,316r:lOtl,3
49、!0tlt2i10.217、10.3110.11101状态转换图如图3・20所示。为方便起见•状态0'〜7'用0〜7来表示。最小化的过程;初始时将状态集分成两组:l0,1,2,3}和{4,5,6,7
50、o由于I(10,1,2,31,a)=11.2,4,6(1(
51、0,1,2,3
52、,b)=
53、0,3,5,7
54、I(14,5,6,71,a)=
55、192,4,6
56、1(
57、4,5,6,7
58、,b)=
59、0,3,5,7
60、因此进一步分成10,11J2,3}、{4,5}和{6,7}四组。由于I(1(),11,a)=
61、
62、1,21I(
63、0,11,b)=10,31因此10,1
64、还要进一步分,其他几组也是这样。因此域终分成了每个集合中都只有一个状态。所以上述DFA已经是最简形式了。