1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.util.*;
5 import edu.berkeley.sbp.Sequence.Pos;
6 import edu.berkeley.sbp.Sequence.Pos;
10 /** a parser which translates an Input<Token> into a Forest<NodeType> */
11 public abstract class Parser<Token, NodeType> implements Serializable {
15 /** create a parser to parse the grammar with start symbol <tt>u</tt> */
16 public Parser(Union u) { this.pt = new Table(u); }
18 /** implement this method to create the output forest corresponding to a lone shifted input token */
19 public abstract Forest<NodeType> shiftToken(Token t, Input.Region region);
21 public abstract Topology<Token> emptyTopology();
23 public String toString() { return pt.toString(); }
25 /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
26 public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
27 long start = System.currentTimeMillis();
28 verbose = System.getProperty("sbp.verbose", null) != null;
30 GSS gss = new GSS(input, this);
32 int[][] count = new int[1024*1024][];
33 HashMap<Pos,Integer> ids = new HashMap<Pos,Integer>();
35 for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
36 if (verbose) debug(current.token, gss, input);
37 if (current.isDone()) return (Forest<NodeType>)current.finalResult;
38 Input.Region region = current.getLocation().createRegion(current.getNextLocation());
39 Forest forest = shiftToken((Token)current.token, region);
42 for(Reduction r : gss.finishedReductions)
43 if (ids.get(r.reduction())==null)
44 ids.put(r.reduction(), idmax++);
45 count[current.pos] = new int[idmax];
46 for(Reduction r : gss.finishedReductions)
47 count[current.pos][ids.get(r.reduction())]++;
49 current = gss.new Phase<Token>(current, forest);
53 long time = System.currentTimeMillis() - start;
54 System.err.println("\r parse time: " + time +"ms "+ ANSI.clreol());
55 debug(null, gss, input);
58 PrintWriter pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("out.plot")));
59 boolean[] use = new boolean[idmax];
60 for(int i=0; i<count.length; i++)
62 for(int j=0; j<count[i].length; j++)
65 for(int i=0; i<count.length; i++)
68 for(int j=0; j<use.length; j++)
71 pw.println(i+", "+row+", "+(j>=count[i].length ? 0 : count[i][j]));
76 pw = new PrintWriter(new OutputStreamWriter(new FileOutputStream("test.plot")));
77 pw.println("set terminal postscript enhanced color");
78 pw.println("set output \"out.ps\"");
79 pw.println("set pm3d map");
80 pw.println("set autoscale");
81 pw.println("set view 0,0");
82 pw.println("set ytics (\\");
84 for(int j=0; j<use.length; j++)
87 for(Pos p : ids.keySet())
88 if (ids.get(p) == j) {
89 String title = p.toString();
90 System.out.println(q + " " + title);
91 pw.println("\""+q+"\" "+(((double)q)+0.5)+",\\");
95 pw.println("\".\" "+(q+1)+")");
96 pw.println("set size square");
97 pw.println("splot \"out.plot\"");
103 // Spinner //////////////////////////////////////////////////////////////////////////////
105 private boolean verbose = false;
106 private static final char[] spin = new char[] { '-', '\\', '|', '/' };
107 private int spinpos = 0;
108 private long last = 0;
110 if (!verbose) return;
111 long now = System.currentTimeMillis();
112 if (now-last < 70) return;
114 System.err.print("\r " + spin[spinpos++ % (spin.length)]+"\r");
117 private int _last = -1;
118 private String buf = "";
119 private void debug(Object t, GSS gss, Input input) {
121 int c = t==null ? -1 : ((t+"").charAt(0));
125 case edu.berkeley.sbp.chr.CharAtom.left:
126 buf += "\033[31m>\033[0m";
128 case edu.berkeley.sbp.chr.CharAtom.right:
129 buf += "\033[31m<\033[0m";
134 if (last==' ') buf += ANSI.blue("\\n");
135 System.err.println("\r"+ANSI.clreol()+"\r"+buf);
140 buf += ANSI.cyan(""+((char)c));
145 // FIXME: clean this up
147 s = " " + spin[spinpos++ % (spin.length)]+" parsing ";
148 s += input.getName();
149 s += " "+input.getLocation();
150 while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s;
151 String y = "@"+gss.viewPos+" ";
152 while(y.length() < 9) y = " " + y;
154 s += " nodes="+gss.numOldNodes;
155 while(s.length() < 50) s = s + " ";
156 s += " shifted="+gss.numNewNodes;
157 while(s.length() < 60) s = s + " ";
158 s += " reductions="+gss.numReductions;
159 while(s.length() < 78) s = s + " ";
160 System.err.print("\r"+ANSI.invert(s+ANSI.clreol())+"\r");
163 // Table //////////////////////////////////////////////////////////////////////////////
165 /** an SLR(1) parse table which may contain conflicts */
166 class Table implements Serializable {
168 /** the start state */
169 final State<Token> start;
171 /** a dummy state from which no reductions can be performed */
172 private final State<Token> dead_state;
174 /** used to generate unique values for State.idx */
175 private int master_state_idx = 0;
177 /** all the states for this table */
178 private transient HashSet<State<Token>> all_states = new HashSet<State<Token>>();
180 /** all the doomed states in this table */
181 private transient HashMap<HashSet<Pos>,State<Token>> doomed_states = new HashMap<HashSet<Pos>,State<Token>>();
183 /** all the non-doomed states in this table */
184 private transient HashMap<HashSet<Pos>,State<Token>> normal_states = new HashMap<HashSet<Pos>,State<Token>>();
186 /** construct a parse table for the given grammar */
188 Union rootUnion = new Union("0", Sequence.create(ux), true);
189 Grammar<Token> grammar = new Grammar<Token>(rootUnion) {
190 public Topology<Token> emptyTopology() { return Parser.this.emptyTopology(); }
193 // create the "dead state"
194 this.dead_state = new State<Token>(new HashSet<Pos>(), true, grammar);
196 // construct the start state; this will recursively create *all* the states
197 this.start = new State<Token>(reachable(rootUnion), false, grammar);
199 buildReductions(grammar);
200 sortReductions(grammar);
203 /** fill in the reductions table */
204 private void buildReductions(Grammar<Token> grammar) {
205 // for each state, fill in the corresponding "row" of the parse table
206 for(State<Token> state : all_states)
207 for(Pos p : state.hs) {
209 // if the element following this position is an atom, copy the corresponding
210 // set of rows out of the "master" goto table and into this state's shift table
211 if (p.element() != null && p.element() instanceof Atom)
212 state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
214 // RNGLR: we can potentially reduce from any "right-nullable" position -- that is,
215 // any position for which all Elements after it in the Sequence are capable of
216 // matching the empty string.
217 if (!grammar.isRightNullable(p)) continue;
218 Topology<Token> follow = grammar.follow(p.owner());
219 for(Pos p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {
220 if (!(p2.element() instanceof Union))
221 throw new Error("impossible -- only Unions can be nullable");
223 // interesting RNGLR-followRestriction interaction: we must intersect
224 // not just the follow-set of the last non-nullable element, but the
225 // follow-sets of the nulled elements as well.
226 for(Sequence s : ((Union)p2.element()))
227 follow = follow.intersect(grammar.follow(s));
228 Topology<Token> set = grammar.epsilonFollowSet((Union)p2.element());
229 if (set != null) follow = follow.intersect(set);
232 // indicate that when the next token is in the set "follow", nodes in this
233 // state should reduce according to Pos "p"
234 state.reductions.put(follow, p);
235 if (grammar.followEof.contains(p.owner())) state.eofReductions.add(p);
238 // optimize the reductions table
239 if (emptyTopology() instanceof IntegerTopology)
240 for(State<Token> state : all_states) {
241 // FIXME: this is pretty ugly
242 state.oreductions = state.reductions.optimize(((IntegerTopology)emptyTopology()).functor());
243 state.oshifts = state.shifts.optimize(((IntegerTopology)emptyTopology()).functor());
247 // FIXME: this method needs to be cleaned up and documented
248 private void sortReductions(Grammar<Token> grammar) {
249 // crude algorithm to assing an ordinal ordering to every position
250 // al will be sorted in DECREASING order (al[0] >= al[1])
251 ArrayList<Sequence.Pos> al = new ArrayList<Sequence.Pos>();
252 for(State s : all_states) {
253 for(Object po : s.positions()) {
254 Sequence.Pos p = (Sequence.Pos)po;
255 if (al.contains(p)) continue;
257 for(; i<al.size(); i++) {
258 if (grammar.comparePositions(p, al.get(i)) < 0)
264 // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
265 // sort in increasing order...
267 for(int i=0; i<al.size(); i++)
268 for(int j=i+1; j<al.size(); j++)
269 if (grammar.comparePositions(al.get(i), al.get(j)) > 0) {
270 Sequence.Pos p = al.remove(j);
279 for(int i=0; i<al.size(); i++) {
281 for(int k=pk; k<i; k++) {
282 if (grammar.comparePositions(al.get(k), al.get(i)) > 0)
283 { inc = true; break; }
295 * A single state in the LR table and the transitions
298 * A state corresponds to a set of Sequence.Pos's. Each
299 * StateNode in the GSS has a State; the StateNode represents a set of
300 * possible parses, one for each Pos in the State.
302 * Every state is either "doomed" or "normal". If a Pos
303 * is part of a Sequence which is a conjunct (that is, it was
304 * passed to Sequence.{and(),andnot()}), then that Pos
305 * will appear only in doomed States. Furthermore, any set
306 * of Positions reachable from a doomed State also forms a
307 * doomed State. Note that in this latter case, a doomed
308 * state might have exactly the same set of Positions as a
311 * Nodes with non-doomed states represent nodes which
312 * contribute to actual valid parses. Nodes with doomed
313 * States exist for no other purpose than to enable/disable
314 * some future reduction from a non-doomed StateNode. Because of
315 * this, we "garbage-collect" Nodes with doomed states if
316 * there are no more non-doomed Nodes which they could
317 * affect (see ResultNode, Reduction, and StateNode for details).
319 * Without this optimization, many seemingly-innocuous uses
320 * of positive and negative conjuncts can trigger O(n^2)
321 * space+time complexity in otherwise simple grammars. There
322 * is an example of this in the regression suite.
324 class State<Token> implements IntegerMappable, Serializable {
326 public final int idx = master_state_idx++;
327 private final transient HashSet<Pos> hs;
328 public HashSet<State<Token>> conjunctStates = new HashSet<State<Token>>();
330 HashMap<Pos,State<Token>> gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
331 private transient TopologicalBag<Token,State<Token>> gotoSetTerminals = new TopologicalBag<Token,State<Token>>();
333 TopologicalBag<Token,Pos> reductions = new TopologicalBag<Token,Pos>();
334 HashSet<Pos> eofReductions = new HashSet<Pos>();
335 private TopologicalBag<Token,State<Token>> shifts = new TopologicalBag<Token,State<Token>>();
336 private boolean accept = false;
338 private VisitableMap<Token,State<Token>> oshifts = null;
339 private VisitableMap<Token,Pos> oreductions = null;
340 public final boolean doomed;
342 // Interface Methods //////////////////////////////////////////////////////////////////////////////
344 public boolean doomed() { return doomed; }
345 boolean isAccepting() { return accept; }
347 Iterable<Pos> positions() { return hs; }
349 boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
350 void invokeShifts(Token t, GSS.Phase phase, StateNode pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
351 boolean canReduce(Token t) {
352 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
353 void invokeEpsilonReductions(Token t, StateNode node) {
354 if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
355 else oreductions.invoke(t, node, null, null);
357 void invokeReductions(Token t, StateNode node, ResultNode only) {
358 if (t==null) for(Pos r : eofReductions) node.invoke(r, only, null);
359 else oreductions.invoke(t, node, only, null);
362 // Constructor //////////////////////////////////////////////////////////////////////////////
365 * create a new state consisting of all the <tt>Pos</tt>s in <tt>hs</tt>
366 * @param hs the set of <tt>Pos</tt>s comprising this <tt>State</tt>
367 * @param all the set of all elements (Atom instances need not be included)
369 * In principle these two steps could be merged, but they
370 * are written separately to highlight these two facts:
372 * <li> Non-atom elements either match all-or-nothing, and do not overlap
373 * with each other (at least not in the sense of which element corresponds
374 * to the last reduction performed). Therefore, in order to make sure we
375 * wind up with the smallest number of states and shifts, we wait until
376 * we've figured out all the token-to-position multimappings before creating
379 * <li> In order to be able to run the state-construction algorithm in a single
380 * shot (rather than repeating until no new items appear in any state set),
381 * we need to use the "yields" semantics rather than the "produces" semantics
382 * for non-Atom Elements.
385 public State(HashSet<Pos> hs, boolean doomed, Grammar<Token> grammar) {
387 this.doomed = doomed;
389 // register ourselves so that no two states are ever
390 // created with an identical position set (termination depends on this)
391 ((HashMap)(doomed ? doomed_states : normal_states)).put(hs, this);
392 ((HashSet)all_states).add(this);
395 // Step 1a: take note if we are an accepting state
396 // (last position of the root Union's sequence)
397 if (p.next()==null && !doomed && grammar.rootUnion.contains(p.owner()))
400 // Step 1b: If any Pos in the set is the first position of its sequence, then this
401 // state is responsible for spawning the "doomed" states for each of the
402 // Sequence's conjuncts. This obligation is recorded by adding the to-be-spawned
403 // states to conjunctStates.
404 if (!p.isFirst()) continue;
405 for(Sequence s : p.owner().needs())
406 if (!hs.contains(s.firstp()))
407 conjunctStates.add(mkstate(reachable(s.firstp()), true, grammar));
408 for(Sequence s : p.owner().hates())
409 if (!hs.contains(s.firstp()))
410 conjunctStates.add(mkstate(reachable(s.firstp()), true, grammar));
413 // Step 2a: examine all Pos's in this state and compute the mappings from
414 // sets of follow tokens (tokens which could follow this position) to sets
415 // of _new_ positions (positions after shifting). These mappings are
416 // collectively known as the _closure_
418 TopologicalBag<Token,Pos> bag0 = new TopologicalBag<Token,Pos>();
419 for(Pos position : hs) {
420 if (position.isLast() || !(position.element() instanceof Atom)) continue;
421 Atom a = (Atom)position.element();
422 HashSet<Pos> hp = new HashSet<Pos>();
423 reachable(position.next(), hp);
424 bag0.addAll(a.getTokenTopology(), hp);
427 // Step 2b: for each _minimal, contiguous_ set of characters having an identical next-position
428 // set, add that character set to the goto table (with the State corresponding to the
429 // computed next-position set).
431 for(Topology<Token> r : bag0) {
432 HashSet<Pos> h = new HashSet<Pos>();
433 for(Pos p : bag0.getAll(r)) h.add(p);
434 ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed, grammar));
437 // Step 3: for every Sequence, compute the closure over every position in this set which
438 // is followed by a symbol which could yield the Sequence.
440 // "yields" [in one or more step] is used instead of "produces" [in exactly one step]
441 // to avoid having to iteratively construct our set of States as shown in most
442 // expositions of the algorithm (ie "keep doing XYZ until things stop changing").
444 HashMapBag<Sequence,Pos> move = new HashMapBag<Sequence,Pos>();
446 if (!p.isLast() && p.element() instanceof Union)
447 for(Sequence s : ((Union)p.element())) {
448 HashSet<Pos> hp = new HashSet<Pos>();
449 reachable(p.next(), hp);
452 OUTER: for(Sequence y : move) {
453 // if a reduction is "lame", it should wind up in the dead_state after reducing
454 HashSet<Pos> h = move.getAll(y);
455 State<Token> s = mkstate(h, doomed, grammar);
457 if (p.element() != null && (p.element() instanceof Union))
458 for(Sequence seq : ((Union)p.element()))
459 if (seq.needs.contains(y) || seq.hates.contains(y)) {
460 // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched
461 // and also directly lamely matched
462 for(Pos pp = y.firstp(); pp != null; pp = pp.next())
463 ((HashMap)gotoSetNonTerminals).put(pp, dead_state);
466 for(Pos pp = y.firstp(); pp != null; pp = pp.next())
467 gotoSetNonTerminals.put(pp, s);
471 private State<Token> mkstate(HashSet<Pos> h, boolean b, Grammar<Token> grammar) {
472 State ret = (b?doomed_states:normal_states).get(h);
473 if (ret==null) ret = new State<Token>(h,b, grammar);
477 public int toInt() { return idx; }
478 public String toString() {
479 StringBuffer ret = new StringBuffer();
482 return ret.toString();
488 // Helpers //////////////////////////////////////////////////////////////////////////////
490 private static HashSet<Pos> reachable(Element e) {
491 HashSet<Pos> h = new HashSet<Pos>();
495 private static void reachable(Element e, HashSet<Pos> h) {
496 if (e instanceof Atom) return;
497 for(Sequence s : ((Union)e))
498 reachable(s.firstp(), h);
500 private static void reachable(Pos p, HashSet<Pos> h) {
501 if (h.contains(p)) return;
503 if (p.element() != null) reachable(p.element(), h);
505 private static HashSet<Pos> reachable(Pos p) {
506 HashSet<Pos> ret = new HashSet<Pos>();