RecursiveDescentParser


1   /*
2    * RecursiveDescentParser.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 java.util.ArrayList  ;
25  import java.util.Iterator  ;
26  
27  /**
28   * A recursive descent parser. This parser handles LL(n) grammars,
29   * selecting the appropriate pattern to parse based on the next few
30   * tokens. The parser is more efficient the fewer look-ahead tokens
31   * that is has to consider.
32   *
33   * @author   Per Cederberg, <per at percederberg dot net>
34   * @version  1.5
35   */
36  public class RecursiveDescentParser extends Parser {
37  
38      /**
39       * Creates a new parser.
40       *
41       * @param tokenizer      the tokenizer to use
42       */
43      public RecursiveDescentParser(Tokenizer tokenizer) {
44          super(tokenizer);
45      }
46  
47      /**
48       * Creates a new parser.
49       *
50       * @param tokenizer      the tokenizer to use
51       * @param analyzer       the analyzer callback to use
52       */
53      public RecursiveDescentParser(Tokenizer tokenizer, Analyzer analyzer) {
54          super(tokenizer, analyzer);
55      }
56  
57      /**
58       * Adds a new production pattern to the parser. The pattern will
59       * be added last in the list. The first pattern added is assumed
60       * to be the starting point in the grammar. The pattern will be
61       * validated against the grammar type to some extent.
62       *
63       * @param pattern        the pattern to add
64       *
65       * @throws ParserCreationException if the pattern couldn't be
66       *             added correctly to the parser
67       */
68      public void addPattern(ProductionPattern pattern)
69          throws ParserCreationException {
70  
71          // Check for empty matches
72          if (pattern.isMatchingEmpty()) {
73              throw new ParserCreationException(
74                  ParserCreationException.INVALID_PRODUCTION_ERROR,
75                  pattern.getName(),
76                  "zero elements can be matched (minimum is one)");
77          }
78  
79          // Check for left-recusive patterns
80          if (pattern.isLeftRecursive()) {
81              throw new ParserCreationException(
82                  ParserCreationException.INVALID_PRODUCTION_ERROR,
83                  pattern.getName(),
84                  "left recursive patterns are not allowed");
85          }
86  
87          // Add pattern
88          super.addPattern(pattern);
89      }
90  
91      /**
92       * Initializes the parser. All the added production patterns will
93       * be analyzed for ambiguities and errors. This method also
94       * initializes the internal data structures used during the
95       * parsing.
96       *
97       * @throws ParserCreationException if the parser couldn't be
98       *             initialized correctly
99       */
100     public void prepare() throws ParserCreationException {
101         Iterator    iter;
102 
103         // Performs production pattern checks
104         super.prepare();
105         setInitialized(false);
106 
107         // Calculate production look-ahead sets
108         iter = getPatterns().iterator();
109         while (iter.hasNext()) {
110             calculateLookAhead((ProductionPattern) iter.next());
111         }
112 
113         // Set initialized flag
114         setInitialized(true);
115     }
116 
117     /**
118      * Parses the input stream and creates a parse tree.
119      *
120      * @return the parse tree
121      *
122      * @throws ParseException if the input couldn't be parsed
123      *             correctly
124      */
125     protected Node parseStart() throws ParseException {
126         Token      token;
127         Node       node;
128         ArrayList    list;
129 
130         node = parsePattern(getStartPattern());
131         token = peekToken(0);
132         if (token != null) {
133             list = new ArrayList  (1);
134             list.add("<EOF>");
135             throw new ParseException(
136                 ParseException.UNEXPECTED_TOKEN_ERROR,
137                 token.toShortString(),
138                 list,
139                 token.getStartLine(),
140                 token.getStartColumn());
141         }
142         return node;
143     }
144 
145     /**
146      * Parses a production pattern. A parse tree node may or may not
147      * be created depending on the analyzer callbacks.
148      *
149      * @param pattern        the production pattern to parse
150      *
151      * @return the parse tree node created, or null
152      *
153      * @throws ParseException if the input couldn't be parsed
154      *             correctly
155      */
156     private Node parsePattern(ProductionPattern pattern)
157         throws ParseException {
158 
159         ProductionPatternAlternative  alt;
160         ProductionPatternAlternative  defaultAlt;
161 
162         defaultAlt = pattern.getDefaultAlternative();
163         for (int i = 0; i < pattern.getAlternativeCount(); i++) {
164             alt = pattern.getAlternative(i);
165             if (defaultAlt != alt && isNext(alt)) {
166                 return parseAlternative(alt);
167             }
168         }
169         if (defaultAlt == null || !isNext(defaultAlt)) {
170             throwParseException(findUnion(pattern));
171         }
172         return parseAlternative(defaultAlt);
173     }
174 
175     /**
176      * Parses a production pattern alternative. A parse tree node may
177      * or may not be created depending on the analyzer callbacks.
178      *
179      * @param alt            the production pattern alternative
180      *
181      * @return the parse tree node created, or null
182      *
183      * @throws ParseException if the input couldn't be parsed
184      *             correctly
185      */
186     private Node parseAlternative(ProductionPatternAlternative alt)
187         throws ParseException {
188 
189         Production  node;
190 
191         node = new Production(alt.getPattern());
192         enterNode(node);
193         for (int i = 0; i < alt.getElementCount(); i++) {
194             try {
195                 parseElement(node, alt.getElement(i));
196             } catch (ParseException e) {
197                 addError(e, true);
198                 nextToken();
199                 i--;
200             }
201         }
202         return exitNode(node);
203     }
204 
205     /**
206      * Parses a production pattern element. All nodes parsed may or
207      * may not be added to the parse tree node specified, depending
208      * on the analyzer callbacks.
209      *
210      * @param node           the production parse tree node
211      * @param elem           the production pattern element to parse
212      *
213      * @throws ParseException if the input couldn't be parsed
214      *             correctly
215      */
216     private void parseElement(Production node,
217                               ProductionPatternElement elem)
218         throws ParseException {
219 
220         Node  child;
221 
222         for (int i = 0; i < elem.getMaxCount(); i++) {
223             if (i < elem.getMinCount() || isNext(elem)) {
224                 if (elem.isToken()) {
225                     child = nextToken(elem.getId());
226                     enterNode(child);
227                     addNode(node, exitNode(child));
228                 } else {
229                     child = parsePattern(getPattern(elem.getId()));
230                     addNode(node, child);
231                 }
232             } else {
233                 break;
234             }
235         }
236     }
237 
238     /**
239      * Checks if the next tokens match a production pattern. The
240      * pattern look-ahead set will be used if existing, otherwise
241      * this method returns false.
242      *
243      * @param pattern        the pattern to check
244      *
245      * @return true if the next tokens match, or
246      *         false otherwise
247      */
248     private boolean isNext(ProductionPattern pattern) {
249         LookAheadSet  set = pattern.getLookAhead();
250 
251         if (set == null) {
252             return false;
253         } else {
254             return set.isNext(this);
255         }
256     }
257 
258     /**
259      * Checks if the next tokens match a production pattern
260      * alternative. The pattern alternative look-ahead set will be
261      * used if existing, otherwise this method returns false.
262      *
263      * @param alt            the pattern alternative to check
264      *
265      * @return true if the next tokens match, or
266      *         false otherwise
267      */
268     private boolean isNext(ProductionPatternAlternative alt) {
269         LookAheadSet  set = alt.getLookAhead();
270 
271         if (set == null) {
272             return false;
273         } else {
274             return set.isNext(this);
275         }
276     }
277 
278     /**
279      * Checks if the next tokens match a production pattern element.
280      * If the element has a look-ahead set it will be used, otherwise
281      * the look-ahead set of the referenced production or token will
282      * be used.
283      *
284      * @param elem           the pattern element to check
285      *
286      * @return true if the next tokens match, or
287      *         false otherwise
288      */
289     private boolean isNext(ProductionPatternElement elem) {
290         LookAheadSet  set = elem.getLookAhead();
291 
292         if (set != null) {
293             return set.isNext(this);
294         } else if (elem.isToken()) {
295             return elem.isMatch(peekToken(0));
296         } else {
297             return isNext(getPattern(elem.getId()));
298         }
299     }
300 
301     /**
302      * Calculates the look-ahead needed for the specified production
303      * pattern. This method attempts to resolve any conflicts and
304      * stores the results in the pattern look-ahead object.
305      *
306      * @param pattern        the production pattern
307      *
308      * @throws ParserCreationException if the look-ahead set couldn't
309      *             be determined due to inherent ambiguities
310      */
311     private void calculateLookAhead(ProductionPattern pattern)
312         throws ParserCreationException {
313 
314         ProductionPatternAlternative  alt;
315         LookAheadSet                  result;
316         LookAheadSet[]                alternatives;
317         LookAheadSet                  conflicts;
318         LookAheadSet                  previous = new LookAheadSet(0);
319         int                           length = 1;
320         int                           i;
321         CallStack                     stack = new CallStack();
322 
323         // Calculate simple look-ahead
324         stack.push(pattern.getName(), 1);
325         result = new LookAheadSet(1);
326         alternatives = new LookAheadSet[pattern.getAlternativeCount()];
327         for (i = 0; i < pattern.getAlternativeCount(); i++) {
328             alt = pattern.getAlternative(i);
329             alternatives[i] = findLookAhead(alt, 1, 0, stack, null);
330             alt.setLookAhead(alternatives[i]);
331             result.addAll(alternatives[i]);
332         }
333         if (pattern.getLookAhead() == null) {
334             pattern.setLookAhead(result);
335         }
336         conflicts = findConflicts(pattern, 1);
337 
338         // Resolve conflicts
339         while (!conflicts.isEmpty()) {
340             length++;
341             stack.clear();
342             stack.push(pattern.getName(), length);
343             conflicts.addAll(previous);
344             for (i = 0; i < pattern.getAlternativeCount(); i++) {
345                 alt = pattern.getAlternative(i);
346                 if (alternatives[i].hasIntersection(conflicts)) {
347                     alternatives[i] = findLookAhead(alt,
348                                                     length,
349                                                     0,
350                                                     stack,
351                                                     conflicts);
352                     alt.setLookAhead(alternatives[i]);
353                 }
354                 if (alternatives[i].hasIntersection(conflicts)) {
355                     if (pattern.getDefaultAlternative() == null) {
356                         pattern.setDefaultAlternative(i);
357                     } else if (pattern.getDefaultAlternative() != alt) {
358                         result = alternatives[i].createIntersection(conflicts);
359                         throwAmbiguityException(pattern.getName(),
360                                                 null,
361                                                 result);
362                     }
363                 }
364             }
365             previous = conflicts;
366             conflicts = findConflicts(pattern, length);
367         }
368 
369         // Resolve conflicts inside rules
370         for (i = 0; i < pattern.getAlternativeCount(); i++) {
371             calculateLookAhead(pattern.getAlternative(i), 0);
372         }
373     }
374 
375     /**
376      * Calculates the look-aheads needed for the specified pattern
377      * alternative. This method attempts to resolve any conflicts in
378      * optional elements by recalculating look-aheads for referenced
379      * productions.
380      *
381      * @param alt            the production pattern alternative
382      * @param pos            the pattern element position
383      *
384      * @throws ParserCreationException if the look-ahead set couldn't
385      *             be determined due to inherent ambiguities
386      */
387     private void calculateLookAhead(ProductionPatternAlternative alt,
388                                     int pos)
389         throws ParserCreationException {
390 
391         ProductionPattern         pattern;
392         ProductionPatternElement  elem;
393         LookAheadSet              first;
394         LookAheadSet              follow;
395         LookAheadSet              conflicts;
396         LookAheadSet              previous = new LookAheadSet(0);
397         String                      location;
398         int                       length = 1;
399 
400         // Check trivial cases
401         if (pos >= alt.getElementCount()) {
402             return;
403         }
404 
405         // Check for non-optional element
406         pattern = alt.getPattern();
407         elem = alt.getElement(pos);
408         if (elem.getMinCount() == elem.getMaxCount()) {
409             calculateLookAhead(alt, pos + 1);
410             return;
411         }
412 
413         // Calculate simple look-aheads
414         first = findLookAhead(elem, 1, new CallStack(), null);
415         follow = findLookAhead(alt, 1, pos + 1, new CallStack(), null);
416 
417         // Resolve conflicts
418         location = "at position " + (pos + 1);
419         conflicts = findConflicts(pattern.getName(),
420                                   location,
421                                   first,
422                                   follow);
423         while (!conflicts.isEmpty()) {
424             length++;
425             conflicts.addAll(previous);
426             first = findLookAhead(elem,
427                                   length,
428                                   new CallStack(),
429                                   conflicts);
430             follow = findLookAhead(alt,
431                                    length,
432                                    pos + 1,
433                                    new CallStack(),
434                                    conflicts);
435             first = first.createCombination(follow);
436             elem.setLookAhead(first);
437             if (first.hasIntersection(conflicts)) {
438                 first = first.createIntersection(conflicts);
439                 throwAmbiguityException(pattern.getName(), location, first);
440             }
441             previous = conflicts;
442             conflicts = findConflicts(pattern.getName(),
443                                       location,
444                                       first,
445                                       follow);
446         }
447 
448         // Check remaining elements
449         calculateLookAhead(alt, pos + 1);
450     }
451 
452     /**
453      * Finds the look-ahead set for a production pattern. The maximum
454      * look-ahead length must be specified. It is also possible to
455      * specify a look-ahead set filter, which will make sure that
456      * unnecessary token sequences will be avoided.
457      *
458      * @param pattern        the production pattern
459      * @param length         the maximum look-ahead length
460      * @param stack          the call stack used for loop detection
461      * @param filter         the look-ahead set filter
462      *
463      * @return the look-ahead set for the production pattern
464      *
465      * @throws ParserCreationException if an infinite loop was found
466      *             in the grammar
467      */
468     private LookAheadSet findLookAhead(ProductionPattern pattern,
469                                        int length,
470                                        CallStack stack,
471                                        LookAheadSet filter)
472         throws ParserCreationException {
473 
474         LookAheadSet  result;
475         LookAheadSet  temp;
476 
477         // Check for infinite loop
478         if (stack.contains(pattern.getName(), length)) {
479             throw new ParserCreationException(
480                 ParserCreationException.INFINITE_LOOP_ERROR,
481                 pattern.getName(),
482                 (String  ) null);
483         }
484 
485         // Find pattern look-ahead
486         stack.push(pattern.getName(), length);
487         result = new LookAheadSet(length);
488         for (int i = 0; i < pattern.getAlternativeCount(); i++) {
489             temp = findLookAhead(pattern.getAlternative(i),
490                                  length,
491                                  0,
492                                  stack,
493                                  filter);
494             result.addAll(temp);
495         }
496         stack.pop();
497 
498         return result;
499     }
500 
501     /**
502      * Finds the look-ahead set for a production pattern alternative.
503      * The pattern position and maximum look-ahead length must be
504      * specified. It is also possible to specify a look-ahead set
505      * filter, which will make sure that unnecessary token sequences
506      * will be avoided.
507      *
508      * @param alt            the production pattern alternative
509      * @param length         the maximum look-ahead length
510      * @param pos            the pattern element position
511      * @param stack          the call stack used for loop detection
512      * @param filter         the look-ahead set filter
513      *
514      * @return the look-ahead set for the pattern alternative
515      *
516      * @throws ParserCreationException if an infinite loop was found
517      *             in the grammar
518      */
519     private LookAheadSet findLookAhead(ProductionPatternAlternative alt,
520                                        int length,
521                                        int pos,
522                                        CallStack stack,
523                                        LookAheadSet filter)
524         throws ParserCreationException {
525 
526         LookAheadSet  first;
527         LookAheadSet  follow;
528         LookAheadSet  overlaps;
529 
530         // Check trivial cases
531         if (length <= 0 || pos >= alt.getElementCount()) {
532             return new LookAheadSet(0);
533         }
534 
535         // Find look-ahead for this element
536         first = findLookAhead(alt.getElement(pos), length, stack, filter);
537         if (alt.getElement(pos).getMinCount() == 0) {
538             first.addEmpty();
539         }
540 
541         // Find remaining look-ahead
542         if (filter == null) {
543             length -= first.getMinLength();
544             if (length > 0) {
545                 follow = findLookAhead(alt, length, pos + 1, stack, null);
546                 first = first.createCombination(follow);
547             }
548         } else if (filter.hasOverlap(first)) {
549             overlaps = first.createOverlaps(filter);
550             length -= overlaps.getMinLength();
551             filter = filter.createFilter(overlaps);
552             follow = findLookAhead(alt, length, pos + 1, stack, filter);
553             first.removeAll(overlaps);
554             first.addAll(overlaps.createCombination(follow));
555         }
556 
557         return first;
558     }
559 
560     /**
561      * Finds the look-ahead set for a production pattern element. The
562      * maximum look-ahead length must be specified. This method takes
563      * the element repeats into consideration when creating the
564      * look-ahead set, but does NOT include an empty sequence even if
565      * the minimum count is zero (0). It is also possible to specify a
566      * look-ahead set filter, which will make sure that unnecessary
567      * token sequences will be avoided.
568      *
569      * @param elem           the production pattern element
570      * @param length         the maximum look-ahead length
571      * @param stack          the call stack used for loop detection
572      * @param filter         the look-ahead set filter
573      *
574      * @return the look-ahead set for the pattern element
575      *
576      * @throws ParserCreationException if an infinite loop was found
577      *             in the grammar
578      */
579     private LookAheadSet findLookAhead(ProductionPatternElement elem,
580                                        int length,
581                                        CallStack stack,
582                                        LookAheadSet filter)
583         throws ParserCreationException {
584 
585         LookAheadSet  result;
586         LookAheadSet  first;
587         LookAheadSet  follow;
588         int           max;
589 
590         // Find initial element look-ahead
591         first = findLookAhead(elem, length, 0, stack, filter);
592         result = new LookAheadSet(length);
593         result.addAll(first);
594         if (filter == null || !filter.hasOverlap(result)) {
595             return result;
596         }
597 
598         // Handle element repetitions
599         if (elem.getMaxCount() == Integer.MAX_VALUE) {
600             first = first.createRepetitive();
601         }
602         max = Math.min(length, elem.getMaxCount());
603         for (int i = 1; i < max; i++) {
604             first = first.createOverlaps(filter);
605             if (first.isEmpty() || first.getMinLength() >= length) {
606                 break;
607             }
608             follow = findLookAhead(elem,
609                                    length,
610                                    0,
611                                    stack,
612                                    filter.createFilter(first));
613             first = first.createCombination(follow);
614             result.addAll(first);
615         }
616 
617         return result;
618     }
619 
620     /**
621      * Finds the look-ahead set for a production pattern element. The
622      * maximum look-ahead length must be specified. This method does
623      * NOT take the element repeat into consideration when creating
624      * the look-ahead set. It is also possible to specify a look-ahead
625      * set filter, which will make sure that unnecessary token
626      * sequences will be avoided.
627      *
628      * @param elem           the production pattern element
629      * @param length         the maximum look-ahead length
630      * @param dummy          a parameter to distinguish the method
631      * @param stack          the call stack used for loop detection
632      * @param filter         the look-ahead set filter
633      *
634      * @return the look-ahead set for the pattern element
635      *
636      * @throws ParserCreationException if an infinite loop was found
637      *             in the grammar
638      */
639     private LookAheadSet findLookAhead(ProductionPatternElement elem,
640                                        int length,
641                                        int dummy,
642                                        CallStack stack,
643                                        LookAheadSet filter)
644         throws ParserCreationException {
645 
646         LookAheadSet       result;
647         ProductionPattern  pattern;
648 
649         if (elem.isToken()) {
650             result = new LookAheadSet(length);
651             result.add(elem.getId());
652         } else {
653             pattern = getPattern(elem.getId());
654             result = findLookAhead(pattern, length, stack, filter);
655             if (stack.contains(pattern.getName())) {
656                 result = result.createRepetitive();
657             }
658         }
659 
660         return result;
661     }
662 
663     /**
664      * Returns a look-ahead set with all conflics between alternatives
665      * in a production pattern.
666      *
667      * @param pattern        the production pattern
668      * @param maxLength      the maximum token sequence length
669      *
670      * @return a look-ahead set with the conflicts found
671      *
672      * @throws ParserCreationException if an inherent ambiguity was
673      *             found among the look-ahead sets
674      */
675     private LookAheadSet findConflicts(ProductionPattern pattern,
676                                        int maxLength)
677         throws ParserCreationException {
678 
679         LookAheadSet  result = new LookAheadSet(maxLength);
680         LookAheadSet  set1;
681         LookAheadSet  set2;
682 
683         for (int i = 0; i < pattern.getAlternativeCount(); i++) {
684             set1 = pattern.getAlternative(i).getLookAhead();
685             for (int j = 0; j < i; j++) {
686                 set2 = pattern.getAlternative(j).getLookAhead();
687                 result.addAll(set1.createIntersection(set2));
688             }
689         }
690         if (result.isRepetitive()) {
691             throwAmbiguityException(pattern.getName(), null, result);
692         }
693         return result;
694     }
695 
696     /**
697      * Returns a look-ahead set with all conflicts between two
698      * look-ahead sets.
699      *
700      * @param pattern        the pattern name being analyzed
701      * @param location       the pattern location
702      * @param set1           the first look-ahead set
703      * @param set2           the second look-ahead set
704      *
705      * @return a look-ahead set with the conflicts found
706      *
707      * @throws ParserCreationException if an inherent ambiguity was
708      *             found among the look-ahead sets
709      */
710     private LookAheadSet findConflicts(String   pattern,
711                                        String   location,
712                                        LookAheadSet set1,
713                                        LookAheadSet set2)
714         throws ParserCreationException {
715 
716         LookAheadSet  result;
717 
718         result = set1.createIntersection(set2);
719         if (result.isRepetitive()) {
720             throwAmbiguityException(pattern, location, result);
721         }
722         return result;
723     }
724 
725     /**
726      * Returns the union of all alternative look-ahead sets in a
727      * production pattern.
728      *
729      * @param pattern        the production pattern
730      *
731      * @return a unified look-ahead set
732      */
733     private LookAheadSet findUnion(ProductionPattern pattern) {
734         LookAheadSet  result;
735         int           length = 0;
736         int           i;
737 
738         for (i = 0; i < pattern.getAlternativeCount(); i++) {
739             result = pattern.getAlternative(i).getLookAhead();
740             if (result.getMaxLength() > length) {
741                 length = result.getMaxLength();
742             }
743         }
744         result = new LookAheadSet(length);
745         for (i = 0; i < pattern.getAlternativeCount(); i++) {
746             result.addAll(pattern.getAlternative(i).getLookAhead());
747         }
748 
749         return result;
750     }
751 
752     /**
753      * Throws a parse exception that matches the specified look-ahead
754      * set. This method will take into account any initial matching
755      * tokens in the look-ahead set.
756      *
757      * @param set            the look-ahead set to match
758      *
759      * @throws ParseException always thrown by this method
760      */
761     private void throwParseException(LookAheadSet set)
762         throws ParseException {
763 
764         Token      token;
765         ArrayList    list = new ArrayList  ();
766         int[]      initials;
767 
768         // Read tokens until mismatch
769         while (set.isNext(this, 1)) {
770             set = set.createNextSet(nextToken().getId());
771         }
772 
773         // Find next token descriptions
774         initials = set.getInitialTokens();
775         for (int i = 0; i < initials.length; i++) {
776             list.add(getTokenDescription(initials[i]));
777         }
778 
779         // Create exception
780         token = nextToken();
781         throw new ParseException(ParseException.UNEXPECTED_TOKEN_ERROR,
782                                  token.toShortString(),
783                                  list,
784                                  token.getStartLine(),
785                                  token.getStartColumn());
786     }
787 
788     /**
789      * Throws a parser creation exception for an ambiguity. The
790      * specified look-ahead set contains the token conflicts to be
791      * reported.
792      *
793      * @param pattern        the production pattern name
794      * @param location       the production pattern location, or null
795      * @param set            the look-ahead set with conflicts
796      *
797      * @throws ParserCreationException always thrown by this method
798      */
799     private void throwAmbiguityException(String   pattern,
800                                          String   location,
801                                          LookAheadSet set)
802         throws ParserCreationException {
803 
804         ArrayList    list = new ArrayList  ();
805         int[]      initials;
806 
807         // Find next token descriptions
808         initials = set.getInitialTokens();
809         for (int i = 0; i < initials.length; i++) {
810             list.add(getTokenDescription(initials[i]));
811         }
812 
813         // Create exception
814         throw new ParserCreationException(
815             ParserCreationException.INHERENT_AMBIGUITY_ERROR,
816             pattern,
817             location,
818             list);
819     }
820 
821 
822     /**
823      * A name value stack. This stack is used to detect loops and
824      * repetitions of the same production during look-ahead analysis.
825      */
826     private class CallStack {
827 
828         /**
829          * A stack with names.
830          */
831         private ArrayList   nameStack = new ArrayList  ();
832 
833         /**
834          * A stack with values.
835          */
836         private ArrayList   valueStack = new ArrayList  ();
837 
838         /**
839          * Checks if the specified name is on the stack.
840          *
841          * @param name           the name to search for
842          *
843          * @return true if the name is on the stack, or
844          *         false otherwise
845          */
846         public boolean contains(String   name) {
847             return nameStack.contains(name);
848         }
849 
850         /**
851          * Checks if the specified name and value combination is on
852          * the stack.
853          *
854          * @param name           the name to search for
855          * @param value          the value to search for
856          *
857          * @return true if the combination is on the stack, or
858          *         false otherwise
859          */
860         public boolean contains(String   name, int value) {
861             Integer    obj = new Integer  (value);
862 
863             for (int i = 0; i < nameStack.size(); i++) {
864                 if (nameStack.get(i).equals(name)
865                  && valueStack.get(i).equals(obj)) {
866 
867                      return true;
868                 }
869             }
870             return false;
871         }
872 
873         /**
874          * Clears the stack. This method removes all elements on the
875          * stack.
876          */
877         public void clear() {
878             nameStack.clear();
879             valueStack.clear();
880         }
881 
882         /**
883          * Adds a new element to the top of the stack.
884          *
885          * @param name           the stack name
886          * @param value          the stack value
887          */
888         public void push(String   name, int value) {
889             nameStack.add(name);
890             valueStack.add(new Integer  (value));
891         }
892 
893         /**
894          * Removes the top element of the stack.
895          */
896         public void pop() {
897             if (nameStack.size() > 0) {
898                 nameStack.remove(nameStack.size() - 1);
899                 valueStack.remove(valueStack.size() - 1);
900             }
901         }
902     }
903 }
904
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags