src/edu/berkeley/sbp/Walk.java

   1 package edu.berkeley.sbp;
   2 import edu.berkeley.sbp.util.*;
   3 import edu.berkeley.sbp.*;
   4 import edu.berkeley.sbp.*;
   5 import edu.berkeley.sbp.Sequence.Position;
   6 import java.io.*;
   7 import java.util.*;
   8 import java.lang.reflect.*;
   9 import java.lang.ref.*;
  10
  11 /** a traversal of the grammar performed by mapping from Elements to a lattice and computing the resulting LUB */
  12 abstract class Walk<T> {
  13     protected HashSet<Element> acc = new HashSet<Element>();
  14     protected abstract T bottom(Element e);
  15
  16     protected final Cache c;
  17     public Walk() { this(null); }
  18     public Walk(Cache c) { this.c = c; }
  19
  20     public  T sequence(Sequence s) {
  21         T ret = bottom(s);
  22         for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
  23             ret = sequence(s, ret, walk(p.element()));
  24         return ret;
  25     }
  26
  27     public      T walkAtom(Atom r) { return walk(r); }
  28     public      T union(Union u, T a, T b) { return  bottom(u); }
  29     public      T sequence(Sequence s, T a, T b) { return  bottom(s); }
  30     protected   T walk(Element e) {
  31         if (acc.contains(e)) return bottom(e);
  32         acc.add(e);
  33         return walk2(e);
  34     }
  35
  36     protected T walk2(Element e) {
  37         if      (e instanceof Atom)     return walkAtom((Atom)e);
  38         else if (e instanceof Sequence) return sequence((Sequence)e);
  39         else if (e instanceof Union) {
  40             T ret = bottom(e);
  41             for(Sequence s : (Union)e) ret = union((Union)e, ret, walk(s));
  42             return ret;
  43         } else {
  44             throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);
  45         }
  46     }
  47
  48     static class YieldSet extends Walk<HashSet<Element>> {
  49         private final Element e;
  50         public final HashSet<Element> walk() { return walk(e); }
  51         public YieldSet(Element e, Cache c)  { super(c); this.e = e; }
  52         public HashSet<Element> bottom(Element e)     { return acc; }
  53         public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
  54         public HashSet<Element> walkAtom(Atom r) {
  55             c.atoms.put(e, c.atoms.get(e)==null ? r.top() : c.atoms.get(e).union(r.top()));
  56             return super.walkAtom(r);
  57         }
  58     }
  59
  60
  61     // Boolean //////////////////////////////////////////////////////////////////////////////
  62
  63     static class PossiblyEpsilon extends Walk<Boolean> {
  64         public Boolean walkAtom(Atom r) { return false; }
  65         public Boolean sequence(Sequence s, Boolean a, Boolean b)  { return new Boolean(a && b); }
  66         public Boolean union(Union u, Boolean a, Boolean b)     { return new Boolean(a || b); }
  67         public Boolean bottom(Element e)    { return (e instanceof Union) ? false : true; }
  68         private HashMap<Element,Boolean> hm = new HashMap<Element,Boolean>();
  69         protected Boolean walk(Element e) {
  70             if (hm.get(e) != null) return hm.get(e);
  71             hm.put(e, false);
  72             Boolean ret = walk2(e);
  73             hm.put(e, ret);
  74             return ret;
  75         }
  76     }
  77
  78
  79     // Token-Set //////////////////////////////////////////////////////////////////////////////
  80
  81     static abstract class WalkTokenSet<Tok extends Token> extends Walk<Topology<Tok>> {
  82         public Topology<Tok> cs;
  83         public WalkTokenSet(Topology<Tok> cs)          { this.cs = cs; }
  84         public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
  85         public Topology<Tok> bottom(Element e)         { return cs; }
  86         public Topology<Tok> walkAtom(Atom r)          { cs.add(r.top()); return cs; }
  87     }
  88
  89     class First<Tok extends Token> extends WalkTokenSet<Tok> {
  90         public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
  91         public Topology<Tok> sequence(Sequence seq) {
  92             for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  93                 walk(p.element());
  94                 if (!p.element().possiblyEpsilon(c)) break;
  95             }
  96             return cs;
  97         }
  98     }
  99
 100     class Last<Tok extends Token> extends WalkTokenSet<Tok> {
 101         public Last(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
 102         public Topology<Tok> sequence(Sequence seq) { sequence(seq.firstp()); return cs; }
 103         private Topology<Tok> sequence(Position p) {
 104             if (p==null) return null;
 105             Topology<Tok> ret = sequence(p.next());
 106             if (ret!=null) return ret;
 107             if (p.isLast()) return null;
 108             if (p.element().possiblyEpsilon(c)) return null;
 109             if (p.element()==null) return null;
 110             return walk(p.element());
 111         }
 112     }
 113
 114     static class Follow<Tok extends Token> extends WalkTokenSet<Tok> {
 115         private final Element me;
 116         private final HashSet<Element> all;
 117         private boolean eof = false;
 118         public boolean includesEof() { return eof; }
 119         public Follow(Topology<Tok> cs, Element me, HashSet<Element> all, Cache c)  { super(cs, c); this.me = me; this.all = all; }
 120         public Topology<Tok> bottom(Element e)                       { return cs; }
 121         public Topology<Tok> sequence(Sequence seq)                  { return cs; }
 122         public Topology<Tok> walkAtom(Atom r) { return walk((Element)r); }
 123         public Topology<Tok> walk(Element e) {
 124             if (acc.contains(e)) return bottom(e);
 125             acc.add(e);
 126
 127             if (c != null) {
 128                 Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
 129                 if (cached != null) {
 130                     cs.add(cached);
 131                     eof |= c.eof.get(e);
 132                     return cs;
 133                 }
 134             }
 135
 136             Topology<Tok> cso = cs;
 137             boolean eofo = eof;
 138             eof = false;
 139             cs = cso.fresh();
 140
 141             if (e instanceof Parser.Table.Top) eof = true;
 142             for(Element x : all) {
 143                 boolean matched = false;
 144                 if (x instanceof Parser.Table.Top) walk(x); // because this symbol might not appear in any other Sequence
 145                 if (!(x instanceof Sequence)) continue;
 146                 Sequence a = (Sequence)x;
 147                 Position mp = null;
 148                 for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
 149                     if (matched) cs.add(new First<Tok>(cs.fresh(), c).walk(pos.element()));
 150                     if (pos.isLast()) { matched = (matched && pos.element().possiblyEpsilon(c)); continue; }
 151                     boolean good = false;
 152                     if (e instanceof Atom) {
 153                         Topology top = c.atoms.get(pos.element());
 154                         if (top==null) continue;
 155                         if (!(top.containsAll(((Atom)e).top()))) continue;
 156                     } else {
 157                         if (c.ys.get(pos.element()).contains(e)) good = true;
 158                     }
 159                     if (good) {
 160                         mp = pos;
 161                         matched = true;
 162                     }
 163                 }
 164                 if (matched) walk(a);
 165             }
 166
 167             if (e instanceof Repeat.MaximalSequence || e instanceof Repeat.Maximal)
 168                 cs.remove(new Last<Tok>(cs.fresh(), c).walk(e));
 169
 170             if (c != null && e==me) {
 171                 c.follow.put(e, cs.dup());
 172                 c.eof.put(e, eof);
 173             }
 174
 175             cso.add(cs);
 176             cs = cso;
 177             eofo |= eof;
 178             eof = eofo;
 179
 180             return cs;
 181         }
 182     }
 183
 184     static class Cache {
 185         public final HashMap<Element,Boolean> possiblyEpsilon = new HashMap<Element,Boolean>();
 186         public HashMap<Element,Boolean> eof = new HashMap<Element,Boolean>();
 187         public HashMap<Element,Topology> follow = new HashMap<Element,Topology>();
 188         public HashMap<Element,HashSet<Element>>  ys            = new HashMap<Element,HashSet<Element>>();
 189         public HashMap<Element,Topology> atoms = new HashMap<Element,Topology>();
 190     }
 191 }