- Performance
- - Next target: TopologicalBag (make it wickedfast: preoptimize)
-
- Forest: keep() and valid() -- can we do this with states
rather than subtrees?
- hash Long->long: it's all bogus
- * huge performance improvement (try for more)
* pick back up cleaning up end of Parser.java (Reduction)
* some weird edge cases; check last regression test, 'make doc'
this.tag = tag;
this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
+ if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
this.creator = creator;
this.unwrap = unwrap;
this.singleton = singleton;
return needs <= -1 * creator.needs.size();
}
-
+ private boolean rep = false;
public String toString() {
- StringBuffer ret = new StringBuffer();
- for(int i=0; i<tokens.length; i++) {
- String q = tokens[i]==null ? "null" : tokens[i].toString();
- if (q.length() > 0) {
- ret.append(q);
- ret.append(" ");
+ if (rep) return "***";
+ try {
+ rep = true;
+ StringBuffer ret = new StringBuffer();
+ for(int i=0; i<tokens.length; i++) {
+ String q = tokens[i]==null ? "null" : tokens[i].toString();
+ if (q.length() > 0) {
+ ret.append(q);
+ ret.append(" ");
+ }
}
+ String tail = ret.toString().trim();
+ String head = (tag!=null && !tag.toString().equals("")) ? (tail.length() > 0 ? tag+":" : tag+"") : "";
+ if (tail.length() > 0) tail = "{" + tail + "}";
+ return head + tail;
+ } finally {
+ rep = false;
}
- String tail = ret.toString().trim();
- String head = (tag!=null && !tag.toString().equals("")) ? (tail.length() > 0 ? tag+":" : tag+"") : "";
- if (tail.length() > 0) tail = "{" + tail + "}";
- return head + tail;
}
}
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);
+ 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); }
FastSet<Body> nh = new FastSet<Body>();
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 (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)
}
}
hp = null;
- return res = new MultiForest(nh, valid);
+ res = new MultiForest(nh, valid);
+ return res;
}
}
* @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 void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) {
- Node p = hash.get(code(state, start));
- if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction, start);
- else newNode3(parent, pending, state, fromEmptyReduction, start);
+ public void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) {
+ Node p = hash.get(code(state, parent==null?null:parent.phase()));
+ if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction);
+ else newNode3(parent, pending, state, fromEmptyReduction);
}
- private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) {
+ private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) {
p.holder.merge(pending);
if (p.parents().contains(parent)) return;
- p.addParent(parent, fromEmptyReduction);
+ p.parents().add(parent);
+ if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
}
- private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) {
+ private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) {
do {
if (token != null && state.canShift(token)) break;
if (state.isAccepting()) break;
if (token==null) break;
- int count = 0;
- Parser.Table.Reduction r = null;
if (!state.canReduce(token)) return;
//if (count > 1) break;
//if (r.numPop == 0) break;
//return;
} while(false);
- Node n = new Node(parent, pending, state, start); // ALLOC
+ Node n = new Node(parent, pending, state); // ALLOC
n.queueEmptyReductions();
if (!fromEmptyReduction) n.queueReductions(parent);
}
}
public void invoke(Parser.Table.State st, Forest result, Node n) {
- next.newNode(n, result, st, true, this);
+ next.newNode(n, result, st, true);
}
private Phase next = null;
/** a node in the GSS */
public final class Node extends FastSet<Node> implements Invokable<Parser.Table.Reduction, Node, Node> {
- public void addParent(Node parent, boolean fromEmptyReduction) {
- if (parents().contains(parent)) return;
- parents().add(parent);
- if (this!=parent && !fromEmptyReduction) queueReductions(parent);
- }
-
private Forest.Ref holder = null;
private boolean allqueued = false;
if (allqueued) return;
allqueued = true;
int where = parents().size();
- /*
- for(Parser.Table.Reduction r : state.getReductions(token))
- if (r.numPop > 0)
- r.reduce(this);
- */
state.invokeReductions(token, this, this, null);
}
public void queueReductions(Node n2) {
if (!allqueued) { queueReductions(); return; }
- /*
- for(Parser.Table.Reduction r : state.getReductions(token))
- if (r.numPop > 0)
- r.reduce(this, n2);
- */
state.invokeReductions(token, this, this, n2);
}
return;
}
if (r.numPop==0) return;
- if (n2==null) {
- r.reduce(n);
- } else {
- r.reduce(n, n2);
- }
+ if (n2==null) r.reduce(n);
+ else r.reduce(n, n2);
}
public void queueEmptyReductions() {
if (!reducing) return;
- /*
- for(Parser.Table.Reduction r : state.getReductions(token))
- if (r.numPop==0)
- r.reduce(this);
- */
state.invokeReductions(token, this, null, null);
}
- private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) {
+ private Node(Node parent, Forest pending, Parser.Table.State state) {
this.state = state;
+ Phase start = parent==null ? null : parent.phase();
if (pending != null) this.holder().merge(pending);
if (parent != null) parents().add(parent);
if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
/** 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);
+ return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1));
}
}
GSS gss = new GSS();
Token.Location loc = input.getLocation();
GSS.Phase current = gss.new Phase(null, input.next(), loc);
- current.newNode(null, null, pt.start, true, null);
+ current.newNode(null, null, pt.start, true);
for(;;) {
loc = input.getLocation();
GSS.Phase next = gss.new Phase(current, input.next(), loc);
if (p.element() != null && p.element() instanceof Atom)
state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element())));
}
+ for(State state : all_states.values()) {
+ state.oreductions = state.reductions.optimize();
+ state.oshifts = state.shifts.optimize();
+ }
}
/** a single state in the LR table and the transitions possible from it */
private TopologicalBag<Token,State> shifts = new TopologicalBag<Token,State>();
private boolean accept = false;
- private VisitableMap<Token,State> oshifts = shifts;
- //private TopologicalBag<Token,Reduction> reductions2 = reductions;
+ private VisitableMap<Token,State> oshifts = null;
+ private VisitableMap<Token,Reduction> oreductions = null;
// Interface Methods //////////////////////////////////////////////////////////////////////////////
public boolean isAccepting() { return accept; }
- public boolean canShift(Token t) { return shifts.contains(t); }
- public boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : reductions.has(t); }
+ public boolean canShift(Token t) { return oshifts.contains(t); }
+ public boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); }
public Iterator<Position> iterator() { return hs.iterator(); }
}
public <B,C> void invokeReductions(Token t, Invokable<Reduction,B,C> irbc, B b, C c) {
if (t==null) for(Reduction r : eofReductions) irbc.invoke(r, b, c);
- else reductions.invoke(t, irbc, b, c);
+ else oreductions.invoke(t, irbc, b, c);
}
// Constructor //////////////////////////////////////////////////////////////////////////////
public void reduce(GSS.Phase.Node parent, GSS.Phase.Node onlychild) {
if (numPop<=0) throw new Error("called wrong form of reduce()");
int pos = numPop-1;
+ Forest old = holder[pos];
holder[pos] = parent.pending();
if (pos==0) {
System.arraycopy(holder, 0, position.holder, 0, holder.length);
} else {
reduce(onlychild, pos-1, parent.phase());
}
+ holder[pos] = old;
}
// FIXME: this could be more elegant and/or cleaner and/or somewhere else
private void reduce(GSS.Phase.Node parent, int pos, GSS.Phase target) {
+ Forest old = holder[pos];
holder[pos] = parent.pending();
if (pos==0) {
System.arraycopy(holder, 0, position.holder, 0, holder.length);
+ for(int i=0; i<position.pos; i++) if (position.holder[i]==null) throw new Error("realbad");
Forest rex = position.rewrite(target.getLocation());
for(GSS.Phase.Node child : parent.parents()) finish(child, rex, target);
} else {
for(GSS.Phase.Node child : parent.parents()) reduce(child, pos-1, target);
}
+ holder[pos] = old;
}
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, parent.phase());
+ target.newNode(parent, result, state, numPop<=0);
}
}
}
final <T> Forest<T> rewrite(Token.Location loc) {
if (this==firstp() && eps) return epsilonForm;
eps = true;
- for(int i=pos; i<elements.length; i++) if (holder[i]==null) holder[i] = elements[i].epsilonForm();
+ 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();
+ if (holder[i]==null) throw new Error("bad " + i);
+ }
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; }
public Unwrap(Element[] e, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.drops = null; }
public Unwrap(Element[] e, boolean[] drops, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.drops = drops; }
public <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args) {
+ for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
if (drops==null) return Forest.create(loc, null, args, this, true, false);
int count = 0;
for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
}
public void add(T t, boolean check) {
//if (check) for(Object o : this) if (o.equals(t)) return;
- if (check) for(Object o : this) if (o==t) return;
+ if (check) {
+ if (only==t) return;
+ if (array != null)
+ for(int i=0; i<size; i++)
+ if (array[i]==t) return;
+ }
add(t);
}
public void add(T t) {
return ret;
}
}
+
+ public VisitableMap<K,V> optimize() {
+ ArrayList<Long> min_ = new ArrayList<Long>();
+ ArrayList<Long> max_ = new ArrayList<Long>();
+ ArrayList<Object[]> v_ = new ArrayList<Object[]>();
+ for(Topology<K> t : h.keySet()) {
+ ArrayList<V> al = new ArrayList<V>();
+ for(V vv : h.get(t)) al.add(vv);
+ Object[] vs = new Object[al.size()];
+ al.toArray(vs);
+ IntegerTopology it = (IntegerTopology)t;
+ for(Range r : it.getRanges()) {
+ min_.add(r.isMinNegInf() ? Long.MIN_VALUE : r.getMin());
+ max_.add(r.isMaxPosInf() ? Long.MAX_VALUE : r.getMax());
+ v_.add(vs);
+ }
+ }
+ final int size = v_.size();
+ final long[] min = new long[size]; for(int i=0; i<min.length; i++) min[i]=min_.get(i);
+ final long[] max = new long[size]; for(int i=0; i<max.length; i++) max[i]=max_.get(i);
+ final Object[][] v = new Object[size][]; v_.toArray(v);
+ return new VisitableMap<K,V>() {
+ public boolean contains(K k) {
+ IntegerTopology.IntegerMappable im = (IntegerTopology.IntegerMappable)k;
+ int asint = im.toInt();
+ for(int i=0; i<size; i++)
+ if (min[i] <= asint && max[i] >= asint && v[i].length > 0)
+ return true;
+ return false;
+ }
+ public <B,C> void invoke(K k, Invokable<V,B,C> ivbc, B b, C c) {
+ IntegerTopology.IntegerMappable im = (IntegerTopology.IntegerMappable)k;
+ int asint = im.toInt();
+ for(int i=0; i<size; i++) {
+ if (min[i] <= asint && max[i] >= asint) {
+ Object[] arr = v[i];
+ for(int j=0; j<arr.length; j++)
+ ivbc.invoke((V)arr[j], b, c);
+ }
+ }
+ }
+ };
+ }
+
private final Iterable<V> emptyIterator = new EmptyIterator<V>();
}
comment = my homepage is at
== Introduction ==
- this is the body adam@megacz.com text
+ this is the body adam@megacz.com
+
- the following paragraph demonstrates verbatim stuff, as well as a
- footnote ((like this)) because they are coool
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*
+
+
+}
kv ::= word "=" text /ws => kv1
-num !::= [0-9]++ => "stringify"
Paragraph ::= { "\"\"" ws text } => "blockquote"
> { "*" " " ws text } => "ul"
> { "#" " " ws text } => "ol"
- > { num " " ws text } => "ol"
+ > { num " " ws text => "ol" }
> { "---" "-"* } => "hr"
> { text } => "p"
port ::= [0-9]+
domain ::= part +/ "."
-part ::= [a-zA-Z0-9\-]++ => "stringify" // interesting use of boolean grammars
+part ::= [A-Za-z0-9\-]++ => "stringify"
// &~ ([\-0-9] ~[]* | ~[]* [\-0-9])
email ::= username "@" host => email
-host ::= [0-9]+ "." [0-9]+ "." [0-9]+ "." [0-9]+ => "ip"
- | domain
+host ::= domain
+ | [0-9]+ "." [0-9]+ "." [0-9]+ "." [0-9]+ => "ip"
// Chars ///////////////////////////////////////////////////////////////
alpha ::= [a-zA-Z]
-num ::= [0-9]
+num !::= [0-9]++ => "stringify"
+//num ::= [0-9]
alphanum ::= [a-zA-Z0-9]
sym ::= ~[a-zA-Z0-9\ \r\n]
projects / sbp.git / commitdiff