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, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+ class Phase<Tok> implements Invokable<State, Node, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
// FIXME: right now, these are the performance bottleneck
private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
parser.spin();
reductionQueue.add(r);
}
- public void invoke(State st, Result result) {
+
+ public void invoke(State st, Node pred, Forest f) {
parser.spin();
- good |= next.newNode(result, st, false);
+ good |= next.newNode(f, null, pred, st, false);
}
/** the token immediately after this phase */
final Tok token;
final int pos;
-
public IntPairMap<Node> hash = new IntPairMap<Node>(); /* ALLOC */
private boolean good = false;
private Phase next = null;
public Phase(State startState) throws ParseFailed, IOException {
this(null, null);
- Result primordealResult = new Result(null, null, null);
- newNode(primordealResult, startState, true);
+ newNode(null, null, null, startState, true);
}
public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
this.location = input.getLocation();
finalResult.merge(r.getForest());
}
if (token == null) continue;
- Result result = new Result(f, n, null);
- n.state().invokeShifts(token, this, result);
+ n.state().invokeShifts(token, this, n, f);
}
numNewNodes = next==null ? 0 : next.hash.size();
viewPos = this.pos;
+
if (!good && token!=null) {
String toks = token+"";
if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
return getLocation().createRegion(getNextLocation());
}
- void newNodeFromReduction(Result result, State state, Pos reduction) {
- int pos = result.phase().pos;
+ void newNodeFromReduction(Forest f, Pos reduction, Node pred) {
+ int pos = pred.phase().pos;
for(int s : reduction.hates())
if (performed.contains(pos, s))
return;
return;
if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
performed.add(pos, reduction.provides());
+ Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
if (state!=null)
- newNode(result, state, reduction.numPops()<=0);
+ newNode(f, reduction, pred, state, reduction.numPops()<=0);
}
/** add a new node (merging with existing nodes if possible)
* @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
- private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
- Node p = hash.get(state, result.phase());
- if (p != null) { p.addResult(result); return !state.doomed(); }
+ private boolean newNode(Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
+ Node p = pred==null ? null : hash.get(state, pred.phase());
+ if (p != null) {
+ p.addResult(f, reduction, pred);
+ return !state.doomed();
+ }
do {
if (token != null && state.canShift(token)) break;
if (state.isAccepting()) break;
if (token==null) break;
if (!state.canReduce(token)) return false;
} while(false);
- Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
+ Node n = new Node(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC
/** FIXME: this null-result can be used to notice bogus/dead states */
for(Object s : state.conjunctStates)
- newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
+ newNode(null, null, n, (State)s, fromEmptyReduction);
return !n.state().doomed();
}
/** a node in the GSS */
final class Node
- implements Invokable<Pos, Result>,
+ implements Invokable<Pos, Result, Object>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
while(successors.size()>0)
for(Result r : successors) {
successors.remove(r);
- r.destroy();
+ r.removePred(this);
break;
}
while(results.size()>0)
private final int idx = node_idx++;
private final GSS.Phase phase;
+ private final GSS.Phase predPhase;
private final Parser.Table.State state;
- private final boolean fromEmptyReduction;
- //private FastSet<Result> results = new FastSet<Result>();
- private HashSet<Result> results = new HashSet<Result>();
- private HashSet<Result> successors = new HashSet<Result>();
+ private boolean fromEmptyReduction;
+ private FastSet<Result> results = new FastSet<Result>();
+ private FastSet<Result> successors = new FastSet<Result>();
+ //private HashSet<Result> results = new HashSet<Result>();
+ //private HashSet<Result> successors = new HashSet<Result>();
- public final void invoke(Pos r, Result only) {
+ public final void invoke(Pos r, Result only, Object o) {
boolean emptyProductions = only==null;
if (emptyProductions != (r.numPops()==0)) return;
if (r.numPops()!=0) reduce(r, r.numPops()-1, phase(), only);
else {
Input.Region region = phase().getLocation().createRegion(phase().getLocation());
- Result.newResult(r.rewrite(region), this, r, phase());
+ phase().newNodeFromReduction(r.rewrite(region), r, this);
}
}
private void reduce(Pos r, int pos, GSS.Phase target, Result only) {
- Forest[] holder = r.holder;
- Forest old = holder[pos];
- if (results==null) return; // FIXME: this should not happen
for(Result res : results)
- if (only == null || res == only) {
- Node pred = res.pred();
- 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);
- }
- }
- holder[pos] = old;
+ if (only == null || res == only)
+ for(Node pred : res.getPreds())
+ reduce2(r, pos, target, pred, res.getForest());
}
+ void reduce2(Pos r, int pos, GSS.Phase target, Node pred, Forest f) {
+ Forest[] holder = r.holder;
+ Forest old = pos >= holder.length ? null : holder[pos];
+ if (pos < holder.length) holder[pos] = f;
+ 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);
+ }
+ if (pos < holder.length) holder[pos] = old;
+ }
+
+ Node(GSS.Phase phase, Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
+ this(phase, new Result(f, reduction, pred), state, fromEmptyReduction);
+ }
Node(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
this.phase = phase;
this.state = state;
this.fromEmptyReduction = fromEmptyReduction;
if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!");
+ this.predPhase = pred.phase();
phase.hash.put(state, pred.phase(), this);
- addResult(pred);
+
+ results.add(pred);
+ pred.addSucc(this);
+ if (!fromEmptyReduction)
+ state.invokeReductions(phase().getToken(), this, pred);
+
state.invokeEpsilonReductions(phase().token, this);
}
// Add/Remove Successors/Results //////////////////////////////////////////////////////////////////////////////
public void removeSucc(Result succ) {
- if (successors==null) return;
successors.remove(succ);
check();
}
public void removeResult(Result result) {
- if (results==null) return;
results.remove(result);
check();
}
public void addSucc(Result succ) {
- if (successors==null) return; // FIXME: this should not happen
successors.add(succ);
}
- public void addResult(Result r) {
- if (results.contains(r)) return;
- results.add(r);
- r.addSucc(this);
- if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r);
+ public void addResult(Forest f, Pos reduction, Node pred) {
+ for(Result r : results)
+ if (r.predecessorsContains(pred)) {
+ r.merge(f);
+ return;
+ }
+ Result result = new Result(f, reduction, pred);
+ results.add(result);
+ result.addSucc(this);
+ if (!this.fromEmptyReduction) state.invokeReductions(phase().getToken(), this, result);
}
// GraphViz //////////////////////////////////////////////////////////////////////////////
HashMap<Pos,State<Token>> gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
private transient TopologicalBag<Token,State<Token>> gotoSetTerminals = new TopologicalBag<Token,State<Token>>();
- private TopologicalBag<Token,Pos> reductions = new TopologicalBag<Token,Pos>();
- private HashSet<Pos> eofReductions = new HashSet<Pos>();
+ TopologicalBag<Token,Pos> reductions = new TopologicalBag<Token,Pos>();
+ HashSet<Pos> eofReductions = new HashSet<Pos>();
private TopologicalBag<Token,State<Token>> shifts = new TopologicalBag<Token,State<Token>>();
private boolean accept = false;
Iterable<Pos> positions() { return hs; }
boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
- void invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
+ void invokeShifts(Token t, GSS.Phase phase, Node pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
boolean canReduce(Token t) {
return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
void invokeEpsilonReductions(Token t, Node node) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
- else oreductions.invoke(t, node, null);
+ if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
+ else oreductions.invoke(t, node, null, null);
}
void invokeReductions(Token t, Node node, Result b) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
- else oreductions.invoke(t, node, b);
+ if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
+ else oreductions.invoke(t, node, b, null);
}
// Constructor //////////////////////////////////////////////////////////////////////////////
}
public void perform() {
- Result.newResult(forest, pred, reduction, phase);
+ if (reduction==null) return;
+ phase.newNodeFromReduction(forest, reduction, pred);
}
public GSS.Phase predPhase() { return pred.phase(); }
public Pos reduction() { return reduction; }
final class Result implements GraphViz.ToGraphViz {
- private Forest f;
- private Node pred;
- private HashSet<Node> successors = new HashSet<Node>();
+ private Forest.Many f = new Forest.Many();
+ //private HashSet<Node> predecessors = new HashSet<Node>();
+ //private HashSet<Node> successors = new HashSet<Node>();
+ private FastSet<Node> predecessors = new FastSet<Node>();
+ private FastSet<Node> successors = new FastSet<Node>();
private boolean destroyed = false;
+ private boolean primordeal;
private int usedByNonDoomedNode = 0;
private Pos reduction;
+ private GSS.Phase predPhase;
- public GSS.Phase phase() { return pred==null ? null : pred.phase(); }
+ public boolean predecessorsContains(Node n) {
+ return predecessors.contains(n);
+ }
+ public Pos reduction() { return reduction; }
+ public void merge(Forest newf) {
+ this.f.merge(newf);
+ /*
+ if (predecessors.contains(pred)) return;
+ addPred(pred);
+ if (fromEmptyReduction) return;
+ n.state().invokeReductions(n.phase().getToken(), n, this);
+ */
+ }
+
+ public boolean noSuccessors() { return successors.size()==0; }
+
+ public GSS.Phase phase() { return predPhase; }
public Forest getForest() { return f; }
- public Node pred() { return pred; }
+ public Iterable<Node> getPreds() { return predecessors; }
public void addSucc(Node succ) {
+ if (successors.contains(succ)) return;
successors.add(succ);
usedByNonDoomedNode += succ.state().doomed ? 0 : 1;
+ if (predecessors.size() > 1) throw new Error();
}
public void removeSucc(Node succ) {
if (!successors.contains(succ)) return;
public boolean usedByAnyNode() { return successors.size() > 0; }
public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; }
- public String toString() { return super.toString()+"->"+pred(); }
+ public String toString() { return super.toString()+"->"+predPhase; }
- public void check() { if (successors.size()==0) destroy(); }
+ public void check() {
+ if (successors.size()==0) destroy();
+ else if (predecessors.size()==0) destroy();
+ }
public void destroy() {
if (destroyed) return;
- if (pred==null) return; // never destroy the "primordeal" result
+ if (primordeal) return; // never destroy the "primordeal" result
destroyed = true;
- pred.removeSucc(this);
+ while(predecessors.size() > 0)
+ for(Node pred : predecessors) {
+ removePred(pred);
+ pred.removeSucc(this);
+ break;
+ }
+ predecessors = null;
while(successors.size() > 0)
- for(Node n : successors) {
- removeSucc(n);
- n.removeResult(this);
+ for(Node succ : successors) {
+ removeSucc(succ);
+ succ.removeResult(this);
break;
}
+ successors = null;
}
- public static void newResult(Forest f, Node pred, Pos reduction, GSS.Phase target) {
- Result r = new Result(f, pred, reduction);
- if (reduction == null) return;
- Parser.Table.State state0 = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
- target.newNodeFromReduction(r, state0, reduction);
+ public void removePred(Node pred) {
+ if (!predecessors.contains(pred)) return;
+ predecessors.remove(pred);
+ check();
+ }
+
+ public void addPred(Node pred) {
+ if (predPhase==null) predPhase = pred.phase();
+ if (predPhase != pred.phase()) throw new Error();
+ predecessors.add(pred);
+ pred.addSucc(this);
+ if (predecessors.size() > 1) throw new Error();
+ }
+
+ public Result() {
+ this(null, null, null);
+ this.primordeal = true;
}
- public Result(Forest f, Node pred, Pos reduction) {
- this.f = f;
- this.pred = pred;
+ public Result(Forest f, Pos reduction, Node pred) {
+ this.f.merge(f);
this.reduction = reduction;
- if (pred != null) pred.addSucc(this);
+ if (pred != null) addPred(pred);
}
// GraphViz //////////////////////////////////////////////////////////////////////////////
GraphViz.Node n = gv.createNode(this);
n.label = ""+f;
n.shape = "rectangle";
- if (pred()!=null) n.edge(pred, "");
+ //if (pred()!=null) n.edge(pred, "");
n.color = "blue";
if (phase() != null)
((GraphViz.Group)phase().toGraphViz(gv)).add(n);