_____________________________________________________________________________
Immediately
+ - keywordification (ie globally reject from all productions?
+ - generalized follow-by?)
+
- clean up util package
- currently we GC the doomed stack when the parent dies... but
int numReductions = 0;
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
- class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
+ class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz /*, Iterable<StateNode>*/ {
// FIXME: right now, these are the performance bottleneck
private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
for(StateNode n : h) n.check();
}
numOldNodes = hash.size();
- for(StateNode n : hash.values()) {
+ for(StateNode n : hash) {
if (token == null && n.state().isAccepting()) {
if (finalResult==null) finalResult = new Forest.Many();
for(ResultNode r : n)
public int size() { return hash==null ? 0 : hash.size(); }
public int pos() { return pos; }
public Tok getToken() { return token; }
- public Iterator<StateNode> iterator() { return hash.iterator(); }
+ //public Iterator<StateNode> iterator() { return hash.iterator(); }
public GSS getGSS() { return GSS.this; }
// GraphViz //////////////////////////////////////////////////////////////////////////////
FileOutputStream fos = new FileOutputStream(filename);
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
GraphViz gv = new GraphViz();
+ /*
for(Object n : this)
((StateNode)n).toGraphViz(gv);
+ */
gv.dump(p);
p.flush();
p.close();
GraphViz.ToGraphViz,
Iterable<OtherNode> {
+ private final GSS.Phase phase;
+ private final GSS.Phase predecessorPhase;
+ protected boolean destroyed = false;
+ private int numNonDoomedSuccessors = 0;
+ private boolean hasPathToRoot = false;
+
+ private FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
+ private FastSet<OtherNode> successors = new FastSet<OtherNode>();
+ //protected HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
+ //protected HashSet<OtherNode> successors = new HashSet<OtherNode>();
+
+ public GSS.Phase phase() { return phase; }
+ public GSS.Phase predecessorPhase() { return predecessorPhase; }
+ public boolean hasPredecessors() { return predecessors.size() > 0; }
+ public boolean hasSuccessors() { return successors.size() > 0; }
+ public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
+
+ public boolean hasPathToRoot() { return hasPathToRoot; }
+ public void updatePathsToRootAfterRemoval() {
+ if (!hasPathToRoot()) return;
+ for(OtherNode on : predecessors)
+ if (on.hasPathToRoot())
+ return;
+ hasPathToRoot = false;
+ for(OtherNode on : successors)
+ on.updatePathsToRootAfterRemoval();
+ }
+
/**
* Every Node has a phase; StateNodes belong to the phase in
* which they were shifted, ResultNodes belong to the phase of
this.predecessorPhase = predecessorPhase;
}
- private final GSS.Phase phase;
- private final GSS.Phase predecessorPhase;
- public GSS.Phase phase() { return phase; }
- public GSS.Phase predecessorPhase() { return predecessorPhase; }
- protected boolean destroyed = false;
- private int numNonDoomedSuccessors = 0;
- public boolean hasSuccessors() { return successors.size() > 0; }
- public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
-
/** only to be invoked (or overridden as public) by the subclass */
protected void addPred(OtherNode pred) {
if (predecessors.contains(pred)) throw new Error("a predecessor was added twice");
if (pred.phase() != predecessorPhase()) throw new Error();
predecessors.add(pred);
pred.addSucc(this);
+ if (pred.hasPathToRoot()) hasPathToRoot = true;
}
public void addSucc(OtherNode succ) {
if (successors.contains(succ)) throw new Error("a predecessor was added twice");
numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1;
if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error();
}
- public void removeSucc(OtherNode succ) {
- if (!successors.contains(succ)) return;
- successors.remove(succ);
- numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
- check();
- }
protected void destroy() {
destroyed = true;
- while(predecessors.size() > 0)
- for(OtherNode pred : predecessors) {
- removePred(pred);
- pred.removeSucc(this);
- break;
- }
+ while(predecessors.size() > 0) {
+ OtherNode pred = predecessors.first();
+ removePred(pred);
+ pred.removeSucc(this);
+ }
predecessors = null;
- while(successors.size() > 0)
- for(OtherNode succ : successors) {
- removeSucc(succ);
- succ.removePred(this);
- break;
- }
+ while(successors.size() > 0) {
+ OtherNode succ = successors.first();
+ removeSucc(succ);
+ succ.removePred(this);
+ }
successors = null;
}
-
- public abstract boolean isDoomedState();
- protected abstract void check();
-
+ public void removeSucc(OtherNode succ) {
+ if (!successors.contains(succ)) return;
+ successors.remove(succ);
+ numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
+ check();
+ }
public void removePred(OtherNode pred) {
if (!predecessors.contains(pred)) return;
predecessors.remove(pred);
+ updatePathsToRootAfterRemoval();
check();
}
- protected FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
- protected FastSet<OtherNode> successors = new FastSet<OtherNode>();
- //private HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
- //private HashSet<OtherNode> successors = new HashSet<OtherNode>();
+
+ public abstract boolean isDoomedState();
+ protected abstract void check();
public Iterator<OtherNode> iterator() { return predecessors.iterator(); }
+ public Iterable<OtherNode> successors() { return successors; }
public boolean noSuccessors() { return successors.size()==0; }
public boolean predecessorsContains(OtherNode n) {
static void error(String message, GSS.Phase phase, Object token, Input.Region region) throws ParseFailed {
error(message,
token,
- phase,
+ /*phase*/null,
region,
phase.getGSS().getInput(),
phase.getGSS());
*/
}
HashMap<Element,Input.Location> hm = new HashMap<Element,Input.Location>();
- for(StateNode no : nodes)
- barf(hm, no, 0, false, region.getStart());
+ if (nodes!=null)
+ for(StateNode no : nodes)
+ barf(hm, no, 0, false, region.getStart());
ret.append("\n expected: ");
Set<Element> hs = hm.keySet();
if (hs.size() == 1) {
public boolean isDoomedState() { /* this is irrelevant */ return false; }
public Forest getForest() { return f; }
public String toString() { return super.toString()+"->"+phase(); }
+ public boolean hasPathToRoot() {
+ if (predecessorPhase()==null) return true;
+ return super.hasPathToRoot();
+ }
public void check() {
if (destroyed) return;
- if (successors.size()==0) destroy();
- else if (predecessors.size()==0) destroy();
+ if (!hasSuccessors() || !hasPredecessors()) destroy();
}
protected void destroy() {
if (destroyed) return;
protected void addPred(StateNode pred) {
super.addPred(pred);
// results should have at most one predecessor
- if (predecessors.size() > 1) throw new Error();
+ //if (predecessors.size() > 1) throw new Error();
}
public ResultNode() { this(null, null, null); }
extends Node<ResultNode>
implements Invokable<Pos, ResultNode, Object> {
- private boolean fromEmptyReduction;
private final Parser.Table.State state;
/** which GSS.Phase this StateNode belongs to */
public Parser.Table.State state() { return state; }
public boolean isDoomedState() { return state.doomed; }
+ public boolean hasPathToRoot() {
+ if (state.doomed) return false;
+ return super.hasPathToRoot();
+ }
public void check() {
if (destroyed) return;
// - be on the frontier or
// - have a non-doomed node closer to the frontier than themself
if (phase().isFrontier()) dead = false;
- else for(ResultNode r : successors)
+ else for(ResultNode r : successors())
if (state.doomed) { if (r.hasSuccessors()) { dead = false; break; } }
else { if (r.hasNonDoomedSuccessors()) { dead = false; break; } }
- dead |= predecessors.size()==0;
+ dead |= !hasPredecessors();
if (!dead) return;
if (phase() != null && phase().hash != null)
phase().hash.remove(state, predecessorPhase());
phase().newNodeFromReduction(r.rewrite(region), r, this);
} else {
// never start reductions at a node that was created via a right-nulled rule
- if (only.reduction().numPops()==0) return;
+ if (only.reduction() != null && only.reduction().numPops()==0) return;
reduce(r, r.numPops()-1, phase(), only);
}
}
private void reduce(Pos r, int pos, GSS.Phase target, ResultNode only) {
- for(ResultNode res : predecessors)
+ for(ResultNode res : this)
if (only == null || res == only)
for(StateNode pred : res) {
Forest[] holder = r.holder;
Forest old = pos >= holder.length ? null : holder[pos];
if (pos < holder.length) holder[pos] = res.getForest();
if (pos>0) pred.reduce(r, pos-1, target, null);
- else {
- Input.Region region = pred.phase().getLocation().createRegion(target.getLocation());
- new Reduction(pred, r, r.rewrite(region), target);
- }
+ else new Reduction(pred, r,
+ pred.hasPathToRoot()
+ ? r.rewrite(pred.phase().getLocation().createRegion(target.getLocation()))
+ : null,
+ target);
if (pos < holder.length) holder[pos] = old;
}
}
StateNode(GSS.Phase phase, ResultNode pred, State state) {
super(phase, pred.phase());
this.state = state;
- this.fromEmptyReduction = pred!=null && pred.reduction()!=null && pred.reduction().numPops()==0;
if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!");
phase.hash.put(state, pred.phase(), this);
addPred(pred);
// Add/Remove Successors/Predecessors //////////////////////////////////////////////////////////////////////////////
public void addPred(Forest f, Pos reduction, StateNode pred) {
- for(ResultNode r : predecessors)
+ for(ResultNode r : this)
if (r.predecessorsContains(pred)) {
r.merge(f);
return;
projects / sbp.git / commitdiff