X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=cff543d699845a77aa71ee30ec05570fb724472f;hp=3843f57020efe11b1df60b4612e8c818e89ddb91;hb=c366dacc334fe2e35835164f5a37d3eebb2ca6d5;hpb=ebb5fe5647046306f415e31e4967b23169c9004e diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 3843f57..cff543d 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -2,6 +2,8 @@ package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.Parser.Table.State; +import edu.berkeley.sbp.Parser.Table.Reduction; import java.io.*; import java.util.*; import java.lang.reflect.*; @@ -12,34 +14,69 @@ class GSS { public GSS() { } private Phase.Node[] reducing_list = null; - + public int resets = 0; + public int waits = 0; + + HashMapBag inhibited = new HashMapBag(); + HashMapBag assumed = new HashMapBag(); + HashMapBag waiting = new HashMapBag(); + HashMapBag performed = new HashMapBag(); + HashSet tail = new HashSet(); + /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - public class Phase implements Invokable { + public class Phase implements Invokable, IntegerMappable { + public int toInt() { return pos+1; } /** the token immediately after this phase */ public final Token token; - boolean reducing = false; + boolean reducing; /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */ private final int pos; /** FIXME */ - public Forest.Ref finalResult = null; + public Forest.Ref finalResult; /** all nodes, keyed by the value returned by code() */ - /*private*/ HashMap hash = new HashMap(); /* ALLOC */ + /*private*/ IntPairMap hash; /* ALLOC */ /** the number of nodes in this phase */ - private int numNodes = 0; + private int numNodes; + + boolean closed; - boolean closed = false; + private boolean good; + private Phase next = null; private Token.Location location; - public Phase(Phase previous, Token token, Token.Location location) { + public final Parser parser; + + private Forest forest; + Phase prev; + public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) { + this.prev = prev; + this.forest = forest; + this.parser = parser; this.pos = previous==null ? 0 : previous.pos+1; this.token = token; this.location = location; + inhibited.clear(); + assumed.clear(); + reset(); + } + + public void reset() { + tail.clear(); + waiting.clear(); + performed.clear(); + hash = new IntPairMap(); + good = false; + closed = false; + numNodes = 0; + reducing = false; + finalResult = null; + if (prev != null) prev.shift(this, forest); } public void complain(Node n, HashMap> errors, boolean force) { @@ -95,7 +132,10 @@ class GSS { ret.append("\n "); ret.append(message); HashMap> errors = new HashMap>(); - for(Node n : hash.values()) complain(n, errors, false); + for(Node n : hash.values()) { + //System.out.println(n.state); + complain(n, errors, false); + } for(String s : errors.keySet()) { ret.append(" while parsing " + yellow(s)); HashSet hs = errors.get(s); @@ -122,8 +162,6 @@ class GSS { return true; } - private String error = "generic syntax error"; - public Token.Location getLocation() { return location; } /** add a new node (merging with existing nodes if possible) @@ -133,21 +171,59 @@ 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(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { - Node p = hash.get(code(state, parent==null?null:parent.phase())); + public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) { + Node p = hash.get(state, parent==null?null:parent.phase()); if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction); else return newNode3(parent, pending, state, fromEmptyReduction); } - private boolean newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { + public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { + int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos; + Sequence owner = reduction==null ? null : reduction.position.owner(); + if (reduction!=null) { + if (inhibited.contains(pos, owner)) return; + /* + if (assumed.contains(pos, owner)) { + tail.add(new Waiting(parent, pending, state, fromEmptyReduction, reduction)); + return; + } + */ + if (owner.needs != null) + for(Sequence s : owner.needs) + if (!performed.contains(pos, s)) { + waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction)); + return; + } + if ((owner.needed != null && owner.needed.size()>0) || + (owner.hated != null && owner.hated.size()>0) || + (owner.hates != null && owner.hates.size()>0)) + performed.add(pos, owner); + } + if (!owner.lame) + newNode(parent, pending, state, fromEmptyReduction); + if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos); + if (reduction != null) { + boolean redo = true; + while(redo) { + redo = false; + for(Waiting w : waiting.getAll(owner)) { + if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) { + waiting.remove(owner, w); + w.perform(); + redo = true; + break; + } + } + } + } + } + private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) { p.holder.merge(pending); if (p.parents().contains(parent)) return true; - //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep"); - //if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2"); p.parents().add(parent, true); if (p!=parent && !fromEmptyReduction) p.queueReductions(parent); return true; } - private boolean newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { + private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) { do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; @@ -165,47 +241,80 @@ class GSS { return true; } + public void uninhibit(int p, Sequence s) { + if (s.hated!=null) + for(Sequence s2 : s.hated) + inhibited.remove(p, s2); + } + + public void inhibit(Reduction r, int p) { + if (r.position.owner().hated == null) return; + // remember that dead states are still allowed to shift -- just not allowed to reduce + boolean reset = false; + for(Sequence seq : r.position.owner().hated) { + if (performed.contains(p,seq)) { + uninhibit(p, seq); + //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq); + //inhibited.clear(); + inhibited.add(p, seq); + //assumed = inhibited; + //inhibited = new HashMapBag(); + reset = true; + resets++; + throw new Reset(); + } + inhibited.add(p, seq); + } + } /** perform all reduction operations */ public void reduce() { - reducing = true; - if (reducing_list==null || reducing_list.length < hash.size()) - reducing_list = new Phase.Node[hash.size() * 4]; - Collection hv = hash.values(); - hv.toArray(reducing_list); - int num = hv.size(); - for(int i=0; inext */ public void shift(Phase next, Forest result) throws Parser.Failed { + if (prev!=null) prev.hash = null; this.next = next; closed = true; Forest res = null; boolean ok = false; for(Phase.Node n : hash.values()) { - if (n.holder==null) continue; - n.holder.resolve(); if (token == null && n.state.isAccepting()) { if (finalResult==null) finalResult = new Forest.Ref(); finalResult.merge(n.holder); } - if (!n.holder.valid()) continue; if (token == null) continue; n.state.invokeShifts(token, this, result, n); } @@ -218,21 +327,41 @@ class GSS { getLocation()); // this massively improves GC performance - hash = null; + //hash = null; } + + public class Waiting { + Node parent; + Forest pending; + State state; + boolean fromEmptyReduction; + Reduction reduction; + public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { + waits++; + this.parent = parent; + this.pending = pending; + this.state = state; + this.fromEmptyReduction = fromEmptyReduction; + this.reduction = reduction; + } + public void perform() { + //System.out.println("performing: " + reduction.position); + newNode(parent, pending, state, fromEmptyReduction, reduction); + } + } // GSS Nodes ////////////////////////////////////////////////////////////////////////////// /** a node in the GSS */ - public final class Node extends FastSet implements Invokable { + public final class Node extends FastSet implements Invokable { public boolean touched = false; private Forest.Ref holder = null; private boolean allqueued = false; /** what state this node is in */ - public final Parser.Table.State state; + public final State state; /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ public Phase phase() { return Phase.this; } @@ -254,7 +383,7 @@ class GSS { state.invokeReductions(token, this, this, n2); } - public final void invoke(Parser.Table.Reduction r, Node n, Node n2) { + public final void invoke(Reduction r, Node n, Node n2) { if (n==null) { if (r.numPop==0) r.reduce(this); return; @@ -269,16 +398,17 @@ class GSS { } private boolean fe; - private Node(Node parent, Forest pending, Parser.Table.State state, boolean fe) { + public boolean dead = false; + public boolean redo = false; + private Node(Node parent, Forest pending, State state, boolean fe) { this.fe = fe; this.state = state; + this.holder().merge(pending); Phase start = parent==null ? null : parent.phase(); - if (pending != null) this.holder().merge(pending); if (parent != null) parents().add(parent, true); - if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!"); - Phase.this.hash.put(code(state, start), this); + if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!"); + Phase.this.hash.put(state, start, this); Phase.this.numNodes++; - if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid } } @@ -290,9 +420,4 @@ class GSS { if (a==null || b==null) return false; return a.equals(b); } - - /** this is something of a hack right now */ - private static long code(Parser.Table.State state, Phase start) { - return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1)); - } }