From: adam <adam@megacz.com>
Date: Mon, 26 Feb 2007 01:15:43 +0000 (-0500)
Subject: partition states into doomed and non-doomed
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=658e5249cdadcd4037a8d6744f8cad0825d77f37;hp=9e202722669e70d83e3e09d926bfb40f80a1e9cb

partition states into doomed and non-doomed

darcs-hash:20070226011543-5007d-549cb2d24a2f60e8372a95a11de96220cab0922c.gz
---

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index f239fe5..df94e83 100644
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -63,7 +63,7 @@ public abstract class Parser<Token, NodeType> {
         public String toString() {
             StringBuffer sb = new StringBuffer();
             sb.append("parse table");
-            for(State<Token> state : all_states.values()) {
+            for(State<Token> state : all_states) {
                 sb.append("  " + state + "\n");
                 for(Topology<Token> t : state.shifts) {
                     sb.append("      shift  \""+
@@ -108,7 +108,9 @@ public abstract class Parser<Token, NodeType> {
 
         /** used to generate unique values for State.idx */
         private int master_state_idx = 0;
-        HashMap<HashSet<Position>,State<Token>>   all_states    = new HashMap<HashSet<Position>,State<Token>>();
+        HashSet<State<Token>>   all_states    = new HashSet<State<Token>>();
+        HashMap<HashSet<Position>,State<Token>>   doomed_states    = new HashMap<HashSet<Position>,State<Token>>();
+        HashMap<HashSet<Position>,State<Token>>   normal_states    = new HashMap<HashSet<Position>,State<Token>>();
         HashSet<SequenceOrElement>                all_elements  = new HashSet<SequenceOrElement>();
 
         /** construct a parse table for the given grammar */
@@ -130,15 +132,15 @@ public abstract class Parser<Token, NodeType> {
             HashSet<Position> hp = new HashSet<Position>();
             reachable(start0, hp);
 
-            this.dead_state = new State<Token>(new HashSet<Position>());
+            this.dead_state = new State<Token>(new HashSet<Position>(), true);
             this.start = new State<Token>(hp);
 
             // for each state, fill in the corresponding "row" of the parse table
-            for(State<Token> state : all_states.values())
+            for(State<Token> state : all_states)
                 for(Position p : state.hs) {
 
                     // the Grammar's designated "last position" is the only accepting state
-                    if (start0.contains(p.owner()) && p.next()==null)
+                    if (start0.contains(p.owner()) && p.next()==null && !state.doomed)
                         state.accept = true;
 
                     if (isRightNullable(p)) {
@@ -161,7 +163,7 @@ public abstract class Parser<Token, NodeType> {
                         state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
                 }
             if (top instanceof IntegerTopology)
-                for(State<Token> state : all_states.values()) {
+                for(State<Token> state : all_states) {
                     state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor());
                     state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor());
                 }
@@ -232,28 +234,29 @@ public abstract class Parser<Token, NodeType> {
              *  </ul>
              */
             public State(HashSet<Position> hs) { this(hs, false); }
-            public boolean special;
-            public State(HashSet<Position> hs, boolean special) {
+            public boolean doomed;
+            public State(HashSet<Position> hs, boolean doomed) {
                 this.hs = hs;
-                this.special = special;
+                this.doomed = doomed;
 
                 // register ourselves in the all_states hash so that no
                 // two states are ever created with an identical position set
-                ((HashMap)all_states).put(hs, this);
-
+                ((HashMap)(doomed ? doomed_states : normal_states)).put(hs, this);
+                ((HashSet)all_states).add(this);
+                
                 for(Position p : hs) {
                     if (!p.isFirst()) continue;
                     for(Sequence s : p.owner().needs()) {
                         if (hs.contains(s.firstp())) continue;
                         HashSet<Position> h2 = new HashSet<Position>();
                         reachable(s.firstp(), h2);
-                        also.add((State<Token>)(all_states.get(h2) == null ? (State)new State<Token>(h2,true) : (State)all_states.get(h2)));
+                        also.add(mkstate(h2, true));
                     }
                     for(Sequence s : p.owner().hates()) {
                         if (hs.contains(s.firstp())) continue;
                         HashSet<Position> h2 = new HashSet<Position>();
                         reachable(s, h2);
-                        also.add((State<Token>)(all_states.get(h2) == null ? (State)new State<Token>(h2,true) : (State)all_states.get(h2)));
+                        also.add(mkstate(h2, true));
                     }
                 }
 
@@ -278,8 +281,7 @@ public abstract class Parser<Token, NodeType> {
                 for(Topology<Token> r : bag0) {
                     HashSet<Position> h = new HashSet<Position>();
                     for(Position p : bag0.getAll(r)) h.add(p);
-                    ((TopologicalBag)gotoSetTerminals).put(r, all_states.get(h) == null
-                                                           ? new State<Token>(h) : all_states.get(h));
+                    ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed));
                 }
 
                 // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction),
@@ -303,7 +305,7 @@ public abstract class Parser<Token, NodeType> {
                 }
                 OUTER: for(SequenceOrElement y : move) {
                     HashSet<Position> h = move.getAll(y);
-                    State<Token> s = all_states.get(h) == null ? (State)new State<Token>(h) : (State)all_states.get(h);
+                    State<Token> s = mkstate(h, doomed);
                     // if a reduction is "lame", it should wind up in the dead_state after reducing
                     if (y instanceof Sequence) {
                         for(Position p : hs) {
@@ -322,6 +324,11 @@ public abstract class Parser<Token, NodeType> {
                 }
             }
 
+            private State<Token> mkstate(HashSet<Position> h, boolean b) {
+                if (b) return doomed_states.get(h) == null ? (State)new State<Token>(h,b) : (State)doomed_states.get(h);
+                else   return normal_states.get(h) == null ? (State)new State<Token>(h,b) : (State)normal_states.get(h);
+            }
+
             public String toStringx() {
                 StringBuffer st = new StringBuffer();
                 for(Position p : this) {