/** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
+ long start = System.currentTimeMillis();
verbose = System.getProperty("sbp.verbose", null) != null;
spinpos = 0;
GSS gss = new GSS(input, this);
+ int idmax = 0;
+ int[][] count = new int[1024*1024][];
+ HashMap<Pos,Integer> ids = new HashMap<Pos,Integer>();
try {
for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
if (verbose) debug(current.token, gss, input);
if (current.isDone()) return (Forest<NodeType>)current.finalResult;
Input.Region region = current.getLocation().createRegion(current.getNextLocation());
Forest forest = shiftToken((Token)current.token, region);
+ /*
+ int maxid = 0;
+ for(Reduction r : gss.finishedReductions)
+ if (ids.get(r.reduction())==null)
+ ids.put(r.reduction(), idmax++);
+ count[current.pos] = new int[idmax];
+ for(Reduction r : gss.finishedReductions)
+ count[current.pos][ids.get(r.reduction())]++;
+ */
current = gss.new Phase<Token>(current, forest);
}
} finally {
if (verbose) {
- System.err.print("\r"+ANSI.clreol());
+ long time = System.currentTimeMillis() - start;
+ System.err.println("\r parse time: " + time +"ms "+ ANSI.clreol());
debug(null, gss, input);
}
+ /*
+ PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("out.plot")));
+ boolean[] use = new boolean[idmax];
+ for(int i=0; i<count.length; i++)
+ if (count[i]!=null)
+ for(int j=0; j<count[i].length; j++)
+ if (count[i][j]>20)
+ use[j] = true;
+ for(int i=0; i<count.length; i++)
+ if (count[i]!=null) {
+ int row = 0;
+ for(int j=0; j<use.length; j++)
+ if (use[j]) {
+ row++;
+ pw.println(i+", "+row+", "+(j>=count[i].length ? 0 : count[i][j]));
+ }
+ pw.println();
+ }
+ pw.close();
+ pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("test.plot")));
+ pw.println("set terminal postscript enhanced color");
+ pw.println("set output \"out.ps\"");
+ pw.println("set pm3d map");
+ pw.println("set autoscale");
+ pw.println("set view 0,0");
+ pw.println("set ytics (\\");
+ int q = -1;
+ for(int j=0; j<use.length; j++)
+ if (use[j]) {
+ q++;
+ for(Pos p : ids.keySet())
+ if (ids.get(p) == j) {
+ String title = p.toString();
+ System.out.println(q + " " + title);
+ pw.println("\""+q+"\" "+(((double)q)+0.5)+",\\");
+ break;
+ }
+ }
+ pw.println("\".\" "+(q+1)+")");
+ pw.println("set size square");
+ pw.println("splot \"out.plot\"");
+ pw.close();
+ */
}
}
* 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)
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, 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) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
- else oreductions.invoke(t, node, null);
+ 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) {
- if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
- else oreductions.invoke(t, node, 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);
}
// Constructor //////////////////////////////////////////////////////////////////////////////
projects / sbp.git / blobdiff