词法分析作业及答案

《词法分析作业及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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已经是最简形式了。