lookaheadset.java

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

     * Creates a new look-ahead set that is the combination of 
     * this set with another set. The combination is created by 
     * creating new token sequences that consist of appending all 
     * elements from the specified set onto all elements in this set. 
     * This is sometimes referred to as the cartesian product.
     * 
     * @param set            the set to combine with
     * 
     * @return a new look-ahead set containing the combination
     */
    public LookAheadSet createCombination(LookAheadSet set) {
        LookAheadSet  result = new LookAheadSet(maxLength);
        Sequence      first;
        Sequence      second;
        
        // Handle special cases
        if (this.size() <= 0) {
            return set;
        } else if (set.size() <= 0) {
            return this;
        }

        // Create combinations
        for (int i = 0; i < elements.size(); i++) {
            first = (Sequence) elements.get(i);
            if (first.length() >= maxLength) {
                result.add(first);
            } else if (first.length() <= 0) {
                result.addAll(set);  
            } else {
                for (int j = 0; j < set.elements.size(); j++) {
                    second = (Sequence) set.elements.get(j);
                    result.add(first.concat(maxLength, second));
                }
            }
        }
        return result;
    }

    /**
     * Creates a new look-ahead set with overlaps from another. All
     * token sequences in this set that overlaps with the other set
     * will be added to the new look-ahead set.
     * 
     * @param set            the look-ahead set to check with
     * 
     * @return a new look-ahead set containing the overlaps
     */
    public LookAheadSet createOverlaps(LookAheadSet set) {
        LookAheadSet  result = new LookAheadSet(maxLength);
        Sequence      seq;
        
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (set.isOverlap(seq)) {
                result.add(seq);
            }
        }
        return result;
    }

    /**
     * Creates a new look-ahead set filter. The filter will contain
     * all sequences from this set, possibly left trimmed by each one
     * of the sequences in the specified set.
     * 
     * @param set            the look-ahead set to trim with
     * 
     * @return a new look-ahead set filter
     */
    public LookAheadSet createFilter(LookAheadSet set) {
        LookAheadSet  result = new LookAheadSet(maxLength);
        Sequence      first;
        Sequence      second;
        
        // Handle special cases
        if (this.size() <= 0 || set.size() <= 0) {
            return this;
        }

        // Create combinations
        for (int i = 0; i < elements.size(); i++) {
            first = (Sequence) elements.get(i);
            for (int j = 0; j < set.elements.size(); j++) {
                second = (Sequence) set.elements.get(j);
                if (first.startsWith(second)) {
                    result.add(first.subsequence(second.length()));
                }
            }
        }
        return result;
    }

    /**
     * Creates a new identical look-ahead set, except for the repeat
     * flag being set in each token sequence.
     * 
     * @return a new repetitive look-ahead set 
     */
    public LookAheadSet createRepetitive() {
        LookAheadSet  result = new LookAheadSet(maxLength);
        Sequence      seq;
        
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (seq.isRepetitive()) {
                result.add(seq);
            } else {
                result.add(new Sequence(true, seq));  
            }
        }
        return result;
    }

    /**
     * Returns a string representation of this object.
     * 
     * @return a string representation of this object
     */
    public String toString() {
        return toString(null);
    }
    
    /**
     * Returns a string representation of this object.
     * 
     * @param tokenizer      the tokenizer containing the tokens
     * 
     * @return a string representation of this object
     */
    public String toString(Tokenizer tokenizer) {
        StringBuffer  buffer = new StringBuffer();
        Sequence      seq;

        buffer.append("{");
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            buffer.append("\n  ");
            buffer.append(seq.toString(tokenizer));
        }
        buffer.append("\n}");
        return buffer.toString();
    }
    
    
    /**
     * A token sequence. This class contains a list of token ids. It
     * is immutable after creation, meaning that no changes will be
     * made to an instance after creation.
     *
     * @author   Per Cederberg, <per at percederberg dot net>
     * @version  1.0
     */
    private class Sequence {

        /**
         * The repeat flag. If this flag is set, the token sequence
         * or some part of it may be repeated infinitely. 
         */
        private boolean repeat = false;        

        /**
         * The list of token ids in this sequence.
         */
        private ArrayList tokens = null;
        
        /**
         * Creates a new empty token sequence. The repeat flag will be
         * set to false.
         */
        public Sequence() {
            this.repeat = false;
            this.tokens = new ArrayList(0);
        }

        /**
         * Creates a new token sequence with a single token.
         * 
         * @param repeat         the repeat flag value
         * @param token          the token to add
         */
        public Sequence(boolean repeat, int token) {
            this.repeat = false;
            this.tokens = new ArrayList(1);
            this.tokens.add(new Integer(token));
        }

        /**
         * Creates a new token sequence that is a duplicate of another
         * sequence. Only a limited number of tokens will be copied
         * however. The repeat flag from the original will be kept
         * intact.
         * 
         * @param length         the maximum number of tokens to copy
         * @param seq            the sequence to copy
         */
        public Sequence(int length, Sequence seq) {
            this.repeat = seq.repeat;
            this.tokens = new ArrayList(length);
            if (seq.length() < length) {
                length = seq.length();
            }
            for (int i = 0; i < length; i++) {
                tokens.add(seq.tokens.get(i)); 
            }
        }

        /**
         * Creates a new token sequence that is a duplicate of another
         * sequence. The new value of the repeat flag will be used
         * however.
         * 
         * @param repeat         the new repeat flag value
         * @param seq            the sequence to copy
         */
        public Sequence(boolean repeat, Sequence seq) {
            this.repeat = repeat;
            this.tokens = seq.tokens;
        }

        /**
         * Returns the length of the token sequence.
         * 
         * @return the number of tokens in the sequence
         */
        public int length() {
            return tokens.size();
        }

        /**
         * Returns a token at a specified position in the sequence.
         * 
         * @param pos            the sequence position
         * 
         * @return the token id found, or null
         */
        public Integer getToken(int pos) {
            if (pos >= 0 && pos < tokens.size()) {
                return (Integer) tokens.get(pos);
            } else {
                return null;
            }
        }

        /**
         * Checks if this sequence is equal to another object. Only
         * token sequences with the same tokens in the same order will
         * be considered equal. The repeat flag will be disregarded.
         * 
         * @param obj            the object to compare with
         * 
         * @return true if the objects are equal, or
         *         false otherwise 
         */
        public boolean equals(Object obj) {
            if (obj instanceof Sequence) {
                return tokens.equals(((Sequence) obj).tokens);
            } else {
                return false;
            }
        }

        /**
         * Checks if this token sequence starts with the tokens from
         * another sequence. If the other sequence is longer than this
         * sequence, this method will always return false.
         * 
         * @param seq            the token sequence to check
         * 
         * @return true if this sequence starts with the other, or
         *         false otherwise
         */
        public boolean startsWith(Sequence seq) {
            if (length() < seq.length()) {
                return false;
            }
            for (int i = 0; i < seq.tokens.size(); i++) {
                if (!tokens.get(i).equals(seq.tokens.get(i))) {
                    return false;
                }
            }
            return true;
        }

        /**
         * Checks if this token sequence is repetitive. A repetitive 
         * token sequence is one with the repeat flag set.
         * 
         * @return true if this token sequence is repetitive, or
         *         false otherwise
         */
        public boolean isRepetitive() {
            return repeat;
        }

        /**
         * Checks if the next token(s) in the parser matches this
         * token sequence.
         * 
         * @param parser         the parser to check
         * 
         * @return true if the next tokens are in the sequence, or
         *         false otherwise
         */
        public boolean isNext(Parser parser) {
            Token    token;
            Integer  id;
            
            for (int i = 0; i < tokens.size(); i++) {
                id = (Integer) tokens.get(i);
                token = parser.peekToken(i);
                if (token == null || token.getId() != id.intValue()) {
                    return false;
                }
            }
            return true;
        }

        /**
         * Checks if the next token(s) in the parser matches this
         * token sequence.
         * 
         * @param parser         the parser to check
         * @param length         the maximum number of tokens to check
         * 
         * @return true if the next tokens are in the sequence, or
         *         false otherwise
         */
        public boolean isNext(Parser parser, int length) {
            Token    token;
            Integer  id;
            
            if (length > tokens.size()) {
                length = tokens.size();
            }
            for (int i = 0; i < length; i++) {
                id = (Integer) tokens.get(i);
                token = parser.peekToken(i);
                if (token == null || token.getId() != id.intValue()) {
                    return false;
                }
            }
            return true;
        }

        /**
         * Returns a string representation of this object.
         * 
         * @return a string representation of this object
         */
        public String toString() {
            return toString(null);
        }
        
        /**
         * Returns a string representation of this object.
         *
         * @param tokenizer      the tokenizer containing the tokens
         *  
         * @return a string representation of this object
         */
        public String toString(Tokenizer tokenizer) {
            StringBuffer  buffer = new StringBuffer();
            String        str;
            Integer       id;

            if (tokenizer == null) {
                buffer.append(tokens.toString());
            } else {
                buffer.append("[");
                for (int i = 0; i < tokens.size(); i++) {
                    id = (Integer) tokens.get(i);
                    str = tokenizer.getPatternDescription(id.intValue());
                    if (i > 0) {
                        buffer.append(" ");
                    }
                    buffer.append(str);
                }
                buffer.append("]");
            }
            if (repeat) {
                buffer.append(" *");
            }
            return buffer.toString();
        }

        /**
         * Creates a new token sequence that is the concatenation of 
         * this sequence and another. A maximum length for the new 
         * sequence is also specified. 
         * 
         * @param length         the maximum length of the result
         * @param seq            the other sequence
         * 
         * @return the concatenated token sequence
         */
        public Sequence concat(int length, Sequence seq) {
            Sequence  res = new Sequence(length, this);

            if (seq.repeat) {
                res.repeat = true;
            }
            length -= this.length();
            if (length > seq.length()) {
                res.tokens.addAll(seq.tokens);
            } else {
                for (int i = 0; i < length; i++) {
                    res.tokens.add(seq.tokens.get(i));
                }
            }
            return res;
        }
        
        /**
         * Creates a new token sequence that is a subsequence of this
         * one.
         * 
         * @param start          the subsequence start position 
         * 
         * @return the new token subsequence
         */
        public Sequence subsequence(int start) {
            Sequence  res = new Sequence(length(), this);
    
            while (start > 0 && res.tokens.size() > 0) {
                res.tokens.remove(0);
                start--;
            }
            return res;
        }
    }
}