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=0000000000000000000000000000000000000000;hp=e2ac662a0e18da8aefd37b46087809e60c7cf875;hb=a82ff8c049dd265ecf1d115d60e1be8ecb81a4c1;hpb=01f461b42d1ea2cdfcbc1750e00a2fd8338146ba

diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
deleted file mode 100644
index e2ac662..0000000
--- a/src/edu/berkeley/sbp/Walk.java
+++ /dev/null
@@ -1,270 +0,0 @@
-// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
-
-package edu.berkeley.sbp;
-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Sequence.Position;
-import java.io.*;
-import java.util.*;
-import java.lang.reflect.*;
-import java.lang.ref.*;
-
-/** a traversal of the grammar performed by mapping from SequenceOrElements to a lattice and computing the resulting LUB */
-abstract class Walk<T> {
-    protected HashSet<SequenceOrElement> acc = new HashSet<SequenceOrElement>();
-    protected abstract T bottom(SequenceOrElement e);
-
-    protected final Cache c;
-    public Walk() { this(null); }
-    public Walk(Cache c) { this.c = c; }
-
-    public  T walkSequence(Sequence s) {
-        T ret = bottom(s);
-        for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
-            ret = sequence(s, ret, walk(p.element()));
-        return ret;
-    }
-    
-    public      T walkAtom(Atom r) { return walk(r); }
-    public      T union(Union u, T a, T b) { return  bottom(u); }
-    public      T sequence(Sequence s, T a, T b) { return  bottom(s); }
-    protected   T walk(SequenceOrElement e) {
-        if (acc.contains(e)) return bottom(e);
-        acc.add(e);
-        return walk2(e);
-    }
-
-    protected T walk2(SequenceOrElement e) {
-        if      (e instanceof Atom)     return walkAtom((Atom)e);
-        else if (e instanceof Sequence) return walkSequence((Sequence)e);
-        else if (e instanceof Union) {
-            T ret = bottom(e);
-            for(Sequence s : (Union)e)
-                ret = union((Union)e, ret, walk(s));
-            return ret;
-        } else {
-            throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);
-        }
-    }
-
-    static class YieldSet extends Walk<HashSet<SequenceOrElement>> {
-        private final SequenceOrElement e;
-        public final HashSet<SequenceOrElement> walk() { return walk(e); }
-        public YieldSet(SequenceOrElement e, Cache c)  { super(c); this.e = e; }
-        public HashSet<SequenceOrElement> bottom(SequenceOrElement e)     { return acc; }
-        public HashSet<SequenceOrElement> walkSequence(Sequence seq) { return bottom(seq); }
-        public HashSet<SequenceOrElement> walkAtom(Atom r) {
-            c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
-            return super.walkAtom(r);
-        }
-        protected HashSet<SequenceOrElement> walk2(SequenceOrElement e) {
-            HashSet<SequenceOrElement> ret = super.walk2(e);
-            if (e instanceof Union)
-                for(Sequence s : (Union)e) {
-                    for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss));
-                    for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss));
-                }
-            return ret;
-        }
-    }
-
-    static class YieldSet2 extends Walk<HashSet<SequenceOrElement>> {
-        private final SequenceOrElement e;
-        public final HashSet<SequenceOrElement> walk() { return walk(e); }
-        public YieldSet2(SequenceOrElement e, Cache c)  { super(c); this.e = e; }
-        public HashSet<SequenceOrElement> bottom(SequenceOrElement e)     { return acc; }
-        public HashSet<SequenceOrElement> walkSequence(Sequence seq) { return bottom(seq); }
-        public HashSet<SequenceOrElement> walkAtom(Atom r) {
-            c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
-            return super.walkAtom(r);
-        }
-    }
-
-    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 //////////////////////////////////////////////////////////////////////////////
-
-    static class PossiblyEpsilon extends Walk<Boolean> {
-        public Boolean walkAtom(Atom r) { return false; }
-        public Boolean sequence(Sequence s, Boolean a, Boolean b)  { return new Boolean(a && b); }
-        public Boolean union(Union u, Boolean a, Boolean b)     { return new Boolean(a || b); }
-        public Boolean bottom(SequenceOrElement e)    { return (e instanceof Union) ? false : true; }
-        private HashMap<SequenceOrElement,Boolean> hm = new HashMap<SequenceOrElement,Boolean>();
-        protected Boolean walk(SequenceOrElement e) {
-            if (hm.get(e) != null) return hm.get(e);
-            hm.put(e, false);
-            Boolean ret = walk2(e);
-            hm.put(e, ret);
-            return ret;
-        }
-    }
-
-    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 //////////////////////////////////////////////////////////////////////////////
-
-    static abstract class WalkTokenSet<Tok extends Input> extends Walk<Topology<Tok>> {
-        public Topology<Tok> cs;
-        public WalkTokenSet(Topology<Tok> cs)          { this.cs = cs; }
-        public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
-        public Topology<Tok> bottom(SequenceOrElement e)         { return cs; }
-        public Topology<Tok> walkAtom(Atom r)          { cs = cs.union(r.getTokenTopology()); return cs; }
-    }
-
-    // feature: intersect with "first" set of all positive conjuncts
-    static class First<Tok extends Input> extends WalkTokenSet<Tok> {
-        public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
-        public Topology<Tok> walkSequence(Sequence seq) {
-            for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
-                walk(p.element());
-                if (!c.possiblyEpsilon(p.element())) break;
-            }
-            return cs;
-        }
-    }
-
-    static class Follow<Tok extends Input> extends WalkTokenSet<Tok> {
-        private final SequenceOrElement me;
-        private final HashSet<SequenceOrElement> all;
-        private boolean eof = false;
-        public boolean includesEof() { return eof; }
-        public Follow(Topology<Tok> cs, SequenceOrElement me, HashSet<SequenceOrElement> all, Cache c)  {
-          super(cs, c); this.me = me; this.all = all; }
-        public Topology<Tok> bottom(SequenceOrElement e)                       { return cs; }
-        public Topology<Tok> walkSequence(Sequence seq)                  { return cs; }
-        public Topology<Tok> walkAtom(Atom r) { return walk((SequenceOrElement)r); }
-        public Topology<Tok> walk(SequenceOrElement e) {
-            if (acc.contains(e)) return bottom(e);
-            acc.add(e);
-
-            if (c != null) {
-                Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
-                if (cached != null) {
-                    cs = cs.union(cached);
-                    eof |= c.eof.get(e);
-                    return cs;
-                }
-            }
-
-            Topology<Tok> cso = cs;
-            boolean eofo = eof;
-            eof = c.eof.get(e) != null && c.eof.get(e).booleanValue();
-            cs = cso.empty();
-
-            for(SequenceOrElement x : all) {
-                boolean matched = false;
-                if (!(x instanceof Sequence)) continue;
-                Sequence a = (Sequence)x;
-                Position mp = null;
-                for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
-                    if (matched) cs = cs.union(c.first(pos.element(), cs.empty()));
-                    if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; }
-                    boolean good = false;
-                    if (e instanceof Atom) {
-                        Topology top = c.atoms.get(pos.element());
-                        if (top==null) continue;
-                        if (!(top.containsAll(((Atom)e)))) continue;
-                    } else {
-                        if (c.ys.contains(pos.element(),e)) good = true;
-                    }
-                    if (good) {
-                        mp = pos;
-                        matched = true;
-                    }
-                }
-                if (matched) walk(a);
-            }
-
-            if (e instanceof Sequence) {
-                Sequence s = (Sequence)e;
-                if (s.follow != null) cs = cs.intersect(s.follow.getTokenTopology());
-            }
-
-            if (c != null && e==me) {
-                c.follow.put(e, cs);
-                c.eof.put(e, eof);
-            }
-
-            cso = cso.union(cs);
-            cs = cso;
-            eofo |= eof;
-            eof = eofo;
-
-            return cs;
-        }
-    }
-
-    static class Cache {
-        public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
-        public HashMap<SequenceOrElement,Boolean> eof = new HashMap<SequenceOrElement,Boolean>();
-        public HashMap<SequenceOrElement,Topology> follow = new HashMap<SequenceOrElement,Topology>();
-        public HashMapBag<SequenceOrElement,SequenceOrElement>  ys = new HashMapBag<SequenceOrElement,SequenceOrElement>();
-        public HashMapBag<SequenceOrElement,SequenceOrElement>  ys2 = new HashMapBag<SequenceOrElement,SequenceOrElement>();
-        public HashMap<SequenceOrElement,Topology> atoms = new HashMap<SequenceOrElement,Topology>();
-        public <Tok extends Input> Topology<Tok> first(SequenceOrElement e, Topology<Tok> empty) {
-            return new Walk.First<Tok>(empty, this).walk(e);
-        }
-        final boolean possiblyEpsilon(SequenceOrElement e) {
-            Walk.Cache cache = this;
-            Boolean ret = possiblyEpsilon.get(e);
-            if (ret != null) return ret.booleanValue();
-            ret = new Walk.PossiblyEpsilon().walk(e) ? Boolean.TRUE : Boolean.FALSE;
-            possiblyEpsilon.put(e, ret);
-            return ret;
-        }
-    }
-}