1 // Copyright 2006 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.Position;
9 // FEATURE: try harder to "fuse" states together along two dimensions:
10 // - identical (equivalent) states, or states that subsume each other
11 // - unnecessary intermediate states ("short cut" GLR)
13 /** a parser which translates an Input<Token> into a Forest<NodeType> */
14 public abstract class Parser<Token, NodeType> {
18 /** create a parser to parse the grammar with start symbol <tt>u</tt> */
19 public Parser(Union u) { this.pt = new Table(u); }
21 /** implement this method to create the output forest corresponding to a lone shifted input token */
22 public abstract Forest<NodeType> shiftToken(Token t, Input.Region region);
24 public abstract Topology<Token> emptyTopology();
26 public String toString() { return pt.toString(); }
27 Grammar cache() { return pt; }
29 /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
30 public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
31 verbose = System.getProperty("sbp.verbose", null) != null;
34 GSS gss = new GSS(input, this);
35 for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
38 // FIXME: clean this up
40 s = " " + spin[spinpos++ % (spin.length)]+" parsing ";
42 s += " "+input.getLocation();
43 while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s;
44 String y = "@"+gss.viewPos+" ";
45 while(y.length() < 9) y = " " + y;
47 s += " nodes="+gss.numOldNodes;
48 while(s.length() < 50) s = s + " ";
49 s += " shifted="+gss.numNewNodes;
50 while(s.length() < 60) s = s + " ";
51 s += " reductions="+gss.numReductions;
52 System.err.print("\r"+s+ANSI.clreol()+"\r");
55 if (current.isDone()) return (Forest<NodeType>)current.finalResult;
56 Forest forest = shiftToken((Token)current.token, current.getRegion());
57 current = gss.new Phase<Token>(current, forest);
59 } finally { if (verbose) System.err.print("\r"+ANSI.clreol()); }
62 // Spinner //////////////////////////////////////////////////////////////////////////////
64 private boolean verbose = false;
65 private static final char[] spin = new char[] { '-', '\\', '|', '/' };
66 private int spinpos = 0;
67 private long last = 0;
70 long now = System.currentTimeMillis();
71 if (now-last < 70) return;
73 System.err.print("\r " + spin[spinpos++ % (spin.length)]+"\r");
76 // Table //////////////////////////////////////////////////////////////////////////////
78 /** an SLR(1) parse table which may contain conflicts */
79 class Table extends Grammar<Token> {
81 /** the start state */
82 final State<Token> start;
84 /** a dummy state from which no reductions can be performed */
85 private final State<Token> dead_state;
87 /** used to generate unique values for State.idx */
88 private int master_state_idx = 0;
90 /** all the states for this table */
91 HashSet<State<Token>> all_states = new HashSet<State<Token>>();
93 /** all the doomed states in this table */
94 HashMap<HashSet<Position>,State<Token>> doomed_states = new HashMap<HashSet<Position>,State<Token>>();
96 /** all the non-doomed states in this table */
97 HashMap<HashSet<Position>,State<Token>> normal_states = new HashMap<HashSet<Position>,State<Token>>();
99 Topology<Token> emptyTopology() { return Parser.this.emptyTopology(); }
101 /** construct a parse table for the given grammar */
103 super(new Union("0", Sequence.create(ux), true));
105 // create the "dead state"
106 this.dead_state = new State<Token>(new HashSet<Position>(), true);
108 // construct the start state; this will recursively create *all* the states
109 this.start = new State<Token>(reachable(rootUnion), false);
115 /** fill in the reductions table */
116 private void buildReductions() {
117 // for each state, fill in the corresponding "row" of the parse table
118 for(State<Token> state : all_states)
119 for(Position p : state.hs) {
121 // if the element following this position is an atom, copy the corresponding
122 // set of rows out of the "master" goto table and into this state's shift table
123 if (p.element() != null && p.element() instanceof Atom)
124 state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
126 // RNGLR: we can potentially reduce from any "right-nullable" position -- that is,
127 // any position for which all Elements after it in the Sequence are capable of
128 // matching the empty string.
129 if (!isRightNullable(p)) continue;
130 Topology<Token> follow = follow(p.owner());
131 for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {
132 if (!(p2.element() instanceof Union))
133 throw new Error("impossible -- only Unions can be nullable");
135 // interesting RNGLR-followRestriction interaction: we must intersect
136 // not just the follow-set of the last non-nullable element, but the
137 // follow-sets of the nulled elements as well.
138 for(Sequence s : ((Union)p2.element()))
139 follow = follow.intersect(follow(s));
140 Topology<Token> set = epsilonFollowSet((Union)p2.element());
141 if (set != null) follow = follow.intersect(set);
144 // indicate that when the next token is in the set "follow", nodes in this
145 // state should reduce according to Position "p"
146 state.reductions.put(follow, p);
147 if (followEof.contains(p.owner())) state.eofReductions.add(p);
150 // optimize the reductions table
151 if (emptyTopology() instanceof IntegerTopology)
152 for(State<Token> state : all_states) {
153 // FIXME: this is pretty ugly
154 state.oreductions = state.reductions.optimize(((IntegerTopology)emptyTopology()).functor());
155 state.oshifts = state.shifts.optimize(((IntegerTopology)emptyTopology()).functor());
159 // FIXME: this method needs to be cleaned up and documented
160 private void sortReductions() {
161 // crude algorithm to assing an ordinal ordering to every position
162 // al will be sorted in DECREASING order (al[0] >= al[1])
163 ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
164 for(State s : all_states) {
166 Sequence.Position p = (Sequence.Position)po;
167 if (al.contains(p)) continue;
169 for(; i<al.size(); i++) {
170 if (comparePositions(p, al.get(i)) < 0)
176 // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
177 // sort in increasing order...
179 for(int i=0; i<al.size(); i++)
180 for(int j=i+1; j<al.size(); j++)
181 if (comparePositions(al.get(i), al.get(j)) > 0) {
182 Sequence.Position p = al.remove(j);
191 for(int i=0; i<al.size(); i++) {
193 for(int k=pk; k<i; k++) {
194 if (comparePositions(al.get(k), al.get(i)) > 0)
195 { inc = true; break; }
207 * A single state in the LR table and the transitions
210 * A state corresponds to a set of Sequence.Position's. Each
211 * Node in the GSS has a State; the Node represents a set of
212 * possible parses, one for each Position in the State.
214 * Every state is either "doomed" or "normal". If a Position
215 * is part of a Sequence which is a conjunct (that is, it was
216 * passed to Sequence.{and(),andnot()}), then that Position
217 * will appear only in doomed States. Furthermore, any set
218 * of Positions reachable from a doomed State also forms a
219 * doomed State. Note that in this latter case, a doomed
220 * state might have exactly the same set of Positions as a
223 * Nodes with non-doomed states represent nodes which
224 * contribute to actual valid parses. Nodes with doomed
225 * States exist for no other purpose than to enable/disable
226 * some future reduction from a non-doomed Node. Because of
227 * this, we "garbage-collect" Nodes with doomed states if
228 * there are no more non-doomed Nodes which they could
229 * affect (see Result, Reduction, and Node for details).
231 * Without this optimization, many seemingly-innocuous uses
232 * of positive and negative conjuncts can trigger O(n^2)
233 * space+time complexity in otherwise simple grammars. There
234 * is an example of this in the regression suite.
236 class State<Token> implements IntegerMappable, Iterable<Position> {
238 public final int idx = master_state_idx++;
239 private final HashSet<Position> hs;
240 public HashSet<State<Token>> conjunctStates = new HashSet<State<Token>>();
242 HashMap<Sequence,State<Token>> gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
243 private transient TopologicalBag<Token,State<Token>> gotoSetTerminals = new TopologicalBag<Token,State<Token>>();
245 private TopologicalBag<Token,Position> reductions = new TopologicalBag<Token,Position>();
246 private HashSet<Position> eofReductions = new HashSet<Position>();
247 private TopologicalBag<Token,State<Token>> shifts = new TopologicalBag<Token,State<Token>>();
248 private boolean accept = false;
250 private VisitableMap<Token,State<Token>> oshifts = null;
251 private VisitableMap<Token,Position> oreductions = null;
252 public final boolean doomed;
254 // Interface Methods //////////////////////////////////////////////////////////////////////////////
256 boolean isAccepting() { return accept; }
257 public Iterator<Position> iterator() { return hs.iterator(); }
258 boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
259 void invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
260 boolean canReduce(Token t) {
261 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
262 void invokeEpsilonReductions(Token t, Node node) {
263 if (t==null) for(Position r : eofReductions) node.invoke(r, null);
264 else oreductions.invoke(t, node, null);
266 void invokeReductions(Token t, Node node, Result b) {
267 if (t==null) for(Position r : eofReductions) node.invoke(r, b);
268 else oreductions.invoke(t, node, b);
271 // Constructor //////////////////////////////////////////////////////////////////////////////
274 * create a new state consisting of all the <tt>Position</tt>s in <tt>hs</tt>
275 * @param hs the set of <tt>Position</tt>s comprising this <tt>State</tt>
276 * @param all the set of all elements (Atom instances need not be included)
278 * In principle these two steps could be merged, but they
279 * are written separately to highlight these two facts:
281 * <li> Non-atom elements either match all-or-nothing, and do not overlap
282 * with each other (at least not in the sense of which element corresponds
283 * to the last reduction performed). Therefore, in order to make sure we
284 * wind up with the smallest number of states and shifts, we wait until
285 * we've figured out all the token-to-position multimappings before creating
288 * <li> In order to be able to run the state-construction algorithm in a single
289 * shot (rather than repeating until no new items appear in any state set),
290 * we need to use the "yields" semantics rather than the "produces" semantics
291 * for non-Atom Elements.
294 public State(HashSet<Position> hs, boolean doomed) {
296 this.doomed = doomed;
298 // register ourselves so that no two states are ever
299 // created with an identical position set (termination depends on this)
300 ((HashMap)(doomed ? doomed_states : normal_states)).put(hs, this);
301 ((HashSet)all_states).add(this);
303 for(Position p : hs) {
304 // Step 1a: take note if we are an accepting state
305 // (last position of the root Union's sequence)
306 if (p.next()==null && !doomed && rootUnion.contains(p.owner()))
309 // Step 1b: If any Position in the set is the first position of its sequence, then this
310 // state is responsible for spawning the "doomed" states for each of the
311 // Sequence's conjuncts. This obligation is recorded by adding the to-be-spawned
312 // states to conjunctStates.
313 if (!p.isFirst()) continue;
314 for(Sequence s : p.owner().needs())
315 if (!hs.contains(s.firstp()))
316 conjunctStates.add(mkstate(reachable(s.firstp()), true));
317 for(Sequence s : p.owner().hates())
318 if (!hs.contains(s.firstp()))
319 conjunctStates.add(mkstate(reachable(s.firstp()), true));
322 // Step 2a: examine all Position's in this state and compute the mappings from
323 // sets of follow tokens (tokens which could follow this position) to sets
324 // of _new_ positions (positions after shifting). These mappings are
325 // collectively known as the _closure_
327 TopologicalBag<Token,Position> bag0 = new TopologicalBag<Token,Position>();
328 for(Position position : hs) {
329 if (position.isLast() || !(position.element() instanceof Atom)) continue;
330 Atom a = (Atom)position.element();
331 HashSet<Position> hp = new HashSet<Position>();
332 reachable(position.next(), hp);
333 bag0.addAll(a.getTokenTopology(), hp);
336 // Step 2b: for each _minimal, contiguous_ set of characters having an identical next-position
337 // set, add that character set to the goto table (with the State corresponding to the
338 // computed next-position set).
340 for(Topology<Token> r : bag0) {
341 HashSet<Position> h = new HashSet<Position>();
342 for(Position p : bag0.getAll(r)) h.add(p);
343 ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed));
346 // Step 3: for every Sequence, compute the closure over every position in this set which
347 // is followed by a symbol which could yield the Sequence.
349 // "yields" [in one or more step] is used instead of "produces" [in exactly one step]
350 // to avoid having to iteratively construct our set of States as shown in most
351 // expositions of the algorithm (ie "keep doing XYZ until things stop changing").
353 HashMapBag<Sequence,Position> move = new HashMapBag<Sequence,Position>();
355 if (!p.isLast() && p.element() instanceof Union)
356 for(Sequence s : ((Union)p.element())) {
357 HashSet<Position> hp = new HashSet<Position>();
358 reachable(p.next(), hp);
361 OUTER: for(Sequence y : move) {
362 // if a reduction is "lame", it should wind up in the dead_state after reducing
363 HashSet<Position> h = move.getAll(y);
364 State<Token> s = mkstate(h, doomed);
366 if (p.element() != null && (p.element() instanceof Union))
367 for(Sequence seq : ((Union)p.element()))
368 if (seq.needs.contains(y) || seq.hates.contains(y)) {
369 // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched
370 // and also directly lamely matched
371 ((HashMap)gotoSetNonTerminals).put(y, dead_state);
374 gotoSetNonTerminals.put(y, s);
378 private State<Token> mkstate(HashSet<Position> h, boolean b) {
379 State ret = (b?doomed_states:normal_states).get(h);
380 if (ret==null) ret = new State<Token>(h,b);
384 public int toInt() { return idx; }
389 // Helpers //////////////////////////////////////////////////////////////////////////////
391 private static HashSet<Position> reachable(Element e) {
392 HashSet<Position> h = new HashSet<Position>();
396 private static void reachable(Element e, HashSet<Position> h) {
397 if (e instanceof Atom) return;
398 for(Sequence s : ((Union)e))
399 reachable(s.firstp(), h);
401 private static void reachable(Position p, HashSet<Position> h) {
402 if (h.contains(p)) return;
404 if (p.element() != null) reachable(p.element(), h);
406 private static HashSet<Position> reachable(Position p) {
407 HashSet<Position> ret = new HashSet<Position>();