From: adam Date: Sun, 8 Jan 2006 01:06:36 +0000 (-0500) Subject: yay, new boolean resolution approach works X-Git-Tag: tag_for_25-Mar~422 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=842f3c9b981b35721bb50d49e85c11085b2040a3 yay, new boolean resolution approach works darcs-hash:20060108010636-5007d-e8e1c2d0456e2c4e5f9bc2f30adbb54bebd260fe.gz --- diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 5c09170..8ed6eb5 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -88,10 +88,13 @@ public abstract class Forest { private boolean kcache = false; private boolean keep = false; public boolean keep() { + return true; + /* if (kcache) return keep; kcache = true; for(Forest token : tokens) if (!token.valid()) return keep = false; return keep = creator==null || (creator.needs.size()==0 && creator.hates.size()==0); + */ } public boolean keep(Iterable> h) { if (keep()) return true; @@ -152,7 +155,7 @@ public abstract class Forest { } public Iterator> iterator() { return ((IterableForest)resolve()).iterator(); } public HashSet> expand(boolean toss) { return resolve().expand(toss); } - public boolean valid() { if (valid) return true; resolve(); return valid; } + 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; @@ -190,7 +193,7 @@ public abstract class Forest { private static class MultiForest extends IterableForest { private final FastSet> results; private boolean valid; - public boolean valid() { return valid; } + public boolean valid() { /*return valid;*/ return true; } private MultiForest(FastSet> results, boolean valid) { this.results = results; this.valid = valid; } public MultiForest(Token.Location loc, T tag, Forest[] tokens, Sequence creator, boolean unwrap, boolean singleton) { this.results = new FastSet>(new Body(loc, tag, tokens, creator, unwrap, singleton)); diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 3843f57..404dee9 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,64 @@ class GSS { public GSS() { } private Phase.Node[] reducing_list = null; + public int resets = 0; + public int waits = 0; + HashMapBag inhibited = new HashMapBag(); + HashMapBag waiting = new HashMapBag(); + HashMapBag performed = new HashMapBag(); + /** 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 { /** 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*/ HashMap hash; /* ALLOC */ /** the number of nodes in this phase */ - private int numNodes = 0; + private int numNodes; - boolean closed = false; + boolean closed; + + 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(); + reset(); + } + + public void reset() { + waiting.clear(); + performed.clear(); + hash = new HashMap(); + 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) { @@ -122,8 +154,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,12 +163,44 @@ 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) { + 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) { + int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos; + 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 (!performed.contains(pos, s)) { + waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction)); + return false; + } + } + } + performed.add(pos, reduction.position.owner()); + } 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); + boolean ret; + 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())) { + if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) { + waiting.remove(reduction.position.owner(), w); + w.perform(); + redo = true; + break; + } + } + } + } + return ret; } - private boolean newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) { + private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { p.holder.merge(pending); if (p.parents().contains(parent)) return true; //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep"); @@ -147,7 +209,7 @@ class GSS { 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, Reduction reduction) { do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; @@ -165,35 +227,54 @@ class GSS { return true; } + 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 + for(Sequence seq : r.position.owner().hated) { + if (performed.contains(p,seq)) { + inhibited.clear(); + inhibited.add(p, seq); + 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; i 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; @@ -218,21 +299,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 +355,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,9 +370,18 @@ 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; + for(Position p : state) { + if (p.owner().needs!=null) + for(Sequence s : p.owner().needs) { + //dead = true; + //redo = false; + } + } Phase start = parent==null ? null : parent.phase(); if (pending != null) this.holder().merge(pending); if (parent != null) parents().add(parent, true); @@ -292,7 +402,7 @@ class GSS { } /** this is something of a hack right now */ - private static long code(Parser.Table.State state, Phase start) { + private static long code(State state, Phase start) { return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1)); } } diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index ddee582..ead3551 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -11,7 +11,7 @@ import java.lang.reflect.*; /** a parser which translates streams of Tokens of type T into a Forest */ public abstract class Parser { - private final Table pt; + public final Table pt; /** create a parser to parse the grammar with start symbol u */ protected Parser(Union u) { this.pt = new Table(u, top()); } @@ -36,16 +36,15 @@ public abstract class Parser { public Forest parse(Token.Stream input) throws IOException, Failed { GSS gss = new GSS(); Token.Location loc = input.getLocation(); - GSS.Phase current = gss.new Phase(null, input.next(1), loc); + GSS.Phase current = gss.new Phase(null, this, null, input.next(1, 0, 0), loc, null); current.newNode(null, null, pt.start, true); int count = 1; for(;;) { loc = input.getLocation(); //current.checkFailure(); - GSS.Phase next = gss.new Phase(current, input.next(count), loc); current.reduce(); Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); - current.shift(next, forest); + GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); count = next.hash.size(); if (current.isDone()) return (Forest)current.finalResult; current = next; @@ -55,7 +54,7 @@ public abstract class Parser { // Exceptions ////////////////////////////////////////////////////////////////////////////// - public static class Failed extends Exception { + public static class Failed extends RuntimeException { private final Token.Location location; private final String message; public Failed() { this("", null); } @@ -83,6 +82,8 @@ public abstract class Parser { static class Table extends Walk.Cache { public final Walk.Cache cache = this; + + public HashMapBag byPosition = new HashMapBag(); private void walk(Element e, HashSet hs) { if (e==null) return; @@ -247,6 +248,7 @@ public abstract class Parser { // register ourselves in the all_states hash so that no // two states are ever created with an identical position set all_states.put(hs, this); + for(Position p : hs) byPosition.add(p,this); // Step 1a: examine all Position's in this state and compute the mappings from // sets of follow tokens (tokens which could follow this position) to sets @@ -381,7 +383,7 @@ public abstract class Parser { private void finish(GSS.Phase.Node parent, Forest result, GSS.Phase target) { State state = parent.state.gotoSetNonTerminals.get(position.owner()); if (state!=null) - target.newNode(parent, result, state, numPop<=0); + target.newNode(parent, result, state, numPop<=0, this); } } } diff --git a/src/edu/berkeley/sbp/Token.java b/src/edu/berkeley/sbp/Token.java index 551ee6d..1014a55 100644 --- a/src/edu/berkeley/sbp/Token.java +++ b/src/edu/berkeley/sbp/Token.java @@ -15,7 +15,7 @@ public interface Token { /** a sequence of input tokens; returns null when EOF is reached */ public static interface Stream { - public T next(int numstates) throws IOException; + public T next(int numstates, int resets, int waits) throws IOException; public abstract Location getLocation(); } diff --git a/src/edu/berkeley/sbp/misc/CharToken.java b/src/edu/berkeley/sbp/misc/CharToken.java index 9d10889..fb02aaf 100644 --- a/src/edu/berkeley/sbp/misc/CharToken.java +++ b/src/edu/berkeley/sbp/misc/CharToken.java @@ -154,7 +154,7 @@ public class CharToken implements Token, IntegerTopology.IntegerMappable { long then = 0; private Token.Location location = new LocWrap(1, 1); public Token.Location getLocation() { return location; } - public Token next(int numstates) throws IOException { + public Token next(int numstates, int resets, int waits) throws IOException { int i = r.read(); if (i==-1) return null; char c = (char)i; @@ -164,7 +164,7 @@ public class CharToken implements Token, IntegerTopology.IntegerMappable { while(s.length() < 4) s = " " + s; s = "line "+s+", col " + col; while(s.length() < 20) s += " "; - s += "[ambiguity level: " + (numstates-1) + "]"; + s += "[ambiguity level: " + (numstates-1) + "] [resets: " + resets + "] [waits: " + waits + "]"; long now = System.currentTimeMillis(); if (now-then > 10) { then = now; diff --git a/src/edu/berkeley/sbp/tib/Tib.java b/src/edu/berkeley/sbp/tib/Tib.java index 9ec8bd8..401d9c0 100644 --- a/src/edu/berkeley/sbp/tib/Tib.java +++ b/src/edu/berkeley/sbp/tib/Tib.java @@ -50,8 +50,8 @@ public class Tib implements Token.Stream { boolean indenting = true; int indentation = 0; private ArrayList istack = new ArrayList(); - public CharToken next(int numstates) throws IOException { - CharToken ret = nextc(numstates); + public CharToken next(int numstates, int resets, int waits) throws IOException { + CharToken ret = nextc(numstates, resets); if (ret==CharToken.left) System.out.print("\033[31m{\033[0m"); else if (ret==CharToken.right) System.out.print("\033[31m}\033[0m"); else if (ret==null) return null; @@ -60,7 +60,7 @@ public class Tib implements Token.Stream { } CharToken waitingBrace = null; - public CharToken nextc(int numstates) throws IOException { + public CharToken nextc(int numstates, int resets) throws IOException { char c; if (waitingBrace != null) { CharToken ret = waitingBrace; @@ -85,7 +85,7 @@ public class Tib implements Token.Stream { else _col++; if (indenting) { if (c==' ') { indentation++; return done(c); } - if (c=='\n') { indentation = 0; if (blank) return nextc(numstates); blank = true; waiting = true; waitingChar='\n'; return new CharToken('\n'); } + if (c=='\n') { indentation = 0; if (blank) return nextc(numstates, resets); blank = true; waiting = true; waitingChar='\n'; return new CharToken('\n'); } int last = istack.size()==0 ? -1 : istack.get(istack.size()-1); if (indentation==last) { if (blank) { diff --git a/src/edu/berkeley/sbp/util/HashMapBag.java b/src/edu/berkeley/sbp/util/HashMapBag.java index 5430a8f..6f5585d 100644 --- a/src/edu/berkeley/sbp/util/HashMapBag.java +++ b/src/edu/berkeley/sbp/util/HashMapBag.java @@ -22,5 +22,16 @@ public final class HashMapBag implements MapBag { return ret; } + public void remove(K k, V v) { + if (hm.get(k)==null) return; + hm.get(k).remove(v); + } + + public void clear() { hm.clear(); } + + public boolean contains(K k, V v) { + return hm.get(k)!=null && hm.get(k).contains(v); + } + public Iterator iterator() { return hm.keySet().iterator(); } } diff --git a/tests/regression.tc b/tests/regression.tc index 7d170e0..025500a 100644 --- a/tests/regression.tc +++ b/tests/regression.tc @@ -255,59 +255,59 @@ testcase { q ::= [a-z]++ => "q" } -testcase { - - input " - - - while x>0 - while y>0 - foo() - bar() - - while x>0 - while y>0 - foo() - bar() - - -"; - output "smt:{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}}}}"; - -indent !::= ww -outdent !::= " " outdent " " - | " " (~[]*) "\n" - -any !::= ~[]* -s ::= any "\n\n" ww statement ww "\n\n" any => smt -ww !::= sp* -ws !::= sp** -sp ::= " " - -block ::= "\n" indent blockBody - &~ "\n" outdent ~[\ ] ~[]* - -blockBody ::= statement - > statement blockBody /ws => "sbb" - -statement ::= call - | ^"while" expr block /ws - -expr ::= ident - | call - | expr ^">" expr /ws - | num - -call ::= expr "()" /ws - -num ::= [0-9]++ - -ident ::= [a-z]++ &~ keyword -keyword ::= "if" | "then" | "else" | "while" - -w ::= " " | "\n" | "\r" -ws ::= w* - - -} +//testcase { +// +// input " +// +// +// while x>0 +// while y>0 +// foo() +// bar() +// +// while x>0 +// while y>0 +// foo() +// bar() +// +// +//"; +// output "smt:{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}}}}"; +// +//indent !::= ww +//outdent !::= " " outdent " " +// | " " (~[]*) "\n" +// +//any !::= ~[]* +//s ::= any "\n\n" ww statement ww "\n\n" any => smt +//ww !::= sp* +//ws !::= sp** +//sp ::= " " +// +//block ::= "\n" indent blockBody +// &~ "\n" outdent ~[\ ] ~[]* +// +//blockBody ::= statement +// > statement blockBody /ws => "sbb" +// +//statement ::= call +// | ^"while" expr block /ws +// +//expr ::= ident +// | call +// | expr ^">" expr /ws +// | num +// +//call ::= expr "()" /ws +// +//num ::= [0-9]++ +// +//ident ::= [a-z]++ &~ keyword +//keyword ::= "if" | "then" | "else" | "while" +// +//w ::= " " | "\n" | "\r" +//ws ::= w* +// +// +//}