src/edu/berkeley/sbp/Grammar.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp;
   4 import edu.berkeley.sbp.util.*;
   5 import edu.berkeley.sbp.Sequence.Pos;
   6 import java.io.*;
   7 import java.util.*;
   8
   9 /**
  10  *  A collection of Elements and Sequences which only reference each other.
  11  *
  12  *  All analyses are done at the Grammar level, since a given
  13  *  Element/Sequence can appear in multiple Grammars.  Some of these
  14  *  analyses depend on which elements *reference* a given element,
  15  *  rather than which elements *are referenced by* a given element.
  16  *
  17  *  This class is package-private because it is likely to change often.
  18  */
  19 abstract class Grammar<Token> {
  20     protected Union rootUnion;
  21
  22     public HashMap<Sequence, Topology> follow = new HashMap<Sequence, Topology>();
  23     public HashSet<Sequence> followEof = new HashSet<Sequence>();
  24     public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
  25     public HashSet<SequenceOrElement> all = new HashSet<SequenceOrElement>();
  26
  27     abstract Topology<Token> emptyTopology();
  28     public Grammar(Union root) {
  29         this.rootUnion = root;
  30         if (root != null)
  31             for(Sequence s : root)
  32                 buildFollowSet(s, emptyTopology(), true);
  33     }
  34
  35     // Follow //////////////////////////////////////////////////////////////////////////////
  36
  37     public Topology follow(Sequence s) { return follow.get(s); }
  38
  39     public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof)  {
  40         all.add(seq);
  41         Topology old = follow.get(seq);
  42         if (old==null) old = followTopology;
  43         else           old = old.union(followTopology);
  44         if (seq.follow != null) old = old.intersect(seq.follow.getTokenTopology());
  45         if (follow.get(seq) != null && follow.get(seq).containsAll(old) && (!eof || followEof.contains(seq)))
  46             return;
  47         follow.put(seq, old);
  48         if (eof) followEof.add(seq);
  49
  50         for(Pos p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
  51             all.add(p.element());
  52             if (p.element() instanceof Union)
  53                 for(Sequence s2 : ((Union)p.element())) {
  54                     buildFollowSet(s2, followTopology, eof);
  55                     for(Sequence ss : s2.needs()) buildFollowSet(ss, followTopology, eof);
  56                     for(Sequence ss : s2.hates()) buildFollowSet(ss, followTopology, eof);
  57                 }
  58             if (!possiblyEpsilon(p.element())) {
  59                 followTopology = followTopology.empty();
  60                 eof = false;
  61             }
  62             followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
  63         }
  64     }
  65
  66     public Topology epsilonFollowSet(Union u) {
  67         Topology ret = emptyTopology();
  68         for(Sequence s : u)
  69             ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
  70         return ret;
  71     }
  72     public Topology epsilonFollowSet(Sequence seq, HashSet<Sequence> seen) {
  73         Topology ret = seq.follow==null ? emptyTopology().complement() : seq.follow.getTokenTopology();
  74         if (seen.contains(seq)) return ret;
  75         seen.add(seq);
  76         for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  77             if (!(p.element() instanceof Union)) continue;
  78             Topology t = emptyTopology();
  79             for(Sequence s : ((Union)p.element()))
  80                 if (possiblyEpsilon(s))
  81                     t = t.union(epsilonFollowSet(s, seen));
  82             ret = ret.intersect(t);
  83         }
  84         return ret;
  85     }
  86
  87     public Topology first(SequenceOrElement e, HashSet<Sequence> seen) {
  88         if (e instanceof Atom) return ((Atom)e).getTokenTopology();
  89         Topology ret = emptyTopology();
  90         if (e instanceof Union) {
  91             for(Sequence s : ((Union)e)) ret = ret.union(first(s, seen));
  92         } else {
  93             Sequence seq = (Sequence)e;
  94             if (seen.contains(seq)) return emptyTopology();
  95             seen.add(seq);
  96             for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  97                 ret = ret.union(first(p.element(), seen));
  98                 if (!possiblyEpsilon(p.element())) break;
  99             }
 100         }
 101         return ret;
 102     }
 103
 104     // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
 105
 106     final boolean possiblyEpsilon(SequenceOrElement e) {
 107         Boolean ret = possiblyEpsilon.get(e);
 108         if (ret != null) return ret.booleanValue();
 109         ret = possiblyEpsilon(e, new HashMap<SequenceOrElement,Boolean>());
 110         possiblyEpsilon.put(e, ret);
 111         return ret;
 112     }
 113
 114     private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
 115         if (hm.get(e) != null) return hm.get(e);
 116         hm.put(e, false);
 117         boolean ret = false;
 118         if      (e instanceof Atom)     ret = false;
 119         else if (e instanceof Union)    { for(Sequence s : (Union)e) ret |= possiblyEpsilon(s, hm); }
 120         else if (e instanceof Sequence) {
 121             ret = true;
 122             Sequence s = (Sequence)e;
 123             for(Pos p = s.firstp(); p!=null && !p.isLast(); p = p.next())
 124                 ret &= possiblyEpsilon(p.element(), hm);
 125         }
 126         hm.put(e, ret);
 127         return ret;
 128     }
 129
 130     public boolean isRightNullable(Pos p) {
 131         if (p.isLast()) return true;
 132         if (!possiblyEpsilon(p.element())) return false;
 133         return isRightNullable(p.next());
 134     }
 135
 136     public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
 137         HashSet<Sequence> eq = new HashSet<Sequence>();
 138         gatherNulledSubsequences(parent, eq);
 139         return eq.contains(potentialSubSequence);
 140     }
 141     private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
 142         if (eq.contains(seq)) return;
 143         eq.add(seq);
 144         Pos p = seq.firstp();
 145         for(; !p.isLast(); p = p.next()) {
 146             if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union)
 147                 for(Sequence s : ((Union)p.element()))
 148                     gatherNulledSubsequences(s, eq);
 149             if (!possiblyEpsilon(p.element())) break;
 150         }
 151     }
 152
 153     // Pos Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
 154
 155     public boolean canKill(Pos mep, Pos himp) {
 156         if (!isRightNullable(mep))  return false;
 157         if (!isRightNullable(himp)) return false;
 158         Sequence me  = mep.owner();
 159         Sequence him = himp.owner();
 160         Boolean b = me.canKill.get(him);
 161         if (b!=null) return b;
 162         for(Sequence killer : him.hates())
 163             if (isNulledSubsequence(killer, me))
 164                 { me.canKill.put(him, true); return true; }
 165         me.canKill.put(him, false);
 166         return false;
 167     }
 168
 169     public boolean canNeed(Pos mep, Pos himp) {
 170         if (!isRightNullable(mep))  return false;
 171         if (!isRightNullable(himp)) return false;
 172         Sequence me  = mep.owner();
 173         Sequence him = himp.owner();
 174         Boolean b = me.canNeed.get(him);
 175         if (b!=null) return b;
 176         for(Sequence needer : him.needs())
 177             if (isNulledSubsequence(needer, me))
 178                 { me.canNeed.put(him, true); return true; }
 179         me.canNeed.put(him, false);
 180         return false;
 181     }
 182
 183     public int comparePositions(Pos position, Pos rposition) {
 184         int ret = 0;
 185         if (canKill(position, rposition) && canKill(rposition, position)) throw new Error();
 186         if      (canKill(position,  rposition))  ret = -1;
 187         else if (canKill(rposition, position))   ret =  1;
 188         else if (canNeed(position,  rposition))  ret = -1;
 189         else if (canNeed(rposition, position))   ret =  1;
 190         /*
 191         else if (isNulledSubsequence(position.owner(),  rposition.owner()) && isNulledSubsequence(rposition.owner(),  position.owner())) ret = 0;
 192         else if (isNulledSubsequence(position.owner(),  rposition.owner())) ret =  1;
 193         else if (isNulledSubsequence(rposition.owner(), position.owner()))  ret = -1;
 194         */
 195         return ret;
 196     }
 197
 198 }
 199