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 * This class is package-private because it is likely to change often.
19 abstract class Grammar<Token> {
20 protected Union rootUnion;
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>();
27 abstract Topology<Token> emptyTopology();
28 public Grammar(Union root) {
29 this.rootUnion = root;
31 for(Sequence s : root)
32 buildFollowSet(s, emptyTopology(), true);
35 // Follow //////////////////////////////////////////////////////////////////////////////
37 public Topology follow(Sequence s) { return follow.get(s); }
39 public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
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)))
48 if (eof) followEof.add(seq);
50 for(Pos p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
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);
58 if (!possiblyEpsilon(p.element())) {
59 followTopology = followTopology.empty();
62 followTopology = followTopology.union(first(p.element(), new HashSet<Sequence>()));
66 public Topology epsilonFollowSet(Union u) {
67 Topology ret = emptyTopology();
69 ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
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;
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);
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));
93 Sequence seq = (Sequence)e;
94 if (seen.contains(seq)) return emptyTopology();
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;
104 // Epsilon-Ness //////////////////////////////////////////////////////////////////////////////
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);
114 private boolean possiblyEpsilon(SequenceOrElement e, HashMap<SequenceOrElement,Boolean> hm) {
115 if (hm.get(e) != null) return hm.get(e);
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) {
122 Sequence s = (Sequence)e;
123 for(Pos p = s.firstp(); p!=null && !p.isLast(); p = p.next())
124 ret &= possiblyEpsilon(p.element(), hm);
130 public boolean isRightNullable(Pos p) {
131 if (p.isLast()) return true;
132 if (!possiblyEpsilon(p.element())) return false;
133 return isRightNullable(p.next());
136 public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
137 HashSet<Sequence> eq = new HashSet<Sequence>();
138 gatherNulledSubsequences(parent, eq);
139 return eq.contains(potentialSubSequence);
141 private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
142 if (eq.contains(seq)) return;
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;
153 // Pos Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
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);
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);
183 public int comparePositions(Pos position, Pos rposition) {
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;
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;