KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > percederberg > grammatica > parser > TestRecursiveDescentParser


1 /*
2  * TestRecursiveDescentParser.java
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public License
6  * as published by the Free Software Foundation; either version 2.1
7  * of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free
16  * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
17  * MA 02111-1307, USA.
18  *
19  * Copyright (c) 2003-2005 Per Cederberg. All rights reserved.
20  */
21
22 package net.percederberg.grammatica.parser;
23
24 import junit.framework.TestCase;
25
26 /**
27  * A test case for the RecursiveDescentParser class.
28  *
29  * @author Per Cederberg, <per at percederberg dot net>
30  * @version 1.0
31  */
32 public class TestRecursiveDescentParser extends TestCase {
33
34     /**
35      * A token constant.
36      */
37     private static final int T1 = 1001;
38
39     /**
40      * A token constant.
41      */
42     private static final int T2 = 1002;
43
44     /**
45      * A token constant.
46      */
47     private static final int T3 = 1003;
48
49     /**
50      * A production constant.
51      */
52     private static final int P1 = 2001;
53
54     /**
55      * A production constant.
56      */
57     private static final int P2 = 2002;
58
59     /**
60      * A production constant.
61      */
62     private static final int P3 = 2003;
63
64     /**
65      * The production pattern variable used in all tests.
66      */
67     private ProductionPattern pattern;
68
69     /**
70      * The production pattern alternative variable used in all tests.
71      */
72     private ProductionPatternAlternative alt;
73
74     /**
75      * Tests adding an empty pattern to the parser.
76      */
77     public void testEmptyPattern() {
78         pattern = new ProductionPattern(P1, "P1");
79         alt = new ProductionPatternAlternative();
80         addAlternative(pattern, alt);
81         failAddPattern(createParser(), pattern);
82     }
83
84     /**
85      * Tests adding a possible empty pattern to the parser.
86      */
87     public void testPossiblyEmptyPattern() {
88         pattern = new ProductionPattern(P1, "P1");
89         alt = new ProductionPatternAlternative();
90         alt.addToken(T1, 1, 1);
91         addAlternative(pattern, alt);
92         alt = new ProductionPatternAlternative();
93         alt.addToken(T2, 0, 1);
94         addAlternative(pattern, alt);
95         failAddPattern(createParser(), pattern);
96     }
97
98     /**
99      * Tests adding a left-recursive pattern to the parser.
100      */
101     public void testLeftRecursivePattern() {
102         pattern = new ProductionPattern(P1, "P1");
103         alt = new ProductionPatternAlternative();
104         alt.addProduction(P1, 0, 1);
105         alt.addToken(T1, 1, 1);
106         addAlternative(pattern, alt);
107         failAddPattern(createParser(), pattern);
108     }
109
110     /**
111      * Tests adding a right-recursive pattern to the parser.
112      */
113     public void testRightRecursivePattern() {
114         pattern = new ProductionPattern(P1, "P1");
115         alt = new ProductionPatternAlternative();
116         alt.addToken(T1, 1, 1);
117         alt.addProduction(P1, 0, 1);
118         addAlternative(pattern, alt);
119         addPattern(createParser(), pattern);
120     }
121
122     /**
123      * Tests adding the same pattern twice.
124      */
125     public void testDuplicatePattern() {
126         Parser parser = createParser();
127
128         pattern = new ProductionPattern(P1, "P1");
129         alt = new ProductionPatternAlternative();
130         alt.addToken(T1, 1, 1);
131         addAlternative(pattern, alt);
132         addPattern(parser, pattern);
133         failAddPattern(parser, pattern);
134     }
135
136     /**
137      * Tests adding two patterns with the same id.
138      */
139     public void testPatternCollision() {
140         Parser parser = createParser();
141
142         pattern = new ProductionPattern(P1, "P1");
143         alt = new ProductionPatternAlternative();
144         alt.addToken(T1, 1, 1);
145         addAlternative(pattern, alt);
146         addPattern(parser, pattern);
147
148         pattern = new ProductionPattern(P1, "P2");
149         alt = new ProductionPatternAlternative();
150         alt.addToken(T2, 1, 1);
151         addAlternative(pattern, alt);
152         failAddPattern(parser, pattern);
153     }
154
155     /**
156      * Tests adding two patterns with the same alternatives.
157      */
158     public void testIdenticalPatterns() {
159         Parser parser = createParser();
160
161         pattern = new ProductionPattern(P1, "P1");
162         alt = new ProductionPatternAlternative();
163         alt.addToken(T1, 1, 1);
164         addAlternative(pattern, alt);
165         addPattern(parser, pattern);
166
167         pattern = new ProductionPattern(P2, "P2");
168         alt = new ProductionPatternAlternative();
169         alt.addToken(T1, 1, 1);
170         addAlternative(pattern, alt);
171         addPattern(parser, pattern);
172     }
173
174     /**
175      * Tests a simple grammar loop.
176      */
177     public void testSimpleGrammarLoop() {
178         Parser parser = createParser();
179
180         pattern = new ProductionPattern(P1, "P1");
181         alt = new ProductionPatternAlternative();
182         alt.addProduction(P2, 1, 1);
183         addAlternative(pattern, alt);
184         addPattern(parser, pattern);
185
186         pattern = new ProductionPattern(P2, "P2");
187         alt = new ProductionPatternAlternative();
188         alt.addProduction(P1, 1, 1);
189         addAlternative(pattern, alt);
190         addPattern(parser, pattern);
191
192         failPrepareParser(parser);
193     }
194
195     /**
196      * Tests a complex grammar loop with optional parts and
197      * alternatives.
198      */
199     public void testComplexGrammarLoop() {
200         Parser parser = createParser();
201
202         pattern = new ProductionPattern(P1, "P1");
203         alt = new ProductionPatternAlternative();
204         alt.addProduction(P2, 1, 1);
205         addAlternative(pattern, alt);
206         addPattern(parser, pattern);
207
208         pattern = new ProductionPattern(P2, "P2");
209         alt = new ProductionPatternAlternative();
210         alt.addProduction(P3, 0, 1);
211         alt.addToken(T1, 1, 1);
212         addAlternative(pattern, alt);
213         addPattern(parser, pattern);
214
215         pattern = new ProductionPattern(P3, "P3");
216         alt = new ProductionPatternAlternative();
217         alt.addToken(T3, 1, 1);
218         addAlternative(pattern, alt);
219         alt = new ProductionPatternAlternative();
220         alt.addProduction(P1, 0, 1);
221         alt.addToken(T2, 1, 1);
222         addAlternative(pattern, alt);
223         addPattern(parser, pattern);
224
225         failPrepareParser(parser);
226     }
227
228     /**
229      * Tests an unresolvable conflict between two productions.
230      */
231     public void testProductionConflict() {
232         Parser parser = createParser();
233
234         pattern = new ProductionPattern(P1, "P1");
235         alt = new ProductionPatternAlternative();
236         alt.addProduction(P2, 1, 1);
237         addAlternative(pattern, alt);
238         alt = new ProductionPatternAlternative();
239         alt.addProduction(P3, 1, 1);
240         addAlternative(pattern, alt);
241         addPattern(parser, pattern);
242
243         pattern = new ProductionPattern(P2, "P2");
244         alt = new ProductionPatternAlternative();
245         alt.addToken(T1, 0, -1);
246         alt.addToken(T2, 1, 1);
247         addAlternative(pattern, alt);
248         addPattern(parser, pattern);
249
250         pattern = new ProductionPattern(P3, "P3");
251         alt = new ProductionPatternAlternative();
252         alt.addToken(T1, 1, 1);
253         alt.addProduction(P3, 0, 1);
254         addAlternative(pattern, alt);
255         addPattern(parser, pattern);
256
257         failPrepareParser(parser);
258     }
259
260     /**
261      * Tests an unresolvable conflict between two production
262      * alternatives.
263      */
264     public void testAlternativeConflict() {
265         Parser parser = createParser();
266
267         pattern = new ProductionPattern(P1, "P1");
268         alt = new ProductionPatternAlternative();
269         alt.addToken(T1, 0, -1);
270         alt.addToken(T2, 1, 1);
271         addAlternative(pattern, alt);
272         alt = new ProductionPatternAlternative();
273         alt.addToken(T1, 1, -1);
274         alt.addToken(T3, 1, 1);
275         addAlternative(pattern, alt);
276         addPattern(parser, pattern);
277
278         failPrepareParser(parser);
279     }
280
281     /**
282      * Tests an unresolvable token conflict inside a production
283      * alternative.
284      */
285     public void testElementTokenConflict() {
286         Parser parser = createParser();
287
288         pattern = new ProductionPattern(P1, "P1");
289         alt = new ProductionPatternAlternative();
290         alt.addToken(T1, 0, 1);
291         alt.addToken(T1, 1, -1);
292         addAlternative(pattern, alt);
293         addPattern(parser, pattern);
294
295         failPrepareParser(parser);
296     }
297
298     /**
299      * Tests an unresolvable production conflict inside a production
300      * alternative.
301      */
302     public void testElementProductionConflict() {
303         Parser parser = createParser();
304
305         pattern = new ProductionPattern(P1, "P1");
306         alt = new ProductionPatternAlternative();
307         alt.addProduction(P2, 0, 1);
308         alt.addProduction(P3, 1, 1);
309         alt.addToken(T2, 1, 1);
310         addAlternative(pattern, alt);
311         addPattern(parser, pattern);
312
313         pattern = new ProductionPattern(P2, "P2");
314         alt = new ProductionPatternAlternative();
315         alt.addToken(T1, 1, 1);
316         alt.addProduction(P2, 0, 1);
317         addAlternative(pattern, alt);
318         addPattern(parser, pattern);
319
320         pattern = new ProductionPattern(P3, "P3");
321         alt = new ProductionPatternAlternative();
322         addAlternative(pattern, alt);
323         alt.addToken(T1, 1, -1);
324         addPattern(parser, pattern);
325
326         failPrepareParser(parser);
327     }
328
329     /**
330      * Tests an unresolvable production conflict in the tail of a
331      * production alternative.
332      */
333     public void testElementTailConflict() {
334         Parser parser = createParser();
335
336         pattern = new ProductionPattern(P1, "P1");
337         alt = new ProductionPatternAlternative();
338         alt.addProduction(P2, 1, 1);
339         alt.addToken(T2, 0, 1);
340         addAlternative(pattern, alt);
341         addPattern(parser, pattern);
342
343         pattern = new ProductionPattern(P2, "P2");
344         alt = new ProductionPatternAlternative();
345         alt.addToken(T1, 1, 1);
346         alt.addToken(T2, 0, 1);
347         addAlternative(pattern, alt);
348         addPattern(parser, pattern);
349
350         // TODO: enable this test
351 // failPrepareParser(parser);
352 }
353
354     /**
355      * Tests a resolvable conflict between two production patterns.
356      */
357     public void testResolvableProductionConflict() {
358         Parser parser = createParser();
359
360         pattern = new ProductionPattern(P1, "P1");
361         alt = new ProductionPatternAlternative();
362         alt.addProduction(P2, 1, 1);
363         addAlternative(pattern, alt);
364         alt = new ProductionPatternAlternative();
365         alt.addProduction(P3, 1, 1);
366         addAlternative(pattern, alt);
367         addPattern(parser, pattern);
368
369         pattern = new ProductionPattern(P2, "P2");
370         alt = new ProductionPatternAlternative();
371         alt.addToken(T1, 1, 1);
372         alt.addToken(T1, 0, 1);
373         alt.addToken(T2, 1, 1);
374         addAlternative(pattern, alt);
375         addPattern(parser, pattern);
376
377         pattern = new ProductionPattern(P3, "P3");
378         alt = new ProductionPatternAlternative();
379         alt.addToken(T1, 1, -1);
380         alt.addToken(T3, 1, 1);
381         addAlternative(pattern, alt);
382         addPattern(parser, pattern);
383
384         prepareParser(parser);
385     }
386
387     /**
388      * Tests a resolvable conflict between two production
389      * alternatives.
390      */
391     public void testResolvableAlternativeConflict() {
392         Parser parser = createParser();
393
394         pattern = new ProductionPattern(P1, "P1");
395         alt = new ProductionPatternAlternative();
396         alt.addToken(T1, 1, 1);
397         alt.addToken(T1, 0, 1);
398         alt.addToken(T2, 1, 1);
399         addAlternative(pattern, alt);
400         alt = new ProductionPatternAlternative();
401         alt.addToken(T1, 1, -1);
402         alt.addToken(T3, 1, 1);
403         addAlternative(pattern, alt);
404         addPattern(parser, pattern);
405
406         prepareParser(parser);
407     }
408
409     /**
410      * Tests a resolvable token conflict inside a production
411      * alternative.
412      */
413     public void testResolvableElementTokenConflict() {
414         Parser parser = createParser();
415
416         pattern = new ProductionPattern(P1, "P1");
417         alt = new ProductionPatternAlternative();
418         alt.addToken(T1, 0, 1);
419         alt.addToken(T1, 1, 1);
420         alt.addToken(T2, 1, 1);
421         addAlternative(pattern, alt);
422         addPattern(parser, pattern);
423
424         prepareParser(parser);
425     }
426
427     /**
428      * Tests a resolvable production conflict inside a production
429      * alternative.
430      */
431     public void testResolvableElementProductionConflict() {
432         Parser parser = createParser();
433
434         pattern = new ProductionPattern(P1, "P1");
435         alt = new ProductionPatternAlternative();
436         alt.addProduction(P2, 0, 1);
437         alt.addToken(T1, 1, -1);
438         addAlternative(pattern, alt);
439         addPattern(parser, pattern);
440
441         pattern = new ProductionPattern(P2, "P2");
442         alt = new ProductionPatternAlternative();
443         alt.addToken(T1, 1, 1);
444         alt.addToken(T2, 1, 1);
445         addAlternative(pattern, alt);
446         addPattern(parser, pattern);
447
448         prepareParser(parser);
449     }
450
451     /**
452      * Tests a resolvable production conflict in the tail of a
453      * production alternative.
454      */
455     public void testResolvableElementTailConflict() {
456         Parser parser = createParser();
457
458         pattern = new ProductionPattern(P1, "P1");
459         alt = new ProductionPatternAlternative();
460         alt.addProduction(P2, 1, 1);
461         alt.addToken(T2, 1, 1);
462         addAlternative(pattern, alt);
463         addPattern(parser, pattern);
464
465         pattern = new ProductionPattern(P2, "P2");
466         alt = new ProductionPatternAlternative();
467         alt.addToken(T1, 1, 1);
468         alt.addToken(T2, 0, 1);
469         addAlternative(pattern, alt);
470         addPattern(parser, pattern);
471
472         prepareParser(parser);
473     }
474
475     /**
476      * Creates a new parser.
477      *
478      * @return a new parser
479      */
480     private Parser createParser() {
481         return new RecursiveDescentParser(null);
482     }
483
484     /**
485      * Prepares the parser and reports a test failure if it failed.
486      *
487      * @param parser the parser to prepare
488      */
489     private void prepareParser(Parser parser) {
490         try {
491             parser.prepare();
492         } catch (ParserCreationException e) {
493             fail(e.getMessage());
494         }
495     }
496
497     /**
498      * Prepares the parser and reports a test failure if it succeeded.
499      *
500      * @param parser the parser to prepare
501      */
502     private void failPrepareParser(Parser parser) {
503         try {
504             parser.prepare();
505             fail();
506         } catch (ParserCreationException e) {
507             // Failure was expected
508 }
509     }
510
511     /**
512      * Adds a production pattern to a parser and reports a test
513      * failure if it failed.
514      *
515      * @param parser the parser to add a pattern to
516      * @param pattern the production pattern to add
517      */
518     private void addPattern(Parser parser, ProductionPattern pattern) {
519         try {
520             parser.addPattern(pattern);
521         } catch (ParserCreationException e) {
522             fail("couldn't add pattern " + pattern.getName() + ": " +
523                  e.getMessage());
524         }
525     }
526
527     /**
528      * Adds a production pattern to a parser and reports a test
529      * failure if it succeeded.
530      *
531      * @param parser the parser to add a pattern to
532      * @param pattern the production pattern to add
533      */
534     private void failAddPattern(Parser parser, ProductionPattern pattern) {
535         try {
536             parser.addPattern(pattern);
537             fail("could add pattern " + pattern.getName());
538         } catch (ParserCreationException e) {
539             // Failure was expected
540 }
541     }
542
543     /**
544      * Adds a pattern alternative. This method reports a test failure
545      * if an exception was thrown.
546      *
547      * @param pattern the production pattern
548      * @param alt the pattern alternative to add
549      */
550     private void addAlternative(ProductionPattern pattern,
551                                 ProductionPatternAlternative alt) {
552
553         try {
554             pattern.addAlternative(alt);
555         } catch (ParserCreationException e) {
556             fail("couldn't add alternative to " + pattern.getName() +
557                  ": " + e.getMessage());
558         }
559     }
560 }
561
Popular Tags