Compiler Construction/State.java

// State.java
 
/*
    Copyright 2005 Takuya Murata
 
    This program 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 program 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
 */
 
import java.util.*;
import java.io.*;
 
public final class State {
    public static interface Delta {
        public void move (int input, Collection<State> result);
    }
 
    public static final Delta nil = new Delta () {
        public void move (int input, Collection<State> result) { }
    };
 
    public static final int
        EMPTY = -2, BEGIN_INPUT = -1, EOF = -1, ACCEPT = 0;
 
    public String label;    // for the debugging purpose.
    private Delta delta = nil;
 
    public State () {
        this.label = super.toString ().replaceAll ("^.+@", "@");
    }
 
    private State (String label, int i) {
        this.label = label + super.toString ().replaceAll ("^.+@", "@");
    }
 
    public State (String label) {
        this.label = label;
    }
 
    public void setTransition (final int entry, final State dest) {
        final Delta prev = delta;
        delta = new Delta () {
            public void move (int input, Collection<State> result) {
                if (entry == input)
                    result.add (dest);
                prev.move (input, result);
            }
        };
    }
 
    public void setTransition (final String inputs, final State dest) {
        final Delta prev = delta;
        delta = new Delta () {
            public void move (int input, Collection<State> result) {
                if (inputs.contains (input))
                    result.add (dest);
                prev.move (input, result);
            }
        };
    }
 
    public void setTransition (final Delta d) {
        final Delta prev = delta;
        delta = new Delta () {
            public void move (int input, Collection<State> result) {
                d.move (input, result);
                prev.move (input, result);
            }
        };
    }
 
    public static final State[] toArray (Collection<State> col) {
        return col.toArray (new State[col.size ()]);
    }
 
    public static Set<State> closure (Collection<State> t) {
        Set<State> ret = new HashSet<State> (t);
 
        for (;;) {
            Collection<State> u = new ArrayList<State> ();
            for (State s : t) {
                Delta d = s.delta;
                d.move (State.EMPTY, ret);
                d.move (State.EMPTY, u);
            }
            if (u.isEmpty ())
                break;
            else
                t = u;
        }
 
        return ret;
    }
 
    public static Set<State> move (Set<State> t, int input) {
        assert BEGIN_INPUT <= input && input < 256;
 
        Set<State> ret = new HashSet<State> ();
        for (State s : closure (t))
            s.delta.move (input, ret);
 
        return ret;
    }
 
    public State[] move (int input) {
        return toArray (move (Collections.singleton (this), input));
    }
 
    // A set of states reachable from this state without shifting an input.
    public State[] closure () {
        return toArray (closure (Collections.singleton (this)));
    }
 
    public State[] move (CharSequence string) {
        Set<State> ret = Collections.singleton (this);
 
        for (int i = 0; i < string.length (); i++)
            ret = move (ret, string.charAt (i));
 
        return toArray (ret);
    }
 
    private static class SingleItemSet<T> extends AbstractList<T> implements Set<T> {
        private T item = null;
 
        public int size () { return (item != null) ? 1 : 0; }
        public T get (int i) { return item; }
 
        public T set (int i, T item) {
            T ret = this.item;
            assert 0 <= i && i < size ();
            this.item = item;
            return ret;
        }
 
        public void add (int i, T item) {
            assert i == 0;
            this.item = item;
        }
 
        public T remove (int i) { return set (i, null); }
 
        public T first () { return item; }
    }
 
    public State moveDFA (int input) {
        if (input == EMPTY)
            return this;
 
        SingleItemSet<State> t = new SingleItemSet<State> ();
        delta.move (input, t);
        if (!t.isEmpty ())
            return t.first ();
        else
            return null;
    }
 
    public State moveDFA (CharSequence string) {
        State s = this;
        for (int i = 0; i < string.length (); i++) {
            s = s.moveDFA (string.charAt (i));
            if (s == null)
                return null;
        }
 
        return s;
    }
 
    private static State createState (Set<State> t, Map<Set<State>, State> table) {
        State existing = table.get (t);
        if (existing != null)
            return existing;
 
        // We now need to make a new state for this states set.
        State q = new State ("q" + table.size ());
        table.put (t, q);
 
        for (int i = BEGIN_INPUT; i < 256; i++) {
            assert i != EMPTY : i;
            Set<State> u = move (t, i);
            if (!u.isEmpty ())
                q.setTransition (i, createState (u, table));
        }
 
        return q;
    }
 
    public State toDFA () {
        Map<Set<State>, State> table = new HashMap<Set<State>, State> ();
        return createState (Collections.singleton (this), table);
    }
 
    private void prettyPrint (StringBuffer buf, Collection<State> marked) {
        if (marked.contains (this))
            return;
        marked.add (this);
 
        buf.append (label + "[");
        boolean notfirst = false;
        for (int i = BEGIN_INPUT; i < 256; i++) {
            Set<State> t = move (Collections.singleton (this), i);
            if (!t.isEmpty ()) {
                if (notfirst)
                    buf.append (", ");
                if (i == EMPTY)
                    buf.append ("@e");
                else if (i == ACCEPT)
                    buf.append ("@acc");
                else
                    buf.append ((char) i);
                buf.append (":" + t);
                notfirst = true;
            }
        }
        buf.append ("]\n");
 
        for (int i = BEGIN_INPUT; i < 256; i++) {
            Set<State> t = move (Collections.singleton (this), i);
            for (State s : t)
                s.prettyPrint (buf, marked);
        }
    }
 
    public String outputString () {
        Set<State> marked = new HashSet<State> ();
        StringBuffer buf = new StringBuffer ();
        this.prettyPrint (buf, marked);
        return buf.toString ();
    }
 
    public String toString () {
        return label;
    }
 
    // Create states and transitions for a string sequence
    public static final State[] stringSequence (CharSequence string) {
        int len = string.length ();
 
        State q[] = new State[len + 1]; // need s[len]
        for (int i = 0; i <= len; i++)
            q[i] = new State ("q" + i, 0);
 
        for (int i = 0; i < len; i++)
            q[i].setTransition (string.charAt (i), q[i + 1]);
 
        return new State[] { q[0], q[len] };
    }
 
    public static final State[] stringSequenceIgnoreCase (CharSequence string) {
        int len = string.length ();
 
        State q[] = new State[len + 1]; // need s[len]
        for (int i = 0; i <= len; i++)
            q[i] = new State ("q" + i, 0);
 
        for (int i = 0; i < len; i++) {
            char
              lower = Character.toLowerCase (string.charAt (i)),
              upper = Character.toUpperCase (lower);
            q[i].setTransition (lower, q[i + 1]);
            q[i].setTransition (upper, q[i + 1]);
        }
 
        return new State[] { q[0], q[len] };
    }
}