X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=65c12e78385d89c64bf3a52d15d2bbbb1223d0af;hp=7d13fb2036426aa2908ab1290886420c0afaeece;hb=03dd839af8e8d1a6c2f69c5410da6d19fbbe3931;hpb=014de68a21aa2d17fdfd0bac7e404a725997a246 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 7d13fb2..65c12e7 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -5,21 +5,6 @@ import java.io.*; import java.util.*; import java.lang.reflect.*; -////////////////////////////////////////////////////////////////////////////// -// TODO: -// -// - fix public/package/private status -// - -////////////////////////////////////////////////////////////////////////////// -// Optimizations to add -// -// ** NOTE: not all of these are appropriate for this class -- it is -// simply a list of optimizations not implemented. This -// class is meant to remain simple and easy to understand; -// optimizations which obscure that do not belong here (they -// should go into the compiled version instead) - /** implements Tomita's Graph Structured Stack */ class GSS { @@ -73,31 +58,32 @@ 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) */ - public void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { - Node p = hash.get(code(state, start)); - if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction, start); - else newNode3(parent, pending, state, fromEmptyReduction, start); + public void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { + Node p = hash.get(code(state, parent==null?null:parent.phase())); + if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction); + else newNode3(parent, pending, state, fromEmptyReduction); } - private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { p.holder.merge(pending); if (p.parents().contains(parent)) return; - p.addParent(parent, fromEmptyReduction); + if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep"); + if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2"); + p.parents().add(parent, true); + if (p!=parent && !fromEmptyReduction) p.queueReductions(parent); } - private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; - int count = 0; - Parser.Table.Reduction r = null; - if (!state.hasReductions(token)) return; + if (!state.canReduce(token)) return; //if (count > 1) break; //if (r.numPop == 0) break; //r.reduce(pending, parent, null, Phase.this, null); //return; } while(false); - Node n = new Node(parent, pending, state, start); // ALLOC + Node n = new Node(parent, pending, state, fromEmptyReduction); // ALLOC n.queueEmptyReductions(); if (!fromEmptyReduction) n.queueReductions(parent); } @@ -124,7 +110,7 @@ class GSS { } public void invoke(Parser.Table.State st, Forest result, Node n) { - next.newNode(n, result, st, true, this); + next.newNode(n, result, st, false); } private Phase next = null; @@ -184,12 +170,6 @@ class GSS { /** a node in the GSS */ public final class Node extends FastSet implements Invokable { - public void addParent(Node parent, boolean fromEmptyReduction) { - if (parents().contains(parent)) return; - parents().add(parent); - if (this!=parent && !fromEmptyReduction) queueReductions(parent); - } - private Forest.Ref holder = null; private boolean allqueued = false; @@ -204,24 +184,15 @@ class GSS { public FastSet parents() { return this; } public void queueReductions() { + if (!reducing) return; if (allqueued) return; allqueued = true; int where = parents().size(); - /* - for(Parser.Table.Reduction r : state.getReductions(token)) - 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); } @@ -231,26 +202,21 @@ class GSS { return; } if (r.numPop==0) return; - if (n2==null) { - r.reduce(n); - } else { - r.reduce(n, n2); - } + if (n2==null) r.reduce(n); + else r.reduce(n, n2); } public void queueEmptyReductions() { 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) { + private boolean fe; + private Node(Node parent, Forest pending, Parser.Table.State state, boolean fe) { + this.fe = fe; this.state = state; + Phase start = parent==null ? null : parent.phase(); if (pending != null) this.holder().merge(pending); - if (parent != null) parents().add(parent); + if (parent != null) parents().add(parent, true); if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!"); Phase.this.hash.put(code(state, start), this); Phase.this.numNodes++; @@ -269,6 +235,6 @@ class GSS { /** this is something of a hack right now */ private static long code(Parser.Table.State state, Phase start) { - return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); + return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1)); } }