From acfe58223b9a0f78e64a14a1ca5d5998626ee3fe Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 3 Jun 2006 04:51:36 -0400 Subject: [PATCH] unrolling forests without recursion darcs-hash:20060603085136-5007d-aa958aa60d5a0d884aa02a8de46c7307d5fb54bc.gz --- Makefile | 7 ++ src/edu/berkeley/sbp/Forest.java | 84 ++++++++++++++++++++++++ src/edu/berkeley/sbp/GSS.java | 30 ++++----- src/edu/berkeley/sbp/chr/CharInput.java | 5 +- src/edu/berkeley/sbp/misc/MetaGrammarTree.java | 10 +++ src/edu/berkeley/sbp/misc/RegressionTests.java | 21 +++++- tests/ifthen.tc | 5 +- tests/loop.tc | 17 ++--- 8 files changed, 147 insertions(+), 32 deletions(-) diff --git a/Makefile b/Makefile index 45bddeb..8cf95ac 100644 --- a/Makefile +++ b/Makefile @@ -53,6 +53,13 @@ loop: edu.berkeley.sbp.jar tests/testcase.g \ tests/loop.tc +pain: edu.berkeley.sbp.jar + $(java) -cp $< edu.berkeley.sbp.misc.RegressionTests \ + -graph \ + tests/meta.g \ + tests/testcase.g \ + tests/pain.tc + ifthen: edu.berkeley.sbp.jar $(java) -cp $< edu.berkeley.sbp.misc.RegressionTests \ tests/meta.g \ diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index bc31117..937a229 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -16,6 +16,42 @@ public abstract class Forest /*extends PrintableTree>*/ private final int idx = master_idx++; public int toInt() { return idx; } + public abstract void expand(TaskList tl, HashSet> ht); + public abstract void gather(TaskList tl, HashSet>[] ht, HashSet> target); + + public static class TaskList extends ArrayList { + public interface Task { + public void perform(); + } + public class ExpandTask implements Task { + private Forest f; + private HashSet hs; + public ExpandTask(Forest f, HashSet hs) { this.f = f; this.hs = hs; } + public void perform() { f.expand(TaskList.this, hs); } + } + public class GatherTask implements Task { + private Forest f; + private HashSet[] ht; + private HashSet hs; + public GatherTask(Forest f, HashSet>[] ht, HashSet> hs) { this.f = f; this.hs = hs; this.ht = ht;} + public void perform() { f.gather(TaskList.this, ht, hs); } + } + public void expand(Forest f, HashSet hs) { + add(new ExpandTask(f, hs)); + } + public void gather(Forest f, HashSet[] ht, HashSet hs) { + add(new GatherTask(f, ht, hs)); + } + public void run() { + while(true) { + if (isEmpty()) return; + Task task = get(size()-1); + remove(size()-1); + task.perform(); + } + } + } + /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */ public final Tree expand1() throws Ambiguous, ParseFailed { try { @@ -27,8 +63,15 @@ public abstract class Forest /*extends PrintableTree>*/ /** expand this forest into a set of trees */ public HashSet> expand(boolean toss) { + /* final HashSetTreeConsumer ret = new HashSetTreeConsumer(); visit(new TreeMaker2(toss, ret), null, null); + */ + TaskList tl = new TaskList(); + HashSet> ret = new HashSet>(); + tl.expand(this, ret); + tl.run(); + if (toss && ret.size() > 1) throw new InnerAmbiguous(this); return ret; } @@ -113,6 +156,41 @@ public abstract class Forest /*extends PrintableTree>*/ this.reduction = reduction; this.labels = labels; } + public void gather(TaskList tl, HashSet>[] ht, HashSet> target) { + gather(tl, ht, target, new Tree[ht.length], 0); + } + private void gather(TaskList tl, HashSet>[] ht, HashSet> target, Tree[] trees, int i) { + if (i==ht.length) { + target.add(new Tree(null, tag, trees)); + return; + } + for(Tree tree : ht[i]) { + if (unwrap && i==trees.length-1) { + // I think this is wrong + Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()]; + System.arraycopy(trees, 0, trees2, 0, trees.length-1); + for(int j=0; j(null, tag, trees2)); + } else { + trees[i] = tree; + gather(tl, ht, target, trees, i+1); + trees[i] = null; + } + } + } + public void expand(TaskList tl, HashSet> ht) { + if (singleton) { + tokens[0].expand(tl, ht); + return; + } + HashSet>[] children = new HashSet[tokens.length]; + tl.gather(this, children, ht); + for(int i=0; i>(); + tl.expand(tokens[i], children[i]); + } + } public void expand(final int i, final TreeMaker h) { if (singleton) { @@ -159,6 +237,12 @@ public abstract class Forest /*extends PrintableTree>*/ * viewed, it becomes immutable */ static class Ref extends Forest { + public void expand(TaskList tl, HashSet> ht) { + for (Forest f : hp) f.expand(tl, ht); + } + public void gather(TaskList tl, HashSet>[] ht, HashSet> target) { + throw new Error(); + } public HashSet parents = new HashSet(); public boolean contains(Forest f) { return hp.contains(f); diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 3df0c21..7af8b07 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -8,9 +8,11 @@ import java.util.*; import java.lang.reflect.*; /** implements Tomita's Graph Structured Stack */ -class GSS { +public class GSS { public static int count = 0; + public static int shifts = 0; + public static int reductions = 0; public GSS() { } @@ -18,6 +20,7 @@ class GSS { public int resets = 0; public int waits = 0; + // FIXME: right now, these are the performance bottleneck HashMapBag waiting = new HashMapBag(); HashMapBag performed = new HashMapBag(); HashMapBag lastperformed = new HashMapBag(); @@ -31,6 +34,7 @@ class GSS { public Iterator iterator() { return hash.iterator(); } public void invoke(State st, Forest result, Node n) { + shifts++; good |= next.newNode(n, result, st, false); } @@ -285,6 +289,7 @@ class GSS { public Iterable results() { return resultMap; } public FastSet parents() { return set; } public boolean merge(Node parent, Forest result) { + // FIXME: inefficient! for(Forest.Ref f : results()) { if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) { f.merge(result); @@ -312,6 +317,7 @@ class GSS { public void performEmptyReductions() { state.invokeReductions(token, this, null, null); } public final void invoke(Position r, Node n, Node n2) { + reductions++; if (n==null || n2==null || r.pos==0) { if (r.pos==0) { if (n==null) n = this; @@ -319,37 +325,31 @@ class GSS { } if (n==null) return; Forest[] holder = new Forest[r.pos]; - if (r.pos==0) n.finish(r, r.zero(), n.phase(), holder); - else n.reduce(r, r.pos-1, n.phase(), holder, null); + if (r.pos==0) n.finish(r, r.zero(), n.phase()); + else n.reduce(r, r.pos-1, n.phase(), null); } else { - Forest[] holder = new Forest[r.pos]; if (r.pos<=0) throw new Error("called wrong form of reduce()"); int pos = r.pos-1; - n.reduce(r, pos, n.phase(), holder, n2); + n.reduce(r, pos, n.phase(), n2); } } - public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only) { - holder = r.holder; + public void reduce(Position r, int pos, Phase target, Node only) { + Forest[] holder = r.holder; Forest old = holder[pos]; for(Forest result : results()) for(Node child : ((Forest.Ref)result).parents) { if (only != null && child!=only) continue; holder[pos] = result; - if (pos==0) { - //System.arraycopy(holder, 0, r.holder, 0, holder.length); - for(int i=0; i target, Forest[] holder) { + public void finish(Position r, Forest result, Phase target) { Parser.Table.State state0 = state.gotoSetNonTerminals.get(r.owner()); if (result==null) throw new Error(); if (state0!=null) diff --git a/src/edu/berkeley/sbp/chr/CharInput.java b/src/edu/berkeley/sbp/chr/CharInput.java index f86e85f..530f25c 100644 --- a/src/edu/berkeley/sbp/chr/CharInput.java +++ b/src/edu/berkeley/sbp/chr/CharInput.java @@ -13,7 +13,7 @@ public class CharInput extends Cartesian.Input { public CharInput(String s) { this(new StringReader(s)); } public CharInput(Reader r) { this(r, null); } - public CharInput(Reader r, String s) { this.r = r; } + public CharInput(Reader r, String s) { this.r = new BufferedReader(r); } public CharInput(InputStream i) { this(i, null); } public CharInput(InputStream i, String s) { this(new InputStreamReader(i), s); } @@ -26,7 +26,8 @@ public class CharInput extends Cartesian.Input { if (i==-1) { System.err.print("\r...done \r"); return null; } char c = (char)i; cr = c=='\n'; - System.err.print(" " + (count++) + "\r"); + if ((count++) % 100 == 0) + System.err.print(" " + count + "\r"); return c; } } diff --git a/src/edu/berkeley/sbp/misc/MetaGrammarTree.java b/src/edu/berkeley/sbp/misc/MetaGrammarTree.java index 6fe8332..b9b9b2b 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammarTree.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammarTree.java @@ -75,6 +75,11 @@ public class MetaGrammarTree { + + + + + // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED new edu.berkeley.sbp.Tree(null, "grammar", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "=", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "G", new edu.berkeley.sbp.Tree[] { }), new edu.berkeley.sbp.Tree(null, "r", new edu.berkeley.sbp.Tree[] { }), @@ -626,3 +631,8 @@ new edu.berkeley.sbp.Tree(null, "grammar", new edu.berkeley.sbp.Tree[] { new edu + + + + + diff --git a/src/edu/berkeley/sbp/misc/RegressionTests.java b/src/edu/berkeley/sbp/misc/RegressionTests.java index 196382c..6501727 100644 --- a/src/edu/berkeley/sbp/misc/RegressionTests.java +++ b/src/edu/berkeley/sbp/misc/RegressionTests.java @@ -62,7 +62,22 @@ public class RegressionTests { TestCase[] expanded = (TestCase[])new TestCaseBuilder().walk(r2.expand1()); System.err.println("executing..."); - for(TestCase tc : expanded) tc.execute(); + for(TestCase tc : expanded) { + tc.execute(); + /* + String st = "a"; + for(int i=0; i<12; i++) { + //System.out.println("length " + st.length()); + tc.input = st; + long nowy = System.currentTimeMillis(); + GSS.shifts = 0; + GSS.reductions = 0; + tc.execute(); + System.out.println("length " + st.length() + " => " + ((System.currentTimeMillis()-nowy)/1000.0) + " " + GSS.shifts + " " + GSS.reductions); + st = st+st; + } + */ + } } catch (Throwable t) { System.err.println("\n\nexception thrown, class == " + t.getClass().getName()); @@ -76,7 +91,7 @@ public class RegressionTests { public static class TestCase { private final boolean tib; private final boolean jav; - public final String input; + public /*final*/ String input; public final String[] output; public final Union grammar; public TestCase(String input, String[] output, Union grammar, boolean tib, boolean jav) throws IOException { @@ -105,6 +120,7 @@ public class RegressionTests { pfe = pf; } //ystem.out.println("res=="+res); + if (graph) { FileOutputStream fos = new FileOutputStream("out.dot"); PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); @@ -147,6 +163,7 @@ public class RegressionTests { return true; } System.out.println("\r\033[32mPASS\033[0m "); + return false; } } diff --git a/tests/ifthen.tc b/tests/ifthen.tc index dbb613d..6d23a52 100644 --- a/tests/ifthen.tc +++ b/tests/ifthen.tc @@ -4,10 +4,9 @@ testcase { s = Expr - Expr = IfThen - | IfThenElse:: IfThen "else" Expr /ws &~ IfThen + Expr = IfThen:: "if" "(" Expr ")" Expr /ws + | IfThenElse:: "if" "(" Expr ")" (x:: Expr "else" Expr /ws &~ Expr) /ws | Identifier:: [a-z]++ - IfThen = IfThen:: "if" "(" Expr ")" Expr /ws ws = [\n ]** diff --git a/tests/loop.tc b/tests/loop.tc index c7b6590..d29cb2f 100644 --- a/tests/loop.tc +++ b/tests/loop.tc @@ -1,23 +1,20 @@ testcase { - input "if (bar!) baz!;"; - output "IfThen:{id:{x:{b x:{a r}}} id:{x:{b x:{a z}}}}"; + input "if (bar) if (bop) baz"; + output ""; - s = Expr ";" + s = Expr Expr = IfThen | IfThenElse - | id:: id "!" - id = [a-z] | x:: [a-z] id + | id:: [a-z]++ IfThen = IfThen:: "if" "(" Expr ")" Expr /ws IfThenElse = IfThenElse:: "if" "(" Expr ")" - NotIfThenExpr - "else" - Expr + ((thenelse:: Expr + "else" + Expr /ws)) /ws /ws - NotIfThenExpr = (Expr & [a-z]+) - SpaceIfThen = (~[])*// !IfThen ws = [\n ]** } \ No newline at end of file -- 1.7.10.4