Table extends Cache

[sbp.git] / src / edu / berkeley / sbp / Parser.java

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 5b31b31..3fad1dd 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -13,9 +13,7 @@ public abstract class Parser<T extends Token, R> {
 
     private final Table pt;
 
-    /**
-     *  create a parser to parse the grammar with start symbol <tt>u</tt>
-     */
+    /** create a parser to parse the grammar with start symbol <tt>u</tt> */
     protected Parser(Union u)  { this.pt = new Table(u, top()); }
     protected Parser(Table pt) { this.pt = pt; }
 
@@ -72,18 +70,9 @@ public abstract class Parser<T extends Token, R> {
     // Table //////////////////////////////////////////////////////////////////////////////
 
     /** an SLR(1) parse table which may contain conflicts */
-    static class Table {
+    static class Table extends Walk.Cache {
 
-        private final Union start0 = new Union("0");
-        private final Sequence start0seq;
-        
-        public final Walk.Cache cache = new Walk.Cache();
-        
-        public HashSet<Position> closure()       {
-            HashSet<Position> hp = new HashSet<Position>();
-            reachable(start0, hp);
-            return hp;
-        }
+        public final Walk.Cache cache = this;
         
         private void walk(Element e, HashSet<Element> hs) {
             if (e==null) return;
@@ -96,21 +85,6 @@ public abstract class Parser<T extends Token, R> {
                     walk(p.element(), hs);
             }
         }
-        public HashSet<Element> walk() {
-            HashSet<Element> ret = new HashSet<Element>();
-            walk(start0, ret);
-            return ret;
-        }
-
-        /*
-        public String toString() {
-            StringBuffer sb = new StringBuffer();
-            for(Element e : walk())
-                if (e instanceof Union)
-                    ((Union)e).toString(sb);
-            return sb.toString();
-        }
-        */
 
         /** the start state */
         public final State   start;
@@ -121,27 +95,29 @@ public abstract class Parser<T extends Token, R> {
         /** construct a parse table for the given grammar */
         public Table(Topology top) { this("s", top); }
         public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); }
-        public Table(Union u, Topology top) {
+        public Table(Union ux, Topology top) {
+            Union start0 = new Union("0");
+            start0.add(new Sequence.Singleton(ux, null, null));
+
+            for(Sequence s : start0) cache.eof.put(s, true);
             cache.eof.put(start0, true);
-            start0seq = new Sequence.Singleton(u, null, null);
-            cache.eof.put(start0seq, true);
-            start0.add(start0seq);
 
             // construct the set of states
             HashMap<HashSet<Position>,State>   all_states    = new HashMap<HashSet<Position>,State>();
-            HashSet<Element>                   all_elements  = walk();
-            all_elements.add(start0);
-            all_elements.add(start0seq);
+            HashSet<Element>                   all_elements  = new HashSet<Element>();
+            walk(start0, all_elements);
             for(Element e : all_elements)
                 cache.ys.put(e, new Walk.YieldSet(e, cache).walk());
-            this.start = new State(closure(), all_states, all_elements);
+            HashSet<Position> hp = new HashSet<Position>();
+            reachable(start0, hp);
+            this.start = new State(hp, all_states, all_elements);
 
             // for each state, fill in the corresponding "row" of the parse table
             for(State state : all_states.values())
                 for(Position p : state.hs) {
 
                     // the Grammar's designated "last position" is the only accepting state
-                    if (p==start0seq.firstp().next())
+                    if (start0.contains(p.owner()) && p.next()==null)
                         state.accept = true;
 
                     // FIXME: how does right-nullability interact with follow restrictions?