recursivedescentparser.java

Grammatica是一个C#和Java的语法分析程序生成器(编译器的编译器)。它可以用LL(k)语法创建可读的和带有注释的源代码。它也支持创建一个运行时语法分析器

        // Handle element repetitions
        if (elem.getMaxCount() == Integer.MAX_VALUE) {
            first = first.createRepetitive();
        }
        max = Math.min(length, elem.getMaxCount());
        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) 
        throws ParserCreationException {

        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) 
        throws ParserCreationException {

        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) 
        throws ParserCreationException {

        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)
        throws ParseException {

        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.UNEXPECTED_TOKEN_ERROR,
                                 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) 
        throws ParserCreationException {

        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.INHERENT_AMBIGUITY_ERROR,
            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 boolean 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 boolean contains(String name, int value) {
            Integer  obj = new Integer(value);

            for (int i = 0; i < nameStack.size(); i++) {
                if (nameStack.get(i).equals(name)
                 && valueStack.get(i).equals(obj)) {
                     
                     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(new Integer(value));
        }

        /**
         * Removes the top element of the stack.
         */
        public void pop() {
            if (nameStack.size() > 0) {
                nameStack.remove(nameStack.size() - 1);
                valueStack.remove(valueStack.size() - 1);
            }
        }
    }
}