1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.util.*;
5 import edu.berkeley.sbp.Sequence.Pos;
10 * A collection of Elements and Sequences which only reference each other.
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.
17 * All members of this class are package-private because they are
18 * likely to change often.
20 public abstract class Grammar<Token> {
21 protected Union rootUnion;
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>();
28 abstract Topology<Token> emptyTopology();
30 this.rootUnion = root;
32 for(Sequence s : root)
33 buildFollowSet(s, emptyTopology(), true);
36 // Follow //////////////////////////////////////////////////////////////////////////////
38 Topology follow(Sequence s) { return follow.get(s); }
40 void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
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)))
49 if (eof) followEof.add(seq);
51 for(Pos p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
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);
59 if (!possiblyEpsilon(p.element())) {
60 followTopology = followTopology.empty();
63 followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
67 Topology epsilonFollowSet(Union u) {
68 Topology ret = emptyTopology();
70 ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
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;
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);
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));
94 Sequence seq = (Sequence)e;
95 if (seen.contains(seq)) return emptyTopology();
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;
105 // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
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);
115 private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
116 if (hm.get(e) != null) return hm.get(e);
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) {
123 Sequence s = (Sequence)e;
124 for(Pos p = s.firstp(); p!=null && !p.isLast(); p = p.next())
125 ret &= possiblyEpsilon(p.element(), hm);
131 boolean isRightNullable(Pos p) {
132 if (p.isLast()) return true;
133 if (!possiblyEpsilon(p.element())) return false;
134 return isRightNullable(p.next());
137 boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
138 HashSet<Sequence> eq = new HashSet<Sequence>();
139 gatherNulledSubsequences(parent, eq);
140 return eq.contains(potentialSubSequence);
142 private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
143 if (eq.contains(seq)) return;
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;
154 // Pos Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
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);
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);
184 int comparePositions(Pos position, Pos rposition) {
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;
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;