From 014de68a21aa2d17fdfd0bac7e404a725997a246 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 4 Jan 2006 22:03:20 -0500 Subject: [PATCH] checkpoint darcs-hash:20060105030320-5007d-85d5bb67a3ad0b54344b05feb6f3e922afd2444b.gz --- src/edu/berkeley/sbp/Forest.java | 2 +- src/edu/berkeley/sbp/GSS.java | 46 +++++++++++++++++++----- src/edu/berkeley/sbp/Parser.java | 12 +++++-- src/edu/berkeley/sbp/misc/RegressionTests.java | 4 +++ src/edu/berkeley/sbp/util/MapBag.java | 1 - src/edu/berkeley/sbp/util/TopologicalBag.java | 10 +++++- 6 files changed, 61 insertions(+), 14 deletions(-) diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 6ac1e4b..6437341 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -32,7 +32,7 @@ public abstract class Forest { protected static class Body { - private final Token.Location location; + private final Token.Location location; private final T tag; private final Forest[] 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 --- 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 between tokens the input stream; same as Tomita's U_i's */ - public class Phase { + public class Phase implements Invokable { /** 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 next */ 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 { + public final class Node extends FastSet implements Invokable { 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 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -181,14 +181,22 @@ public abstract class Parser { // Interface Methods ////////////////////////////////////////////////////////////////////////////// + public boolean isAccepting() { return accept; } + public boolean canShift(Token t) { return shifts.contains(t); } public Iterable getShifts(Token t) { return shifts.get(t); } - public boolean isAccepting() { return accept; } + public Iterable 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 getEofReductions() { return eofReductions; } + public Iterator iterator() { return hs.iterator(); } + public void invokeShifts(Token t, Invokable irbc, B b, C c) { shifts.invoke(t, irbc, b, c); } + public void invokeReductions(Token t, Invokable 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 --- 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 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 --- 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 extends Iterable { public void add(K k, V v); public void addAll(K k, Iterable iv); - public Iterable getAll(K k); public Iterator iterator(); } diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java index cdbe976..38e3925 100644 --- a/src/edu/berkeley/sbp/util/TopologicalBag.java +++ b/src/edu/berkeley/sbp/util/TopologicalBag.java @@ -82,7 +82,7 @@ public class TopologicalBag implements MapBag,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 t : h.keySet()) @@ -100,6 +100,14 @@ public class TopologicalBag implements MapBag,V> { private HashMap> cache = new HashMap>(); public Iterable getAll(Topology k) { return h.get(k); } + + public void invoke(K k, Invokable ivbc, B b, C c) { + for(Topology t : h.keySet()) + if (t.contains(k)) + for(V v : h.get(t)) + ivbc.invoke(v, b, c); + } + public Iterable get(K k) { Iterable c = cache.get(k); if (c != null) return c; -- 1.7.10.4