lookaheadset.java

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

/*
 * LookAheadSet.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;

import java.util.ArrayList;

/**
 * A token look-ahead set. This class contains a set of token id 
 * sequences. All sequences in the set are limited in length, so that
 * no single sequence is longer than a maximum value. This class also 
 * filters out duplicates. Each token sequence also contains a repeat
 * flag, allowing the look-ahead set to contain information about 
 * possible infinite repetitions of certain sequences. That 
 * information is important when conflicts arise between two 
 * look-ahead sets, as such a conflict cannot be resolved if the 
 * conflicting sequences can be repeated (would cause infinite loop). 
 *
 * @author   Per Cederberg, <per at percederberg dot net>
 * @version  1.1
 */
class LookAheadSet {

    /**
     * The set of token look-ahead sequences. Each sequence in 
     * turn is represented by an ArrayList with Integers for the
     * token id:s.
     */
    private ArrayList elements = new ArrayList();
    
    /**
     * The maximum length of any look-ahead sequence.
     */
    private int maxLength;

    /**
     * Creates a new look-ahead set with the specified maximum
     * length.
     * 
     * @param maxLength      the maximum token sequence length
     */
    public LookAheadSet(int maxLength) {
        this.maxLength = maxLength;
    }

    /**
     * Creates a duplicate look-ahead set, possibly with a different 
     * maximum length. 
     * 
     * @param maxLength      the maximum token sequence length
     * @param set            the look-ahead set to copy
     */
    public LookAheadSet(int maxLength, LookAheadSet set) {
        this(maxLength);
        addAll(set);
    }

    /**
     * Returns the size of this look-ahead set.
     * 
     * @return the number of token sequences in the set
     */
    public int size() {
        return elements.size();
    }

