-// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
* analyses depend on which elements *reference* a given element,
* rather than which elements *are referenced by* a given element.
*
- * This class is package-private because it is likely to change often.
+ * All members of this class are package-private because they are
+ * likely to change often.
*/
-abstract class Grammar<Token> {
+public abstract class Grammar<Token> {
protected Union rootUnion;
- public HashMap<Sequence, Topology> follow = new HashMap<Sequence, Topology>();
- public HashSet<Sequence> followEof = new HashSet<Sequence>();
- public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
- public HashSet<SequenceOrElement> all = new HashSet<SequenceOrElement>();
+ HashMap<Sequence, Topology> follow = new HashMap<Sequence, Topology>();
+ HashSet<Sequence> followEof = new HashSet<Sequence>();
+ final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
+ HashSet<SequenceOrElement> all = new HashSet<SequenceOrElement>();
abstract Topology<Token> emptyTopology();
- public Grammar(Union root) {
+ Grammar(Union root) {
this.rootUnion = root;
if (root != null)
for(Sequence s : root)
// Follow //////////////////////////////////////////////////////////////////////////////
- public Topology follow(Sequence s) { return follow.get(s); }
+ Topology follow(Sequence s) { return follow.get(s); }
- public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
+ void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) {
all.add(seq);
Topology old = follow.get(seq);
if (old==null) old = followTopology;
follow.put(seq, old);
if (eof) followEof.add(seq);
- for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
+ for(Pos p = seq.firstp().last().prev(); p!=null; p = p.prev()) {
all.add(p.element());
if (p.element() instanceof Union)
for(Sequence s2 : ((Union)p.element())) {
}
}
- public Topology epsilonFollowSet(Union u) {
+ Topology epsilonFollowSet(Union u) {
Topology ret = emptyTopology();
for(Sequence s : u)
ret = ret.union(epsilonFollowSet(s, new HashSet<Sequence>()));
return ret;
}
- public Topology epsilonFollowSet(Sequence seq, HashSet<Sequence> seen) {
+ Topology epsilonFollowSet(Sequence seq, HashSet<Sequence> seen) {
Topology ret = seq.follow==null ? emptyTopology().complement() : seq.follow.getTokenTopology();
if (seen.contains(seq)) return ret;
seen.add(seq);
- for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+ for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
if (!(p.element() instanceof Union)) continue;
Topology t = emptyTopology();
for(Sequence s : ((Union)p.element()))
return ret;
}
- public Topology first(SequenceOrElement e, HashSet<Sequence> seen) {
+ Topology first(SequenceOrElement e, HashSet<Sequence> seen) {
if (e instanceof Atom) return ((Atom)e).getTokenTopology();
Topology ret = emptyTopology();
if (e instanceof Union) {
Sequence seq = (Sequence)e;
if (seen.contains(seq)) return emptyTopology();
seen.add(seq);
- for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
+ for(Pos p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
ret = ret.union(first(p.element(), seen));
if (!possiblyEpsilon(p.element())) break;
}
else if (e instanceof Sequence) {
ret = true;
Sequence s = (Sequence)e;
- for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
+ for(Pos p = s.firstp(); p!=null && !p.isLast(); p = p.next())
ret &= possiblyEpsilon(p.element(), hm);
}
hm.put(e, ret);
return ret;
}
- public boolean isRightNullable(Position p) {
+ boolean isRightNullable(Pos p) {
if (p.isLast()) return true;
if (!possiblyEpsilon(p.element())) return false;
return isRightNullable(p.next());
}
- public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
+ boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) {
HashSet<Sequence> eq = new HashSet<Sequence>();
gatherNulledSubsequences(parent, eq);
return eq.contains(potentialSubSequence);
private void gatherNulledSubsequences(Sequence seq, HashSet<Sequence> eq) {
if (eq.contains(seq)) return;
eq.add(seq);
- Position p = seq.firstp();
+ Pos p = seq.firstp();
for(; !p.isLast(); p = p.next()) {
if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union)
for(Sequence s : ((Union)p.element()))
}
}
- // Position Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
+ // Pos Ordinality Comparisons //////////////////////////////////////////////////////////////////////////////
- public boolean canKill(Position mep, Position himp) {
+ boolean canKill(Pos mep, Pos himp) {
if (!isRightNullable(mep)) return false;
if (!isRightNullable(himp)) return false;
Sequence me = mep.owner();
return false;
}
- public boolean canNeed(Position mep, Position himp) {
+ boolean canNeed(Pos mep, Pos himp) {
if (!isRightNullable(mep)) return false;
if (!isRightNullable(himp)) return false;
Sequence me = mep.owner();
return false;
}
- public int comparePositions(Position position, Position rposition) {
+ int comparePositions(Pos position, Pos rposition) {
int ret = 0;
if (canKill(position, rposition) && canKill(rposition, position)) throw new Error();
if (canKill(position, rposition)) ret = -1;