checkpoint

darcs-hash:20060105030320-5007d-85d5bb67a3ad0b54344b05feb6f3e922afd2444b.gz

diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
index 6ac1e4b..6437341 100644 (file)
--- a/src/edu/berkeley/sbp/Forest.java
+++ b/src/edu/berkeley/sbp/Forest.java
@@ -32,7 +32,7 @@ public abstract class Forest<T> {
 
     protected static class Body<T> {
 
-        private final Token.Location          location;
+        private final Token.Location    location;
         private final T                 tag;
         private final Forest<T>[]       tokens;
         private final Sequence          creator;

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 645fa8f..7d13fb2 100644 (file)
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,7 +1,5 @@
 package edu.berkeley.sbp;
 import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.*;
 import edu.berkeley.sbp.util.*;
 import java.io.*;
 import java.util.*;
@@ -30,7 +28,7 @@ class GSS {
     private Phase.Node[] reducing_list = null;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    public class Phase {
+    public class Phase implements Invokable<Parser.Table.State, Forest, GSS.Phase.Node> {
 
         /** the token immediately after this phase */
         public  final Token token;
@@ -125,8 +123,14 @@ class GSS {
             }
         }
 
+        public void invoke(Parser.Table.State st, Forest result, Node n) {
+            next.newNode(n, result, st, true, this);
+        }
+        private Phase next = null;
+
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
         public void shift(Phase next, Forest result) {
+            this.next = next;
             closed = true;
             Forest res = null;
             boolean ok = false;
@@ -140,11 +144,14 @@ class GSS {
                 }
                 if (!n.holder.valid()) continue;
                 if (token == null) continue;
+                n.state.invokeShifts(token, this, result, n);
+                /*
                 for(Parser.Table.State st : n.state.getShifts(token)) {
                     if (res == null) res = result;
                     next.newNode(n, res, st, true, this);
                     ok = true;
                 }
+                */
             }
 
             if (!ok && token != null) {
@@ -175,10 +182,11 @@ class GSS {
         // GSS Nodes //////////////////////////////////////////////////////////////////////////////
 
         /** a node in the GSS */
-        public final class Node extends FastSet<Node> {
+        public final class Node extends FastSet<Node> implements Invokable<Parser.Table.Reduction, Node, Node> {
 
             public void addParent(Node parent, boolean fromEmptyReduction) {
-                parents().add(parent, true);
+                if (parents().contains(parent)) return;
+                parents().add(parent);
                 if (this!=parent && !fromEmptyReduction) queueReductions(parent);
             }
 
@@ -199,24 +207,44 @@ class GSS {
                 if (allqueued) return;
                 allqueued = true;
                 int where = parents().size();
+                /*
                 for(Parser.Table.Reduction r : state.getReductions(token))
-                    if (r.numPop >= 1)
+                    if (r.numPop > 0)
                         r.reduce(this);
+                */
+                state.invokeReductions(token, this, this, null);
             }
 
             public void queueReductions(Node n2) {
                 if (!allqueued) { queueReductions(); return; }
+                /*
                 for(Parser.Table.Reduction r : state.getReductions(token))
                     if (r.numPop > 0)
                         r.reduce(this, n2);
+                */
+                state.invokeReductions(token, this, this, n2);
             }
 
-
+            public final void invoke(Parser.Table.Reduction r, Node n, Node n2) {
+                if (n==null) {
+                    if (r.numPop==0) r.reduce(this);
+                    return;
+                }
+                if (r.numPop==0) return;
+                if (n2==null) {
+                    r.reduce(n);
+                } else {
+                    r.reduce(n, n2);
+                }
+            }
             public void queueEmptyReductions() {
-                if (reducing)
-                    for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token))
+                if (!reducing) return;
+                /*
+                  for(Parser.Table.Reduction r : state.getReductions(token))
                         if (r.numPop==0)
                             r.reduce(this);
+                */
+                state.invokeReductions(token, this, null, null);
             }
 
             private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) {

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 5c399cc..076bc7d 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -181,14 +181,22 @@ public abstract class Parser<T extends Token, R> {
 
             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 
+            public boolean             isAccepting()               { return accept; }
+
             public boolean             canShift(Token t)           { return shifts.contains(t); }
             public Iterable<State>     getShifts(Token t)          { return shifts.get(t); }
-            public boolean             isAccepting()               { return accept; }
+
             public Iterable<Reduction> getReductions(Token t)      { return t==null ? eofReductions : reductions.get(t); }
             public boolean             hasReductions(Token t)      { return t==null ? eofReductions.size()>0 : reductions.has(t); }
-            public Iterable<Reduction> getEofReductions()          { return eofReductions; }
+
             public Iterator<Position>  iterator()                  { return hs.iterator(); }
 
+            public <B,C> void          invokeShifts(Token t, Invokable<State,B,C> irbc, B b, C c) { shifts.invoke(t, irbc, b, c); }
+            public <B,C> void          invokeReductions(Token t, Invokable<Reduction,B,C> irbc, B b, C c) {
+                if (t==null) for(Reduction r : eofReductions) irbc.invoke(r, b, c);
+                else         reductions.invoke(t, irbc, b, c);
+            }
+
             // Constructor //////////////////////////////////////////////////////////////////////////////
 
             /**

diff --git a/src/edu/berkeley/sbp/misc/RegressionTests.java b/src/edu/berkeley/sbp/misc/RegressionTests.java
index 9429b69..7da0b26 100644 (file)
--- a/src/edu/berkeley/sbp/misc/RegressionTests.java
+++ b/src/edu/berkeley/sbp/misc/RegressionTests.java
@@ -37,7 +37,11 @@ public class RegressionTests {
                 System.out.println("\nready...");
                 System.in.read();
             }
+            System.gc();
+            long now = System.currentTimeMillis();
             Forest<String> r2 = parser.parse(cs);
+            System.out.println();
+            System.out.println("elapsed = " + (System.currentTimeMillis()-now) + "ms");
             if (profile) {
                 System.out.println("\ndone");
                 System.in.read();

diff --git a/src/edu/berkeley/sbp/util/MapBag.java b/src/edu/berkeley/sbp/util/MapBag.java
index f1da08c..f93a2e8 100644 (file)
--- a/src/edu/berkeley/sbp/util/MapBag.java
+++ b/src/edu/berkeley/sbp/util/MapBag.java
@@ -5,6 +5,5 @@ import java.util.*;
 public interface MapBag<K,V> extends Iterable<K> {
     public void add(K k, V v);
     public void addAll(K k, Iterable<V> iv);
-    public Iterable<V> getAll(K k);
     public Iterator<K> iterator();
 }

diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
index cdbe976..38e3925 100644 (file)
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -82,7 +82,7 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
         return true;
     }
 
-    public boolean contains(K k) { return get(k).iterator().hasNext(); }
+    public boolean contains(K k) { return has(k); }
 
     public boolean contains(K k, V v) {
         for(Topology<K> t : h.keySet())
@@ -100,6 +100,14 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
 
     private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
     public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
+
+    public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
+        for(Topology<K> t : h.keySet())
+            if (t.contains(k))
+                for(V v : h.get(t))
+                    ivbc.invoke(v, b, c);
+    }
+
     public Iterable<V> get(K k) {
         Iterable<V> c = cache.get(k);
         if (c != null) return c;