From: adam Date: Tue, 4 Mar 2008 04:03:10 +0000 (-0500) Subject: some simplifications to GSS, ResultNode, and StateNode X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=52e7a254d32940210e0efce25e622d6266fc7f37 some simplifications to GSS, ResultNode, and StateNode darcs-hash:20080304040310-5007d-f165435d44a4bde78144c20ad004d4c7bb87adc2.gz --- diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 2d2e550..7666ec2 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -18,9 +18,6 @@ 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; @@ -44,7 +41,7 @@ class GSS { public void invoke(State st, StateNode pred, Forest f) { parser.spin(); - good |= next.newNode(f, null, pred, st, false); + good |= next.newNode(f, null, pred, st); } /** the token immediately after this phase */ @@ -61,7 +58,7 @@ class GSS { public Phase(State startState) throws ParseFailed, IOException { this(null, null); - newNode(null, null, null, startState, true); + newNode(null, null, null, startState); } public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { this.location = input.getLocation(); @@ -179,32 +176,32 @@ class GSS { performed.add(pos, reduction.provides()); Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction); if (state!=null) - newNode(f, reduction, pred, state, reduction.numPops()<=0); + newNode(f, reduction, pred, state); } /** add a new node (merging with existing nodes if possible) * @param parent the parent of the new node * @param result the SPPF result corresponding to the new node * @param state the state that the new node is in - * @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(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) { + private boolean newNode(Forest f, Pos reduction, StateNode pred, State state) { StateNode p = pred==null ? null : hash.get(state, pred.phase()); if (p != null) { p.addPred(f, reduction, pred); return !state.doomed(); } do { + // optimizations if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; if (!state.canReduce(token)) return false; } while(false); - StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC + StateNode n = new StateNode(Phase.this, new ResultNode(f, reduction, pred), state); // ALLOC /** FIXME: this null-result can be used to notice bogus/dead states */ for(Object s : state.conjunctStates) - newNode(null, null, n, (State)s, fromEmptyReduction); + newNode(null, null, n, (State)s); return !n.state().doomed(); } diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 56ee0ca..bfc022d 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -354,9 +354,9 @@ public abstract class Parser implements Serializable { if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null); else oreductions.invoke(t, node, null, null); } - void invokeReductions(Token t, StateNode node, ResultNode b) { - if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null); - else oreductions.invoke(t, node, b, null); + void invokeReductions(Token t, StateNode node, ResultNode only) { + if (t==null) for(Pos r : eofReductions) node.invoke(r, only, null); + else oreductions.invoke(t, node, only, null); } // Constructor ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/ResultNode.java b/src/edu/berkeley/sbp/ResultNode.java index 579a868..65732a6 100644 --- a/src/edu/berkeley/sbp/ResultNode.java +++ b/src/edu/berkeley/sbp/ResultNode.java @@ -9,8 +9,8 @@ import java.util.*; final class ResultNode extends Node { - private Forest.Many f = new Forest.Many(); private Pos reduction; + private Forest.Many f = new Forest.Many(); public void merge(Forest newf) { this.f.merge(newf); } public Pos reduction() { return reduction; } @@ -29,9 +29,9 @@ final class ResultNode super.destroy(); } - public void addPred(StateNode pred) { + protected void addPred(StateNode pred) { super.addPred(pred); - // results have only one predecessor + // results should have at most one predecessor if (predecessors.size() > 1) throw new Error(); } diff --git a/src/edu/berkeley/sbp/StateNode.java b/src/edu/berkeley/sbp/StateNode.java index af1a3e9..768d8bf 100644 --- a/src/edu/berkeley/sbp/StateNode.java +++ b/src/edu/berkeley/sbp/StateNode.java @@ -15,11 +15,10 @@ final class StateNode extends Node implements Invokable { + private boolean fromEmptyReduction; private final Parser.Table.State state; - private boolean fromEmptyReduction; /** which GSS.Phase this StateNode belongs to */ - public Iterator iterator() { return predecessors.iterator(); } public Parser.Table.State state() { return state; } public boolean isDoomedState() { return state.doomed; } @@ -44,39 +43,36 @@ final class StateNode public final void invoke(Pos r, ResultNode only, Object o) { boolean emptyProductions = only==null; if (emptyProductions != (r.numPops()==0)) return; - if (r.numPops()!=0) reduce(r, r.numPops()-1, phase(), only); - else { + if (r.numPops()==0) { Input.Region region = phase().getLocation().createRegion(phase().getLocation()); phase().newNodeFromReduction(r.rewrite(region), r, this); + } else { + // never start reductions at a node that was created via a right-nulled rule + if (only.reduction().numPops()==0) return; + reduce(r, r.numPops()-1, phase(), only); } } private void reduce(Pos r, int pos, GSS.Phase target, ResultNode only) { for(ResultNode res : predecessors) if (only == null || res == only) - for(StateNode pred : res) - reduce2(r, pos, target, pred, res.getForest()); + for(StateNode pred : res) { + Forest[] holder = r.holder; + Forest old = pos >= holder.length ? null : holder[pos]; + if (pos < holder.length) holder[pos] = res.getForest(); + if (pos>0) pred.reduce(r, pos-1, target, null); + else { + Input.Region region = pred.phase().getLocation().createRegion(target.getLocation()); + new Reduction(pred, r, r.rewrite(region), target); + } + if (pos < holder.length) holder[pos] = old; + } } - void reduce2(Pos r, int pos, GSS.Phase target, StateNode pred, Forest f) { - Forest[] holder = r.holder; - Forest old = pos >= holder.length ? null : holder[pos]; - if (pos < holder.length) holder[pos] = f; - if (pos>0) pred.reduce(r, pos-1, target, null); - else { - Input.Region region = pred.phase().getLocation().createRegion(target.getLocation()); - new Reduction(pred, r, r.rewrite(region), target); - } - if (pos < holder.length) holder[pos] = old; - } - - StateNode(GSS.Phase phase, Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) { - this(phase, new ResultNode(f, reduction, pred), state, fromEmptyReduction); - } - StateNode(GSS.Phase phase, ResultNode pred, State state, boolean fromEmptyReduction) { + StateNode(GSS.Phase phase, ResultNode pred, State state) { super(phase, pred.phase()); this.state = state; - this.fromEmptyReduction = fromEmptyReduction; + this.fromEmptyReduction = pred!=null && pred.reduction()!=null && pred.reduction().numPops()==0; if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!"); phase.hash.put(state, pred.phase(), this); addPred(pred); @@ -95,7 +91,6 @@ final class StateNode } protected void addPred(ResultNode result) { super.addPred(result); - if (!this.fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, result); + state.invokeReductions(phase().getToken(), this, result); } }