X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=2e573486c9e8d3ff80cd13cfabb5d24ad489fed1;hp=bf58e6461ba0fd6aeb5566c21b3c7ecfb61f62ba;hb=c53fc2952c7885d727500ce404887d552c5dec5f;hpb=33d7b8fa4974bad96108c11e5548b354cf10ecb8 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index bf58e64..2e57348 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -18,13 +18,16 @@ class GSS { public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;} public Input getInput() { return input; } + /* + HashSet finishedReductions = new HashSet(); + */ int numNewNodes = 0; int numOldNodes = 0; int viewPos = 0; int numReductions = 0; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { + class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { // FIXME: right now, these are the performance bottleneck private HashMapBag performed = new HashMapBag(); @@ -38,16 +41,16 @@ class GSS { parser.spin(); reductionQueue.add(r); } - public void invoke(State st, Result result) { + + public void invoke(State st, StateNode pred, Forest f) { parser.spin(); - good |= next.newNode(result, st, false); + good |= next.newNode(f, null, pred, st, false); } /** the token immediately after this phase */ final Tok token; final int pos; - - public IntPairMap hash = new IntPairMap(); /* ALLOC */ + public IntPairMap hash = new IntPairMap(); /* ALLOC */ private boolean good = false; private Phase next = null; private Phase prev; @@ -58,8 +61,7 @@ class GSS { public Phase(State startState) throws ParseFailed, IOException { this(null, null); - Result primordealResult = new Result(null, null, null); - newNode(primordealResult, startState, true); + newNode(null, null, null, startState, true); } public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { this.location = input.getLocation(); @@ -70,6 +72,9 @@ class GSS { this.pos = prev==null ? 0 : prev.pos+1; if (prev != null) prev.shift(this, forest); numReductions = 0; + /* + finishedReductions.clear(); + */ int minPhasePos = Integer.MAX_VALUE; Reduction best = null; @@ -95,6 +100,9 @@ class GSS { best = r; } } + /* + finishedReductions.add(r); + */ numReductions++; } if (token==null) shift(null, null); @@ -117,24 +125,24 @@ class GSS { this.next = next; // this massively improves GC performance if (prev != null) { - IntPairMap h = prev.hash; + IntPairMap h = prev.hash; prev.hash = null; prev.performed = null; - for(Node n : h) n.check(); + for(StateNode n : h) n.check(); } numOldNodes = hash.size(); - for(Node n : hash.values()) { + for(StateNode n : hash.values()) { if (token == null && n.state().isAccepting()) { if (finalResult==null) finalResult = new Forest.Many(); - for(Result r : n) + for(ResultNode r : n) finalResult.merge(r.getForest()); } if (token == null) continue; - Result result = new Result(f, n, null); - n.state().invokeShifts(token, this, result); + n.state().invokeShifts(token, this, n, f); } numNewNodes = next==null ? 0 : next.hash.size(); viewPos = this.pos; + if (!good && token!=null) { String toks = token+""; if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) { @@ -152,15 +160,15 @@ class GSS { if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this, null, getLocation().createRegion(getLocation())); - for(Node n : hash) n.check(); + for(StateNode n : hash) n.check(); } Input.Region getRegionFromThisToNext() { return getLocation().createRegion(getNextLocation()); } - void newNodeFromReduction(Result result, State state, Pos reduction) { - int pos = result.phase().pos; + void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) { + int pos = pred.phase().pos; for(int s : reduction.hates()) if (performed.contains(pos, s)) return; @@ -169,8 +177,9 @@ class GSS { return; if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides())) performed.add(pos, reduction.provides()); + Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction); if (state!=null) - newNode(result, state, reduction.numPops()<=0); + newNode(f, reduction, pred, state, reduction.numPops()<=0); } /** add a new node (merging with existing nodes if possible) @@ -180,19 +189,22 @@ 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) */ - private boolean newNode(Result result, State state, boolean fromEmptyReduction) { - Node p = hash.get(state, result.phase()); - if (p != null) { p.addResult(result); return !state.doomed(); } + private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) { + StateNode p = pred==null ? null : hash.get(state, pred.phase()); + if (p != null) { + p.addResult(f, reduction, pred); + return !state.doomed(); + } do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; if (!state.canReduce(token)) return false; } while(false); - Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC /** FIXME: this null-result can be used to notice bogus/dead states */ for(Object s : state.conjunctStates) - newNode(new Result(null, n, null), (State)s, fromEmptyReduction); + newNode(null, null, n, (State)s, fromEmptyReduction); return !n.state().doomed(); } @@ -200,12 +212,12 @@ class GSS { public int size() { return hash==null ? 0 : hash.size(); } public int pos() { return pos; } public Tok getToken() { return token; } - public Iterator iterator() { return hash.iterator(); } + public Iterator iterator() { return hash.iterator(); } public GSS getGSS() { return GSS.this; } // GraphViz ////////////////////////////////////////////////////////////////////////////// - public GraphViz.Node toGraphViz(GraphViz gv) { + public GraphViz.StateNode toGraphViz(GraphViz gv) { if (gv.hasNode(this)) return gv.createNode(this); GraphViz.Group g = gv.createGroup(this); g.label = "Phase " + pos; @@ -221,7 +233,7 @@ class GSS { PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); GraphViz gv = new GraphViz(); for(Object n : this) - ((Node)n).toGraphViz(gv); + ((StateNode)n).toGraphViz(gv); gv.dump(p); p.flush(); p.close();