abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
abstract void gather(HashSet<Forest<NodeType>> ignore);
- abstract void edges(GraphViz.Node n);
+ abstract void edges(GraphViz.StateNode n);
boolean ambiguous() { return false; }
// One //////////////////////////////////////////////////////////////////////////////
public boolean isTransparent() { return false; }
public boolean isHidden() { return false; }
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = headToString()==null?"":headToString();
n.directed = true;
edges(n);
return n;
}
boolean edges = false; // FIXME ??
- public void edges(GraphViz.Node n) {
+ public void edges(GraphViz.StateNode n) {
if (edges) return;
edges = true;
for(int i=0; i<children.length; i++) {
public boolean isTransparent() { return hp.size()==1; }
public boolean isHidden() { return hp.size()==0; }
- public void edges(GraphViz.Node n) {
+ public void edges(GraphViz.StateNode n) {
if (hp.size()==1) { hp.iterator().next().edges(n); return; }
for(Forest f : hp) f.edges(n);
}
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = "?";
n.color = "red";
for(Forest f : hp) n.edge(f, null);
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, Node, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+ 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>();
reductionQueue.add(r);
}
- public void invoke(State st, Node pred, Forest f) {
+ public void invoke(State st, StateNode pred, Forest f) {
parser.spin();
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 */
+ public IntPairMap<StateNode> hash = new IntPairMap<StateNode>(); /* ALLOC */
private boolean good = false;
private Phase next = null;
private Phase prev;
this.next = next;
// this massively improves GC performance
if (prev != null) {
- IntPairMap<Node> h = prev.hash;
+ IntPairMap<StateNode> h = prev.hash;
prev.hash = null;
prev.performed = null;
- for(Node n : h) n.check();
+ for(StateNode n : h) n.check();
}
numOldNodes = hash.size();
- for(Node n : hash.values()) {
+ for(StateNode n : hash.values()) {
if (token == null && n.state().isAccepting()) {
if (finalResult==null) finalResult = new Forest.Many();
for(Result r : n)
if (token==null && finalResult==null)
ParseFailed.error("unexpected end of file", this, null,
getLocation().createRegion(getLocation()));
- for(Node n : hash) n.check();
+ for(StateNode n : hash) n.check();
}
Input.Region getRegionFromThisToNext() {
return getLocation().createRegion(getNextLocation());
}
- void newNodeFromReduction(Forest f, Pos reduction, Node pred) {
+ void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
int pos = pred.phase().pos;
for(int s : reduction.hates())
if (performed.contains(pos, s))
* @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(Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
- Node p = pred==null ? null : hash.get(state, pred.phase());
+ private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
+ StateNode p = pred==null ? null : hash.get(state, pred.phase());
if (p != null) {
p.addResult(f, reduction, pred);
return !state.doomed();
if (token==null) break;
if (!state.canReduce(token)) return false;
} while(false);
- Node n = new Node(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC
+ StateNode n = new StateNode(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(null, null, n, (State)s, fromEmptyReduction);
public int size() { return hash==null ? 0 : hash.size(); }
public int pos() { return pos; }
public Tok getToken() { return token; }
- public Iterator<Node> iterator() { return hash.iterator(); }
+ public Iterator<StateNode> iterator() { return hash.iterator(); }
public GSS getGSS() { return GSS.this; }
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
GraphViz.Group g = gv.createGroup(this);
g.label = "Phase " + pos;
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
GraphViz gv = new GraphViz();
for(Object n : this)
- ((Node)n).toGraphViz(gv);
+ ((StateNode)n).toGraphViz(gv);
gv.dump(p);
p.flush();
p.close();
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.GSS.Phase;
-import edu.berkeley.sbp.Node;
+import edu.berkeley.sbp.StateNode;
import edu.berkeley.sbp.util.*;
import java.io.*;
import java.util.*;
return (c >= 'A' && c <= 'Z');
}
- static <Tok> void barf(HashMap<Element,Input.Location> sb, Node n, int indent, boolean skip, int count, Input.Location loc) {
+ static <Tok> void barf(HashMap<Element,Input.Location> sb, StateNode n, int indent, boolean skip, int count, Input.Location loc) {
if (count <= 0) {
barf(sb, n, indent, skip, loc);
} else {
/*
FIXME: removed
- for(Node nn : (Iterable<Node>)n.parents())
+ for(StateNode nn : (Iterable<StateNode>)n.parents())
barf(sb, nn, indent, skip, count-1, n.phase().getLocation());
*/
}
}
- static <Tok> void barf(HashMap<Element,Input.Location> sb, Node n, int indent, boolean skip, Input.Location loc) {
+ static <Tok> void barf(HashMap<Element,Input.Location> sb, StateNode n, int indent, boolean skip, Input.Location loc) {
if (touched.contains(n)) return;
touched.add(n);
String s = "";
for(int i=0; i< indent; i++) s += " ";
- Node parent = n;
+ StateNode parent = n;
boolean done = false;
boolean alldone = false;
boolean go = false;
// FIXME
- private static HashSet<Node> touched = new HashSet<Node>();
- static <Tok> void complain(Node n, HashMap<String,HashSet<String>> errors, boolean force, int indent) {
+ private static HashSet<StateNode> touched = new HashSet<StateNode>();
+ static <Tok> void complain(StateNode n, HashMap<String,HashSet<String>> errors, boolean force, int indent) {
if (touched.contains(n)) return;
touched.add(n);
for(Pos p : (Iterable<Pos>)n.state()) {
!important(p)) {
/*
FIXME: removed
- for(Node n2 : n.parents())
+ for(StateNode n2 : n.parents())
complain(n2, errors, force
//| p.isFirst()
, indent);
}
private static void error(String message,
Object token,
- Iterable<Node> nodes,
+ Iterable<StateNode> nodes,
Input.Region region,
Input input,
GSS gss) throws ParseFailed{
*/
}
HashMap<Element,Input.Location> hm = new HashMap<Element,Input.Location>();
- for(Node no : nodes)
+ for(StateNode no : nodes)
barf(hm, no, 0, false, region.getStart());
ret.append("\n expected: ");
Set<Element> hs = hm.keySet();
/*
ret.append("\n The author of SBP apologizes for the these nearly-useless error messages:\n\n");
HashMap<String,HashSet<String>> errors = new HashMap<String,HashSet<String>>();
- for(Node n : nodes) {
+ for(StateNode n : nodes) {
//System.out.println(n.state);
complain(n, errors, false, 0);
}
* possible from it
*
* A state corresponds to a set of Sequence.Pos's. Each
- * Node in the GSS has a State; the Node represents a set of
+ * StateNode in the GSS has a State; the StateNode represents a set of
* possible parses, one for each Pos in the State.
*
* Every state is either "doomed" or "normal". If a Pos
* Nodes with non-doomed states represent nodes which
* contribute to actual valid parses. Nodes with doomed
* States exist for no other purpose than to enable/disable
- * some future reduction from a non-doomed Node. Because of
+ * some future reduction from a non-doomed StateNode. Because of
* this, we "garbage-collect" Nodes with doomed states if
* there are no more non-doomed Nodes which they could
- * affect (see Result, Reduction, and Node for details).
+ * affect (see Result, Reduction, and StateNode for details).
*
* Without this optimization, many seemingly-innocuous uses
* of positive and negative conjuncts can trigger O(n^2)
Iterable<Pos> positions() { return hs; }
boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
- void invokeShifts(Token t, GSS.Phase phase, Node pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
+ void invokeShifts(Token t, GSS.Phase phase, StateNode 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) {
+ void invokeEpsilonReductions(Token t, StateNode node) {
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) {
+ void invokeReductions(Token t, StateNode node, Result b) {
if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
else oreductions.invoke(t, node, b, null);
}
private Pos reduction;
private GSS.Phase phase;
private Forest forest;
- private Node pred;
+ private StateNode pred;
- public Reduction(Node pred, Pos reduction, Forest forest, GSS.Phase target) {
+ public Reduction(StateNode pred, Pos reduction, Forest forest, GSS.Phase target) {
this.reduction = reduction;
this.forest = forest;
this.phase = target;
import edu.berkeley.sbp.Sequence.Pos;
import java.util.*;
-final class Result implements GraphViz.ToGraphViz {
+final class Result
+ implements GraphViz.ToGraphViz {
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 HashSet<StateNode> predecessors = new HashSet<StateNode>();
+ //private HashSet<StateNode> successors = new HashSet<StateNode>();
+ private FastSet<StateNode> predecessors = new FastSet<StateNode>();
+ private FastSet<StateNode> successors = new FastSet<StateNode>();
private boolean destroyed = false;
private boolean primordeal;
private int usedByNonDoomedNode = 0;
private Pos reduction;
private GSS.Phase predPhase;
- public boolean predecessorsContains(Node n) {
+ public boolean predecessorsContains(StateNode n) {
return predecessors.contains(n);
}
public Pos reduction() { return reduction; }
public GSS.Phase phase() { return predPhase; }
public Forest getForest() { return f; }
- public Iterable<Node> getPreds() { return predecessors; }
- public void addSucc(Node succ) {
+ public Iterable<StateNode> getPreds() { return predecessors; }
+ public void addSucc(StateNode 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) {
+ public void removeSucc(StateNode succ) {
if (!successors.contains(succ)) return;
successors.remove(succ);
usedByNonDoomedNode -= succ.state().doomed ? 0 : 1;
if (primordeal) return; // never destroy the "primordeal" result
destroyed = true;
while(predecessors.size() > 0)
- for(Node pred : predecessors) {
+ for(StateNode pred : predecessors) {
removePred(pred);
pred.removeSucc(this);
break;
}
predecessors = null;
while(successors.size() > 0)
- for(Node succ : successors) {
+ for(StateNode succ : successors) {
removeSucc(succ);
succ.removeResult(this);
break;
successors = null;
}
- public void removePred(Node pred) {
+ public void removePred(StateNode pred) {
if (!predecessors.contains(pred)) return;
predecessors.remove(pred);
check();
}
- public void addPred(Node pred) {
+ public void addPred(StateNode pred) {
if (predPhase==null) predPhase = pred.phase();
if (predPhase != pred.phase()) throw new Error();
predecessors.add(pred);
this(null, null, null);
this.primordeal = true;
}
- public Result(Forest f, Pos reduction, Node pred) {
+ public Result(Forest f, Pos reduction, StateNode pred) {
this.f.merge(f);
this.reduction = reduction;
if (pred != null) addPred(pred);
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = ""+f;
n.shape = "rectangle";
//if (pred()!=null) n.edge(pred, "");
import java.lang.reflect.*;
/** a node in the GSS */
-final class Node
+final class StateNode
implements Invokable<Pos, Result, Object>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
- /** which GSS.Phase this Node belongs to */
+ /** which GSS.Phase this StateNode belongs to */
public GSS.Phase phase() { return phase; }
public Iterator<Result> iterator() { return results.iterator(); }
public Parser.Table.State state() { return state; }
private void reduce(Pos r, int pos, GSS.Phase target, Result only) {
for(Result res : results)
if (only == null || res == only)
- for(Node pred : res.getPreds())
+ for(StateNode pred : res.getPreds())
reduce2(r, pos, target, pred, res.getForest());
}
- void reduce2(Pos r, int pos, GSS.Phase target, Node pred, Forest f) {
+ void reduce2(Pos r, int pos, GSS.Phase target, StateNode pred, Forest f) {
Forest[] holder = r.holder;
Forest old = pos >= holder.length ? null : holder[pos];
if (pos < holder.length) holder[pos] = f;
if (pos < holder.length) holder[pos] = old;
}
- Node(GSS.Phase phase, Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
+ StateNode(GSS.Phase phase, Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
this(phase, new Result(f, reduction, pred), state, fromEmptyReduction);
}
- Node(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
+ StateNode(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
this.phase = phase;
this.state = state;
this.fromEmptyReduction = fromEmptyReduction;
public void addSucc(Result succ) {
successors.add(succ);
}
- public void addResult(Forest f, Pos reduction, Node pred) {
+ public void addResult(Forest f, Pos reduction, StateNode pred) {
for(Result r : results)
if (r.predecessorsContains(pred)) {
r.merge(f);
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (results.size()==0) return null;
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = "state["+state.toInt()+"]";
n.shape = "rectangle";
boolean haspreds = false;
public class GraphViz {
- IdentityHashMap<ToGraphViz,Node> ihm = new IdentityHashMap<ToGraphViz,Node>();
- HashMap<Node,Group> groups = new HashMap<Node,Group>();
+ IdentityHashMap<ToGraphViz,StateNode> ihm = new IdentityHashMap<ToGraphViz,StateNode>();
+ HashMap<StateNode,Group> groups = new HashMap<StateNode,Group>();
- public class Group extends Node {
+ public class Group extends StateNode {
private final int idx = master_idx++;
public boolean cluster = false;
public boolean primary = true;
public Group() { }
- public void add(Node n) { groups.put(n, this); }
+ public void add(StateNode n) { groups.put(n, this); }
public String name() { return cluster?("cluster_"+idx):("subgraph_"+idx); }
public boolean simple() { return false; }
- public void dump(PrintWriter pw, IdentityHashMap<Node,Node> done) {
+ public void dump(PrintWriter pw, IdentityHashMap<StateNode,StateNode> done) {
Group g = this;
if (done.get(g)!=null) return;
done.put(g,g);
pw.println(" label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\";\n");
pw.println(" color="+g.color+";\n");
pw.println(" shape="+g.shape+";\n");
- for(Node n : groups.keySet())
+ for(StateNode n : groups.keySet())
if (groups.get(n)==g)
n.dump(pw, done);
pw.println(" }\n");
private static int master_idx=0;
- public class Node {
+ public class StateNode {
private final int idx = master_idx++;
public String label;
public String comment;
public String color="black";
public String fill="white";
public String shape="ellipse";
- public ArrayList<Node> edges = new ArrayList<Node>();
+ public ArrayList<StateNode> edges = new ArrayList<StateNode>();
public ArrayList<Object> labels = new ArrayList<Object>();
- public ArrayList<Node> inbound = new ArrayList<Node>();
+ public ArrayList<StateNode> inbound = new ArrayList<StateNode>();
public void edge(ToGraphViz o, Object label) {
- Node n = o.toGraphViz(GraphViz.this);
+ StateNode n = o.toGraphViz(GraphViz.this);
if (n==null) return;
edges.add(n);
labels.add(label);
public void edges(PrintWriter pw) {
if (simple()) return;
for(int i=0; i<edges.size(); i++) {
- Node n = edges.get(i);
+ StateNode n = edges.get(i);
Object label = labels.get(i);
pw.println(" "+name()+" -> " + n.name() + " [color="+color+" "
+(label==null?"":("label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\""))+ "];\n");
boolean simple = true;
if (label!=null && !label.equals("")) simple = false;
if (simple)
- for(Node n : edges)
+ for(StateNode n : edges)
//if (n.numEdges()>0) { simple = false; break; }
if (n.inbound.size() > 1) { simple = false; break; }
return simple;
}
- public void dump(PrintWriter pw, IdentityHashMap<Node,Node> done) {
+ public void dump(PrintWriter pw, IdentityHashMap<StateNode,StateNode> done) {
if (done.get(this)!=null) return;
done.put(this, this);
if (inbound.size() > 0) {
boolean good = false;
- for(Node n : inbound)
+ for(StateNode n : inbound)
if (!n.simple())
{ good = true; break; }
if (!good) return;
pw.print(" shape=record ");
pw.print(" label=\"");
boolean complex = false;
- for(Node n : edges)
+ for(StateNode n : edges)
if (n.edges.size()>0)
complex = true;
if (!complex) pw.print("{");
boolean first = true;
- for(Node n : edges) {
+ for(StateNode n : edges) {
if (!first) pw.print("|");
first = false;
pw.print("<node_"+n.idx+">");
return ihm.get(o)!=null;
}
- public Node createNode(ToGraphViz o) {
- Node n = ihm.get(o);
+ public StateNode createNode(ToGraphViz o) {
+ StateNode n = ihm.get(o);
if (n!=null) return n;
- n = new Node();
+ n = new StateNode();
ihm.put(o, n);
return n;
}
}
public static interface ToGraphViz {
- Node toGraphViz(GraphViz gv);
+ StateNode toGraphViz(GraphViz gv);
boolean isTransparent();
boolean isHidden();
}
public void dump(OutputStream os) { dump(new PrintWriter(new OutputStreamWriter(os))); }
public void dump(PrintWriter pw) {
- IdentityHashMap<Node,Node> done = new IdentityHashMap<Node,Node>();
+ IdentityHashMap<StateNode,StateNode> done = new IdentityHashMap<StateNode,StateNode>();
pw.println("digraph G { rankdir=LR; ordering=out; compound=true; \n");
for(Group g : groups.values())
if (g.primary)
g.dump(pw, done);
- for(Node n : ihm.values()) {
+ for(StateNode n : ihm.values()) {
if (done.get(n)!=null) continue;
if (n instanceof Group) continue;
n.dump(pw, done);
}
- for(Node n : ihm.values()) n.edges(pw);
+ for(StateNode n : ihm.values()) n.edges(pw);
pw.println("}\n");
pw.flush();
}
// this is here to keep it out of the javadoc for Tree<T>
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = head()==null ? "" : head().toString();
for(T t : this) n.edge(t, null);
return n;
projects / sbp.git / commitdiff