/** expand this forest into a set of trees */
public abstract HashSet<Tree<T>> expand(boolean toss);
-
- abstract boolean valid();
+ public abstract boolean empty();
static <T> Forest<T> singleton(Token.Location loc, Sequence creator) { return create(loc, null, new Forest[] { }, creator, false, true); }
static <T> Forest<T> singleton(Token.Location loc, Forest<T> body, Sequence creator) { return create(loc, null, new Forest[] { body }, creator, false, true); }
b.expand(toss, toks, 0, h);
} else {
- if (tokens[i]!=null) {
- HashSet<Tree<T>> exp = tokens[i].expand(toss);
- if (exp != null)
- for(Tree<T> r : exp) {
- int old = toks.size();
- toks.add(r);
- expand(toss, toks, i+1, h);
- while(toks.size() > old) toks.remove(toks.size()-1);
- }
+ boolean hit = false;
+ for(Tree<T> r : tokens[i].expand(toss)) {
+ hit = true;
+ int old = toks.size();
+ toks.add(r);
+ expand(toss, toks, i+1, h);
+ while(toks.size() > old) toks.remove(toks.size()-1);
}
+ //if (!hit) throw new Error();
}
return h;
}
else for(Body b : (IterableForest<T>)tokens[0]) b.addTo(h);
}
- private boolean kcache = false;
- private boolean keep = false;
- public boolean keep() {
- return true;
- /*
- if (kcache) return keep;
- kcache = true;
- for(Forest<T> token : tokens) if (!token.valid()) return keep = false;
- return keep = creator==null || (creator.needs.size()==0 && creator.hates.size()==0);
- */
- }
- public boolean keep(Iterable<Body<T>> h) {
- if (keep()) return true;
- for(Forest<T> token : tokens) if (!token.valid()) return false;
- int needs = 0;
- for(Body<T> b : h) {
- if (creator.hates.contains(b.creator) && b.keep(h)) return false;
- if (creator.needs.contains(b.creator) && b.keep(h)) needs--;
- }
- return needs <= -1 * creator.needs.size();
- }
private boolean rep = false;
public String toString() {
* viewed, it becomes immutable
*/
static class Ref<T> extends IterableForest<T> {
+ public boolean empty() {
+ if (res!=null) return res.empty();
+ for(Forest f : hp) if (!f.empty()) return false;
+ return true;
+ }
private FastSet<Forest> hp = new FastSet<Forest>();
private Forest res = null;
- public boolean valid = false;
public Ref() { }
public void merge(Forest p) {
- //if (p==null) throw new Error("bad evil bad!");
if (res != null) throw new Error("already resolved!");
if (p==null) throw new Error();
if (p!=this) hp.add(p, true);
}
public Iterator<Body<T>> iterator() { return ((IterableForest<T>)resolve()).iterator(); }
public HashSet<Tree<T>> expand(boolean toss) { return resolve().expand(toss); }
- public boolean valid() { return true; /*if (valid) return true; resolve(); return valid;*/ }
public String toString() { return resolve().toString(); }
public Forest resolve() {
if (hp==null) return res;
FastSet<Body> nh = new FastSet<Body>();
- /*
- HashSet<Body> results = null;
- for(Forest<?> p : hp)
- for(Body<?> b : (IterableForest<?>)p) {
- if (b.keep() && (b.creator==null || !b.creator.lame)) {
- valid = true;
- b.addTo(nh);
- } else {
- results = new HashSet<Body>();
- }
- }
- if (results != null) {
- for(Forest<?> p : hp)
- for(Body<?> b : (IterableForest<?>)p)
- results.add(b);
- for(Body b : results) {
- if (b.keep() && (b.creator==null || !b.creator.lame)) continue;
- if (b.creator!=null && b.creator.lame) continue;
- if (!b.keep(results)) continue;
- valid = true;
- b.addTo(nh);
- }
- }
- hp = null;
- */
for(Forest<?> p : hp)
for(Body<?> b : (IterableForest<?>)p)
- if (b.creator==null || !b.creator.lame)
- b.addTo(nh);
- res = new MultiForest(nh, nh.size()>0);
+ b.addTo(nh);
+ res = new MultiForest(nh);
hp = null;
return res;
}
// Implementations //////////////////////////////////////////////////////////////////////////////
private static class MultiForest<T> extends IterableForest<T> {
+ public boolean empty() { return results.size()>0; }
private final FastSet<Body<T>> results;
- private boolean valid;
- public boolean valid() { /*return valid;*/ return true; }
- private MultiForest(FastSet<Body<T>> results, boolean valid) { this.results = results; this.valid = valid; }
+ private MultiForest(FastSet<Body<T>> results) { this.results = results; }
public MultiForest(Token.Location loc, T tag, Forest<T>[] tokens, Sequence creator, boolean unwrap, boolean singleton) {
this.results = new FastSet<Body<T>>(new Body(loc, tag, tokens, creator, unwrap, singleton));
- this.valid = true;
}
public Iterator<Body<T>> iterator() { return results.iterator(); }
public int waits = 0;
HashMapBag<Integer,Sequence> inhibited = new HashMapBag<Integer,Sequence>();
+ HashMapBag<Integer,Sequence> assumed = new HashMapBag<Integer,Sequence>();
HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
+ HashSet<Phase.Waiting> tail = new HashSet<Phase.Waiting>();
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
public class Phase implements Invokable<State, Forest, GSS.Phase.Node> {
this.token = token;
this.location = location;
inhibited.clear();
+ assumed.clear();
reset();
}
public void reset() {
+ tail.clear();
waiting.clear();
performed.clear();
hash = new HashMap<Long,Phase.Node>();
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
- return newNode(parent, pending, state, fromEmptyReduction, null); }
- public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
+ Node p = hash.get(code(state, parent==null?null:parent.phase()));
+ if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction);
+ else return newNode3(parent, pending, state, 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, reduction.position.owner())) return false;
- if (reduction.position.owner().needs != null) {
- for(Sequence s : reduction.position.owner().needs) {
+ 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 false;
+ return;
}
- }
- }
- if ((reduction.position.owner().needed != null && reduction.position.owner().needed.size()>0) ||
- (reduction.position.owner().hated != null && reduction.position.owner().hated.size()>0) ||
- (reduction.position.owner().hates != null && reduction.position.owner().hates.size()>0))
- performed.add(pos, reduction.position.owner());
+ 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);
}
- Node p = hash.get(code(state, parent==null?null:parent.phase()));
- boolean ret;
+ if (!owner.lame)
+ newNode(parent, pending, state, fromEmptyReduction);
if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
- if (p != null) ret = newNode2(p, parent, pending, state, fromEmptyReduction, reduction);
- else ret = newNode3(parent, pending, state, fromEmptyReduction, reduction);
if (reduction != null) {
boolean redo = true;
while(redo) {
redo = false;
- for(Waiting w : waiting.getAll(reduction.position.owner())) {
+ for(Waiting w : waiting.getAll(owner)) {
if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
- waiting.remove(reduction.position.owner(), w);
+ waiting.remove(owner, w);
w.perform();
redo = true;
break;
}
}
}
- return ret;
}
- private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
+ 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, State state, boolean fromEmptyReduction, Reduction reduction) {
+ private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
do {
if (token != null && state.canShift(token)) break;
if (state.isAccepting()) break;
if (performed.contains(p,seq)) {
uninhibit(p, seq);
//System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
- if (!reset) inhibited.add(p, seq);
+ //inhibited.clear();
+ inhibited.add(p, seq);
+ //assumed = inhibited;
+ //inhibited = new HashMapBag<Integer,Sequence>();
reset = true;
+ resets++;
+ throw new Reset();
}
- if (!reset) inhibited.add(p, seq);
- }
- if (reset) {
- resets++;
- throw new Reset();
+ inhibited.add(p, seq);
}
}
reducing_list[i] = null;
n.queueReductions();
}
+ //for(Waiting w : tail)
+ //w.perform();
} catch (Reset r) {
reset();
reduce();
Forest res = null;
boolean ok = false;
for(Phase.Node n : hash.values()) {
- if (n.holder==null) continue;
- n.holder.resolve();
+ //if (n.holder().empty() && pos>0) continue;
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);
}
private Node(Node parent, Forest pending, State state, boolean fe) {
this.fe = fe;
this.state = state;
- for(Position p : state) {
- if (p.owner().needs!=null)
- for(Sequence s : p.owner().needs) {
- //dead = true;
- //redo = false;
- }
- }
+ this.holder().merge(pending);
+ //if (holder().empty()) throw new Error(holder()+"");
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);
Phase.this.numNodes++;
- if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid
}
}
GSS gss = new GSS();
Token.Location loc = input.getLocation();
GSS.Phase current = gss.new Phase(null, this, null, input.next(1, 0, 0), loc, null);
- current.newNode(null, null, pt.start, true);
+ current.newNode(null, Forest.leaf(null, null, null), pt.start, true);
int count = 1;
for(;;) {
loc = input.getLocation();
}
private void finish(GSS.Phase.Node parent, Forest result, GSS.Phase target) {
State state = parent.state.gotoSetNonTerminals.get(position.owner());
+ if (result==null) throw new Error();
if (state!=null)
target.newNode(parent, result, state, numPop<=0, this);
}
HashSet<Sequence> hated;
final HashSet<Sequence> needs;
final HashSet<Sequence> hates;
- boolean lame = false;
+ public boolean lame = false;
final Position firstp;
Position firstp() { return firstp; }
Forest epsilonForm() {
if (epsilonForm==null) {
epsilonForm = new Forest.Ref();
- Forest fo = firstp().rewrite(null);
- epsilonForm.merge(fo);
+ epsilonForm.merge(firstp().rewrite2(null));
}
return epsilonForm;
}
// Reduction /////////////////////////////////////////////////////////////////////////////////
final <T> Forest<T> rewrite(Token.Location loc) {
- if (this==firstp() && eps) return epsilonForm;
- eps = true;
+ if (this==firstp()) return epsilonForm();
+ return rewrite2(loc);
+ }
+
+ final <T> Forest<T> rewrite2(Token.Location loc) {
for(int i=0; i<pos; i++) if (holder[i]==null) throw new Error("realbad " + i);
for(int i=pos; i<elements.length; i++) {
if (holder[i]==null) holder[i] = elements[i].epsilonForm();
}
Forest<T> ret = Sequence.this.postReduce(loc, holder);
for(int k=0; k<pos; k++) holder[k] = null; // to help GC
- if (this==firstp()) { if (epsilonForm==null) epsilonForm=new Forest.Ref(); epsilonForm.merge(ret); return epsilonForm; }
return ret;
}
} catch (Parser.Failed pf) {
pfe = pf;
}
+ //ystem.out.println("res=="+res);
Collection<Tree<String>> results = res==null ? new HashSet<Tree<String>>() : res.expand(false);
System.out.print("\r");
if (results.size() == 0 && output.length > 0) {
while x>0
- while y>0
- foo()
- bar()
+ while y>0
+ foo()
+ bar()
+
while x>0
- while y>0
- foo()
- bar()
+ while y>0
+ foo()
+ bar()
";
- output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}} while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}}}";
- output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}} while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}";
+ output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}} while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}";
indent !::= ww
outdent !::= " " outdent " "
&~ "\n" outdent ~[\ ] ~[]*
blockBody ::= statement
- | statement ws blockBody => "sbb"
+ > statement ws blockBody => "sbb"
statement ::= call
| ^"while" expr block /ws
projects / sbp.git / commitdiff