repeatelement.java

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

/*
 * RepeatElement.java
 *
 * This work is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2 of the License,
 * or (at your option) any later version.
 *
 * This work is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 *
 * As a special exception, the copyright holders of this library give
 * you permission to link this library with independent modules to
 * produce an executable, regardless of the license terms of these
 * independent modules, and to copy and distribute the resulting
 * executable under terms of your choice, provided that you also meet,
 * for each linked independent module, the terms and conditions of the
 * license of that module. An independent module is a module which is
 * not derived from or based on this library. If you modify this
 * library, you may extend this exception to your version of the
 * library, but you are not obligated to do so. If you do not wish to
 * do so, delete this exception statement from your version.
 *
 * Copyright (c) 2003 Per Cederberg. All rights reserved.
 */

package net.percederberg.grammatica.parser.re;

import java.io.PrintWriter;
import java.util.BitSet;

/**
 * A regular expression element repeater. The element repeats the 
 * matches from a specified element, attempting to reach the maximum 
 * repetition count.
 *
 * @author   Per Cederberg, <per at percederberg dot net>
 * @version  1.1
 */
class RepeatElement extends Element {

    /**
     * The greedy repeat type constant.
     */
    public static final int GREEDY = 1;
    
    /**
     * The reluctant repeat type constant.
     */
    public static final int RELUCTANT = 2;
    
    /**
     * The possesive repeat type constant.
     */
    public static final int POSSESSIVE = 3;

    /**
     * The element to repeat.
     */
    private Element elem;
    
    /**
     * The minimum number of repetitions.
     */
    private int min;

    /**
     * The maximum number of repetitions.
     */    
    private int max;

    /**
     * The repeat type.
     */
    private int type;

    /**
     * The start position of the last set of matches. 
     */
    private int matchStart;

    /**
     * A set with all matches starting as matchStart. A match with a
     * specific length is reported by a non-zero bit in the bit set.
     */
    private BitSet matches;

    /**
     * Creats a new element repeater.
     * 
     * @param elem           the element to repeat
     * @param min            the minimum count
     * @param max            the maximum count
     * @param type           the repeat type constant
     * 
     * @see #GREEDY
     * @see #RELUCTANT
     * @see #POSSESIVE
     */
    public RepeatElement(Element elem, int min, int max, int type) {
        this.elem = elem;
        this.min = min;
        if (max <= 0) {
            this.max = Integer.MAX_VALUE;
        } else {
            this.max = max;
        }
        this.type = type;
        this.matchStart = -1;
        this.matches = null;
    }

    /**
     * Creates a copy of this element. The copy will be an instance
     * of the same class matching the same strings. Copies of elements
     * are necessary to allow elements to cache intermediate results
     * while matching strings without interfering with other threads.
     * 
     * @return a copy of this element
     */
    public Object clone() {
        return new RepeatElement((Element) elem.clone(), min, max, type);
    }

    /**
     * Returns the length of a matching string starting at the 
     * specified position. The number of matches to skip can also be
     * specified.
     *
     * @param m              the matcher being used 
     * @param str            the string to match
     * @param start          the starting position
     * @param skip           the number of matches to skip
     * 
     * @return the length of the matching string, or
     *         -1 if no match was found
     */
    public int match(Matcher m, CharBuffer str, int start, int skip) {
        if (skip == 0) {
            matchStart = -1;
            matches = null;
        }
        switch (type) {
        case GREEDY:
            return matchGreedy(m, str, start, skip);
        case RELUCTANT:
            return matchReluctant(m, str, start, skip);
        case POSSESSIVE:
            if (skip == 0) {
                return matchPossessive(m, str, start, 0);
            }
            break;
        }
        return -1;
    }

