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> {
  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         verbose = System.getProperty("sbp.verbose", null) != null;
  28         spinpos = 0;
  29         GSS gss = new GSS(input, this);
  30         try {
  31             for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
  32                 if (verbose) debug(current.token, gss, input);
  33                 if (current.isDone()) return (Forest<NodeType>)current.finalResult;
  34                 Input.Region region = current.getLocation().createRegion(current.getNextLocation());
  35                 Forest forest = shiftToken((Token)current.token, region);
  36                 current = gss.new Phase<Token>(current, forest);
  37             }
  38         } finally {
  39             if (verbose) {
  40                 System.err.print("\r"+ANSI.clreol());
  41                 debug(null, gss, input);
  42             }
  43         }
  44     }
  45
  46     // Spinner //////////////////////////////////////////////////////////////////////////////
  47
  48     private boolean verbose = false;
  49     private static final char[] spin = new char[] { '-', '\\', '|', '/' };
  50     private int spinpos = 0;
  51     private long last = 0;
  52     void spin() {
  53         if (!verbose) return;
  54         long now = System.currentTimeMillis();
  55         if (now-last < 70) return;
  56         last = now;
  57         System.err.print("\r  " + spin[spinpos++ % (spin.length)]+"\r");
  58     }
  59
  60     private int _last = -1;
  61     private String buf = "";
  62     private void debug(Object t, GSS gss, Input input) {
  63         //FIXME
  64         int c = t==null ? -1 : ((t+"").charAt(0));
  65         int last = _last;
  66         _last = c;
  67         switch(c) {
  68             case edu.berkeley.sbp.chr.CharAtom.left:
  69                 buf += "\033[31m>\033[0m";
  70                 break;
  71             case edu.berkeley.sbp.chr.CharAtom.right:
  72                 buf += "\033[31m<\033[0m";
  73                 break;
  74             case -1: // FIXME
  75             case '\n':
  76                 if (verbose) {
  77                     if (last==' ') buf += ANSI.blue("\\n");
  78                     System.err.println("\r"+ANSI.clreol()+"\r"+buf);
  79                     buf = "";
  80                 }
  81                 break;
  82             default:
  83                 buf += ANSI.cyan(""+((char)c));
  84                 break;
  85         }
  86         if (t==null) return;
  87
  88         // FIXME: clean this up
  89         String s;
  90         s = "  " + spin[spinpos++ % (spin.length)]+" parsing ";
  91         s += input.getName();
  92         s += " "+input.getLocation();
  93         while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s;
  94         String y = "@"+gss.viewPos+" ";
  95         while(y.length() < 9) y = " " + y;
  96         s += y;
  97         s += "   nodes="+gss.numOldNodes;
  98         while(s.length() < 50) s = s + " ";
  99         s += " shifted="+gss.numNewNodes;
 100         while(s.length() < 60) s = s + " ";
 101         s += " reductions="+gss.numReductions;
 102         while(s.length() < 78) s = s + " ";
 103         System.err.print("\r"+ANSI.invert(s+ANSI.clreol())+"\r");
 104     }
 105
 106     // Table //////////////////////////////////////////////////////////////////////////////
 107
 108     /** an SLR(1) parse table which may contain conflicts */
 109     class Table extends Grammar<Token> implements Serializable {
 110
 111         /** the start state */
 112         final State<Token>   start;
 113
 114         /** a dummy state from which no reductions can be performed */
 115         private final State<Token>   dead_state;
 116
 117         /** used to generate unique values for State.idx */
 118         private int master_state_idx = 0;
 119
 120         /** all the states for this table */
 121         private transient HashSet<State<Token>>                all_states       = new HashSet<State<Token>>();
 122
 123         /** all the doomed states in this table */
 124         private transient HashMap<HashSet<Pos>,State<Token>>   doomed_states    = new HashMap<HashSet<Pos>,State<Token>>();
 125
 126         /** all the non-doomed states in this table */
 127         private transient HashMap<HashSet<Pos>,State<Token>>   normal_states    = new HashMap<HashSet<Pos>,State<Token>>();
 128
 129         /** construct a parse table for the given grammar */
 130         Table(Union ux) {
 131             Union rootUnion = new Union("0", Sequence.create(ux), true);
 132             Grammar<Token> grammar = new Grammar<Token>(rootUnion) {
 133                 public Topology<Token> emptyTopology() { return Parser.this.emptyTopology(); }
 134             };
 135
 136             // create the "dead state"
 137             this.dead_state = new State<Token>(new HashSet<Pos>(), true, grammar);
 138
 139             // construct the start state; this will recursively create *all* the states
 140             this.start = new State<Token>(reachable(rootUnion), false, grammar);
 141
 142             buildReductions(grammar);
 143             sortReductions(grammar);
 144         }
 145
 146         /** fill in the reductions table */
 147         private void buildReductions(Grammar<Token> grammar) {
 148             // for each state, fill in the corresponding "row" of the parse table
 149             for(State<Token> state : all_states)
 150                 for(Pos p : state.hs) {
 151
 152                     // if the element following this position is an atom, copy the corresponding
 153                     // set of rows out of the "master" goto table and into this state's shift table
 154                     if (p.element() != null && p.element() instanceof Atom)
 155                         state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
 156
 157                     // RNGLR: we can potentially reduce from any "right-nullable" position -- that is,
 158                     // any position for which all Elements after it in the Sequence are capable of
 159                     // matching the empty string.
 160                     if (!grammar.isRightNullable(p)) continue;
 161                     Topology<Token> follow = grammar.follow(p.owner());
 162                     for(Pos p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {
 163                         if (!(p2.element() instanceof Union))
 164                             throw new Error("impossible -- only Unions can be nullable");
 165
 166                         // interesting RNGLR-followRestriction interaction: we must intersect
 167                         // not just the follow-set of the last non-nullable element, but the
 168                         // follow-sets of the nulled elements as well.
 169                         for(Sequence s : ((Union)p2.element()))
 170                             follow = follow.intersect(grammar.follow(s));
 171                         Topology<Token> set = grammar.epsilonFollowSet((Union)p2.element());
 172                         if (set != null) follow = follow.intersect(set);
 173                     }
 174
 175                     // indicate that when the next token is in the set "follow", nodes in this
 176                     // state should reduce according to Pos "p"
 177                     state.reductions.put(follow, p);
 178                     if (grammar.followEof.contains(p.owner())) state.eofReductions.add(p);
 179                 }
 180
 181             // optimize the reductions table
 182             if (emptyTopology() instanceof IntegerTopology)
 183                 for(State<Token> state : all_states) {
 184                     // FIXME: this is pretty ugly
 185                     state.oreductions = state.reductions.optimize(((IntegerTopology)emptyTopology()).functor());
 186                     state.oshifts     = state.shifts.optimize(((IntegerTopology)emptyTopology()).functor());
 187                 }
 188         }
 189
 190         // FIXME: this method needs to be cleaned up and documented
 191         private void sortReductions(Grammar<Token> grammar) {
 192             // crude algorithm to assing an ordinal ordering to every position
 193             // al will be sorted in DECREASING order (al[0] >= al[1])
 194             ArrayList<Sequence.Pos> al = new ArrayList<Sequence.Pos>();
 195             for(State s : all_states) {
 196                 for(Object po : s.positions()) {
 197                     Sequence.Pos p = (Sequence.Pos)po;
 198                     if (al.contains(p)) continue;
 199                     int i=0;
 200                     for(; i<al.size(); i++) {
 201                         if (grammar.comparePositions(p, al.get(i)) < 0)
 202                             break;
 203                     }
 204                     al.add(i, p);
 205                 }
 206             }
 207             // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
 208             // sort in increasing order...
 209             OUTER: while(true) {
 210                 for(int i=0; i<al.size(); i++)
 211                     for(int j=i+1; j<al.size(); j++)
 212                         if (grammar.comparePositions(al.get(i), al.get(j)) > 0) {
 213                             Sequence.Pos p = al.remove(j);
 214                             al.add(i, p);
 215                             continue OUTER;
 216                         }
 217                 break;
 218             }
 219
 220             int j = 1;
 221             int pk = 0;
 222             for(int i=0; i<al.size(); i++) {
 223                 boolean inc = false;
 224                 for(int k=pk; k<i; k++) {
 225                     if (grammar.comparePositions(al.get(k), al.get(i)) > 0)
 226                         { inc = true; break; }
 227                 }
 228                 inc = true;
 229                 if (inc) {
 230                     j++;
 231                     pk = i;
 232                 }
 233                 al.get(i).ord = j;
 234             }
 235         }
 236
 237         /**
 238          *  A single state in the LR table and the transitions
 239          *  possible from it
 240          *
 241          *  A state corresponds to a set of Sequence.Pos's.  Each
 242          *  Node in the GSS has a State; the Node represents a set of
 243          *  possible parses, one for each Pos in the State.
 244          *
 245          *  Every state is either "doomed" or "normal".  If a Pos
 246          *  is part of a Sequence which is a conjunct (that is, it was
 247          *  passed to Sequence.{and(),andnot()}), then that Pos
 248          *  will appear only in doomed States.  Furthermore, any set
 249          *  of Positions reachable from a doomed State also forms a
 250          *  doomed State.  Note that in this latter case, a doomed
 251          *  state might have exactly the same set of Positions as a
 252          *  non-doomed state.
 253          *
 254          *  Nodes with non-doomed states represent nodes which
 255          *  contribute to actual valid parses.  Nodes with doomed
 256          *  States exist for no other purpose than to enable/disable
 257          *  some future reduction from a non-doomed Node.  Because of
 258          *  this, we "garbage-collect" Nodes with doomed states if
 259          *  there are no more non-doomed Nodes which they could
 260          *  affect (see Result, Reduction, and Node for details).
 261          *
 262          *  Without this optimization, many seemingly-innocuous uses
 263          *  of positive and negative conjuncts can trigger O(n^2)
 264          *  space+time complexity in otherwise simple grammars.  There
 265          *  is an example of this in the regression suite.
 266          */
 267         class State<Token> implements IntegerMappable, Serializable {
 268
 269             public  final     int               idx    = master_state_idx++;
 270             private final  transient   HashSet<Pos> hs;
 271             public HashSet<State<Token>> conjunctStates = new HashSet<State<Token>>();
 272
 273             HashMap<Pos,State<Token>>      gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
 274             private transient TopologicalBag<Token,State<Token>>  gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 275
 276             private           TopologicalBag<Token,Pos>      reductions          = new TopologicalBag<Token,Pos>();
 277             private           HashSet<Pos>                   eofReductions       = new HashSet<Pos>();
 278             private           TopologicalBag<Token,State<Token>>  shifts              = new TopologicalBag<Token,State<Token>>();
 279             private           boolean                             accept              = false;
 280
 281             private VisitableMap<Token,State<Token>> oshifts     = null;
 282             private VisitableMap<Token,Pos>     oreductions = null;
 283             public  final boolean doomed;
 284
 285             // Interface Methods //////////////////////////////////////////////////////////////////////////////
 286
 287             public boolean doomed() { return doomed; }
 288             boolean                    isAccepting()           { return accept; }
 289
 290             Iterable<Pos>  positions()             { return hs; }
 291
 292             boolean                    canShift(Token t)       { return oshifts!=null && oshifts.contains(t); }
 293             void                       invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
 294             boolean                    canReduce(Token t)        {
 295                 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
 296             void          invokeEpsilonReductions(Token t, Node node) {
 297                 if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
 298                 else         oreductions.invoke(t, node, null);
 299             }
 300             void          invokeReductions(Token t, Node node, Result b) {
 301                 if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
 302                 else         oreductions.invoke(t, node, b);
 303             }
 304
 305             // Constructor //////////////////////////////////////////////////////////////////////////////
 306
 307             /**
 308              *  create a new state consisting of all the <tt>Pos</tt>s in <tt>hs</tt>
 309              *  @param hs           the set of <tt>Pos</tt>s comprising this <tt>State</tt>
 310              *  @param all the set of all elements (Atom instances need not be included)
 311              *
 312              *   In principle these two steps could be merged, but they
 313              *   are written separately to highlight these two facts:
 314              * <ul>
 315              * <li> Non-atom elements either match all-or-nothing, and do not overlap
 316              *      with each other (at least not in the sense of which element corresponds
 317              *      to the last reduction performed).  Therefore, in order to make sure we
 318              *      wind up with the smallest number of states and shifts, we wait until
 319              *      we've figured out all the token-to-position multimappings before creating
 320              *      any new states
 321              *
 322              * <li> In order to be able to run the state-construction algorithm in a single
 323              *      shot (rather than repeating until no new items appear in any state set),
 324              *      we need to use the "yields" semantics rather than the "produces" semantics
 325              *      for non-Atom Elements.
 326              *  </ul>
 327              */
 328             public State(HashSet<Pos> hs, boolean doomed, Grammar<Token> grammar) {
 329                 this.hs = hs;
 330                 this.doomed = doomed;
 331
 332                 // register ourselves so that no two states are ever
 333                 // created with an identical position set (termination depends on this)
 334                 ((HashMap)(doomed ? doomed_states : normal_states)).put(hs, this);
 335                 ((HashSet)all_states).add(this);
 336
 337                 for(Pos p : hs) {
 338                     // Step 1a: take note if we are an accepting state
 339                     //          (last position of the root Union's sequence)
 340                     if (p.next()==null && !doomed && grammar.rootUnion.contains(p.owner()))
 341                         accept = true;
 342
 343                     // Step 1b: If any Pos in the set is the first position of its sequence, then this
 344                     //          state is responsible for spawning the "doomed" states for each of the
 345                     //          Sequence's conjuncts.  This obligation is recorded by adding the to-be-spawned
 346                     //          states to conjunctStates.
 347                     if (!p.isFirst()) continue;
 348                     for(Sequence s : p.owner().needs())
 349                         if (!hs.contains(s.firstp()))
 350                             conjunctStates.add(mkstate(reachable(s.firstp()), true, grammar));
 351                     for(Sequence s : p.owner().hates())
 352                         if (!hs.contains(s.firstp()))
 353                             conjunctStates.add(mkstate(reachable(s.firstp()), true, grammar));
 354                 }
 355
 356                 // Step 2a: examine all Pos's in this state and compute the mappings from
 357                 //          sets of follow tokens (tokens which could follow this position) to sets
 358                 //          of _new_ positions (positions after shifting).  These mappings are
 359                 //          collectively known as the _closure_
 360
 361                 TopologicalBag<Token,Pos> bag0 = new TopologicalBag<Token,Pos>();
 362                 for(Pos position : hs) {
 363                     if (position.isLast() || !(position.element() instanceof Atom)) continue;
 364                     Atom a = (Atom)position.element();
 365                     HashSet<Pos> hp = new HashSet<Pos>();
 366                     reachable(position.next(), hp);
 367                     bag0.addAll(a.getTokenTopology(), hp);
 368                 }
 369
 370                 // Step 2b: for each _minimal, contiguous_ set of characters having an identical next-position
 371                 //          set, add that character set to the goto table (with the State corresponding to the
 372                 //          computed next-position set).
 373
 374                 for(Topology<Token> r : bag0) {
 375                     HashSet<Pos> h = new HashSet<Pos>();
 376                     for(Pos p : bag0.getAll(r)) h.add(p);
 377                     ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed, grammar));
 378                 }
 379
 380                 // Step 3: for every Sequence, compute the closure over every position in this set which
 381                 //         is followed by a symbol which could yield the Sequence.
 382                 //
 383                 //         "yields" [in one or more step] is used instead of "produces" [in exactly one step]
 384                 //         to avoid having to iteratively construct our set of States as shown in most
 385                 //         expositions of the algorithm (ie "keep doing XYZ until things stop changing").
 386
 387                 HashMapBag<Sequence,Pos> move = new HashMapBag<Sequence,Pos>();
 388                 for(Pos p : hs)
 389                     if (!p.isLast() && p.element() instanceof Union)
 390                         for(Sequence s : ((Union)p.element())) {
 391                             HashSet<Pos> hp = new HashSet<Pos>();
 392                             reachable(p.next(), hp);
 393                             move.addAll(s, hp);
 394                         }
 395                 OUTER: for(Sequence y : move) {
 396                     // if a reduction is "lame", it should wind up in the dead_state after reducing
 397                     HashSet<Pos> h = move.getAll(y);
 398                     State<Token> s = mkstate(h, doomed, grammar);
 399                     for(Pos p : hs)
 400                         if (p.element() != null && (p.element() instanceof Union))
 401                             for(Sequence seq : ((Union)p.element()))
 402                                 if (seq.needs.contains(y) || seq.hates.contains(y)) {
 403                                     // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched
 404                                     //        and also directly lamely matched
 405                                     for(Pos pp = y.firstp(); pp != null; pp = pp.next())
 406                                         ((HashMap)gotoSetNonTerminals).put(pp, dead_state);
 407                                     continue OUTER;
 408                                 }
 409                     for(Pos pp = y.firstp(); pp != null; pp = pp.next())
 410                         gotoSetNonTerminals.put(pp, s);
 411                 }
 412             }
 413
 414             private State<Token> mkstate(HashSet<Pos> h, boolean b, Grammar<Token> grammar) {
 415                 State ret = (b?doomed_states:normal_states).get(h);
 416                 if (ret==null) ret = new State<Token>(h,b, grammar);
 417                 return ret;
 418             }
 419
 420             public int toInt() { return idx; }
 421             public String toString() {
 422                 StringBuffer ret = new StringBuffer();
 423                 for(Pos p : hs)
 424                     ret.append(p+"\n");
 425                 return ret.toString();
 426             }
 427         }
 428
 429     }
 430
 431     // Helpers //////////////////////////////////////////////////////////////////////////////
 432
 433     private static HashSet<Pos> reachable(Element e) {
 434         HashSet<Pos> h = new HashSet<Pos>();
 435         reachable(e, h);
 436         return h;
 437     }
 438     private static void reachable(Element e, HashSet<Pos> h) {
 439         if (e instanceof Atom) return;
 440         for(Sequence s : ((Union)e))
 441             reachable(s.firstp(), h);
 442     }
 443     private static void reachable(Pos p, HashSet<Pos> h) {
 444         if (h.contains(p)) return;
 445         h.add(p);
 446         if (p.element() != null) reachable(p.element(), h);
 447     }
 448     private static HashSet<Pos> reachable(Pos p) {
 449         HashSet<Pos> ret = new HashSet<Pos>();
 450         reachable(p, ret);
 451         return ret;
 452     }
 453
 454 }