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