    /**
     * Returns the length of the longest possible matching string 
     * starting at the specified position. The number of matches to 
     * skip can also be specified.
     *
     * @param m              the matcher being used 
     * @param str            the string to match
     * @param start          the starting position
     * @param skip           the number of matches to skip
     * 
     * @return the length of the longest matching string, or
     *         -1 if no match was found
     */
    private int matchGreedy(Matcher m, 
                            CharBuffer str, 
                            int start,
                            int skip) {

        // Check for simple case
        if (skip == 0) {
            return matchPossessive(m, str, start, 0);
        }

        // Find all matches
        if (matchStart != start) {
            matchStart = start;
            matches = new BitSet();
            findMatches(m, str, start, 0, 0, 0);
        }

        // Find first non-skipped match
        for (int i = matches.size(); i >= 0; i--) {
            if (matches.get(i)) {
                if (skip == 0) {
                    return i;
                }
                skip--;
            }
        }
        return -1;
    }

    /**
     * Returns the length of the shortest possible matchine string
     * starting at the specified position. The number of matches to 
     * skip can also be specified.
     *
     * @param m              the matcher being used 
     * @param str            the string to match
     * @param start          the starting position
     * @param skip           the number of matches to skip
     * 
     * @return the length of the shortest matching string, or
     *         -1 if no match was found
     */
    private int matchReluctant(Matcher m, 
                               CharBuffer str, 
                               int start,
                               int skip) {
    
        // Find all matches
        if (matchStart != start) {
            matchStart = start;
            matches = new BitSet();
            findMatches(m, str, start, 0, 0, 0);
        }

        // Find first non-skipped match
        for (int i = 0; i <= matches.size(); i++) {
            if (matches.get(i)) {
                if (skip == 0) {
                    return i;
                }
                skip--;
            }
        }
        return -1;
    }

    /**
     * Returns the length of the maximum number of elements matching 
     * the string starting at the specified position. This method 
     * allows no backtracking, i.e. no skips..
     *
     * @param m              the matcher being used 
     * @param str            the string to match
     * @param start          the starting position
     * @param count          the start count, normally zero (0)
     * 
     * @return the length of the longest matching string, or
     *         -1 if no match was found
     */
    private int matchPossessive(Matcher m, 
                                CharBuffer str, 
                                int start,
                                int count) {
                                   
        int  length = 0;
        int  subLength = 1;
        
        // Match as many elements as possible
        while (subLength > 0 && count < max) {
            subLength = elem.match(m, str, start + length, 0);
            if (subLength >= 0) {
                count++;
                length += subLength;
            }
        }

        // Return result
        if (min <= count && count <= max) {
            return length;
        } else {
            return -1;
        }
    }

    /**
     * Finds all matches and adds the lengths to the matches set.  
     * 
     * @param m              the matcher being used 
     * @param str            the string to match
     * @param start          the starting position
     * @param length         the match length at the start position
     * @param count          the number of sub-elements matched
     * @param attempt        the number of match attempts here
     */
    private void findMatches(Matcher m, 
                             CharBuffer str, 
                             int start,
                             int length,
                             int count, 
                             int attempt) {

        int  subLength;

        // Check match ending here
        if (count > max) {
            return;
        }
        if (min <= count && attempt == 0) {
            matches.set(length);
        }
        
        // Check element match
        subLength = elem.match(m, str, start, attempt);
        if (subLength < 0) {
            return;
        } else if (subLength == 0) {
            if (min == count + 1) {
                matches.set(length);
            }
            return;
        }

        // Find alternative and subsequent matches 
        findMatches(m, str, start, length, count, attempt + 1);
        findMatches(m, 
                    str, 
                    start + subLength, 
                    length + subLength, 
                    count + 1, 
                    0); 
    }

    /**
     * Prints this element to the specified output stream.
     * 
     * @param output         the output stream to use
     * @param indent         the current indentation
     */
    public void printTo(PrintWriter output, String indent) {
        output.print(indent + "Repeat (" + min + "," + max + ")");
        if (type == RELUCTANT) {
            output.print("?");
        } else if (type == POSSESSIVE) {
            output.print("+");
        }
        output.println();
        elem.printTo(output, indent + "  ");
    }
}