recursivedescentparser.cs

Grammatica is a C# and Java parser generator (compiler compiler). It improves upon simlar tools (lik

        private bool IsNext(ProductionPatternElement elem) {
            LookAheadSet  set = elem.GetLookAhead();
        
            if (set != null) {
                return set.IsNext(this);
            } else if (elem.IsToken()) {
                return elem.IsMatch(PeekToken(0));
            } else {
                return IsNext(GetPattern(elem.GetId()));
            }
        }

        /**
         * Calculates the look-ahead needed for the specified production 
         * pattern. This method attempts to resolve any conflicts and 
         * stores the results in the pattern look-ahead object. 
         * 
         * @param pattern        the production pattern
         * 
         * @throws ParserCreationException if the look-ahead set couldn't
         *             be determined due to inherent ambiguities
         */
        private void CalculateLookAhead(ProductionPattern pattern) {
            ProductionPatternAlternative  alt;
            LookAheadSet                  result;
            LookAheadSet[]                alternatives;
            LookAheadSet                  conflicts;
            LookAheadSet                  previous = new LookAheadSet(0);
            int                           length = 1;
            int                           i;
            CallStack                     stack = new CallStack();
            
            // Calculate simple look-ahead
            stack.Push(pattern.GetName(), 1);
            result = new LookAheadSet(1);
            alternatives = new LookAheadSet[pattern.GetAlternativeCount()];
            for (i = 0; i < pattern.GetAlternativeCount(); i++) {
                alt = pattern.GetAlternative(i);
                alternatives[i] = FindLookAhead(alt, 1, 0, stack, null);
                alt.SetLookAhead(alternatives[i]);
                result.AddAll(alternatives[i]);
            }
            if (pattern.GetLookAhead() == null) {
                pattern.SetLookAhead(result);
            }
            conflicts = FindConflicts(pattern, 1);
    
            // Resolve conflicts
            while (conflicts.Size() > 0) {
                length++;
                stack.Clear();
                stack.Push(pattern.GetName(), length);
                conflicts.AddAll(previous);
                for (i = 0; i < pattern.GetAlternativeCount(); i++) {
                    alt = pattern.GetAlternative(i);
                    if (alternatives[i].Intersects(conflicts)) {
                        alternatives[i] = FindLookAhead(alt, 
                                                        length,
                                                        0,
                                                        stack,
                                                        conflicts);
                        alt.SetLookAhead(alternatives[i]);
                    }
                    if (alternatives[i].Intersects(conflicts)) {
                        if (pattern.GetDefaultAlternative() == null) {
                            pattern.SetDefaultAlternative(i);
                        } else if (pattern.GetDefaultAlternative() != alt) {
                            result = alternatives[i].CreateIntersection(conflicts);
                            ThrowAmbiguityException(pattern.GetName(), 
                                                    null, 
                                                    result);
                        }
                    }
                }
                previous = conflicts;
                conflicts = FindConflicts(pattern, length);
            }
            
            // Resolve conflicts inside rules
            for (i = 0; i < pattern.GetAlternativeCount(); i++) {
                CalculateLookAhead(pattern.GetAlternative(i), 0);
            }
        }
    
        /**
         * Calculates the look-aheads needed for the specified pattern 
         * alternative. This method attempts to resolve any conflicts in 
         * optional elements by recalculating look-aheads for referenced 
         * productions. 
         * 
         * @param alt            the production pattern alternative
         * @param pos            the pattern element position
         * 
         * @throws ParserCreationException if the look-ahead set couldn't
         *             be determined due to inherent ambiguities
         */
        private void CalculateLookAhead(ProductionPatternAlternative alt,
                                        int pos) {
    
            ProductionPattern         pattern;
            ProductionPatternElement  elem;
            LookAheadSet              first;
            LookAheadSet              follow;
            LookAheadSet              conflicts;
            LookAheadSet              previous = new LookAheadSet(0);
            String                    location;
            int                       length = 1;
    
            // Check trivial cases
            if (pos >= alt.GetElementCount()) {
                return;
            }
    
            // Check for non-optional element
            pattern = alt.GetPattern();
            elem = alt.GetElement(pos);
            if (elem.GetMinCount() == elem.GetMaxCount()) {
                CalculateLookAhead(alt, pos + 1);
                return;
            }
    
            // Calculate simple look-aheads
            first = FindLookAhead(elem, 1, new CallStack(), null);
            follow = FindLookAhead(alt, 1, pos + 1, new CallStack(), null); 
            
            // Resolve conflicts
            location = "at position " + (pos + 1);
            conflicts = FindConflicts(pattern.GetName(), 
                                      location, 
                                      first, 
                                      follow);
            while (conflicts.Size() > 0) {
                length++;
                conflicts.AddAll(previous);
                first = FindLookAhead(elem, 
                                      length, 
                                      new CallStack(), 
                                      conflicts);
                follow = FindLookAhead(alt, 
                                       length, 
                                       pos + 1, 
                                       new CallStack(), 
                                       conflicts);
                first = first.CreateCombination(follow);
                elem.SetLookAhead(first);
                if (first.Intersects(conflicts)) {
                    first = first.CreateIntersection(conflicts);
                    ThrowAmbiguityException(pattern.GetName(), location, first);
                }
                previous = conflicts;
                conflicts = FindConflicts(pattern.GetName(), 
                                          location, 
                                          first, 
                                          follow);
            }
    
            // Check remaining elements
            CalculateLookAhead(alt, pos + 1);
        }
    
        /**
         * Finds the look-ahead set for a production pattern. The maximum 
         * look-ahead length must be specified. It is also possible to 
         * specify a look-ahead set filter, which will make sure that 
         * unnecessary token sequences will be avoided.
         * 
         * @param pattern        the production pattern
         * @param length         the maximum look-ahead length
         * @param stack          the call stack used for loop detection
         * @param filter         the look-ahead set filter
         * 
         * @return the look-ahead set for the production pattern
         * 
         * @throws ParserCreationException if an infinite loop was found
         *             in the grammar
         */
        private LookAheadSet FindLookAhead(ProductionPattern pattern, 
                                           int length,
                                           CallStack stack,
                                           LookAheadSet filter) {
    
            LookAheadSet  result;
            LookAheadSet  temp;
    
            // Check for infinite loop
            if (stack.Contains(pattern.GetName(), length)) {
                throw new ParserCreationException(
                    ParserCreationException.ErrorType.INFINITE_LOOP,
                    pattern.GetName(),
                    (String) null);
            }
    
            // Find pattern look-ahead
            stack.Push(pattern.GetName(), length);
            result = new LookAheadSet(length);
            for (int i = 0; i < pattern.GetAlternativeCount(); i++) {
                temp = FindLookAhead(pattern.GetAlternative(i), 
                                     length,
                                     0,
                                     stack,
                                     filter);
                result.AddAll(temp);
            }
            stack.Pop();
    
            return result;
        }
    
        /**
         * Finds the look-ahead set for a production pattern alternative. 
         * The pattern position and maximum look-ahead length must be 
         * specified. It is also possible to specify a look-ahead set 
         * filter, which will make sure that unnecessary token sequences 
         * will be avoided.
         * 
         * @param alt            the production pattern alternative
         * @param length         the maximum look-ahead length
         * @param pos            the pattern element position
         * @param stack          the call stack used for loop detection
         * @param filter         the look-ahead set filter
         * 
         * @return the look-ahead set for the pattern alternative
         * 
         * @throws ParserCreationException if an infinite loop was found
         *             in the grammar
         */
        private LookAheadSet FindLookAhead(ProductionPatternAlternative alt,
                                           int length,
                                           int pos,
                                           CallStack stack,
                                           LookAheadSet filter) {
    
            LookAheadSet  first;
            LookAheadSet  follow;
            LookAheadSet  overlaps;
    
            // Check trivial cases
            if (length <= 0 || pos >= alt.GetElementCount()) {
                return new LookAheadSet(0);
            }
    
            // Find look-ahead for this element
            first = FindLookAhead(alt.GetElement(pos), length, stack, filter);
            if (alt.GetElement(pos).GetMinCount() == 0) {
                first.AddEmpty();
            }
            
            // Find remaining look-ahead
            if (filter == null) {
                length -= first.GetMinLength();
                if (length > 0) {
                    follow = FindLookAhead(alt, length, pos + 1, stack, null); 
                    first = first.CreateCombination(follow);
                }
            } else if (filter.IsOverlap(first)) {
                overlaps = first.CreateOverlaps(filter);
                length -= overlaps.GetMinLength();
                filter = filter.CreateFilter(overlaps);
                follow = FindLookAhead(alt, length, pos + 1, stack, filter); 
                first.RemoveAll(overlaps);
                first.AddAll(overlaps.CreateCombination(follow));
            }
    
            return first;
        }
    
        /**
         * Finds the look-ahead set for a production pattern element. The
         * maximum look-ahead length must be specified. This method takes
         * the element repeats into consideration when creating the 
         * look-ahead set, but does NOT include an empty sequence even if
         * the minimum count is zero (0). It is also possible to specify a
         * look-ahead set filter, which will make sure that unnecessary 
         * token sequences will be avoided.
         * 
         * @param elem           the production pattern element
         * @param length         the maximum look-ahead length
         * @param stack          the call stack used for loop detection
         * @param filter         the look-ahead set filter
         * 
         * @return the look-ahead set for the pattern element
         * 
         * @throws ParserCreationException if an infinite loop was found
         *             in the grammar
         */
        private LookAheadSet FindLookAhead(ProductionPatternElement elem,
                                           int length,
                                           CallStack stack,
                                           LookAheadSet filter) {
    
            LookAheadSet  result;
            LookAheadSet  first;
            LookAheadSet  follow;
            int           max;
    
            // Find initial element look-ahead
            first = FindLookAhead(elem, length, 0, stack, filter);
            result = new LookAheadSet(length);
            result.AddAll(first);
            if (filter == null || !filter.IsOverlap(result)) {
                return result;
            }