X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FWalk.java;fp=src%2Fedu%2Fberkeley%2Fsbp%2FWalk.java;h=0b19cd49b2fee38880592f3a350b7874795a875c;hp=a92bcb8eaa6d875f243b3e74d76398e169c552d1;hb=e84029a8b861075d6d0ed5040f919b2e4da4c98f;hpb=a8478f5ddfbfbc8d910d09f27163cbd55752d3b6

diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
index a92bcb8..0b19cd4 100644
--- 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 //////////////////////////////////////////////////////////////////////////////