checkpoint harmony

[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 db08afc..18bec5a 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -12,7 +12,7 @@ public abstract class Parser<T extends Token, R> {
 
     /** 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; }
+    protected Parser(Table pt) { this.pt = pt; }
 
     /** implement this method to create the output forest corresponding to a lone shifted input token */
     public abstract Forest<R> shiftedToken(T t, Token.Location loc);
@@ -20,17 +20,6 @@ public abstract class Parser<T extends Token, R> {
     /** this method must return an empty topology of the input token type */
     public abstract Topology<T> top();
 
-    /** parse <tt>input</tt> for a exactly one unique result, throwing <tt>Ambiguous</tt> if not unique or <tt>ParseFailed</tt> if none */
-    public Tree<R> parse1(Token.Stream<T> input) throws IOException, ParseFailed, Ambiguous {
-        Forest<R> ret = parse(input);
-        try { return ret.expand1(); }
-        catch (Ambiguous a) {
-            System.out.println("while expanding:");
-            System.out.println(ret);
-            throw a;
-        }
-    }
-
     /** parse <tt>input</tt>, using the table <tt>pt</tt> to drive the parser */
     public Forest<R> parse(Token.Stream<T> input) throws IOException, ParseFailed {
         GSS gss = new GSS();
@@ -48,10 +37,6 @@ public abstract class Parser<T extends Token, R> {
             current = next;
         }
     }
-    
-
-    // Exceptions //////////////////////////////////////////////////////////////////////////////
-
 
     // Table //////////////////////////////////////////////////////////////////////////////
 
@@ -60,8 +45,6 @@ public abstract class Parser<T extends Token, R> {
 
         public final Walk.Cache cache = this;
 
-        public HashMapBag<Position,State> byPosition = new HashMapBag<Position,State>();
-        
         private void walk(Element e, HashSet<Element> hs) {
             if (e==null) return;
             if (hs.contains(e)) return;
@@ -95,7 +78,7 @@ public abstract class Parser<T extends Token, R> {
             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());
+                cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk());
             HashSet<Position> hp = new HashSet<Position>();
             reachable(start0, hp);
             this.start = new State(hp, all_states, all_elements);
@@ -108,7 +91,7 @@ public abstract class Parser<T extends Token, R> {
                     if (start0.contains(p.owner()) && p.next()==null)
                         state.accept = true;
 
-                    if (p.isRightNullable(cache)) {
+                    if (isRightNullable(p)) {
                         Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache);
                         Reduction red = new Reduction(p);
 
@@ -138,6 +121,12 @@ public abstract class Parser<T extends Token, R> {
             }
         }
 
+        private boolean isRightNullable(Position p) {
+            if (p.isLast()) return true;
+            if (!p.element().possiblyEpsilon(this)) return false;
+            return isRightNullable(p.next());
+        }
+
         /** a single state in the LR table and the transitions possible from it */
 
         public class State implements Comparable<Table.State>, IntegerMappable, Iterable<Position> {
@@ -235,7 +224,6 @@ public abstract class Parser<T extends Token, R> {
                 // register ourselves in the all_states hash so that no
                 // two states are ever created with an identical position set
                 all_states.put(hs, this);
-                for(Position p : hs) byPosition.add(p,this);
 
                 // Step 1a: examine all Position's in this state and compute the mappings from
                 //          sets of follow tokens (tokens which could follow this position) to sets
@@ -268,27 +256,14 @@ public abstract class Parser<T extends Token, R> {
                 //         "yields" [in one or more step] is used instead of "produces" [in exactly one step]
                 //         to avoid having to iteratively construct our set of States as shown in most
                 //         expositions of the algorithm (ie "keep doing XYZ until things stop changing").
-                /*
-                for(Element e : all_elements) {
-                    if (e instanceof Atom) continue;
-                    HashSet<Position> h = new Walk.Closure(null, g.cache).closure(e, hs);
-                    State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h);
-                    if (gotoSetNonTerminals.get(e) != null)
-                        throw new Error("this should not happen");
-                    gotoSetNonTerminals.put(e, s);
-                }
-                */
                 HashMapBag<Element,Position> move = new HashMapBag<Element,Position>();
                 for(Position p : hs) {
                     Element e = p.element();
                     if (e==null) continue;
-                    HashSet<Element> ys = cache.ys.get(e);
-                    if (ys != null) {
-                        for(Element y : ys) {
-                            HashSet<Position> hp = new HashSet<Position>();
-                            reachable(p.next(), hp);
-                            move.addAll(y, hp);
-                        }
+                    for(Element y : cache.ys.getAll(e)) {
+                        HashSet<Position> hp = new HashSet<Position>();
+                        reachable(p.next(), hp);
+                        move.addAll(y, hp);
                     }
                 }
                 for(Element y : move) {