    /**
     * Returns the length of the shortest token sequence in this
     * set. This method will return zero (0) if the set is empty.
     * 
     * @return the length of the shortest token sequence
     */
    public int getMinLength() {
        Sequence  seq;
        int       min = -1;
        
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (min < 0 || seq.length() < min) {
                min = seq.length();
            }
        }
        return (min < 0) ? 0 : min;
    }

    /**
     * Returns the length of the longest token sequence in this
     * set. This method will return zero (0) if the set is empty.
     * 
     * @return the length of the longest token sequence
     */
    public int getMaxLength() {
        Sequence  seq;
        int       max = 0;
        
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (seq.length() > max) {
                max = seq.length();
            }
        }
        return max;
    }

    /**
     * Returns a list of the initial token id:s in this look-ahead 
     * set. The list returned will not contain any duplicates. 
     * 
     * @return a list of the inital token id:s in this look-ahead set
     */
    public int[] getInitialTokens() {
        ArrayList  list = new ArrayList();
        int[]      result;
        Integer    token;
        int        i;
        
        for (i = 0; i < elements.size(); i++) {
            token = ((Sequence) elements.get(i)).getToken(0);
            if (token != null && !list.contains(token)) {
                list.add(token);
            }
        }
        result = new int[list.size()];
        for (i = 0; i < list.size(); i++) {
            result[i] = ((Integer) list.get(i)).intValue();
        }
        return result;
    }

    /**
     * Checks if this look-ahead set contains a repetitive token
     * sequence.
     * 
     * @return true if at least one token sequence is repetitive, or
     *         false otherwise
     */
    public boolean isRepetitive() {
        Sequence  seq;

        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (seq.isRepetitive()) {
                return true;
            }
        }
        return false;
    }

    /**
     * Checks if the next token(s) in the parser match any token 
     * sequence in this set.
     *
     * @param parser         the parser to check
     *  
     * @return true if the next tokens are in the set, or
     *         false otherwise
     */
    public boolean isNext(Parser parser) {
        Sequence  seq;

        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (seq.isNext(parser)) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Checks if the next token(s) in the parser match any token 
     * sequence in this set.
     *
     * @param parser         the parser to check
     * @param length         the maximum number of tokens to check
     *  
     * @return true if the next tokens are in the set, or
     *         false otherwise
     */
    public boolean isNext(Parser parser, int length) {
        Sequence  seq;

        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            if (seq.isNext(parser, length)) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Checks if another look-ahead set has an overlapping token 
     * sequence. An overlapping token sequence is a token sequence
     * that is identical to another sequence, but for the length. I.e.
     * one of the two sequences may be longer than the other. 
     * 
     * @param set            the look-ahead set to check
     * 
     * @return true if there is some token sequence that overlaps, or
     *         false otherwise
     */
    public boolean isOverlap(LookAheadSet set) {
        for (int i = 0; i < elements.size(); i++) {
            if (set.isOverlap((Sequence) elements.get(i))) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Checks if a token sequence is overlapping. An overlapping token
     * sequence is a token sequence that is identical to another 
     * sequence, but for the length. I.e. one of the two sequences may
     * be longer than the other. 
     * 
     * @param seq            the token sequence to check
     * 
     * @return true if there is some token sequence that overlaps, or
     *         false otherwise
     */
    private boolean isOverlap(Sequence seq) {
        Sequence  elem;

        for (int i = 0; i < elements.size(); i++) {
            elem = (Sequence) elements.get(i);
            if (seq.startsWith(elem) || elem.startsWith(seq)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Checks if the specified token sequence is present in the
     * set.
     * 
     * @param elem           the token sequence to check
     * 
     * @return true if the sequence is present in this set, or
     *         false otherwise
     */
    private boolean contains(Sequence elem) {
        return findSequence(elem) != null;
    }

    /**
     * Checks if some token sequence is present in both this set 
     * and a specified one.
     * 
     * @param set            the look-ahead set to compare with
     * 
     * @return true if the look-ahead sets intersect, or
     *         false otherwise 
     */
    public boolean intersects(LookAheadSet set) {
        for (int i = 0; i < elements.size(); i++) {
            if (set.contains((Sequence) elements.get(i))) {
                return true;
            }
        }
        return false;
    }

    /**
     * Finds an identical token sequence if present in the set.
     * 
     * @param elem           the token sequence to search for
     * 
     * @return an identical the token sequence if found, or
     *         null if not found
     */
    private Sequence findSequence(Sequence elem) {
        for (int i = 0; i < elements.size(); i++) {
            if (elements.get(i).equals(elem)) {
                return (Sequence) elements.get(i);
            }
        }
        return null;
    }

    /**
     * Adds a token sequence to this set. The sequence will only be 
     * added if it is not already in the set. Also, if the sequence is
     * longer than the allowed maximum, a truncated sequence will be
     * added instead.
     * 
     * @param seq            the token sequence to add
     */
    private void add(Sequence seq) {
        if (seq.length() > maxLength) {
            seq = new Sequence(maxLength, seq);
        }
        if (!contains(seq)) {
            elements.add(seq);
        }
    }

    /**
     * Adds a new token sequence with a single token to this set. The 
     * sequence will only be added if it is not already in the set.
     * 
     * @param token          the token to add
     */
    public void add(int token) {
        add(new Sequence(false, token));
    }

    /**
     * Adds all the token sequences from a specified set. Only 
     * sequences not already in this set will be added.
     * 
     * @param set            the set to add from
     */
    public void addAll(LookAheadSet set) {
        for (int i = 0; i < set.elements.size(); i++) {
            add((Sequence) set.elements.get(i));
        }
    }

    /**
     * Adds an empty token sequence to this set. The sequence will 
     * only be added if it is not already in the set. 
     */
    public void addEmpty() {
        add(new Sequence());
    }
    
    /**
     * Removes a token sequence from this set.
     * 
     * @param seq            the token sequence to remove
     */
    private void remove(Sequence seq) {
        elements.remove(seq);
    }

    /**
     * Removes all the token sequences from a specified set. Only 
     * sequences already in this set will be removed.
     * 
     * @param set            the set to remove from
     */
    public void removeAll(LookAheadSet set) {
        for (int i = 0; i < set.elements.size(); i++) {
            remove((Sequence) set.elements.get(i));
        }
    }

    /**
     * Creates a new look-ahead set that is the result of reading the
     * specified token. The new look-ahead set will contain the 
     * rest of all the token sequences that started with the specified
     * token.
     * 
     * @param token          the token to read 
     * 
     * @return a new look-ahead set containing the remaining tokens 
     */
    public LookAheadSet createNextSet(int token) {
        LookAheadSet  result = new LookAheadSet(maxLength - 1);
        Sequence      seq;
        Integer       value;
        
        for (int i = 0; i < elements.size(); i++) {
            seq = (Sequence) elements.get(i);
            value = seq.getToken(0); 
            if (value != null && value.intValue() == token) {
                result.add(seq.subsequence(1));
            }
        }
        return result;
    }

    /**
     * Creates a new look-ahead set that is the intersection of
     * this set with another set. The token sequences in the net set
     * will only have the repeat flag set if it was set in both the
     * identical token sequences.
     * 
     * @param set            the set to intersect with
     * 
     * @return a new look-ahead set containing the intersection
     */
    public LookAheadSet createIntersection(LookAheadSet set) {
        LookAheadSet  result = new LookAheadSet(maxLength);
        Sequence      seq1;
        Sequence      seq2;

        for (int i = 0; i < elements.size(); i++) {
            seq1 = (Sequence) elements.get(i);
            seq2 = set.findSequence(seq1);
            if (seq2 != null && seq1.isRepetitive()) {
                result.add(seq2);
            } else if (seq2 != null) {
                result.add(seq1);
            }
        }
        return result;
    }

    /**