Java > Open Source Codes > org > sablecc > sablecc > automaton > NfaTest


1 /* This file is part of SableCC ( http://sablecc.org ).
2  *
3  * Copyright 2007 Raymond Audet <raymond.audet@gmail.com>
4  * Copyright 2007 Etienne M. Gagnon <egagnon@j-meg.com>
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18
19 package org.sablecc.sablecc.automaton;
20
21 import static org.junit.Assert.assertFalse;
22 import static org.junit.Assert.assertTrue;
23 import static org.junit.Assert.fail;
24
25 import java.util.Collection ;
26 import java.util.LinkedList ;
27 import java.util.SortedSet ;
28
29 import org.junit.Before;
30 import org.junit.Test;
31 import org.sablecc.sablecc.alphabet.Interval;
32 import org.sablecc.sablecc.alphabet.Realms;
33 import org.sablecc.sablecc.alphabet.Symbol;
34 import org.sablecc.sablecc.exception.InternalException;
35
36 public class NfaTest {
37
38     Nfa<Integer > nfa;
39
40     NfaCombineResult<Integer > result;
41
42     Nfa<Integer > unstableNfa;
43
44     Interval<Integer > interval;
45
46     Symbol<Integer > symbol;
47
48     @Before
49     public void setUp()
50             throws Exception {
51
52         this.nfa = new Nfa<Integer >();
53
54         // In order to get an unstable Nfa
55 this.result = this.nfa.combineWith(this.nfa);
56         this.unstableNfa = this.result.getNewNfa();
57
58         this.interval = Realms.getInteger().createInterval(5);
59         this.symbol = new Symbol<Integer >(this.interval);
60         this.nfa = new Nfa<Integer >(this.interval);
61
62     }
63
64     @Test
65     public void testNfa() {
66
67         assertTrue("the first state should be startState", this.nfa.getStates()
68                 .first() == this.nfa.getStartState());
69         assertTrue("the last state should be an acceptation state", this.nfa
70                 .getStates().last() == this.nfa.getAcceptState());
71         assertTrue("there should only be two states", this.nfa.getStates()
72                 .size() == 2);
73
74     }
75
76     @Test
77     public void testNfaIntervalOfT() {
78
79         // Case with null interval
80 Interval<Integer > nullInterval = null;
81         try {
82             this.nfa = new Nfa<Integer >(nullInterval);
83             fail("inteval may not be null");
84         }
85         catch (InternalException e) {
86             // Expected
87 }
88
89         // Typical case
90
91         NfaState<Integer > expectedTarget = this.nfa.getStartState().getTargets(
92                 this.symbol).first();
93         assertTrue(
94                 "the target of the startState with the right symbol should be the acceptionState.",
95                 this.nfa.getAcceptState() == expectedTarget);
96
97     }
98
99     @Test
100     public void testGetStates() {
101
102         // Case with unstable Nfa
103 try {
104             this.unstableNfa.getStates();
105             fail("the Nfa is not stable yet");
106         }
107         catch (InternalException e) {
108             // Expected
109 }
110     }
111
112     @Test
113     public void testGetStartState() {
114
115         // Case with unstable Nfa
116 try {
117             this.unstableNfa.getStartState();
118             fail("the Nfa is not stable yet");
119         }
120         catch (InternalException e) {
121             // Expected
122 }
123
124     }
125
126     @Test
127     public void testGetAcceptState() {
128
129         // Case with unstable Nfa
130 try {
131             this.unstableNfa.getStartState();
132             fail("the Nfa is not stable yet");
133         }
134         catch (InternalException e) {
135             // Expected
136 }
137     }
138
139     @Test
140     public void testStabilize() {
141
142         // Case with already stable Nfa
143 try {
144             this.nfa.stabilize();
145             fail("this Nfa is already stable");
146         }
147         catch (InternalException e) {
148             // Expected
149 }
150
151     }
152
153     @SuppressWarnings ("unused")
154     @Test
155     public void testUnionWith() {
156
157         // Case with null Nfa
158 Nfa<Integer > nullNfa = null;
159         try {
160             this.nfa.unionWith(nullNfa);
161             fail("nfa may not be null");
162         }
163         catch (InternalException e) {
164             // Expected
165 }
166
167         // Case with unstable Nfa
168 try {
169             this.nfa.unionWith(this.unstableNfa);
170             fail("nfa is not stable yet");
171         }
172         catch (InternalException e) {
173             // Expected
174 }
175
176         try {
177             this.unstableNfa.unionWith(this.nfa);
178             fail("this Nfa is not stable yet");
179         }
180         catch (InternalException e) {
181             // Expected
182 }
183
184         // Typical case
185 Interval<Integer > secondInterval = Realms.getInteger().createInterval(
186                 10);
187         Nfa<Integer > secondNfa = new Nfa<Integer >(secondInterval);
188         Nfa<Integer > unionNfa = this.nfa.unionWith(secondNfa);
189         MinimalDfa<Integer > minimalUnion = new MinimalDfa<Integer >(
190                 new Dfa<Integer >(unionNfa));
191
192         Collection <Interval<Integer >> intervals = new LinkedList <Interval<Integer >>();
193         intervals.add(this.interval);
194         intervals.add(secondInterval);
195
196         Symbol<Integer > symbolUnion = new Symbol<Integer >(intervals);
197
198         assertTrue(
199                 "from the startState, the unionSymbol should lead to the acceptionState",
200                 minimalUnion.getStartState().getTarget(symbolUnion) == minimalUnion
201                         .getAcceptStates().first());
202     }
203
204     @Test
205     public void testConcatenateWith() {
206
207         // Case with null Nfa
208 Nfa<Integer > nullNfa = null;
209         try {
210             this.nfa.concatenateWith(nullNfa);
211             fail("nfa may not be null");
212         }
213         catch (InternalException e) {
214             // Expected
215 }
216
217         // Case with unstable Nfa
218 try {
219             this.nfa.concatenateWith(this.unstableNfa);
220             fail("nfa is not stable yet");
221         }
222         catch (InternalException e) {
223             // Expected
224 }
225
226         try {
227             this.unstableNfa.concatenateWith(this.nfa);
228             fail("this Nfa is not stable yet");
229         }
230         catch (InternalException e) {
231             // Expected
232 }
233
234         // Typical case
235 Interval<Integer > secondInterval = Realms.getInteger().createInterval(
236                 10);
237         Symbol<Integer > secondSymbol = new Symbol<Integer >(secondInterval);
238
239         Nfa<Integer > secondNfa = new Nfa<Integer >(secondInterval);
240         Nfa<Integer > concatenateNfa = this.nfa.concatenateWith(secondNfa);
241
242         MinimalDfa<Integer > minimalConcatenate = new MinimalDfa<Integer >(
243                 new Dfa<Integer >(concatenateNfa));
244
245         assertTrue(
246                 "from the startState, the two symbols should lead to the acceptionState",
247                 minimalConcatenate.getStartState().getTarget(this.symbol)
248                         .getTarget(secondSymbol) == minimalConcatenate
249                         .getAcceptStates().first());
250     }
251
252     @Test
253     public void testZeroOrMore() {
254
255         // Case with unstable Nfa
256 try {
257             this.unstableNfa.zeroOrMore();
258             fail("this Nfa is not stable yet");
259         }
260         catch (InternalException e) {
261             // Expected
262 }
263
264         // Typical case
265 this.nfa = this.nfa.zeroOrMore();
266         MinimalDfa<Integer > minimalDfa = new MinimalDfa<Integer >(
267                 new Dfa<Integer >(this.nfa));
268
269         // test with no transition
270 assertTrue(
271                 "from the startState, no transition should lead to an AcceptionState",
272                 minimalDfa.getStartState() == minimalDfa.getAcceptStates()
273                         .first());
274
275         // test with only one transition
276 assertTrue(
277                 "from the startState, one transition of the same symbol should lead to the acceptionState",
278                 minimalDfa.getStartState().getTarget(this.symbol) == minimalDfa
279                         .getAcceptStates().first());
280
281         // test with more than one transition
282 assertTrue(
283                 "from the startState, one or more transition of the same symbol should lead to the acceptionState",
284                 minimalDfa.getStartState().getTarget(this.symbol).getTarget(
285                         this.symbol) == minimalDfa.getAcceptStates().first());
286     }
287
288     @Test
289     public void testZeroOrOne() {
290
291         // Case with unstable Nfa
292 try {
293             this.unstableNfa.zeroOrOne();
294             fail("this Nfa is not stable yet");
295         }
296         catch (InternalException e) {
297             // Expected
298 }
299
300         this.nfa = this.nfa.zeroOrOne();
301         MinimalDfa<Integer > minimalDfa = new MinimalDfa<Integer >(
302                 new Dfa<Integer >(this.nfa));
303
304         // test with no transition
305 assertTrue(
306                 "from the startState, no transition should lead to an AcceptionState",
307                 minimalDfa.getStartState() == minimalDfa.getAcceptStates()
308                         .first());
309
310         // test with only one transition
311 assertTrue(
312                 "from the startState, one transition of the same symbol should lead to the acceptionState",
313                 minimalDfa.getStartState().getTarget(this.symbol) == minimalDfa
314                         .getAcceptStates().last());
315
316         // test with more than one transition
317 assertFalse(
318                 "from the startState, one or more transition of the same symbol should not lead to the acceptionState",
319                 minimalDfa.getStartState().getTarget(this.symbol).getTarget(
320                         this.symbol) == minimalDfa.getAcceptStates().first());
321     }
322
323     @Test
324     public void testOneOrMore() {
325
326         this.nfa = this.nfa.oneOrMore();
327
328         MinimalDfa<Integer > minimalDfa = new MinimalDfa<Integer >(
329                 new Dfa<Integer >(this.nfa));
330
331         // test with no transition
332 assertFalse(
333                 "from the startState, no transition should not lead to an AcceptionState",
334                 minimalDfa.getStartState() == minimalDfa.getAcceptStates()
335                         .first());
336
337         // test with only one transition
338 assertTrue(
339                 "from the startState, one transition of the same symbol should lead to the acceptionState",
340                 minimalDfa.getStartState().getTarget(this.symbol) == minimalDfa
341                         .getAcceptStates().first());
342
343         // test with more than one transition
344 assertTrue(
345                 "from the startState, one or more transition of the same symbol should lead to the acceptionState",
346                 minimalDfa.getStartState().getTarget(this.symbol).getTarget(
347                         this.symbol) == minimalDfa.getAcceptStates().first());
348     }
349
350     @Test
351     public void testSimpleExponent() {
352
353         // Case with unstable Nfa
354 try {
355             this.unstableNfa.simpleExponent(2);
356             fail("this Nfa is not stable yet");
357         }
358         catch (InternalException e) {
359             // Expected
360 }
361
362         // Case with wrong exponent
363 try {
364             this.nfa.simpleExponent(-5);
365             fail("exponent my be greater or equal to zero");
366         }
367         catch (InternalException e) {
368             // Expected
369 }
370     }
371
372     @Test
373     public void testRangeExponent() {
374
375         // Case with unstable Nfa
376 try {
377             this.unstableNfa.rangeExponent(2, 5);
378             fail("this Nfa is not stable yet");
379         }
380         catch (InternalException e) {
381             // Expected
382 }
383
384         // Case with wrong exponents
385 try {
386             this.nfa.rangeExponent(-5, 10);
387             fail("exponent my be greater or equal to zero");
388         }
389         catch (InternalException e) {
390             // Expected
391 }
392
393         try {
394             this.nfa.rangeExponent(10, -6);
395             fail("exponent my be greater or equal to zero");
396         }
397         catch (InternalException e) {
398             // Expected
399 }
400
401         try {
402             this.nfa.rangeExponent(10, 2);
403             fail("upperBound must be greater or equal to lowerBound");
404         }
405         catch (InternalException e) {
406             // Expected
407 }
408
409     }
410
411     @Test
412     public void testAtLeastExponent() {
413
414         // Case with unstable Nfa
415 try {
416             this.unstableNfa.atLeastExponent(2);
417             fail("this Nfa is not stable yet");
418         }
419         catch (InternalException e) {
420             // Expected
421 }
422
423         // Case with wrong exponent
424 try {
425             this.nfa.atLeastExponent(-5);
426             fail("exponent my be greater or equal to zero");
427         }
428         catch (InternalException e) {
429             // Expected
430 }
431
432     }
433
434     @Test
435     public void testShortest() {
436
437         // Case with null nfa
438 Nfa<Integer > nullNfa = null;
439         try {
440             Dfa.shortest(nullNfa);
441             fail("the nfa cannot be null");
442         }
443         catch (InternalException e) {
444             // Expected
445 }
446
447         Dfa<Integer > dfa = new Nfa<Integer >(Realms.getInteger().createInterval(
448                 10)).oneOrMore().shortest();
449
450         // Check that accept states have no outgoing transitions
451 for (DfaState<Integer > state : dfa.getAcceptStates()) {
452             assertTrue(state.getTransitions().entrySet().size() == 0);
453         }
454     }
455
456     @Test
457     public void testSubtract() {
458
459         // Case with null nfa
460 Nfa<Integer > nullNfa = null;
461         try {
462             this.nfa.subtract(nullNfa);
463             fail("the nfa cannot be null");
464         }
465         catch (InternalException e) {
466             // Expected
467 }
468
469         // Typical case
470 Dfa<Integer > dfa = new Dfa<Integer >(this.nfa);
471         Symbol<Integer > subtractSymbol = new Symbol<Integer >(Realms
472                 .getInteger().createInterval(10));
473         Nfa<Integer > secondNfa = new Nfa<Integer >(Realms.getInteger()
474                 .createInterval(10));
475
476         dfa = this.nfa.subtract(secondNfa);
477
478         // test with the symbol of the substacted nfa
479 assertFalse(
480                 "a transition to a state using a substracted symbol should not lead to the acceptationState.",
481                 dfa.getStartState().getTarget(subtractSymbol) == dfa
482                         .getAcceptStates().first());
483
484         // test with the correct symbol
485 assertTrue(
486                 "a transition to a state using a good symbol should lead to the acceptationState.",
487                 dfa.getStartState().getTarget(this.symbol) == dfa
488                         .getAcceptStates().first());
489     }
490
491     @Test
492     public void testIntersect() {
493
494         // Case with null nfa
495 Nfa<Integer > nullNfa = null;
496         try {
497             this.nfa.intersect(nullNfa);
498             fail("the nfa cannot be null");
499         }
500         catch (InternalException e) {
501             // Expected
502 }
503
504         Dfa<Integer > dfa = new Dfa<Integer >(this.nfa);
505         Nfa<Integer > secondNfa = new Nfa<Integer >(Realms.getInteger()
506                 .createInterval(0, 100));
507
508         dfa = this.nfa.intersect(secondNfa);
509
510         // test with the symbol of the intersecting nfa
511 assertTrue(
512                 "a transition to a state using the intersecting symbol should lead to the acceptationState.",
513                 dfa.getStartState().getTarget(this.symbol) == dfa
514                         .getAcceptStates().first());
515     }
516
517     @Test
518     public void testCombineWith() {
519
520         // Case with null nfa
521 Nfa<Integer > nullNfa = null;
522         try {
523             this.nfa.combineWith(nullNfa);
524             fail("nfa may not be null");
525         }
526         catch (InternalException e) {
527             // Expected
528 }
529
530         // Case with unstable nfa
531 try {
532             this.nfa.combineWith(this.unstableNfa);
533             fail("nfa is not stable yet");
534         }
535         catch (InternalException e) {
536             // Expected
537 }
538
539         try {
540             this.unstableNfa.combineWith(this.nfa);
541             fail("this Nfa is not stable yet");
542         }
543         catch (InternalException e) {
544             // Expected
545 }
546         Symbol<Integer > secondSymbol = new Symbol<Integer >(Realms.getInteger()
547                 .createInterval(10));
548         Nfa<Integer > secondNfa = new Nfa<Integer >(Realms.getInteger()
549                 .createInterval(10));
550
551         NfaCombineResult<Integer > combinedResult = this.nfa
552                 .combineWith(secondNfa);
553
554         Nfa<Integer > combinedNfa = combinedResult.getNewNfa();
555
556         combinedNfa.stabilize();
557         SortedSet <Symbol<Integer >> symbols = combinedNfa.getAlphabet()
558                 .getSymbols();
559
560         assertTrue(
561                 "the merging of the two alphabets should contains the two symbols",
562                 symbols.contains(this.symbol) == true
563                         && symbols.contains(secondSymbol));
564     }
565
566     @Test
567     public void testGetNextStateId() {
568
569         // Case with already stable nfa
570 try {
571             this.nfa.getNextStateId();
572             fail("a stable Nfa may not be modified");
573         }
574         catch (InternalException e) {
575             // Expected
576 }
577
578     }
579
580     @Test
581     public void testAddState() {
582
583         NfaState<Integer > newState = new NfaState<Integer >(this.unstableNfa);
584         newState.stabilize();
585
586         // Case with already stable nfa
587 try {
588             this.nfa.addState(newState);
589             fail("a stable Nfa may not be modified");
590         }
591         catch (InternalException e) {
592             // Expected
593 }
594
595         // Case with a state already in stateSet
596 try {
597             this.unstableNfa.addState(newState);
598             fail("state is already in state set");
599         }
600         catch (InternalException e) {
601             // Expected
602 }
603     }
604 }
605

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags