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 (file)
--- 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; }
 
     public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
     public Input getInput() { return input; }
 

-    /*
-    HashSet<Reduction> finishedReductions = new HashSet<Reduction>();
-    */

     int numNewNodes = 0;
     int numOldNodes = 0;
     int viewPos = 0;
     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();
 
         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 */
         }
 
         /** the token immediately after this phase */

@@ -61,7 +58,7 @@ class GSS {
 
         public Phase(State startState) throws ParseFailed, IOException {
             this(null, null);
 
         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();
         }
         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)
                 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
         }
 
         /** 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)
          */
          *  @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 {
             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);
                 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)
             /** 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();
         }
 
             return !n.state().doomed();
         }
 

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 56ee0ca..bfc022d 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -354,9 +354,9 @@ public abstract class Parser<Token, NodeType> implements Serializable {
                 if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
                 else         oreductions.invoke(t, node, null, null);
             }
                 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 //////////////////////////////////////////////////////////////////////////////
             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////

diff --git a/src/edu/berkeley/sbp/ResultNode.java b/src/edu/berkeley/sbp/ResultNode.java
index 579a868..65732a6 100644 (file)
--- 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<StateNode> {
 
 final class ResultNode
     extends Node<StateNode> {
 

-    private Forest.Many f = new Forest.Many();

     private Pos reduction;
     private Pos reduction;

+    private Forest.Many f = new Forest.Many();

 
     public void merge(Forest newf) { this.f.merge(newf); }
     public Pos reduction() { return reduction; }
 
     public void merge(Forest newf) { this.f.merge(newf); }
     public Pos reduction() { return reduction; }

@@ -29,9 +29,9 @@ final class ResultNode
         super.destroy();
     }
 
         super.destroy();
     }
 

-    public void addPred(StateNode pred) {
+    protected void addPred(StateNode pred) {

         super.addPred(pred);
         super.addPred(pred);

-        // results have only one predecessor
+        // results should have at most one predecessor

         if (predecessors.size() > 1) throw new Error();
     }
         
         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 (file)
--- a/src/edu/berkeley/sbp/StateNode.java
+++ b/src/edu/berkeley/sbp/StateNode.java
@@ -15,11 +15,10 @@ final class StateNode
     extends Node<ResultNode>
     implements Invokable<Pos, ResultNode, Object> {
 
     extends Node<ResultNode>
     implements Invokable<Pos, ResultNode, Object> {
 

+    private boolean fromEmptyReduction;

     private final Parser.Table.State state;
     private final Parser.Table.State state;

-    private  boolean fromEmptyReduction;

 
     /** which GSS.Phase this StateNode belongs to */
 
     /** which GSS.Phase this StateNode belongs to */

-    public Iterator<ResultNode> iterator() { return predecessors.iterator(); }

     public Parser.Table.State state() { return state; }
     public boolean isDoomedState() { return state.doomed; }
 
     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;
     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);
             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)
         }
     }
 
     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;
         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);
         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);
     }
     protected void addPred(ResultNode result) {
         super.addPred(result);

-        if (!this.fromEmptyReduction)
-            state.invokeReductions(phase().getToken(), this, result);
+        state.invokeReductions(phase().getToken(), this, result);

     }
 }
     }
 }