對于給定文法:
E->E+T
E->E-T
E->T
T->T*F
T->T/F
T->F
F->(E)
F->i
生成DFA狀態機得:
1 該文法的拓展文法為：
2 $->E
3 E->E+T
4 E->E-T
5 E->T
6 T->T*F
7 T->T/F
8 T->F
9 F->(E)
10 F->i
11 該文法的項目如下：
12 (1) $->.E,#
13 (2) E->.E+T,#
14 (3) E->.E-T,#
15 (4) E->.T,#
16 (5) E->.E+T,+
17 (6) E->.E-T,+
18 (7) E->.T,+
19 (8) E->.E+T,-
20 (9) E->.E-T,-
21 (10) E->.T,-
22 (11) T->.T*F,#
23 (12) T->.T/F,#
24 (13) T->.F,#
25 (14) T->.T*F,+
26 (15) T->.T/F,+
27 (16) T->.F,+
28 (17) T->.T*F,-
29 (18) T->.T/F,-
30 (19) T->.F,-
31 (20) T->.T*F,*
32 (21) T->.T/F,*
33 (22) T->.F,*
34 (23) T->.T*F,/
35 (24) T->.T/F,/
36 (25) T->.F,/
37 (26) F->.(E),#
38 (27) F->.i,#
39 (28) F->.(E),+
40 (29) F->.i,+
41 (30) F->.(E),-
42 (31) F->.i,-
43 (32) F->.(E),*
44 (33) F->.i,*
45 (34) F->.(E),/
46 (35) F->.i,/
47 (36) $->E.,#
48 (37) E->E.+T,#
49 (38) E->E.-T,#
50 (39) E->E.+T,+
51 (40) E->E.-T,+
52 (41) E->E.+T,-
53 (42) E->E.-T,-
54 (43) E->T.,#
55 (44) E->T.,+
56 (45) E->T.,-
57 (46) T->T.*F,#
58 (47) T->T./F,#
59 (48) T->T.*F,+
60 (49) T->T./F,+
61 (50) T->T.*F,-
62 (51) T->T./F,-
63 (52) T->T.*F,*
64 (53) T->T./F,*
65 (54) T->T.*F,/
66 (55) T->T./F,/
67 (56) T->F.,#
68 (57) T->F.,+
69 (58) T->F.,-
70 (59) T->F.,*
71 (60) T->F.,/
72 (61) F->(.E),#
73 (62) E->.E+T,)
74 (63) E->.E-T,)
75 (64) E->.T,)
76 (65) T->.T*F,)
77 (66) T->.T/F,)
78 (67) T->.F,)
79 (68) F->.(E),)
80 (69) F->.i,)
81 (70) F->(.E),+
82 (71) F->(.E),-
83 (72) F->(.E),*
84 (73) F->(.E),/
85 (74) F->i.,#
86 (75) F->i.,+
87 (76) F->i.,-
88 (77) F->i.,*
89 (78) F->i.,/
90 (79) E->E+.T,#
91 (80) E->E+.T,+
92 (81) E->E+.T,-
93 (82) E->E-.T,#
94 (83) E->E-.T,+
95 (84) E->E-.T,-
96 (85) T->T*.F,#
97 (86) T->T*.F,+
98 (87) T->T*.F,-
99 (88) T->T*.F,*
100 (89) T->T*.F,/
101 (90) T->T/.F,#
102 (91) T->T/.F,+
103 (92) T->T/.F,-
104 (93) T->T/.F,*
105 (94) T->T/.F,/
106 (95) F->(E.),#
107 (96) E->E.+T,)
108 (97) E->E.-T,)
109 (98) F->(E.),+
110 (99) F->(E.),-
111 (100) F->(E.),*
112 (101) F->(E.),/
113 (102) E->T.,)
114 (103) T->T.*F,)
115 (104) T->T./F,)
116 (105) T->F.,)
117 (106) F->(.E),)
118 (107) F->i.,)
119 (108) E->E+T.,#
120 (109) E->E+T.,+
121 (110) E->E+T.,-
122 (111) E->E-T.,#
123 (112) E->E-T.,+
124 (113) E->E-T.,-
125 (114) T->T*F.,#
126 (115) T->T*F.,+
127 (116) T->T*F.,-
128 (117) T->T*F.,*
129 (118) T->T*F.,/
130 (119) T->T/F.,#
131 (120) T->T/F.,+
132 (121) T->T/F.,-
133 (122) T->T/F.,*
134 (123) T->T/F.,/
135 (124) F->(E).,#
136 (125) F->(E).,+
137 (126) F->(E).,-
138 (127) F->(E).,*
139 (128) F->(E).,/
140 (129) E->E+.T,)
141 (130) E->E-.T,)
142 (131) T->T*.F,)
143 (132) T->T/.F,)
144 (133) F->(E.),)
145 (134) E->E+T.,)
146 (135) E->E-T.,)
147 (136) T->T*F.,)
148 (137) T->T/F.,)
149 (138) F->(E).,)
150 項目規范族如下：
151 I0 { 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 }
152 I1 { 36, 37, 38, 39, 40, 41, 42 }
153 I2 { 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 }
154 I3 { 56, 57, 58, 59, 60 }
155 I4 { 61, 62, 63, 64, 5, 6, 7, 8, 9, 10, 65, 66, 67, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 68, 69, 28, 29, 30, 31, 32, 33, 34, 35, 70, 71, 72, 73 }
156 I5 { 74, 75, 76, 77, 78 }
157 I6 { 79, 11, 12, 13, 20, 21, 22, 23, 24, 25, 26, 27, 32, 33, 34, 35, 80, 14, 15, 16, 28, 29, 81, 17, 18, 19, 30, 31 }
158 I7 { 82, 11, 12, 13, 20, 21, 22, 23, 24, 25, 26, 27, 32, 33, 34, 35, 83, 14, 15, 16, 28, 29, 84, 17, 18, 19, 30, 31 }
159 I8 { 85, 26, 27, 86, 28, 29, 87, 30, 31, 88, 32, 33, 89, 34, 35 }
160 I9 { 90, 26, 27, 91, 28, 29, 92, 30, 31, 93, 32, 33, 94, 34, 35 }
161 I10 { 95, 96, 97, 39, 40, 41, 42, 98, 99, 100, 101 }
162 I11 { 102, 44, 45, 103, 104, 48, 49, 50, 51, 52, 53, 54, 55 }
163 I12 { 105, 57, 58, 59, 60 }
164 I13 { 106, 62, 63, 64, 5, 6, 7, 8, 9, 10, 65, 66, 67, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 68, 69, 28, 29, 30, 31, 32, 33, 34, 35, 70, 71, 72, 73 }
165 I14 { 107, 75, 76, 77, 78 }
166 I15 { 108, 46, 47, 52, 53, 54, 55, 109, 48, 49, 110, 50, 51 }
167 I16 { 56, 59, 60, 57, 58 }
168 I17 { 61, 62, 63, 64, 5, 6, 7, 8, 9, 10, 65, 66, 67, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 68, 69, 28, 29, 30, 31, 32, 33, 34, 35, 72, 73, 70, 71 }
169 I18 { 74, 77, 78, 75, 76 }
170 I19 { 111, 46, 47, 52, 53, 54, 55, 112, 48, 49, 113, 50, 51 }
171 I20 { 114, 115, 116, 117, 118 }
172 I21 { 119, 120, 121, 122, 123 }
173 I22 { 124, 125, 126, 127, 128 }
174 I23 { 129, 65, 66, 67, 20, 21, 22, 23, 24, 25, 68, 69, 32, 33, 34, 35, 80, 14, 15, 16, 28, 29, 81, 17, 18, 19, 30, 31 }
175 I24 { 130, 65, 66, 67, 20, 21, 22, 23, 24, 25, 68, 69, 32, 33, 34, 35, 83, 14, 15, 16, 28, 29, 84, 17, 18, 19, 30, 31 }
176 I25 { 131, 68, 69, 86, 28, 29, 87, 30, 31, 88, 32, 33, 89, 34, 35 }
177 I26 { 132, 68, 69, 91, 28, 29, 92, 30, 31, 93, 32, 33, 94, 34, 35 }
178 I27 { 133, 96, 97, 39, 40, 41, 42, 98, 99, 100, 101 }
179 I28 { 85, 26, 27, 88, 32, 33, 89, 34, 35, 86, 28, 29, 87, 30, 31 }
180 I29 { 90, 26, 27, 93, 32, 33, 94, 34, 35, 91, 28, 29, 92, 30, 31 }
181 I30 { 95, 96, 97, 39, 40, 41, 42, 100, 101, 98, 99 }
182 I31 { 134, 103, 104, 52, 53, 54, 55, 109, 48, 49, 110, 50, 51 }
183 I32 { 105, 59, 60, 57, 58 }
184 I33 { 106, 62, 63, 64, 5, 6, 7, 8, 9, 10, 65, 66, 67, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 68, 69, 28, 29, 30, 31, 32, 33, 34, 35, 72, 73, 70, 71 }
185 I34 { 107, 77, 78, 75, 76 }
186 I35 { 135, 103, 104, 52, 53, 54, 55, 112, 48, 49, 113, 50, 51 }
187 I36 { 136, 115, 116, 117, 118 }
188 I37 { 137, 120, 121, 122, 123 }
189 I38 { 138, 125, 126, 127, 128 }
190 I39 { 114, 117, 118, 115, 116 }
191 I40 { 119, 122, 123, 120, 121 }
192 I41 { 124, 127, 128, 125, 126 }
193 I42 { 131, 68, 69, 88, 32, 33, 89, 34, 35, 86, 28, 29, 87, 30, 31 }
194 I43 { 132, 68, 69, 93, 32, 33, 94, 34, 35, 91, 28, 29, 92, 30, 31 }
195 I44 { 133, 96, 97, 39, 40, 41, 42, 100, 101, 98, 99 }
196 I45 { 136, 117, 118, 115, 116 }
197 I46 { 137, 122, 123, 120, 121 }
198 I47 { 138, 127, 128, 125, 126 }
199 狀態轉移表如下：
200 I0 -> I1 [ E ]
201 I0 -> I2 [ T ]
202 I0 -> I3 [ F ]
203 I0 -> I4 [ ( ]
204 I0 -> I5 [ i ]
205 I1 -> I6 [ + ]
206 I1 -> I7 [ - ]
207 I2 -> I8 [ * ]
208 I2 -> I9 [ / ]
209 I4 -> I10 [ E ]
210 I4 -> I11 [ T ]
211 I4 -> I12 [ F ]
212 I4 -> I13 [ ( ]
213 I4 -> I14 [ i ]
214 I6 -> I15 [ T ]
215 I6 -> I16 [ F ]
216 I6 -> I17 [ ( ]
217 I6 -> I18 [ i ]
218 I7 -> I19 [ T ]
219 I7 -> I16 [ F ]
220 I7 -> I17 [ ( ]
221 I7 -> I18 [ i ]
222 I8 -> I20 [ F ]
223 I8 -> I4 [ ( ]
224 I8 -> I5 [ i ]
225 I9 -> I21 [ F ]
226 I9 -> I4 [ ( ]
227 I9 -> I5 [ i ]
228 I10 -> I22 [ ) ]
229 I10 -> I23 [ + ]
230 I10 -> I24 [ - ]
231 I11 -> I25 [ * ]
232 I11 -> I26 [ / ]
233 I13 -> I27 [ E ]
234 I13 -> I11 [ T ]
235 I13 -> I12 [ F ]
236 I13 -> I13 [ ( ]
237 I13 -> I14 [ i ]
238 I15 -> I28 [ * ]
239 I15 -> I29 [ / ]
240 I17 -> I30 [ E ]
241 I17 -> I11 [ T ]
242 I17 -> I12 [ F ]
243 I17 -> I13 [ ( ]
244 I17 -> I14 [ i ]
245 I19 -> I28 [ * ]
246 I19 -> I29 [ / ]
247 I23 -> I31 [ T ]
248 I23 -> I32 [ F ]
249 I23 -> I33 [ ( ]
250 I23 -> I34 [ i ]
251 I24 -> I35 [ T ]
252 I24 -> I32 [ F ]
253 I24 -> I33 [ ( ]
254 I24 -> I34 [ i ]
255 I25 -> I36 [ F ]
256 I25 -> I13 [ ( ]
257 I25 -> I14 [ i ]
258 I26 -> I37 [ F ]
259 I26 -> I13 [ ( ]
260 I26 -> I14 [ i ]
261 I27 -> I38 [ ) ]
262 I27 -> I23 [ + ]
263 I27 -> I24 [ - ]
264 I28 -> I39 [ F ]
265 I28 -> I17 [ ( ]
266 I28 -> I18 [ i ]
267 I29 -> I40 [ F ]
268 I29 -> I17 [ ( ]
269 I29 -> I18 [ i ]
270 I30 -> I41 [ ) ]
271 I30 -> I23 [ + ]
272 I30 -> I24 [ - ]
273 I31 -> I42 [ * ]
274 I31 -> I43 [ / ]
275 I33 -> I44 [ E ]
276 I33 -> I11 [ T ]
277 I33 -> I12 [ F ]
278 I33 -> I13 [ ( ]
279 I33 -> I14 [ i ]
280 I35 -> I42 [ * ]
281 I35 -> I43 [ / ]
282 I42 -> I45 [ F ]
283 I42 -> I33 [ ( ]
284 I42 -> I34 [ i ]
285 I43 -> I46 [ F ]
286 I43 -> I33 [ ( ]
287 I43 -> I34 [ i ]
288 I44 -> I47 [ ) ]
289 I44 -> I23 [ + ]
290 I44 -> I24 [ - ]
由此可見LR(1)分析表會變得無比的巨大.
posted on 2010-07-16 16:03
lwch 閱讀(511)
評論(0) 編輯 收藏 引用 所屬分類:
NScript