lookaheadset.cs

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

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

using System.Collections;
using System.Text;

namespace PerCederberg.Grammatica.Parser {

    /**
     * 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
     */
    internal 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.Count;
        }

        /**
         * 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.Count; i++) {
                seq = (Sequence) elements[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.Count; i++) {
                seq = (Sequence) elements[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;
            object     token;
            int        i;
        
            for (i = 0; i < elements.Count; i++) {
                token = ((Sequence) elements[i]).GetToken(0);
                if (token != null && !list.Contains(token)) {
                    list.Add(token);
                }
            }
            result = new int[list.Count];
            for (i = 0; i < list.Count; i++) {
                result[i] = (int) list[i];
            }
            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 bool IsRepetitive() {
            Sequence  seq;
            
            for (int i = 0; i < elements.Count; i++) {
                seq = (Sequence) elements[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 bool IsNext(Parser parser) {
            Sequence  seq;
            
            for (int i = 0; i < elements.Count; i++) {
                seq = (Sequence) elements[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 bool IsNext(Parser parser, int length) {
            Sequence  seq;
            
            for (int i = 0; i < elements.Count; i++) {
                seq = (Sequence) elements[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 bool IsOverlap(LookAheadSet set) {
            for (int i = 0; i < elements.Count; i++) {
                if (set.IsOverlap((Sequence) elements[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 bool IsOverlap(Sequence seq) {
            Sequence  elem;

            for (int i = 0; i < elements.Count; i++) {
                elem = (Sequence) elements[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 bool 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 bool Intersects(LookAheadSet set) {
            for (int i = 0; i < elements.Count; i++) {
                if (set.Contains((Sequence) elements[i])) {
                    return true;
                }
            }
            return false;
        }

        /**