recursivedescentparser.cs

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

            // Handle element repetitions
            if (elem.GetMaxCount() == Int32.MaxValue) {
                first = first.CreateRepetitive();
            }
            max = elem.GetMaxCount();
            if (length < max) {
                max = length;
            }
            for (int i = 1; i < max; i++) {
                first = first.CreateOverlaps(filter);
                if (first.Size() <= 0 || first.GetMinLength() >= length) {
                    break;
                }
                follow = FindLookAhead(elem, 
                                       length, 
                                       0, 
                                       stack, 
                                       filter.CreateFilter(first));
                first = first.CreateCombination(follow);
                result.AddAll(first);
            }
    
            return result;
        }
    
        /**
         * Finds the look-ahead set for a production pattern element. The
         * maximum look-ahead length must be specified. This method does
         * NOT take the element repeat into consideration when creating 
         * the look-ahead set. 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 dummy          a parameter to distinguish the method
         * @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,
                                           int dummy,
                                           CallStack stack,
                                           LookAheadSet filter) {
    
            LookAheadSet       result;
            ProductionPattern  pattern;
    
            if (elem.IsToken()) {
                result = new LookAheadSet(length);
                result.Add(elem.GetId());
            } else {
                pattern = GetPattern(elem.GetId());
                result = FindLookAhead(pattern, length, stack, filter);
                if (stack.Contains(pattern.GetName())) {
                    result = result.CreateRepetitive();
                }
            }
    
            return result;
        }
    
        /**
         * Returns a look-ahead set with all conflics between
         * alternatives in a production pattern.
         * 
         * @param pattern        the production pattern
         * @param maxLength      the maximum token sequence length
         * 
         * @return a look-ahead set with the conflicts found
         * 
         * @throws ParserCreationException if an inherent ambiguity was
         *             found among the look-ahead sets
         */
        private LookAheadSet FindConflicts(ProductionPattern pattern,
                                           int maxLength) {

            LookAheadSet  result = new LookAheadSet(maxLength);
            LookAheadSet  set1;
            LookAheadSet  set2;

            for (int i = 0; i < pattern.GetAlternativeCount(); i++) {
                set1 = pattern.GetAlternative(i).GetLookAhead();
                for (int j = 0; j < i; j++) {
                    set2 = pattern.GetAlternative(j).GetLookAhead();
                    result.AddAll(set1.CreateIntersection(set2));
                }
            }
            if (result.IsRepetitive()) {
                ThrowAmbiguityException(pattern.GetName(), null, result);
            }
            return result;
        }
    
        /**
         * Returns a look-ahead set with all conflicts between two
         * look-ahead sets.
         * 
         * @param pattern        the pattern name being analyzed
         * @param location       the pattern location
         * @param set1           the first look-ahead set
         * @param set2           the second look-ahead set
         * 
         * @return a look-ahead set with the conflicts found
         * 
         * @throws ParserCreationException if an inherent ambiguity was
         *             found among the look-ahead sets
         */
        private LookAheadSet FindConflicts(string pattern,
                                           string location,
                                           LookAheadSet set1,
                                           LookAheadSet set2) {

            LookAheadSet  result;
            
            result = set1.CreateIntersection(set2);
            if (result.IsRepetitive()) {
                ThrowAmbiguityException(pattern, location, result);
            }
            return result;
        }

        /**
         * Returns the union of all alternative look-ahead sets in a
         * production pattern.
         * 
         * @param pattern        the production pattern
         * 
         * @return a unified look-ahead set
         */
        private LookAheadSet FindUnion(ProductionPattern pattern) {
            LookAheadSet  result;
            int           length = 0;
            int           i;

            for (i = 0; i < pattern.GetAlternativeCount(); i++) {
                result = pattern.GetAlternative(i).GetLookAhead();
                if (result.GetMaxLength() > length) {
                    length = result.GetMaxLength(); 
                }
            }
            result = new LookAheadSet(length);
            for (i = 0; i < pattern.GetAlternativeCount(); i++) {
                result.AddAll(pattern.GetAlternative(i).GetLookAhead());
            }
            
            return result;
        }

        /**
         * Throws a parse exception that matches the specified look-ahead
         * set. This method will take into account any initial matching 
         * tokens in the look-ahead set.
         * 
         * @param set            the look-ahead set to match
         * 
         * @throws ParseException always thrown by this method
         */
        private void ThrowParseException(LookAheadSet set) {
            Token      token;
            ArrayList  list = new ArrayList();
            int[]      initials;
        
            // Read tokens until mismatch
            while (set.IsNext(this, 1)) {
                set = set.CreateNextSet(NextToken().GetId());
            }
        
            // Find next token descriptions
            initials = set.GetInitialTokens();
            for (int i = 0; i < initials.Length; i++) {
                list.Add(GetTokenDescription(initials[i]));
            }
        
            // Create exception
            token = NextToken();
            throw new ParseException(ParseException.ErrorType.UNEXPECTED_TOKEN,
                                     token.ToShortString(),
                                     list,
                                     token.GetStartLine(),
                                     token.GetStartColumn());
        }

        /**
         * Throws a parser creation exception for an ambiguity. The 
         * specified look-ahead set contains the token conflicts to be 
         * reported.
         *
         * @param pattern        the production pattern name
         * @param location       the production pattern location, or null  
         * @param set            the look-ahead set with conflicts
         * 
         * @throws ParserCreationException always thrown by this method
         */
        private void ThrowAmbiguityException(string pattern, 
                                             string location,
                                             LookAheadSet set) {

            ArrayList  list = new ArrayList();
            int[]      initials;
        
            // Find next token descriptions
            initials = set.GetInitialTokens();
            for (int i = 0; i < initials.Length; i++) {
                list.Add(GetTokenDescription(initials[i]));
            }
        
            // Create exception
            throw new ParserCreationException(
                ParserCreationException.ErrorType.INHERENT_AMBIGUITY,
                pattern,
                location,
                list);
        }


        /**
         * A name value stack. This stack is used to detect loops and 
         * repetitions of the same production during look-ahead analysis.
         */
        private class CallStack {
            
            /**
             * A stack with names.
             */
            private ArrayList nameStack = new ArrayList();

            /**
             * A stack with values.
             */
            private ArrayList valueStack = new ArrayList();

            /**
             * Checks if the specified name is on the stack. 
             * 
             * @param name           the name to search for
             * 
             * @return true if the name is on the stack, or
             *         false otherwise
             */
            public bool Contains(string name) {
                return nameStack.Contains(name);
            }
        
            /**
             * Checks if the specified name and value combination is on
             * the stack.
             * 
             * @param name           the name to search for
             * @param value          the value to search for
             * 
             * @return true if the combination is on the stack, or
             *         false otherwise
             */
            public bool Contains(string name, int value) {
                for (int i = 0; i < nameStack.Count; i++) {
                    if (nameStack[i].Equals(name)
                     && valueStack[i].Equals(value)) {
                        
                        return true;
                    }
                }
                return false;
            }

            /**
             * Clears the stack. This method removes all elements on
             * the stack.
             */
            public void Clear() {
                nameStack.Clear();
                valueStack.Clear();
            }
        
            /**
             * Adds a new element to the top of the stack.
             * 
             * @param name           the stack name 
             * @param value          the stack value
             */
            public void Push(string name, int value) {
                nameStack.Add(name);
                valueStack.Add(value);
            }

            /**
             * Removes the top element of the stack.
             */
            public void Pop() {
                if (nameStack.Count > 0) {
                    nameStack.RemoveAt(nameStack.Count - 1);
                    valueStack.RemoveAt(valueStack.Count - 1);
                }
            }
        }
    }
}