lookaheadset.cs

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

         * 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.Count; i++) {
                if (elements[i].Equals(elem)) {
                    return (Sequence) elements[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.Count; i++) {
                Add((Sequence) set.elements[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.Count; i++) {
                Remove((Sequence) set.elements[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;
            object        value;
            
            for (int i = 0; i < elements.Count; i++) {
                seq = (Sequence) elements[i];
                value = seq.GetToken(0); 
                if (value != null && token == (int) value) {
                    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.Count; i++) {
                seq1 = (Sequence) elements[i];
                seq2 = set.FindSequence(seq1);
                if (seq2 != null && seq1.IsRepetitive()) {
                    result.Add(seq2);
                } else if (seq2 != null) {
                    result.Add(seq1);
                }
            }
            return result;
        }

        /**
         * 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.Count; i++) {
                first = (Sequence) elements[i];
                if (first.Length() >= maxLength) {
                    result.Add(first);
                } else if (first.Length() <= 0) {
                    result.AddAll(set);  
                } else {
                    for (int j = 0; j < set.elements.Count; j++) {
                        second = (Sequence) set.elements[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.Count; i++) {
                seq = (Sequence) elements[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.Count; i++) {
                first = (Sequence) elements[i];
                for (int j = 0; j < set.elements.Count; j++) {
                    second = (Sequence) set.elements[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.Count; i++) {
                seq = (Sequence) elements[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 override 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) {
            StringBuilder  buffer = new StringBuilder();
            Sequence       seq;

            buffer.Append("{");
            for (int i = 0; i < elements.Count; i++) {
                seq = (Sequence) elements[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 bool repeat = false;