src/edu/berkeley/sbp/Parser.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   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;
   7 import java.io.*;
   8 import java.util.*;
   9
  10 /** a parser which translates an Input&lt;Token&gt; into a Forest&lt;NodeType&gt; */
  11 public abstract class Parser<Token, NodeType> implements Serializable {
  12
  13     final Table pt;
  14
  15     /** create a parser to parse the grammar with start symbol <tt>u</tt> */
  16     public Parser(Union u)  { this.pt = new Table(u); }
  17
  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);
  20
  21     public abstract Topology<Token> emptyTopology();
  22
  23     public String toString() { return pt.toString(); }
  24
  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;
  29         spinpos = 0;
  30         GSS gss = new GSS(input, this);
  31         int idmax = 0;
  32         int[][] count = new int[1024*1024][];
  33         HashMap<Pos,Integer> ids = new HashMap<Pos,Integer>();
  34         try {
  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);
  40                 /*
  41                 int maxid = 0;
  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())]++;
  48                 */
  49                 current = gss.new Phase<Token>(current, forest);
  50             }
  51         } finally {
  52             if (verbose) {
  53                 long time = System.currentTimeMillis() - start;
  54                 System.err.println("\r parse time: " + time +"ms "+ ANSI.clreol());
  55                 debug(null, gss, input);
  56             }
  57             /*
  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++)
  61                 if (count[i]!=null)
  62                 for(int j=0; j<count[i].length; j++)
  63                     if (count[i][j]>20)
  64                         use[j] = true;
  65             for(int i=0; i<count.length; i++)
  66                 if (count[i]!=null) {
  67                     int row = 0;
  68                     for(int j=0; j<use.length; j++)
  69                         if (use[j]) {
  70                             row++;
  71                             pw.println(i+", "+row+", "+(j>=count[i].length ? 0 : count[i][j]));
  72                         }
  73                     pw.println();
  74                 }
  75             pw.close();
  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 (\\");
  83             int q = -1;
  84             for(int j=0; j<use.length; j++)
  85                 if (use[j]) {
  86                     q++;
  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)+",\\");
  92                             break;
  93                         }
  94                 }
  95             pw.println("\".\"  "+(q+1)+")");
  96             pw.println("set size square");
  97             pw.println("splot \"out.plot\"");
  98             pw.close();
  99             */
 100         }
 101     }
 102
 103     // Spinner //////////////////////////////////////////////////////////////////////////////
 104
 105     private boolean verbose = false;
 106     private static final char[] spin = new char[] { '-', '\\', '|', '/' };
 107     private int spinpos = 0;
 108     private long last = 0;
 109     void spin() {
 110         if (!verbose) return;
 111         long now = System.currentTimeMillis();
 112         if (now-last < 70) return;
 113         last = now;
 114         System.err.print("\r  " + spin[spinpos++ % (spin.length)]+"\r");
 115     }
 116
 117     private int _last = -1;
 118     private String buf = "";
 119     private void debug(Object t, GSS gss, Input input) {
 120         //FIXME
 121         int c = t==null ? -1 : ((t+"").charAt(0));
 122         int last = _last;
 123         _last = c;
 124         switch(c) {
 125             case edu.berkeley.sbp.chr.CharAtom.left:
 126                 buf += "\033[31m>\033[0m";
 127                 break;
 128             case edu.berkeley.sbp.chr.CharAtom.right:
 129                 buf += "\033[31m<\033[0m";
 130                 break;
 131             case -1: // FIXME
 132             case '\n':
 133                 if (verbose) {
 134                     if (last==' ') buf += ANSI.blue("\\n");
 135                     System.err.println("\r"+ANSI.clreol()+"\r"+buf);
 136                     buf = "";
 137                 }
 138                 break;
 139             default:
 140                 buf += ANSI.cyan(""+((char)c));
 141                 break;
 142         }
 143         if (t==null) return;
 144
 145         // FIXME: clean this up
 146         String s;
 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;
 153         s += 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");
 161     }
 162
 163     // Table //////////////////////////////////////////////////////////////////////////////
 164
 165     /** an SLR(1) parse table which may contain conflicts */
 166     class Table implements Serializable {
 167
 168         /** the start state */
 169         final State<Token>   start;
 170
 171         /** a dummy state from which no reductions can be performed */
 172         private final State<Token>   dead_state;
 173
 174         /** used to generate unique values for State.idx */
 175         private int master_state_idx = 0;
 176
 177         /** all the states for this table */
 178         private transient HashSet<State<Token>>                all_states       = new HashSet<State<Token>>();
 179
 180         /** all the doomed states in this table */
 181         private transient HashMap<HashSet<Pos>,State<Token>>   doomed_states    = new HashMap<HashSet<Pos>,State<Token>>();
 182
 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>>();
 185
 186         /** construct a parse table for the given grammar */
 187         Table(Union ux) {
 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(); }
 191             };
 192
 193             // create the "dead state"
 194             this.dead_state = new State<Token>(new HashSet<Pos>(), true, grammar);
 195
 196             // construct the start state; this will recursively create *all* the states
 197             this.start = new State<Token>(reachable(rootUnion), false, grammar);
 198
 199             buildReductions(grammar);
 200             sortReductions(grammar);
 201         }
 202
 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) {
 208
 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()));
 213
 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");
 222
 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);
 230                     }
 231
 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);
 236                 }
 237
 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());
 244                 }
 245         }
 246
 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;
 256                     int i=0;
 257                     for(; i<al.size(); i++) {
 258                         if (grammar.comparePositions(p, al.get(i)) < 0)
 259                             break;
 260                     }
 261                     al.add(i, p);
 262                 }
 263             }
 264             // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
 265             // sort in increasing order...
 266             OUTER: while(true) {
 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);
 271                             al.add(i, p);
 272                             continue OUTER;
 273                         }
 274                 break;
 275             }
 276
 277             int j = 1;
 278             int pk = 0;
 279             for(int i=0; i<al.size(); i++) {
 280                 boolean inc = false;
 281                 for(int k=pk; k<i; k++) {
 282                     if (grammar.comparePositions(al.get(k), al.get(i)) > 0)
 283                         { inc = true; break; }
 284                 }
 285                 inc = true;
 286                 if (inc) {
 287                     j++;
 288                     pk = i;
 289                 }
 290                 al.get(i).ord = j;
 291             }
 292         }
 293
 294         /**
 295          *  A single state in the LR table and the transitions
 296          *  possible from it
 297          *
 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.
 301          *
 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
 309          *  non-doomed state.
 310          *
 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).
 318          *
 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.
 323          */
 324         class State<Token> implements IntegerMappable, Serializable {
 325
 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>>();
 329
 330             HashMap<Pos,State<Token>>      gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
 331             private transient TopologicalBag<Token,State<Token>>  gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 332
 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;
 337
 338             private VisitableMap<Token,State<Token>> oshifts     = null;
 339             private VisitableMap<Token,Pos>     oreductions = null;
 340             public  final boolean doomed;
 341
 342             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 343
 344             public boolean doomed() { return doomed; }
 345             boolean                    isAccepting()           { return accept; }
 346
 347             Iterable<Pos>  positions()             { return hs; }
 348
 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);
 356             }
 357             void          invokeReductions(Token t, StateNode node, ResultNode b) {
 358                 if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
 359                 else         oreductions.invoke(t, node, b, null);
 360             }
 361
 362             // Constructor //////////////////////////////////////////////////////////////////////////////
 363
 364             /**
 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)
 368              *
 369              *   In principle these two steps could be merged, but they
 370              *   are written separately to highlight these two facts:
 371              * <ul>
 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
 377              *      any new states
 378              *
 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.
 383              *  </ul>
 384              */
 385             public State(HashSet<Pos> hs, boolean doomed, Grammar<Token> grammar) {
 386                 this.hs = hs;
 387                 this.doomed = doomed;
 388
 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);
 393
 394                 for(Pos p : hs) {
 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()))
 398                         accept = true;
 399
 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));
 411                 }
 412
 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_
 417
 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);
 425                 }
 426
 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).
 430
 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));
 435                 }
 436
 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.
 439                 //
 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").
 443
 444                 HashMapBag<Sequence,Pos> move = new HashMapBag<Sequence,Pos>();
 445                 for(Pos p : hs)
 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);
 450                             move.addAll(s, hp);
 451                         }
 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);
 456                     for(Pos p : hs)
 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);
 464                                     continue OUTER;
 465                                 }
 466                     for(Pos pp = y.firstp(); pp != null; pp = pp.next())
 467                         gotoSetNonTerminals.put(pp, s);
 468                 }
 469             }
 470
 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);
 474                 return ret;
 475             }
 476
 477             public int toInt() { return idx; }
 478             public String toString() {
 479                 StringBuffer ret = new StringBuffer();
 480                 for(Pos p : hs)
 481                     ret.append(p+"\n");
 482                 return ret.toString();
 483             }
 484         }
 485
 486     }
 487
 488     // Helpers //////////////////////////////////////////////////////////////////////////////
 489
 490     private static HashSet<Pos> reachable(Element e) {
 491         HashSet<Pos> h = new HashSet<Pos>();
 492         reachable(e, h);
 493         return h;
 494     }
 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);
 499     }
 500     private static void reachable(Pos p, HashSet<Pos> h) {
 501         if (h.contains(p)) return;
 502         h.add(p);
 503         if (p.element() != null) reachable(p.element(), h);
 504     }
 505     private static HashSet<Pos> reachable(Pos p) {
 506         HashSet<Pos> ret = new HashSet<Pos>();
 507         reachable(p, ret);
 508         return ret;
 509     }
 510
 511 }