recursivedescentparser.java

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

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

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

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

        LookAheadSet  result;
        LookAheadSet  temp;

        // Check for infinite loop
        if (stack.contains(pattern.getName(), length)) {
            throw new ParserCreationException(
                ParserCreationException.INFINITE_LOOP_ERROR,
                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) 
        throws ParserCreationException {

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

        ProductionPattern  pattern;
        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;
        }