if (p.element() != null && p.element() instanceof Atom)
state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
}
+
if (top instanceof IntegerTopology)
for(State<Token> state : all_states) {
state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor());
state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor());
}
+
+ // crude algorithm to assing an ordinal ordering to every position
+ ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
+ for(State s : all_states) {
+ for(Object po : s) {
+ Sequence.Position p = (Sequence.Position)po;
+ if (al.contains(p)) continue;
+ int i=0;
+ for(; i<al.size(); i++) {
+ if (p.compareTo(al.get(i), cache) > 0)
+ break;
+ }
+ al.add(i, p);
+ }
+ }
+ for(int i=0; i<al.size(); i++)
+ al.get(i).ord = i;
}
private boolean isRightNullable(Position p) {
public int compareTo(Reduction r) {
int ret = compareTo0(r);
- if (ret == 0) {
- Walk.Cache cache = node.state().cache();
- if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
- if (canKill(cache, position, r.position)) ret = 1;
- else if (canKill(cache, r.position, position)) ret = -1;
- if (canNeed(cache, position, r.position)) ret = 1;
- else if (canNeed(cache, r.position, position)) ret = -1;
- }
- return -1 * ret;
+ if (ret != 0) return -1 * ret;
+ return (position.ord - r.position.ord);
}
private static boolean isRightNullable(Walk.Cache c, Position p) {
if (!isRightNullable(cache, himp)) return false;
Sequence me = mep.owner();
Sequence him = himp.owner();
+ Boolean b = me.canKill.get(him);
+ if (b!=null) return b;
for(Sequence killer : him.hates()) {
HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
- if (eq2.contains(me)) return true;
+ if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
}
+ me.canKill.put(him, false);
return false;
}
if (!isRightNullable(cache, himp)) return false;
Sequence me = mep.owner();
Sequence him = himp.owner();
+ Boolean b = me.canNeed.get(him);
+ if (b!=null) return b;
for(Sequence needer : him.needs()) {
HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
- if (eq2.contains(me)) return true;
+ if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
}
+ me.canNeed.put(him, false);
return false;
}
}
public boolean needed_or_hated = false;
- final HashSet<Sequence> hated = new HashSet<Sequence>();
+ public HashMap<Sequence,Boolean> canNeed = new HashMap<Sequence,Boolean>();
+ public HashMap<Sequence,Boolean> canKill = new HashMap<Sequence,Boolean>();
+
+ final HashSet<Sequence> hated = new HashSet<Sequence>();
final HashSet<Sequence> needs = new HashSet<Sequence>();
final HashSet<Sequence> hates = new HashSet<Sequence>();
/** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
class Position implements IntegerMappable {
+ public int ord = -1;
+ public int compareTo(Position p, Walk.Cache cache) {
+ Position position = this;
+ Position rposition = p;
+ int ret = 0;
+ if (Reduction.canKill(cache, position, rposition) &&
+ Reduction.canKill(cache, rposition, position)) throw new Error();
+ if (Reduction.canKill(cache, position, rposition)) ret = 1;
+ else if (Reduction.canKill(cache, rposition, position)) ret = -1;
+ if (Reduction.canNeed(cache, position, rposition)) ret = 1;
+ else if (Reduction.canNeed(cache, rposition, position)) ret = -1;
+ return ret;
+ }
+
private Forest zero = null;
public Forest zero(Input.Region reg) {
if (zero != null) return zero;