From: adam Date: Mon, 26 Mar 2007 05:52:57 +0000 (-0400) Subject: MAJOR: huge revamp of Sequence, Result, Reduction, Parser, Node, GSS X-Git-Tag: tag_for_25-Mar~8 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=9d727bd14c659cdc6c34153b988e8d3fdb8067f5 MAJOR: huge revamp of Sequence, Result, Reduction, Parser, Node, GSS darcs-hash:20070326055257-5007d-e7f33e2199ea28d9bbbb799a81887378c0f1c524.gz --- diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 91ef765..c96ceee 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -13,22 +13,31 @@ import java.lang.reflect.*; class GSS { Input input; - public GSS(Input input) { this.input = input; } + private Parser parser; + public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;} public Input getInput() { return input; } - // FIXME: right now, these are the performance bottleneck - HashMapBag performed = new HashMapBag(); - - /** FIXME */ - Forest.Many finalResult; + int numNewNodes = 0; + int numOldNodes = 0; + int viewPos = 0; + int numReductions = 0; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { + class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { + + // FIXME: right now, these are the performance bottleneck + private HashMapBag performed = new HashMapBag(); - public PriorityQueue reductionQueue = new PriorityQueue(); + public Forest.Many finalResult; + private PriorityQueue reductionQueue = new PriorityQueue(); - public void invoke(State st, Result result, Object o) { - //shifts++; + public void addReduction(Reduction r) { + //System.out.println("+ " + r); + parser.spin(); + reductionQueue.add(r); + } + public void invoke(State st, Result result) { + parser.spin(); good |= next.newNode(result, st, false); } @@ -36,8 +45,8 @@ class GSS { final Tok token; final int pos; - public IntPairMap hash; /* ALLOC */ - private boolean good; + public IntPairMap hash = new IntPairMap(); /* ALLOC */ + private boolean good = false; private Phase next = null; private Phase prev; private Input.Location location; @@ -46,23 +55,54 @@ class GSS { private Forest forest; - public Phase(Phase prev, Phase previous, Tok token, Input.Location location, - Input.Location nextLocation, Forest forest) throws ParseFailed { + public Phase(State startState) throws ParseFailed, IOException { + this(null, null); + Result primordealResult = new Result(null, null, null); + newNode(primordealResult, startState, true); + } + public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { + this.location = input.getLocation(); + this.token = (Tok)input.next(); this.prevLocation = prev==null ? location : prev.getLocation(); this.prev = prev; this.forest = forest; - this.pos = previous==null ? 0 : previous.pos+1; - this.token = token; - this.location = location; - this.nextLocation = nextLocation; - performed.clear(); - hash = new IntPairMap(); - good = false; - finalResult = null; + this.pos = prev==null ? 0 : prev.pos+1; + this.nextLocation = input.getLocation(); if (prev != null) prev.shift(this, forest); + numReductions = 0; + + int minPhasePos = Integer.MAX_VALUE; + int maxOrd = -1; + Reduction best = null; + //System.out.println("=============================================================================="); + while(!reductionQueue.isEmpty()) { + Reduction r = reductionQueue.poll(); + //System.out.println("- " + r); + if (r.parentPhase() != null) + if (r.parentPhase().pos > minPhasePos) + throw new Error(); + r.perform(); + if (r.parentPhase() != null) { + if (r.parentPhase().pos < minPhasePos) { + minPhasePos = r.parentPhase().pos; + maxOrd = r.reduction().ord; + best = r; + } else if (r.parentPhase().pos == minPhasePos) { + /* + if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0) + throw new Error("\n"+r+"\n"+best+"\n"+ + Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+ + "\n"+(r.reduction().ord-best.reduction().ord)); + */ + maxOrd = r.reduction().ord; + best = r; + } + } + numReductions++; + } + if (token==null) shift(null, null); } - public boolean isFrontier() { return next==null; } public boolean isDone() throws ParseFailed { if (token != null) return false; if (token==null && finalResult==null) @@ -74,12 +114,20 @@ class GSS { public Input.Location getLocation() { return location; } public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); } public Input.Location getNextLocation() { return nextLocation; } + public boolean isFrontier() { return hash!=null; } /** perform all shift operations, adding promoted nodes to next */ - public void shift(Phase next, Forest result) throws ParseFailed { - // this massively improves GC performance - if (prev!=null) prev.hash = null; + private void shift(Phase next, Forest result) throws ParseFailed { this.next = next; + // this massively improves GC performance + if (prev != null) { + IntPairMap h = prev.hash; + prev.hash = null; + prev.performed = null; + for(Node n : h) + n.check(); + } + numOldNodes = hash.size(); for(Node n : hash.values()) { if (token == null && n.state().isAccepting()) { if (finalResult==null) finalResult = new Forest.Many(); @@ -87,32 +135,28 @@ class GSS { finalResult.merge(r.getForest()); } if (token == null) continue; - n.state().invokeShifts(token, this, new Result(result, n, null), null); + n.state().invokeShifts(token, this, new Result(result, n, null)); } - for(Node n : hash.values()) n.check(); + numNewNodes = next==null ? 0 : next.hash.size(); + viewPos = this.pos; if (!good && token!=null) ParseFailed.error("unexpected character", this); if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this); + for(Node n : hash) n.check(); } - /** perform all reduction operations */ - public void reduce() throws ParseFailed { - while(!reductionQueue.isEmpty()) - reductionQueue.poll().perform(); - } - - public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) { + void newNodeFromReduction(Result result, State state, Position reduction) { int pos = result.phase().pos; Sequence owner = reduction.owner(); - for(Sequence s : owner.hates) + for(Sequence s : owner.hates()) if (performed.contains(pos, s)) return; - for(Sequence s : owner.needs) + for(Sequence s : owner.needs()) if (!performed.contains(pos, s)) return; if (owner.needed_or_hated && !performed.contains(pos, owner)) performed.add(pos, owner); if (state!=null) - newNode(result, state, fromEmptyReduction); + newNode(result, state, reduction.pos<=0); } /** add a new node (merging with existing nodes if possible) @@ -122,16 +166,18 @@ class GSS { * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper) * @param start the earliest part of the input contributing to this node (used to make merging decisions) */ - public boolean newNode(Result result, State state, boolean fromEmptyReduction) { + private boolean newNode(Result result, State state, boolean fromEmptyReduction) { Node p = hash.get(state, result.phase()); - if (p != null) { p.merge(result); return true; } + if (p != null) { p.addResult(result); return true; } do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; if (!state.canReduce(token)) return false; } while(false); - new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + for(Object s : state.also) + newNode(new Result(null, n, null), (State)s, fromEmptyReduction); return true; } @@ -155,6 +201,17 @@ class GSS { public boolean isTransparent() { return false; } public boolean isHidden() { return false; } + public void dumpGraphViz(String filename) throws IOException { + FileOutputStream fos = new FileOutputStream(filename); + PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); + GraphViz gv = new GraphViz(); + for(Object n : this) + ((Node)n).toGraphViz(gv); + gv.dump(p); + p.flush(); + p.close(); + } + } } diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 1d5e05a..b734a8f 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -11,41 +11,33 @@ import java.lang.reflect.*; /** a node in the GSS */ final class Node - implements Invokable, + implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { /** which GSS.Phase this Node belongs to */ - public GSS.Phase phase() { return phase; } + public GSS.Phase phase() { return phase; } public Iterator iterator() { return results.iterator(); } public Parser.Table.State state() { return state; } public int toInt() { return idx; } - public boolean merge(Result r) { - if (results.contains(r)) return true; - results.add(r); - r.addChild(this); - if (fromEmptyReduction) return false; - state.invokeReductions(phase().getToken(), this, false, r); - return false; - } + boolean destroyed = false; - private boolean destroyed = false; - public boolean check() { + public void check() { + if (destroyed) return; boolean dead = true; // - all nodes must have a parent // - non-doomed nodes must either: // - be on the frontier or // - have a non-doomed node closer to the frontier than themself - if (phase.isFrontier()) dead = false; for(Result r : children) - if (state.doomed) { if (r.usedByAnyNode()) dead = false; } - else { if (r.usedByNonDoomedNode()) dead = false; } + if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } + else { if (r.usedByNonDoomedNode()) { dead = false; break; } } dead |= results.size()==0; - if (!dead || destroyed) return dead; + if (!dead || destroyed) return; destroyed = true; while(children.size()>0) for(Result r : children) { @@ -57,10 +49,10 @@ final class Node for(Result r : results) { results.remove(r); r.removeChild(this); - r.check(); break; } - return dead; + results = null; + children = null; } ////////////////////////////////////////////////////////////////////// @@ -74,19 +66,18 @@ final class Node //private FastSet results = new FastSet(); private HashSet results = new HashSet(); private HashSet children = new HashSet(); - public void removeChild(Result child) { children.remove(child); } - public void removeResult(Result result) { results.remove(result); } - public void addChild(Result child) { children.add(child); } - public final void invoke(Position r, Boolean emptyProductions, Result only) { + public final void invoke(Position r, Result only) { + boolean emptyProductions = only==null; if (emptyProductions != (r.pos==0)) return; - if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase()); + if (r.pos==0) new Result(r.zero(phase().getLocation().createRegion(phase().getLocation())), this, r, phase()); else reduce(r, r.pos-1, phase(), only); } private void reduce(Position r, int pos, GSS.Phase target, Result only) { Forest[] holder = r.holder; Forest old = holder[pos]; + if (results==null) return; // FIXME: this should not happen for(Result res : results) if (only == null || res == only) { Node child = res.parent(); @@ -97,27 +88,37 @@ final class Node holder[pos] = old; } - void finish(Position r, Forest forest, GSS.Phase target) { - Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner()); - Result result = new Result(forest, this, r); - target.newNodeFromReduction(result, state0, r.pos<=0, r); - } - Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) { this.phase = phase; this.state = state; this.fromEmptyReduction = fromEmptyReduction; - results.add(result); - result.addChild(this); if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!"); phase.hash.put(state, result.phase(), this); + addResult(result); + state.invokeEpsilonReductions(phase().token, this); + } - for(Object s : state.also) - phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction); + // Add/Remove Children/Results ////////////////////////////////////////////////////////////////////////////// - state.invokeReductions(phase().token, this, true, null); - if (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, false, null); + public void removeChild(Result child) { + if (children==null) return; + children.remove(child); + check(); + } + public void removeResult(Result result) { + if (results==null) return; + results.remove(result); + check(); + } + public void addChild(Result child) { + if (children==null) return; // FIXME: this should not happen + children.add(child); + } + public void addResult(Result r) { + if (results.contains(r)) return; + results.add(r); + r.addChild(this); + if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r); } // GraphViz ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index adf24c4..c2e7023 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -9,96 +9,73 @@ import java.util.*; /** a parser which translates an Input<Token> into a Forest<NodeType> */ public abstract class Parser { + protected final Table pt; /** create a parser to parse the grammar with start symbol u */ public Parser(Union u, Topology top) { this.pt = new Table(u, top); } - Parser(Table pt) { this.pt = pt; } /** implement this method to create the output forest corresponding to a lone shifted input token */ public abstract Forest shiftToken(Token t, Input.Location newloc); - boolean helpgc = true; - public String toString() { return pt.toString(); } - /** parse input, and return the shared packed parse forest (or throw an exception) */ - public Forest parse(Input input) throws IOException, ParseFailed { - GSS gss = new GSS(input); - Input.Location loc = input.getLocation(); - Token tok = input.next(); - GSS.Phase current = gss.new Phase(null, null, tok, loc, input.getLocation(), null); - current.newNode(new Result(Forest.create(loc.createRegion(loc), null, null, false), null, null), pt.start, true); - int count = 1; - for(int idx=0;;idx++) { - Input.Location oldloc = loc; - current.reduce(); - Forest forest = current.token==null ? null : shiftToken((Token)current.token, loc); - loc = input.getLocation(); - Token nextToken = input.next(); - GSS.Phase next = gss.new Phase(current, current, nextToken, loc, input.getLocation(), forest); - - /* - FileOutputStream fos = new FileOutputStream("out-"+idx+".dot"); - PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); - GraphViz gv = new GraphViz(); - for(Object n : current) - ((Node)n).toGraphViz(gv); - gv.dump(p); - p.flush(); - p.close(); - */ - - count = next.size(); - if (current.isDone()) return (Forest)gss.finalResult; - current = next; + private boolean verbose = false;; + private static final char[] spin = new char[] { '-', '\\', '|', '/' }; + private int spinpos = 0; + private long last = 0; + void spin() { + if (verbose) { + long now = System.currentTimeMillis(); + if (now-last < 100) return; + last = now; + System.err.print("\r " + spin[spinpos++ % (spin.length)]+ANSI.clreol()+"\r"); } } - // Table ////////////////////////////////////////////////////////////////////////////// - - /** an SLR(1) parse table which may contain conflicts */ - static class Table extends Walk.Cache { - - public String toString() { - StringBuffer sb = new StringBuffer(); - sb.append("parse table"); - for(State state : all_states) { - sb.append(" " + state + "\n"); - for(Topology t : state.shifts) { - sb.append(" shift \""+ - new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => "); - for(State st : state.shifts.getAll(t)) - sb.append(st.idx+" "); - sb.append("\n"); + /** parse input, and return the shared packed parse forest (or throw an exception) */ + public Forest parse(Input input) throws IOException, ParseFailed { + verbose = System.getProperty("sbp.verbose", null) != null; + spinpos = 0; + try { + GSS gss = new GSS(input, this); + for(GSS.Phase current = gss.new Phase(pt.start); ;) { + + if (verbose) { + String s; + s = " " + spin[spinpos++ % (spin.length)]+" parsing "; + s += input.getName(); + s += " "+input.getLocation(); + while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s; + String y = "@"+gss.viewPos+" "; + while(y.length() < 9) y = " " + y; + s += y; + //s += " doom="+Node.doomedNodes; + //while(s.length() < 40) s = s + " "; + s += " nodes="+gss.numOldNodes; + while(s.length() < 50) s = s + " "; + s += " shifted="+gss.numNewNodes; + while(s.length() < 60) s = s + " "; + s += " reductions="+gss.numReductions; + System.err.print("\r"+s+ANSI.clreol()+"\r"); } - for(Topology t : state.reductions) - sb.append(" reduce \""+ - new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => " + - state.reductions.getAll(t) + "\n"); - for(Sequence s : state.gotoSetNonTerminals.keySet()) - sb.append(" goto "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n"); + + // FIXME: make sure all the locations line up properly in here + if (current.isDone()) return (Forest)current.finalResult; + Forest forest = shiftToken((Token)current.token, input.getLocation()); + current = gss.new Phase(current, forest); } - return sb.toString(); + } finally { + if (verbose) + System.err.print("\r \r"); } + } - public final Walk.Cache cache = this; - private void walk(Element e, HashSet hs) { - if (e==null) return; - if (hs.contains(e)) return; - hs.add(e); - if (e instanceof Atom) return; - for(Sequence s : (Union)e) - walk(s, hs); - } - private void walk(Sequence s, HashSet hs) { - hs.add(s); - for(Position p = s.firstp(); p != null; p = p.next()) - walk(p.element(), hs); - for(Sequence ss : s.needs()) walk(ss, hs); - for(Sequence ss : s.hates()) walk(ss, hs); - } + // Table ////////////////////////////////////////////////////////////////////////////// + + /** an SLR(1) parse table which may contain conflicts */ + static class Table extends Cache { /** the start state */ public final State start; @@ -111,24 +88,18 @@ public abstract class Parser { HashSet> all_states = new HashSet>(); HashMap,State> doomed_states = new HashMap,State>(); HashMap,State> normal_states = new HashMap,State>(); - HashSet all_elements = new HashSet(); /** construct a parse table for the given grammar */ public Table(Topology top) { this("s", top); } public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); } public Table(Union ux, Topology top) { + super(ux, top); Union start0 = new Union("0"); - start0.add(new Sequence.Singleton(ux)); - - for(Sequence s : start0) cache.eof.put(s, true); - cache.eof.put(start0, true); + Sequence seq0 = new Sequence.Singleton(ux); + start0.add(seq0); + buildFollowSet(seq0, top, true); // construct the set of states - walk(start0, all_elements); - for(SequenceOrElement e : all_elements) - cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); - for(SequenceOrElement e : all_elements) - cache.ys2.addAll(e, new Walk.YieldSet2(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); @@ -144,17 +115,19 @@ public abstract class Parser { state.accept = true; if (isRightNullable(p)) { - Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache); - Topology follow = wf.walk(p.owner()); + Topology follow = (Topology)follow(p.owner()); for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) { - Atom set = new Walk.EpsilonFollowSet(new edu.berkeley.sbp.chr.CharAtom(top.empty().complement()), - new edu.berkeley.sbp.chr.CharAtom(top.empty()), - cache).walk(p2.element()); - follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element())); + if (!(p2.element() instanceof Union)) throw new Error("impossible"); + Union u = (Union)p2.element(); + Atom set = new edu.berkeley.sbp.chr.CharAtom(new edu.berkeley.sbp.chr.CharTopology((Topology)epsilonFollowSet(u))); + Element p2e = p2.element(); + if (p2e instanceof Union) + for(Sequence p2es : ((Union)p2e)) + follow = follow.intersect(follow(p2es)); if (set != null) follow = follow.intersect(set.getTokenTopology()); } state.reductions.put(follow, p); - if (wf.includesEof()) state.eofReductions.add(p); + if (followEof.contains(p.owner())) state.eofReductions.add(p); } // if the element following this position is an atom, copy the corresponding @@ -170,6 +143,7 @@ public abstract class Parser { } // crude algorithm to assing an ordinal ordering to every position + // al will be sorted in DECREASING order (al[0] >= al[1]) ArrayList al = new ArrayList(); for(State s : all_states) { for(Object po : s) { @@ -177,55 +151,83 @@ public abstract class Parser { if (al.contains(p)) continue; int i=0; for(; i 0) + if (comparePositions(p, al.get(i)) < 0) break; } al.add(i, p); } } - for(int i=0; i 0) { + Sequence.Position p = al.remove(j); + al.add(i, p); + continue OUTER; + } + break; + } + + int j = 1; + int pk = 0; + for(int i=0; i 0) + { inc = true; break; } + } + inc = true; + if (inc) { + j++; + pk = i; + } + al.get(i).ord = j; + } - private boolean isRightNullable(Position p) { - if (p.isLast()) return true; - if (!possiblyEpsilon(p.element())) return false; - return isRightNullable(p.next()); + /* + for(int i=0; i implements IntegerMappable, Iterable { public final int idx = master_state_idx++; private final HashSet hs; public HashSet> also = new HashSet>(); - public transient HashMap> gotoSetNonTerminals = new HashMap>(); + public transient HashMap> gotoSetNonTerminals = new HashMap>(); private transient TopologicalBag> gotoSetTerminals = new TopologicalBag>(); - private TopologicalBag reductions = new TopologicalBag(); - private HashSet eofReductions = new HashSet(); - private TopologicalBag> shifts = new TopologicalBag>(); - private boolean accept = false; + private TopologicalBag reductions = new TopologicalBag(); + private HashSet eofReductions = new HashSet(); + private TopologicalBag> shifts = new TopologicalBag>(); + private boolean accept = false; - private VisitableMap> oshifts = null; - private VisitableMap oreductions = null; + private VisitableMap> oshifts = null; + private VisitableMap oreductions = null; // Interface Methods ////////////////////////////////////////////////////////////////////////////// - boolean isAccepting() { return accept; } - public Iterator iterator() { return hs.iterator(); } - - boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); } - void invokeShifts(Token t, Invokable,B,C> irbc, B b, C c) { - oshifts.invoke(t, irbc, b, c); + boolean isAccepting() { return accept; } + public Iterator iterator() { return hs.iterator(); } + boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); } + void invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); } + 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(Position r : eofReductions) node.invoke(r, null); + else oreductions.invoke(t, node, null); } - - boolean canReduce(Token t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); } - void invokeReductions(Token t, Invokable irbc, B b, C c) { - if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c); - else oreductions.invoke(t, irbc, b, c); + void invokeReductions(Token t, Node node, Result b) { + //System.err.println("\rinvokage: " + this); + if (t==null) for(Position r : eofReductions) node.invoke(r, b); + else oreductions.invoke(t, node, b); } // Constructor ////////////////////////////////////////////////////////////////////////////// @@ -233,7 +235,7 @@ public abstract class Parser { /** * create a new state consisting of all the Positions in hs * @param hs the set of Positions comprising this State - * @param all_elements the set of all elements (Atom instances need not be included) + * @param all the set of all elements (Atom instances need not be included) * * In principle these two steps could be merged, but they * are written separately to highlight these two facts: @@ -267,7 +269,7 @@ public abstract class Parser { for(Sequence s : p.owner().needs()) { if (hs.contains(s.firstp())) continue; HashSet h2 = new HashSet(); - reachable(s.firstp(), h2); + reachable(s, h2); also.add(mkstate(h2, true)); } for(Sequence s : p.owner().hates()) { @@ -302,43 +304,35 @@ public abstract class Parser { ((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed)); } - // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction), - // compute the closure over every position in this set which is followed by a symbol - // which could yield the Element in question. + // Step 2: for every Sequence, compute the closure over every position in this set which + // is followed by a symbol which could yield the Sequence. // // "yields" [in one or more step] is used instead of "produces" [in exactly one step] // to avoid having to iteratively construct our set of States as shown in most // expositions of the algorithm (ie "keep doing XYZ until things stop changing"). - HashMapBag move = new HashMapBag(); - for(Position p : hs) { - Element e = p.element(); - if (e==null) continue; - for(SequenceOrElement y : cache.ys2.getAll(e)) { - //System.out.println(e + " yields " + y); - HashSet hp = new HashSet(); - reachable(p.next(), hp); - move.addAll(y, hp); - } - } - OUTER: for(SequenceOrElement y : move) { + HashMapBag move = new HashMapBag(); + for(Position p : hs) + if (!p.isLast() && p.element() instanceof Union) + for(Sequence s : ((Union)p.element())) { + HashSet hp = new HashSet(); + reachable(p.next(), hp); + move.addAll(s, hp); + } + OUTER: for(Sequence y : move) { + // if a reduction is "lame", it should wind up in the dead_state after reducing HashSet h = move.getAll(y); State s = mkstate(h, doomed); - // if a reduction is "lame", it should wind up in the dead_state after reducing - if (y instanceof Sequence) { - for(Position p : hs) { - if (p.element() != null && (p.element() instanceof Union)) { - Union u = (Union)p.element(); - for(Sequence seq : u) - if (seq.needs.contains((Sequence)y) || seq.hates.contains((Sequence)y)) { - // FIXME: what if there are two "routes" to get to the sequence? - ((HashMap)gotoSetNonTerminals).put((Sequence)y, dead_state); - continue OUTER; - } - } - } - gotoSetNonTerminals.put((Sequence)y, s); - } + for(Position p : hs) + if (p.element() != null && (p.element() instanceof Union)) + for(Sequence seq : ((Union)p.element())) + if (seq.needs.contains(y) || seq.hates.contains(y)) { + // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched + // and also directly lamely matched + ((HashMap)gotoSetNonTerminals).put(y, dead_state); + continue OUTER; + } + gotoSetNonTerminals.put(y, s); } } @@ -355,6 +349,7 @@ public abstract class Parser { } return st.toString(); } + public String toString() { StringBuffer ret = new StringBuffer(); ret.append("state["+idx+"]: "); @@ -362,9 +357,30 @@ public abstract class Parser { return ret.toString(); } - public Walk.Cache cache() { return cache; } public int toInt() { return idx; } } + + public String toString() { + StringBuffer sb = new StringBuffer(); + sb.append("parse table"); + for(State state : all_states) { + sb.append(" " + state + "\n"); + for(Topology t : state.shifts) { + sb.append(" shift \""+ + new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => "); + for(State st : state.shifts.getAll(t)) + sb.append(st.idx+" "); + sb.append("\n"); + } + for(Topology t : state.reductions) + sb.append(" reduce \""+ + new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => " + + state.reductions.getAll(t) + "\n"); + for(Sequence s : state.gotoSetNonTerminals.keySet()) + sb.append(" goto "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n"); + } + return sb.toString(); + } } // Helpers ////////////////////////////////////////////////////////////////////////////// @@ -384,5 +400,5 @@ public abstract class Parser { h.add(p); if (p.element() != null) reachable(p.element(), h); } - + //public static Cache mastercache = null; } diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java index 684fbf8..5e59a4e 100644 --- a/src/edu/berkeley/sbp/Reduction.java +++ b/src/edu/berkeley/sbp/Reduction.java @@ -1,90 +1,47 @@ // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license package edu.berkeley.sbp; -import edu.berkeley.sbp.*; -import edu.berkeley.sbp.util.*; -import edu.berkeley.sbp.Parser.Table.*; import edu.berkeley.sbp.Sequence.Position; -import java.io.*; -import java.util.*; -import java.lang.reflect.*; final class Reduction implements Comparable { - public Position position; - public GSS.Phase phase; - public Forest result; - public Node node; - boolean done = false; + private Position reduction; + private GSS.Phase phase; + private Forest forest; + private Node parent; - public Reduction(Node node, Position position, Forest result, GSS.Phase target) { - this.position = position; - this.result = result; + public Reduction(Node parent, Position reduction, Forest forest, GSS.Phase target) { + this.reduction = reduction; + this.forest = forest; this.phase = target; - this.node = node; - target.reductionQueue.add(this); - } - - public void perform() { - if (done) return; - done = true; - node.finish(position, result, phase); + this.parent = parent; + target.addReduction(this); } public int compareTo(Reduction r) { - int ret = compareTo0(r); - if (ret != 0) return -1 * ret; - return (position.ord - r.position.ord); - } - - private static boolean isRightNullable(Walk.Cache c, Position p) { - if (p.isLast()) return true; - if (!c.possiblyEpsilon(p.element())) return false; - return isRightNullable(c, p.next()); - } - - public static boolean canKill(Walk.Cache cache, Position mep, Position himp) { - if (!isRightNullable(cache, mep)) return false; - if (!isRightNullable(cache, himp)) return false; - Sequence me = mep.owner(); - Sequence him = himp.owner(); - Boolean b = me.canKill.get(him); - if (b!=null) return b; - for(Sequence killer : him.hates()) { - HashSet eq2 = new Walk.EquivalentTo(killer, cache).walk(); - if (eq2.contains(me)) { me.canKill.put(him, true); return true; } + if (parent.phase()!=null || r.parent.phase()!=null) { + if (parent.phase()==null) return 1; + if (r.parent.phase()==null) return -1; + if (parent.phase().pos < r.parent.phase().pos) return 1; + if (parent.phase().pos > r.parent.phase().pos) return -1; } - me.canKill.put(him, false); - return false; + /* + int master = Parser.mastercache.comparePositions(reduction(), r.reduction()); + if (master != 0 && master != signum(reduction.ord - r.reduction.ord)) + throw new Error("master="+master+" and a="+reduction.ord+" and b="+r.reduction.ord+"\n"+reduction+"\n"+r.reduction); + */ + return reduction.ord - r.reduction.ord; } - public static final int LESS_THAN = -1; - public static final int EQUAL_TO = 0; - public static final int GREATER_THAN = 1; - - public int compareTo0(Reduction n) { - if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO; - if (targetPhase()==null) return LESS_THAN; - if (n.targetPhase()==null) return GREATER_THAN; - if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN; - if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN; - return 0; + private int signum(int x) { + if (x==0) return 0; + if (x<0) return -1; + return 1; } - public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; } - public GSS.Phase targetPhase() { return node.phase(); } - public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) { - if (!isRightNullable(cache, mep)) return false; - if (!isRightNullable(cache, himp)) return false; - Sequence me = mep.owner(); - Sequence him = himp.owner(); - Boolean b = me.canNeed.get(him); - if (b!=null) return b; - for(Sequence needer : him.needs()) { - HashSet eq2 = new Walk.EquivalentTo(needer, cache).walk(); - if (eq2.contains(me)) { me.canNeed.put(him, true); return true; } - } - me.canNeed.put(him, false); - return false; - } + public void perform() { new Result(forest, parent, reduction, phase); } + public GSS.Phase parentPhase() { return parent.phase(); } + public Position reduction() { return reduction; } + public GSS.Phase targetPhase() { return phase; } + public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction.ord+":"+ reduction+" "+reduction.owner(); } } diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java index 9db5aee..d333f41 100644 --- a/src/edu/berkeley/sbp/Result.java +++ b/src/edu/berkeley/sbp/Result.java @@ -9,14 +9,11 @@ final class Result implements GraphViz.ToGraphViz { private Forest f; private Node parent; - private GSS.Phase phase; - private Position reduction; private HashSet children = new HashSet(); private boolean destroyed = false; private int usedByNonDoomedNode = 0; - public Position reduction() { return reduction; } - public GSS.Phase phase() { return phase; } + public GSS.Phase phase() { return parent==null ? null : parent.phase(); } public Forest getForest() { return f; } public Node parent() { return parent; } public void addChild(Node child) { @@ -24,8 +21,10 @@ final class Result implements GraphViz.ToGraphViz { usedByNonDoomedNode += child.state().doomed ? 0 : 1; } public void removeChild(Node child) { + if (!children.contains(child)) return; children.remove(child); usedByNonDoomedNode -= child.state().doomed ? 0 : 1; + check(); } public boolean usedByAnyNode() { return children.size() > 0; } @@ -38,27 +37,25 @@ final class Result implements GraphViz.ToGraphViz { if (destroyed) return; if (parent==null) return; // never destroy the "primordeal" result destroyed = true; - if (parent() != null) { - parent().removeChild(this); - parent().check(); - } - OUTER: while(true) { + parent.removeChild(this); + while(children.size() > 0) for(Node n : children) { children.remove(n); n.removeResult(this); - n.check(); - continue OUTER; + break; } - break; - } } public Result(Forest f, Node parent, Position reduction) { + this(f, parent, reduction, null); + } + public Result(Forest f, Node parent, Position reduction, GSS.Phase target) { this.f = f; - this.reduction = reduction; this.parent = parent; if (parent != null) parent.addChild(this); - if (parent != null) phase = parent.phase(); + if (reduction == null) return; + Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction.owner()); + target.newNodeFromReduction(this, state0, reduction); } // GraphViz ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index 2c36c8d..3e260f1 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -98,7 +98,10 @@ public abstract class Sequence implements Iterable, SequenceOrElement { public Iterator iterator() { return new ArrayIterator(elements); } protected Sequence(Element[] elements) { this.elements = elements; - this.firstp = new Position(0); + for(int i=0; i, SequenceOrElement { class Position implements IntegerMappable { public int ord = -1; - public int compareTo(Position p, Walk.Cache cache) { - Position position = this; - Position rposition = p; - int ret = 0; - if (Reduction.canKill(cache, position, rposition) && - Reduction.canKill(cache, rposition, position)) throw new Error(); - if (Reduction.canKill(cache, position, rposition)) ret = 1; - else if (Reduction.canKill(cache, rposition, position)) ret = -1; - if (Reduction.canNeed(cache, position, rposition)) ret = 1; - else if (Reduction.canNeed(cache, rposition, position)) ret = -1; - return ret; - } private Forest zero = null; public Forest zero(Input.Region reg) { if (zero != null) return zero; - if (pos > 0) throw new Error(); + if (pos > 0) throw new RuntimeException("Position.zero(): pos>0"); return zero = rewrite(reg); } - final int pos; private final Position next; private final Position prev; final Forest[] holder; - private Position(int pos) { + private Position(int pos, Position prev) { this.pos = pos; - this.next = pos==elements.length ? null : new Position(pos+1); + this.next = pos==elements.length ? null : new Position(pos+1, this); this.holder = new Forest[elements.length]; this.prev = prev; } @@ -178,9 +168,7 @@ public abstract class Sequence implements Iterable, SequenceOrElement { if (holder[i]==null) holder[i] = elements[i].epsilonForm(loc); if (holder[i]==null) throw new Error("bad " + i); } - Forest ret = Sequence.this.postReduce(loc, holder, this); - //for(int k=0; k, SequenceOrElement { Forest[] args2 = new Forest[count]; int j = 0; for(int i=0; i