summary patch for Nov->Jan work

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

diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
index a92bcb8..0b19cd4 100644 (file)
--- a/src/edu/berkeley/sbp/Walk.java
+++ b/src/edu/berkeley/sbp/Walk.java
@@ -64,6 +64,34 @@ abstract class Walk<T> {
         }
     }
 
+    static class EquivalentTo extends Walk<HashSet<Sequence>> {
+        private final Sequence s;
+        private final HashSet<Sequence> eq = new HashSet<Sequence>();
+        public final HashSet<Sequence> walk() { return walk(s); }
+        public EquivalentTo(Sequence e, Cache c)  {
+            super(c); this.s = e;
+        }
+        public HashSet<Sequence> bottom(SequenceOrElement e)     { return eq; }
+        public HashSet<Sequence> walkSequence(Sequence seq) {
+            eq.add(seq);
+            Position p = seq.firstp();
+            for(; !p.isLast(); p = p.next()) {
+                if (!p.isLast() && isRightNullable(p.next()))
+                    walk(p.element());
+                if (!c.possiblyEpsilon(p.element())) break;
+            }
+            return eq;
+        }
+        public HashSet<Sequence> walkAtom(Atom r) {
+            return eq;
+        }
+        private boolean isRightNullable(Position p) {
+            if (p.isLast()) return true;
+            if (!c.possiblyEpsilon(p.element())) return false;
+            return isRightNullable(p.next());
+        }
+    }
+
 
     // Boolean //////////////////////////////////////////////////////////////////////////////
 
@@ -82,6 +110,34 @@ abstract class Walk<T> {
         }
     }
 
+    static class EpsilonFollowSet extends Walk<Atom> {
+        Atom all;
+        Atom empty;
+        public EpsilonFollowSet(Atom a, Atom empty, Cache c) {
+            super(c);
+            this.all = all;
+            this.empty = empty;
+        }
+        public Atom walkAtom(Atom r) { return all; }
+        public Atom walkSequence(Sequence s) {
+            if (s.follow==null) return all;
+            return s.follow;
+        }
+        public Atom sequence(Sequence s, Atom a, Atom b)  {
+            throw new RuntimeException();
+        }
+        public Atom union(Union u, Atom a, Atom b) {
+            /*
+            if (a==null) return b;
+            if (b==null) return a;
+            */
+            if (a==null || b==null) return all;
+            return (Atom)a.union(b);
+        }
+        public Atom bottom(SequenceOrElement e) {
+            return (e instanceof Union) ? empty : all;
+        }
+    }
 
     // Input-Set //////////////////////////////////////////////////////////////////////////////