實驗一：詞法分析
實驗目的:
通過DFA程式的實現理解自動機的原理
實驗內容：
1、閱讀並理解實驗案例中DFA的程式實現；
2、參考實驗案例，完成簡單的DFA程式設計。
實驗要求：
請對下列程式進行詞法分析，判斷是否字串“abbb”將被識別或通過在FA接受？
1、假定FA=（{0,1,2,3}, {a,b}, M, 0, {3}）
M：
M(0,a)=1 M(0,b)=2 M(1,a)=3 M(1,b)=2
M(2,a)=1 M(2,b)=3 M(3,a)=3 M(3,b)=3
確定化後的DFA為：
參考代碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
| #include <stdio.h>
int in(int s,int z)
{
if (s==z)
{printf("3\n这个最后状态跳转到终态!");
return 1;
}
else return 0;
}
int step (int s,char t)
{
if(t=='a')
switch(s)
{
case 0: return 1;
case 1: return 3;
case 2: return 1;
case 3: return 3;
}
else if (t=='b')
switch(s)
{
case 0: return 2;
case 1: return 2;
case 2: return 3;
case 3: return 3;
}
return 0;
}
int realize(char *input)
{
int z=3;
int s,i;
s=0;
for(i=0;input[i]!='\n';i++)
{
printf("%d\n",s);
s=step(s,input[i]);
}
if (in(s,z))
return 1;
else return 0;
}
main()
{
int i;
int a;
char input[40];
printf("FA=({0,1,2,3}, {a,b}, M, 0, {3})\n");
printf("M:\n");
printf(" M(0,a)=1 M(0,b)=2\n");
printf(" M(1,a)=3 M(1,b)=2\n");
printf(" M(2,a)=1 M(2,b)=3\n");
printf(" M(3,a)=3 M(3,b)=3\n");
printf("请输入要检查的字符串:\n");
lop: for(i=0;input[i-1]!='\n';i++)
scanf("%c",&input[i]);
for(i=0;input[i-1]!='\n';i++)
if(input[i]!='a'&&input[i]!='b'&&input[i]!='\n')
{
printf("输入错误，请重新输入:\n");
goto lop;
}
printf("这个状态转换为:\n");
a=realize(input);
if(a==1)
printf("\n这个字符串不能识别\n");
else printf("\n这个字符串不能识别n");
printf("请回车离开此程序\n");
getchar();
}
|
實驗結果：
測試數據：aab 測試結果：0 1 3 3
