MAJOR: huge revamp of Sequence, Result, Reduction, Parser, Node, GSS

darcs-hash:20070326055257-5007d-e7f33e2199ea28d9bbbb799a81887378c0f1c524.gz

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 91ef765..c96ceee 100644 (file)
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -13,22 +13,31 @@ import java.lang.reflect.*;
 class GSS {
 
     Input input;
 class GSS {
 
     Input input;

-    public GSS(Input input) { this.input = input; }
+    private Parser parser;
+    public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}

     public Input getInput() { return input; }
 
     public Input getInput() { return input; }
 

-    // FIXME: right now, these are the performance bottleneck
-    HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
-
-    /** FIXME */
-    Forest.Many finalResult;
+    int numNewNodes = 0;
+    int numOldNodes = 0;
+    int viewPos = 0;
+    int numReductions = 0;

 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */

-    class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+    class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+
+        // FIXME: right now, these are the performance bottleneck
+        private HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();

 
 

-        public PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
+        public Forest.Many finalResult;
+        private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();

 
 

-        public void invoke(State st, Result result, Object o) {
-            //shifts++;
+        public void addReduction(Reduction r) {
+            //System.out.println("+ " + r);
+            parser.spin();
+            reductionQueue.add(r);
+        }
+        public void invoke(State st, Result result) {
+            parser.spin();

             good |= next.newNode(result, st, false);
         }
 
             good |= next.newNode(result, st, false);
         }
 

@@ -36,8 +45,8 @@ class GSS {
         final Tok token;
         final int pos;
 
         final Tok token;
         final int pos;
 

-        public IntPairMap<Node> hash;  /* ALLOC */
-        private boolean good;
+        public IntPairMap<Node> hash = new IntPairMap<Node>();  /* ALLOC */
+        private boolean good = false;

         private Phase next = null;
         private Phase prev;
         private Input.Location location;
         private Phase next = null;
         private Phase prev;
         private Input.Location location;

@@ -46,23 +55,54 @@ class GSS {
         
         private Forest forest;
 
         
         private Forest forest;
 

-        public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
-                     Input.Location nextLocation, Forest forest) throws ParseFailed {
+        public Phase(State startState) throws ParseFailed, IOException {
+            this(null, null);
+            Result primordealResult = new Result(null, null, null);
+            newNode(primordealResult, startState, true);
+        }
+        public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
+            this.location = input.getLocation();
+            this.token = (Tok)input.next();

             this.prevLocation = prev==null ? location : prev.getLocation();
             this.prev = prev;
             this.forest = forest;
             this.prevLocation = prev==null ? location : prev.getLocation();
             this.prev = prev;
             this.forest = forest;

-            this.pos = previous==null ? 0 : previous.pos+1;
-            this.token = token;
-            this.location = location;
-            this.nextLocation = nextLocation;
-            performed.clear();
-            hash = new IntPairMap<Node>();
-            good = false;
-            finalResult = null;
+            this.pos = prev==null ? 0 : prev.pos+1;
+            this.nextLocation = input.getLocation();

             if (prev != null) prev.shift(this, forest);
             if (prev != null) prev.shift(this, forest);

+            numReductions = 0;
+
+            int minPhasePos = Integer.MAX_VALUE;
+            int maxOrd = -1;
+            Reduction best = null;
+            //System.out.println("==============================================================================");
+            while(!reductionQueue.isEmpty()) {
+                Reduction r = reductionQueue.poll();
+                //System.out.println("- " + r);
+                if (r.parentPhase() != null)
+                    if (r.parentPhase().pos > minPhasePos)
+                        throw new Error();
+                r.perform();
+                if (r.parentPhase() != null) {
+                    if (r.parentPhase().pos < minPhasePos) {
+                        minPhasePos = r.parentPhase().pos;
+                        maxOrd = r.reduction().ord;
+                        best = r;
+                    } else if (r.parentPhase().pos == minPhasePos) {
+                        /*
+                        if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
+                            throw new Error("\n"+r+"\n"+best+"\n"+
+                                            Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
+                                            "\n"+(r.reduction().ord-best.reduction().ord));
+                        */
+                        maxOrd = r.reduction().ord;
+                        best = r;
+                    }
+                }
+                numReductions++;
+            }
+            if (token==null) shift(null, null);

         }
 
         }
 

-        public boolean isFrontier() { return next==null; }

         public boolean isDone() throws ParseFailed {
             if (token != null) return false;
             if (token==null && finalResult==null)
         public boolean isDone() throws ParseFailed {
             if (token != null) return false;
             if (token==null && finalResult==null)

@@ -74,12 +114,20 @@ class GSS {
         public Input.Location getLocation() { return location; }
         public Input.Region   getRegion() { return getPrevLocation().createRegion(getLocation()); }
         public Input.Location getNextLocation() { return nextLocation; }
         public Input.Location getLocation() { return location; }
         public Input.Region   getRegion() { return getPrevLocation().createRegion(getLocation()); }
         public Input.Location getNextLocation() { return nextLocation; }

+        public boolean        isFrontier() { return hash!=null; }

 
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
 
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */

-        public void shift(Phase next, Forest result) throws ParseFailed {
-            // this massively improves GC performance
-            if (prev!=null) prev.hash = null;
+        private void shift(Phase next, Forest result) throws ParseFailed {

             this.next = next;
             this.next = next;

+            // this massively improves GC performance
+            if (prev != null) {
+                IntPairMap<Node> h = prev.hash;
+                prev.hash = null;
+                prev.performed = null;
+                for(Node n : h)
+                    n.check();
+            }
+            numOldNodes = hash.size();

             for(Node n : hash.values()) {
                 if (token == null && n.state().isAccepting()) {
                     if (finalResult==null) finalResult = new Forest.Many();
             for(Node n : hash.values()) {
                 if (token == null && n.state().isAccepting()) {
                     if (finalResult==null) finalResult = new Forest.Many();

@@ -87,32 +135,28 @@ class GSS {
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;

-                n.state().invokeShifts(token, this, new Result(result, n, null), null);
+                n.state().invokeShifts(token, this, new Result(result, n, null));

             }
             }

-            for(Node n : hash.values()) n.check();
+            numNewNodes = next==null ? 0 : next.hash.size();
+            viewPos = this.pos;

             if (!good && token!=null) ParseFailed.error("unexpected character", this);
             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
             if (!good && token!=null) ParseFailed.error("unexpected character", this);
             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);

+            for(Node n : hash) n.check();

         }
 
         }
 

-        /** perform all reduction operations */
-        public void reduce() throws ParseFailed {
-            while(!reductionQueue.isEmpty())
-                reductionQueue.poll().perform();
-        }
-
-        public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {
+        void newNodeFromReduction(Result result, State state, Position reduction) {

             int pos = result.phase().pos;
             Sequence owner = reduction.owner();
             int pos = result.phase().pos;
             Sequence owner = reduction.owner();

-            for(Sequence s : owner.hates)
+            for(Sequence s : owner.hates())

                 if (performed.contains(pos, s))
                     return;
                 if (performed.contains(pos, s))
                     return;

-            for(Sequence s : owner.needs)
+            for(Sequence s : owner.needs())

                 if (!performed.contains(pos, s))
                     return;
             if (owner.needed_or_hated && !performed.contains(pos, owner))
                 performed.add(pos, owner);
             if (state!=null)
                 if (!performed.contains(pos, s))
                     return;
             if (owner.needed_or_hated && !performed.contains(pos, owner))
                 performed.add(pos, owner);
             if (state!=null)

-                newNode(result, state, fromEmptyReduction);
+                newNode(result, state, reduction.pos<=0);

         }
 
         /** add a new node (merging with existing nodes if possible)
         }
 
         /** add a new node (merging with existing nodes if possible)

@@ -122,16 +166,18 @@ class GSS {
          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
          */
          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
          */

-        public boolean newNode(Result result, State state, boolean fromEmptyReduction) {
+        private boolean newNode(Result result, State state, boolean fromEmptyReduction) {

             Node p = hash.get(state, result.phase());
             Node p = hash.get(state, result.phase());

-            if (p != null) { p.merge(result); return true; }
+            if (p != null) { p.addResult(result); return true; }

             do {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
                 if (token==null) break;
                 if (!state.canReduce(token)) return false;
             } while(false);
             do {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
                 if (token==null) break;
                 if (!state.canReduce(token)) return false;
             } while(false);

-            new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
+            Node n = new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
+            for(Object s : state.also)
+                newNode(new Result(null, n, null), (State)s, fromEmptyReduction);

             return true;
         }
 
             return true;
         }
 

@@ -155,6 +201,17 @@ class GSS {
         public boolean isTransparent() { return false; }
         public boolean isHidden() { return false; }
 
         public boolean isTransparent() { return false; }
         public boolean isHidden() { return false; }
 

+        public void dumpGraphViz(String filename) throws IOException {
+            FileOutputStream fos = new FileOutputStream(filename);
+            PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
+            GraphViz gv = new GraphViz();
+            for(Object n : this)
+                ((Node)n).toGraphViz(gv);
+            gv.dump(p);
+            p.flush();
+            p.close();
+        }
+

     }
 
 }
     }
 
 }

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index 1d5e05a..b734a8f 100644 (file)
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -11,41 +11,33 @@ import java.lang.reflect.*;
 
 /** a node in the GSS */
 final class Node
 
 /** a node in the GSS */
 final class Node

-    implements Invokable<Position, Boolean, Result>,
+    implements Invokable<Position, Result>,

                IntegerMappable,
                GraphViz.ToGraphViz,
                Iterable<Result> {
 
     /** which GSS.Phase this Node belongs to */
                IntegerMappable,
                GraphViz.ToGraphViz,
                Iterable<Result> {
 
     /** which GSS.Phase this Node belongs to */

-    public  GSS.Phase phase() { return phase; }
+    public GSS.Phase phase() { return phase; }

     public Iterator<Result> iterator() { return results.iterator(); }
     public Parser.Table.State state() { return state; }
 
     public int toInt() { return idx; }
 
     public Iterator<Result> iterator() { return results.iterator(); }
     public Parser.Table.State state() { return state; }
 
     public int toInt() { return idx; }
 

-    public boolean merge(Result r) {
-        if (results.contains(r)) return true;
-        results.add(r);
-        r.addChild(this);
-        if (fromEmptyReduction) return false;
-        state.invokeReductions(phase().getToken(), this, false, r);
-        return false;
-    }
+    boolean destroyed = false;

 
 

-    private boolean destroyed = false;
-    public boolean check() {
+    public void check() {
+        if (destroyed) return;

         boolean dead = true;
         // - all nodes must have a parent
         // - non-doomed nodes must either:
         //      - be on the frontier or
         //      - have a non-doomed node closer to the frontier than themself
         boolean dead = true;
         // - all nodes must have a parent
         // - non-doomed nodes must either:
         //      - be on the frontier or
         //      - have a non-doomed node closer to the frontier than themself

-

         if (phase.isFrontier()) dead = false;
         for(Result r : children)
         if (phase.isFrontier()) dead = false;
         for(Result r : children)

-            if (state.doomed) { if (r.usedByAnyNode()) dead = false; }
-            else              { if (r.usedByNonDoomedNode()) dead = false; }
+            if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } }
+            else              { if (r.usedByNonDoomedNode()) { dead = false; break; } }

         dead |= results.size()==0;
         dead |= results.size()==0;

-        if (!dead || destroyed) return dead;
+        if (!dead || destroyed) return;

         destroyed = true;
         while(children.size()>0)
             for(Result r : children) {
         destroyed = true;
         while(children.size()>0)
             for(Result r : children) {

@@ -57,10 +49,10 @@ final class Node
             for(Result r : results) {
                 results.remove(r);
                 r.removeChild(this);
             for(Result r : results) {
                 results.remove(r);
                 r.removeChild(this);

-                r.check();

                 break;
             }
                 break;
             }

-        return dead;
+        results = null;
+        children = null;

     }
 
     //////////////////////////////////////////////////////////////////////
     }
 
     //////////////////////////////////////////////////////////////////////

@@ -74,19 +66,18 @@ final class Node
     //private       FastSet<Result> results = new FastSet<Result>();
     private       HashSet<Result> results = new HashSet<Result>();
     private       HashSet<Result> children = new HashSet<Result>();
     //private       FastSet<Result> results = new FastSet<Result>();
     private       HashSet<Result> results = new HashSet<Result>();
     private       HashSet<Result> children = new HashSet<Result>();

-    public void removeChild(Result child) { children.remove(child); }
-    public void removeResult(Result result) { results.remove(result); }
-    public void addChild(Result child) { children.add(child); }

 
 

-    public final void invoke(Position r, Boolean emptyProductions, Result only) {
+    public final void invoke(Position r, Result only) {
+        boolean emptyProductions = only==null;

         if (emptyProductions != (r.pos==0)) return;
         if (emptyProductions != (r.pos==0)) return;

-        if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase());
+        if (r.pos==0) new Result(r.zero(phase().getLocation().createRegion(phase().getLocation())), this, r, phase());

         else          reduce(r, r.pos-1, phase(), only);
     }
 
     private void reduce(Position r, int pos, GSS.Phase target, Result only) {
         Forest[] holder = r.holder;
         Forest old = holder[pos];
         else          reduce(r, r.pos-1, phase(), only);
     }
 
     private void reduce(Position r, int pos, GSS.Phase target, Result only) {
         Forest[] holder = r.holder;
         Forest old = holder[pos];

+        if (results==null) return;   // FIXME: this should not happen

         for(Result res : results)
             if (only == null || res == only) {
                 Node child = res.parent();
         for(Result res : results)
             if (only == null || res == only) {
                 Node child = res.parent();

@@ -97,27 +88,37 @@ final class Node
         holder[pos] = old;
     }
 
         holder[pos] = old;
     }
 

-    void finish(Position r, Forest forest, GSS.Phase target) {
-        Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
-        Result result = new Result(forest, this, r);
-        target.newNodeFromReduction(result, state0, r.pos<=0, r);
-    }
-

     Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
         this.phase = phase;
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;
     Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
         this.phase = phase;
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;

-        results.add(result);
-        result.addChild(this);

         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
         phase.hash.put(state, result.phase(), this);
         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
         phase.hash.put(state, result.phase(), this);

+        addResult(result);
+        state.invokeEpsilonReductions(phase().token, this);
+    }

 
 

-        for(Object s : state.also)
-            phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction);
+    // Add/Remove Children/Results //////////////////////////////////////////////////////////////////////////////

 
 

-        state.invokeReductions(phase().token, this, true, null);
-        if (!fromEmptyReduction)
-            state.invokeReductions(phase().getToken(), this, false, null);
+    public void removeChild(Result child)   {
+        if (children==null) return;
+        children.remove(child);
+        check();
+    }
+    public void removeResult(Result result) {
+        if (results==null) return;
+        results.remove(result);
+        check();
+    }
+    public void addChild(Result child)      {
+        if (children==null) return;   // FIXME: this should not happen
+        children.add(child);
+    }
+    public void addResult(Result r) {
+        if (results.contains(r)) return;
+        results.add(r);
+        r.addChild(this);
+        if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r);

     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////
     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index adf24c4..c2e7023 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -9,96 +9,73 @@ import java.util.*;
 
 /** a parser which translates an Input<Token> into a Forest<NodeType> */
 public abstract class Parser<Token, NodeType> {
 
 /** a parser which translates an Input&lt;Token&gt; into a Forest&lt;NodeType&gt; */
 public abstract class Parser<Token, NodeType> {

+

     protected final Table<Token> pt;
 
     /** create a parser to parse the grammar with start symbol <tt>u</tt> */
     public Parser(Union u, Topology<Token> top)  { this.pt = new Table<Token>(u, top); }
     protected final Table<Token> pt;
 
     /** create a parser to parse the grammar with start symbol <tt>u</tt> */
     public Parser(Union u, Topology<Token> top)  { this.pt = new Table<Token>(u, top); }

-    Parser(Table<Token> pt)               { this.pt = pt; }

 
     /** implement this method to create the output forest corresponding to a lone shifted input token */
     public abstract Forest<NodeType> shiftToken(Token t, Input.Location newloc);
 
 
     /** implement this method to create the output forest corresponding to a lone shifted input token */
     public abstract Forest<NodeType> shiftToken(Token t, Input.Location newloc);
 

-    boolean helpgc = true;
-

     public String toString() { return pt.toString(); }
 
     public String toString() { return pt.toString(); }
 

-    /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
-    public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
-        GSS gss = new GSS(input);
-        Input.Location loc = input.getLocation();
-        Token tok = input.next();
-        GSS.Phase current = gss.new Phase<Token>(null, null, tok, loc, input.getLocation(), null);
-        current.newNode(new Result(Forest.create(loc.createRegion(loc), null, null, false), null, null), pt.start, true);
-        int count = 1;
-        for(int idx=0;;idx++) {
-            Input.Location oldloc = loc;
-            current.reduce();
-            Forest forest = current.token==null ? null : shiftToken((Token)current.token, loc);
-            loc = input.getLocation();
-            Token nextToken = input.next();
-            GSS.Phase next = gss.new Phase<Token>(current, current, nextToken, loc, input.getLocation(), forest);
-
-            /*
-            FileOutputStream fos = new FileOutputStream("out-"+idx+".dot");
-            PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
-            GraphViz gv = new GraphViz();
-            for(Object n : current)
-                ((Node)n).toGraphViz(gv);
-            gv.dump(p);
-            p.flush();
-            p.close();
-            */
-
-            count = next.size();
-            if (current.isDone()) return (Forest<NodeType>)gss.finalResult;
-            current = next;
+    private boolean verbose = false;;
+    private static final char[] spin = new char[] { '-', '\\', '|', '/' };
+    private int spinpos = 0;
+    private long last = 0;
+    void spin() {
+        if (verbose) {
+            long now = System.currentTimeMillis();
+            if (now-last < 100) return;
+            last = now;
+            System.err.print("\r  " + spin[spinpos++ % (spin.length)]+ANSI.clreol()+"\r");

         }
     }
 
         }
     }
 

-    // Table //////////////////////////////////////////////////////////////////////////////
-
-    /** an SLR(1) parse table which may contain conflicts */
-    static class Table<Token> extends Walk.Cache {
-
-        public String toString() {
-            StringBuffer sb = new StringBuffer();
-            sb.append("parse table");
-            for(State<Token> state : all_states) {
-                sb.append("  " + state + "\n");
-                for(Topology<Token> t : state.shifts) {
-                    sb.append("      shift  \""+
-                              new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => ");
-                    for(State st : state.shifts.getAll(t))
-                        sb.append(st.idx+"  ");
-                    sb.append("\n");
+    /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
+    public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
+        verbose = System.getProperty("sbp.verbose", null) != null;
+        spinpos = 0;
+        try {
+            GSS gss = new GSS(input, this);
+            for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
+                
+                if (verbose) {
+                    String s;
+                    s = "  " + spin[spinpos++ % (spin.length)]+" parsing ";
+                    s += input.getName();
+                    s += " "+input.getLocation();
+                    while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s;
+                    String y = "@"+gss.viewPos+" ";
+                    while(y.length() < 9) y = " " + y;
+                    s += y;
+                    //s += "   doom="+Node.doomedNodes;
+                    //while(s.length() < 40) s = s + " ";
+                    s += "   nodes="+gss.numOldNodes;
+                    while(s.length() < 50) s = s + " ";
+                    s += " shifted="+gss.numNewNodes;
+                    while(s.length() < 60) s = s + " ";
+                    s += " reductions="+gss.numReductions;
+                    System.err.print("\r"+s+ANSI.clreol()+"\r");

                 }
                 }

-                for(Topology<Token> t : state.reductions)
-                    sb.append("      reduce \""+
-                              new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => " +
-                              state.reductions.getAll(t) + "\n");
-                for(Sequence s : state.gotoSetNonTerminals.keySet())
-                    sb.append("      goto   "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n");
+                
+                // FIXME: make sure all the locations line up properly in here
+                if (current.isDone()) return (Forest<NodeType>)current.finalResult;
+                Forest forest = shiftToken((Token)current.token, input.getLocation());
+                current = gss.new Phase<Token>(current, forest);

             }
             }

-            return sb.toString();
+        } finally {
+            if (verbose)
+                System.err.print("\r                                                                                \r");

         }
         }

+    }

 
 

-        public final Walk.Cache cache = this;

 
 

-        private void walk(Element e, HashSet<SequenceOrElement> hs) {
-            if (e==null) return;
-            if (hs.contains(e)) return;
-            hs.add(e);
-            if (e instanceof Atom) return;
-            for(Sequence s : (Union)e)
-                walk(s, hs);
-        }
-        private void walk(Sequence s, HashSet<SequenceOrElement> hs) {
-            hs.add(s);
-            for(Position p = s.firstp(); p != null; p = p.next())
-                walk(p.element(), hs);
-            for(Sequence ss : s.needs()) walk(ss, hs);
-            for(Sequence ss : s.hates()) walk(ss, hs);
-        }
+    // Table //////////////////////////////////////////////////////////////////////////////
+
+    /** an SLR(1) parse table which may contain conflicts */
+    static class Table<Token> extends Cache {

 
         /** the start state */
         public  final State<Token>   start;
 
         /** the start state */
         public  final State<Token>   start;

@@ -111,24 +88,18 @@ public abstract class Parser<Token, NodeType> {
         HashSet<State<Token>>   all_states    = new HashSet<State<Token>>();
         HashMap<HashSet<Position>,State<Token>>   doomed_states    = new HashMap<HashSet<Position>,State<Token>>();
         HashMap<HashSet<Position>,State<Token>>   normal_states    = new HashMap<HashSet<Position>,State<Token>>();
         HashSet<State<Token>>   all_states    = new HashSet<State<Token>>();
         HashMap<HashSet<Position>,State<Token>>   doomed_states    = new HashMap<HashSet<Position>,State<Token>>();
         HashMap<HashSet<Position>,State<Token>>   normal_states    = new HashMap<HashSet<Position>,State<Token>>();

-        HashSet<SequenceOrElement>                all_elements  = new HashSet<SequenceOrElement>();

 
         /** construct a parse table for the given grammar */
         public Table(Topology top) { this("s", top); }
         public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); }
         public Table(Union ux, Topology top) {
 
         /** construct a parse table for the given grammar */
         public Table(Topology top) { this("s", top); }
         public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); }
         public Table(Union ux, Topology top) {

+            super(ux, top);

             Union start0 = new Union("0");
             Union start0 = new Union("0");

-            start0.add(new Sequence.Singleton(ux));
-
-            for(Sequence s : start0) cache.eof.put(s, true);
-            cache.eof.put(start0, true);
+            Sequence seq0 = new Sequence.Singleton(ux);
+            start0.add(seq0);
+            buildFollowSet(seq0, top, true);

 
             // construct the set of states
 
             // construct the set of states

-            walk(start0, all_elements);
-            for(SequenceOrElement e : all_elements)
-                cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk());
-            for(SequenceOrElement e : all_elements)
-                cache.ys2.addAll(e, new Walk.YieldSet2(e, cache).walk());

             HashSet<Position> hp = new HashSet<Position>();
             reachable(start0, hp);
 
             HashSet<Position> hp = new HashSet<Position>();
             reachable(start0, hp);
 

@@ -144,17 +115,19 @@ public abstract class Parser<Token, NodeType> {
                         state.accept = true;
 
                     if (isRightNullable(p)) {
                         state.accept = true;
 
                     if (isRightNullable(p)) {

-                        Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache);
-                        Topology follow = wf.walk(p.owner());
+                        Topology<Token> follow = (Topology<Token>)follow(p.owner());

                         for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {
                         for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {

-                            Atom set = new Walk.EpsilonFollowSet(new edu.berkeley.sbp.chr.CharAtom(top.empty().complement()),
-                                                                 new edu.berkeley.sbp.chr.CharAtom(top.empty()),
-                                                                 cache).walk(p2.element());
-                            follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element()));
+                            if (!(p2.element() instanceof Union)) throw new Error("impossible");
+                            Union u = (Union)p2.element();
+                            Atom set = new edu.berkeley.sbp.chr.CharAtom(new edu.berkeley.sbp.chr.CharTopology((Topology<Character>)epsilonFollowSet(u)));
+                            Element p2e = p2.element();
+                            if (p2e instanceof Union)
+                                for(Sequence p2es : ((Union)p2e))
+                                    follow = follow.intersect(follow(p2es));

                             if (set != null) follow = follow.intersect(set.getTokenTopology());
                         }
                         state.reductions.put(follow, p);
                             if (set != null) follow = follow.intersect(set.getTokenTopology());
                         }
                         state.reductions.put(follow, p);

-                        if (wf.includesEof()) state.eofReductions.add(p);
+                        if (followEof.contains(p.owner())) state.eofReductions.add(p);

                     }
 
                     // if the element following this position is an atom, copy the corresponding
                     }
 
                     // if the element following this position is an atom, copy the corresponding

@@ -170,6 +143,7 @@ public abstract class Parser<Token, NodeType> {
                 }
 
             // crude algorithm to assing an ordinal ordering to every position
                 }
 
             // crude algorithm to assing an ordinal ordering to every position

+            // al will be sorted in DECREASING order (al[0] >= al[1])

             ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
             for(State s : all_states) {
                 for(Object po : s) {
             ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
             for(State s : all_states) {
                 for(Object po : s) {

@@ -177,55 +151,83 @@ public abstract class Parser<Token, NodeType> {
                     if (al.contains(p)) continue;
                     int i=0;
                     for(; i<al.size(); i++) {
                     if (al.contains(p)) continue;
                     int i=0;
                     for(; i<al.size(); i++) {

-                        if (p.compareTo(al.get(i), cache) > 0)
+                        if (comparePositions(p, al.get(i)) < 0)

                             break;
                     }
                     al.add(i, p);
                 }
             }
                             break;
                     }
                     al.add(i, p);
                 }
             }

-            for(int i=0; i<al.size(); i++)
-                al.get(i).ord = i;
-        }
+            // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
+            // sort in increasing order...
+            OUTER: while(true) {
+                for(int i=0; i<al.size(); i++)
+                    for(int j=i+1; j<al.size(); j++)
+                        if (comparePositions(al.get(i), al.get(j)) > 0) {
+                            Sequence.Position p = al.remove(j);
+                            al.add(i, p);
+                            continue OUTER;
+                        }
+                break;
+            }
+
+            int j = 1;
+            int pk = 0;
+            for(int i=0; i<al.size(); i++) {
+                boolean inc = false;
+                for(int k=pk; k<i; k++) {
+                    if (comparePositions(al.get(k), al.get(i)) > 0)
+                        { inc = true; break; }
+                }
+                inc = true;
+                if (inc) {
+                    j++;
+                    pk = i;
+                }
+                al.get(i).ord = j;
+            }

 
 

-        private boolean isRightNullable(Position p) {
-            if (p.isLast()) return true;
-            if (!possiblyEpsilon(p.element())) return false;
-            return isRightNullable(p.next());
+            /*
+            for(int i=0; i<al.size(); i++)
+                if (isRightNullable(al.get(i)))
+                    System.out.println(al.get(i).ord + "   " + al.get(i));
+            */
+            //mastercache = this;

         }
 
         /** a single state in the LR table and the transitions possible from it */
         }
 
         /** a single state in the LR table and the transitions possible from it */

-

         class State<Token> implements IntegerMappable, Iterable<Position> {
         
             public  final     int               idx    = master_state_idx++;
             private final     HashSet<Position> hs;
             public HashSet<State<Token>> also = new HashSet<State<Token>>();
 
         class State<Token> implements IntegerMappable, Iterable<Position> {
         
             public  final     int               idx    = master_state_idx++;
             private final     HashSet<Position> hs;
             public HashSet<State<Token>> also = new HashSet<State<Token>>();
 

-            public transient HashMap<Sequence,State<Token>>         gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
+            public  transient HashMap<Sequence,State<Token>>         gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();

             private transient TopologicalBag<Token,State<Token>>     gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 
             private transient TopologicalBag<Token,State<Token>>     gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 

-            private           TopologicalBag<Token,Position> reductions          = new TopologicalBag<Token,Position>();
-            private           HashSet<Position>              eofReductions       = new HashSet<Position>();
-            private           TopologicalBag<Token,State<Token>>     shifts              = new TopologicalBag<Token,State<Token>>();
-            private           boolean                         accept              = false;
+            private           TopologicalBag<Token,Position>      reductions          = new TopologicalBag<Token,Position>();
+            private           HashSet<Position>                   eofReductions       = new HashSet<Position>();
+            private           TopologicalBag<Token,State<Token>>  shifts              = new TopologicalBag<Token,State<Token>>();
+            private           boolean                             accept              = false;

 
 

-            private VisitableMap<Token,State<Token>> oshifts = null;
-            private VisitableMap<Token,Position> oreductions = null;
+            private VisitableMap<Token,State<Token>> oshifts     = null;
+            private VisitableMap<Token,Position>     oreductions = null;

 
             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 
 
             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 

-            boolean             isAccepting()           { return accept; }
-            public Iterator<Position>  iterator()       { return hs.iterator(); }
-
-            boolean             canShift(Token t)         { return oshifts!=null && oshifts.contains(t); }
-            <B,C> void          invokeShifts(Token t, Invokable<State<Token>,B,C> irbc, B b, C c) {
-                oshifts.invoke(t, irbc, b, c);
+            boolean                    isAccepting()           { return accept; }
+            public Iterator<Position>  iterator()              { return hs.iterator(); }
+            boolean                    canShift(Token t)       { return oshifts!=null && oshifts.contains(t); }
+            void                       invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
+            boolean                    canReduce(Token t)        {
+                return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
+            void          invokeEpsilonReductions(Token t, Node node) {
+                if (t==null) for(Position r : eofReductions) node.invoke(r, null);
+                else         oreductions.invoke(t, node, null);

             }
             }

-
-            boolean             canReduce(Token t)        { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
-            <B,C> void          invokeReductions(Token t, Invokable<Position,B,C> irbc, B b, C c) {
-                if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c);
-                else         oreductions.invoke(t, irbc, b, c);
+            void          invokeReductions(Token t, Node node, Result b) {
+                //System.err.println("\rinvokage:  " + this);
+                if (t==null) for(Position r : eofReductions) node.invoke(r, b);
+                else         oreductions.invoke(t, node, b);

             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////
             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////

@@ -233,7 +235,7 @@ public abstract class Parser<Token, NodeType> {
             /**
              *  create a new state consisting of all the <tt>Position</tt>s in <tt>hs</tt>
              *  @param hs           the set of <tt>Position</tt>s comprising this <tt>State</tt>
             /**
              *  create a new state consisting of all the <tt>Position</tt>s in <tt>hs</tt>
              *  @param hs           the set of <tt>Position</tt>s comprising this <tt>State</tt>

-             *  @param all_elements the set of all elements (Atom instances need not be included)
+             *  @param all the set of all elements (Atom instances need not be included)

              *  
              *   In principle these two steps could be merged, but they
              *   are written separately to highlight these two facts:
              *  
              *   In principle these two steps could be merged, but they
              *   are written separately to highlight these two facts:

@@ -267,7 +269,7 @@ public abstract class Parser<Token, NodeType> {
                     for(Sequence s : p.owner().needs()) {
                         if (hs.contains(s.firstp())) continue;
                         HashSet<Position> h2 = new HashSet<Position>();
                     for(Sequence s : p.owner().needs()) {
                         if (hs.contains(s.firstp())) continue;
                         HashSet<Position> h2 = new HashSet<Position>();

-                        reachable(s.firstp(), h2);
+                        reachable(s, h2);

                         also.add(mkstate(h2, true));
                     }
                     for(Sequence s : p.owner().hates()) {
                         also.add(mkstate(h2, true));
                     }
                     for(Sequence s : p.owner().hates()) {

@@ -302,43 +304,35 @@ public abstract class Parser<Token, NodeType> {
                     ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed));
                 }
 
                     ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed));
                 }
 

-                // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction),
-                //         compute the closure over every position in this set which is followed by a symbol
-                //         which could yield the Element in question.
+                // Step 2: for every Sequence, compute the closure over every position in this set which
+                //         is followed by a symbol which could yield the Sequence.

                 //
                 //         "yields" [in one or more step] is used instead of "produces" [in exactly one step]
                 //         to avoid having to iteratively construct our set of States as shown in most
                 //         expositions of the algorithm (ie "keep doing XYZ until things stop changing").
 
                 //
                 //         "yields" [in one or more step] is used instead of "produces" [in exactly one step]
                 //         to avoid having to iteratively construct our set of States as shown in most
                 //         expositions of the algorithm (ie "keep doing XYZ until things stop changing").
 

-                HashMapBag<SequenceOrElement,Position> move = new HashMapBag<SequenceOrElement,Position>();
-                for(Position p : hs) {
-                    Element e = p.element();
-                    if (e==null) continue;
-                    for(SequenceOrElement y : cache.ys2.getAll(e)) {
-                        //System.out.println(e + " yields " + y);
-                        HashSet<Position> hp = new HashSet<Position>();
-                        reachable(p.next(), hp);
-                        move.addAll(y, hp);
-                    }
-                }
-                OUTER: for(SequenceOrElement y : move) {
+                HashMapBag<Sequence,Position> move = new HashMapBag<Sequence,Position>();
+                for(Position p : hs)
+                    if (!p.isLast() && p.element() instanceof Union)
+                        for(Sequence s : ((Union)p.element())) {
+                            HashSet<Position> hp = new HashSet<Position>();
+                            reachable(p.next(), hp);
+                            move.addAll(s, hp);
+                        }
+                OUTER: for(Sequence y : move) {
+                    // if a reduction is "lame", it should wind up in the dead_state after reducing

                     HashSet<Position> h = move.getAll(y);
                     State<Token> s = mkstate(h, doomed);
                     HashSet<Position> h = move.getAll(y);
                     State<Token> s = mkstate(h, doomed);

-                    // if a reduction is "lame", it should wind up in the dead_state after reducing
-                    if (y instanceof Sequence) {
-                        for(Position p : hs) {
-                            if (p.element() != null && (p.element() instanceof Union)) {
-                                Union u = (Union)p.element();
-                                for(Sequence seq : u)
-                                    if (seq.needs.contains((Sequence)y) || seq.hates.contains((Sequence)y)) {
-                                        // FIXME: what if there are two "routes" to get to the sequence?
-                                        ((HashMap)gotoSetNonTerminals).put((Sequence)y, dead_state);
-                                        continue OUTER;
-                                    }
-                            }
-                        }
-                        gotoSetNonTerminals.put((Sequence)y, s);
-                    }
+                    for(Position p : hs)
+                        if (p.element() != null && (p.element() instanceof Union))
+                            for(Sequence seq : ((Union)p.element()))
+                                if (seq.needs.contains(y) || seq.hates.contains(y)) {
+                                    // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched
+                                    //        and also directly lamely matched
+                                    ((HashMap)gotoSetNonTerminals).put(y, dead_state);
+                                    continue OUTER;
+                                }
+                    gotoSetNonTerminals.put(y, s);

                 }
             }
 
                 }
             }
 

@@ -355,6 +349,7 @@ public abstract class Parser<Token, NodeType> {
                 }
                 return st.toString();
             }
                 }
                 return st.toString();
             }

+

             public String toString() {
                 StringBuffer ret = new StringBuffer();
                 ret.append("state["+idx+"]: ");
             public String toString() {
                 StringBuffer ret = new StringBuffer();
                 ret.append("state["+idx+"]: ");

@@ -362,9 +357,30 @@ public abstract class Parser<Token, NodeType> {
                 return ret.toString();
             }
 
                 return ret.toString();
             }
 

-            public Walk.Cache cache() { return cache; }

             public int toInt() { return idx; }
         }
             public int toInt() { return idx; }
         }

+
+        public String toString() {
+            StringBuffer sb = new StringBuffer();
+            sb.append("parse table");
+            for(State<Token> state : all_states) {
+                sb.append("  " + state + "\n");
+                for(Topology<Token> t : state.shifts) {
+                    sb.append("      shift  \""+
+                              new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => ");
+                    for(State st : state.shifts.getAll(t))
+                        sb.append(st.idx+"  ");
+                    sb.append("\n");
+                }
+                for(Topology<Token> t : state.reductions)
+                    sb.append("      reduce \""+
+                              new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => " +
+                              state.reductions.getAll(t) + "\n");
+                for(Sequence s : state.gotoSetNonTerminals.keySet())
+                    sb.append("      goto   "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n");
+            }
+            return sb.toString();
+        }

     }
 
     // Helpers //////////////////////////////////////////////////////////////////////////////
     }
 
     // Helpers //////////////////////////////////////////////////////////////////////////////

@@ -384,5 +400,5 @@ public abstract class Parser<Token, NodeType> {
         h.add(p);
         if (p.element() != null) reachable(p.element(), h);
     }
         h.add(p);
         if (p.element() != null) reachable(p.element(), h);
     }

-
+    //public static Cache mastercache = null;

 }
 }

diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java
index 684fbf8..5e59a4e 100644 (file)
--- a/src/edu/berkeley/sbp/Reduction.java
+++ b/src/edu/berkeley/sbp/Reduction.java
@@ -1,90 +1,47 @@
 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
 
 package edu.berkeley.sbp;
 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
 
 package edu.berkeley.sbp;

-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Parser.Table.*;

 import edu.berkeley.sbp.Sequence.Position;
 import edu.berkeley.sbp.Sequence.Position;

-import java.io.*;
-import java.util.*;
-import java.lang.reflect.*;

 
 final class Reduction implements Comparable<Reduction> {
 
 
 final class Reduction implements Comparable<Reduction> {
 

-    public Position position;
-    public GSS.Phase phase;
-    public Forest result;
-    public Node node;
-    boolean done = false;
+    private Position reduction;
+    private GSS.Phase phase;
+    private Forest forest;
+    private Node parent;

     
     

-    public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
-        this.position = position;
-        this.result = result;
+    public Reduction(Node parent, Position reduction, Forest forest, GSS.Phase target) {
+        this.reduction = reduction;
+        this.forest = forest;

         this.phase = target;
         this.phase = target;

-        this.node = node;
-        target.reductionQueue.add(this);
-    }
-
-    public void perform() {
-        if (done) return;
-        done = true;
-        node.finish(position, result, phase);
+        this.parent = parent;
+        target.addReduction(this);

     }
 
     public int compareTo(Reduction r) {
     }
 
     public int compareTo(Reduction r) {

-        int ret = compareTo0(r);
-        if (ret != 0) return -1 * ret;
-        return (position.ord - r.position.ord);
-    }
-
-    private static boolean isRightNullable(Walk.Cache c, Position p) {
-        if (p.isLast()) return true;
-        if (!c.possiblyEpsilon(p.element())) return false;
-        return isRightNullable(c, p.next());
-    }
-
-    public static boolean canKill(Walk.Cache cache, Position mep, Position himp) {
-        if (!isRightNullable(cache, mep))  return false;
-        if (!isRightNullable(cache, himp)) return false;
-        Sequence me  = mep.owner();
-        Sequence him = himp.owner();
-        Boolean b = me.canKill.get(him);
-        if (b!=null) return b;
-        for(Sequence killer : him.hates()) {
-            HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
-            if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
+        if (parent.phase()!=null || r.parent.phase()!=null) {
+            if (parent.phase()==null) return 1;
+            if (r.parent.phase()==null) return -1;
+            if (parent.phase().pos < r.parent.phase().pos) return 1;
+            if (parent.phase().pos > r.parent.phase().pos) return -1;

         }
         }

-        me.canKill.put(him, false);
-        return false;
+        /*
+        int master = Parser.mastercache.comparePositions(reduction(), r.reduction());
+        if (master != 0 && master != signum(reduction.ord - r.reduction.ord))
+            throw new Error("master="+master+" and a="+reduction.ord+" and b="+r.reduction.ord+"\n"+reduction+"\n"+r.reduction);
+        */
+        return reduction.ord - r.reduction.ord;

     }
 
     }
 

-    public static final int LESS_THAN = -1;
-    public static final int EQUAL_TO = 0;
-    public static final int GREATER_THAN = 1;
-
-    public int compareTo0(Reduction n) {
-        if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
-        if (targetPhase()==null) return LESS_THAN;
-        if (n.targetPhase()==null) return GREATER_THAN;
-        if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
-        if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
-        return 0;
+    private int signum(int x) {
+        if (x==0) return 0;
+        if (x<0) return -1;
+        return 1;

     }
     }

-    public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
-    public GSS.Phase targetPhase() { return node.phase(); }

 
 

-    public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
-        if (!isRightNullable(cache, mep))  return false;
-        if (!isRightNullable(cache, himp)) return false;
-        Sequence me  = mep.owner();
-        Sequence him = himp.owner();
-        Boolean b = me.canNeed.get(him);
-        if (b!=null) return b;
-        for(Sequence needer : him.needs()) {
-            HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
-            if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
-        }
-        me.canNeed.put(him, false);
-        return false;
-    }
+    public void perform() { new Result(forest, parent, reduction, phase); }
+    public GSS.Phase parentPhase() { return parent.phase(); }
+    public Position reduction() { return reduction; }
+    public GSS.Phase targetPhase() { return phase; }
+    public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction.ord+":"+ reduction+" "+reduction.owner(); }

 }
 }

diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java
index 9db5aee..d333f41 100644 (file)
--- a/src/edu/berkeley/sbp/Result.java
+++ b/src/edu/berkeley/sbp/Result.java
@@ -9,14 +9,11 @@ final class Result implements GraphViz.ToGraphViz {
 
     private Forest f;
     private Node parent;
 
     private Forest f;
     private Node parent;

-    private GSS.Phase phase;
-    private Position reduction;

     private HashSet<Node> children = new HashSet<Node>();
     private boolean destroyed = false;
     private int usedByNonDoomedNode = 0;
 
     private HashSet<Node> children = new HashSet<Node>();
     private boolean destroyed = false;
     private int usedByNonDoomedNode = 0;
 

-    public Position reduction() { return reduction; }
-    public GSS.Phase phase() { return phase; }
+    public GSS.Phase phase() { return parent==null ? null : parent.phase(); }

     public Forest getForest() { return f; }
     public Node parent() { return parent; }
     public void addChild(Node child) {
     public Forest getForest() { return f; }
     public Node parent() { return parent; }
     public void addChild(Node child) {

@@ -24,8 +21,10 @@ final class Result implements GraphViz.ToGraphViz {
         usedByNonDoomedNode += child.state().doomed ? 0 : 1;
     }
     public void removeChild(Node child) {
         usedByNonDoomedNode += child.state().doomed ? 0 : 1;
     }
     public void removeChild(Node child) {

+        if (!children.contains(child)) return;

         children.remove(child);
         usedByNonDoomedNode -= child.state().doomed ? 0 : 1;
         children.remove(child);
         usedByNonDoomedNode -= child.state().doomed ? 0 : 1;

+        check();

     }
 
     public boolean usedByAnyNode() { return children.size() > 0; }
     }
 
     public boolean usedByAnyNode() { return children.size() > 0; }

@@ -38,27 +37,25 @@ final class Result implements GraphViz.ToGraphViz {
         if (destroyed) return;
         if (parent==null) return;  // never destroy the "primordeal" result
         destroyed = true;
         if (destroyed) return;
         if (parent==null) return;  // never destroy the "primordeal" result
         destroyed = true;

-        if (parent() != null) {
-            parent().removeChild(this);
-            parent().check();
-        }
-        OUTER: while(true) {
+        parent.removeChild(this);
+        while(children.size() > 0)

             for(Node n : children) {
                 children.remove(n);
                 n.removeResult(this);
             for(Node n : children) {
                 children.remove(n);
                 n.removeResult(this);

-                n.check();
-                continue OUTER;
+                break;

             }
             }

-            break;
-        }

     }
 
     public Result(Forest f, Node parent, Position reduction) {
     }
 
     public Result(Forest f, Node parent, Position reduction) {

+        this(f, parent, reduction, null);
+    }
+    public Result(Forest f, Node parent, Position reduction, GSS.Phase target) {

         this.f = f;
         this.f = f;

-        this.reduction = reduction;

         this.parent = parent;
         if (parent != null) parent.addChild(this);
         this.parent = parent;
         if (parent != null) parent.addChild(this);

-        if (parent != null) phase = parent.phase();
+        if (reduction == null) return;
+        Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction.owner());
+        target.newNodeFromReduction(this, state0, reduction);

     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////
     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////

diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index 2c36c8d..3e260f1 100644 (file)
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -98,7 +98,10 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
     public Iterator<Element> iterator()    { return new ArrayIterator<Element>(elements); }
     protected Sequence(Element[] elements) {
         this.elements = elements;
     public Iterator<Element> iterator()    { return new ArrayIterator<Element>(elements); }
     protected Sequence(Element[] elements) {
         this.elements = elements;

-        this.firstp = new Position(0);
+        for(int i=0; i<elements.length; i++)
+            if (elements[i]==null)
+                throw new RuntimeException("cannot have nulls in a sequence: " + this);
+        this.firstp = new Position(0, null);

     }
 
     // DO NOT MESS WITH THE FOLLOWING LINE!!!
     }
 
     // DO NOT MESS WITH THE FOLLOWING LINE!!!

@@ -119,35 +122,22 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
     class Position implements IntegerMappable {
 
         public int ord = -1;
     class Position implements IntegerMappable {
 
         public int ord = -1;

-        public int compareTo(Position p, Walk.Cache cache) {
-            Position position = this;
-            Position rposition = p;
-            int ret = 0;
-            if (Reduction.canKill(cache, position, rposition) &&
-                Reduction.canKill(cache, rposition, position)) throw new Error();
-            if      (Reduction.canKill(cache, position,   rposition)) ret =  1;
-            else if (Reduction.canKill(cache, rposition, position)) ret = -1;
-            if      (Reduction.canNeed(cache, position,   rposition)) ret =  1;
-            else if (Reduction.canNeed(cache, rposition, position)) ret = -1;
-            return ret;
-        }

 
         private Forest zero = null;
         public Forest zero(Input.Region reg) {
             if (zero != null) return zero;
 
         private Forest zero = null;
         public Forest zero(Input.Region reg) {
             if (zero != null) return zero;

-            if (pos > 0) throw new Error();
+            if (pos > 0) throw new RuntimeException("Position.zero(): pos>0");

             return zero = rewrite(reg);
         }
 
             return zero = rewrite(reg);
         }
 

-

                 final int      pos;
         private final Position next;
         private final Position prev;
                 final Forest[] holder;
         
                 final int      pos;
         private final Position next;
         private final Position prev;
                 final Forest[] holder;
         

-        private Position(int pos) {
+        private Position(int pos, Position prev) {

             this.pos      = pos;
             this.pos      = pos;

-            this.next     = pos==elements.length ? null : new Position(pos+1);
+            this.next     = pos==elements.length ? null : new Position(pos+1, this);

             this.holder   = new Forest[elements.length];
             this.prev     = prev;
         }
             this.holder   = new Forest[elements.length];
             this.prev     = prev;
         }

@@ -178,9 +168,7 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
                 if (holder[i]==null) holder[i] = elements[i].epsilonForm(loc);
                 if (holder[i]==null) throw new Error("bad " + i);
             }
                 if (holder[i]==null) holder[i] = elements[i].epsilonForm(loc);
                 if (holder[i]==null) throw new Error("bad " + i);
             }

-            Forest<T> ret = Sequence.this.postReduce(loc, holder, this);
-            //for(int k=0; k<pos; k++) holder[k] = null; // to help GC
-            return ret;
+            return Sequence.this.postReduce(loc, holder, this);

         }
 
         public String   toString() {
         }
 
         public String   toString() {

@@ -283,7 +271,6 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
             Forest<T>[] args2 = new Forest[count];
             int j = 0;
             for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
             Forest<T>[] args2 = new Forest[count];
             int j = 0;
             for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];

-            //System.out.println("reduce \""+tag+"\"");

             return Forest.create(loc, (T)tag, args2, false);
         }
         public StringBuffer toString(StringBuffer sb, boolean spacing) {
             return Forest.create(loc, (T)tag, args2, false);
         }
         public StringBuffer toString(StringBuffer sb, boolean spacing) {