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 \
private final int idx = master_idx++;
public int toInt() { return idx; }
+ public abstract void expand(TaskList tl, HashSet<Tree<T>> ht);
+ public abstract void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target);
+
+ public static class TaskList extends ArrayList<TaskList.Task> {
+ 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<Tree<?>>[] ht, HashSet<Tree<?>> 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<T> expand1() throws Ambiguous, ParseFailed {
try {
/** expand this forest into a set of trees */
public HashSet<Tree<T>> expand(boolean toss) {
+ /*
final HashSetTreeConsumer<T> ret = new HashSetTreeConsumer<T>();
visit(new TreeMaker2<T>(toss, ret), null, null);
+ */
+ TaskList tl = new TaskList();
+ HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
+ tl.expand(this, ret);
+ tl.run();
+
if (toss && ret.size() > 1) throw new InnerAmbiguous(this);
return ret;
}
this.reduction = reduction;
this.labels = labels;
}
+ public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
+ gather(tl, ht, target, new Tree[ht.length], 0);
+ }
+ private void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target, Tree[] trees, int i) {
+ if (i==ht.length) {
+ target.add(new Tree<T>(null, tag, trees));
+ return;
+ }
+ for(Tree<T> 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<tree.numChildren(); j++)
+ trees2[trees.length-1+j] = tree.child(j);
+ target.add(new Tree<T>(null, tag, trees2));
+ } else {
+ trees[i] = tree;
+ gather(tl, ht, target, trees, i+1);
+ trees[i] = null;
+ }
+ }
+ }
+ public void expand(TaskList tl, HashSet<Tree<T>> ht) {
+ if (singleton) {
+ tokens[0].expand(tl, ht);
+ return;
+ }
+ HashSet<Tree<T>>[] children = new HashSet[tokens.length];
+ tl.gather(this, children, ht);
+ for(int i=0; i<children.length; i++) {
+ children[i] = new HashSet<Tree<T>>();
+ tl.expand(tokens[i], children[i]);
+ }
+ }
public void expand(final int i, final TreeMaker<T> h) {
if (singleton) {
* viewed, it becomes immutable
*/
static class Ref<T> extends Forest<T> {
+ public void expand(TaskList tl, HashSet<Tree<T>> ht) {
+ for (Forest<T> f : hp) f.expand(tl, ht);
+ }
+ public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
+ throw new Error();
+ }
public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
public boolean contains(Forest f) {
return hp.contains(f);
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() { }
public int resets = 0;
public int waits = 0;
+ // FIXME: right now, these are the performance bottleneck
HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
HashMapBag<Integer,Sequence> lastperformed = new HashMapBag<Integer,Sequence>();
public Iterator<Phase.Node> iterator() { return hash.iterator(); }
public void invoke(State st, Forest result, Node n) {
+ shifts++;
good |= next.newNode(n, result, st, false);
}
public Iterable<Forest.Ref> results() { return resultMap; }
public FastSet<Node> 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);
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;
}
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<r.pos; i++) if (r.holder[i]==null) throw new Error("realbad");
- child.finish(r, r.rewrite(phase().getLocation()), target, holder);
- } else {
- child.reduce(r, pos-1, target, holder, null);
- }
+ if (pos==0) child.finish(r, r.rewrite(phase().getLocation()), target);
+ else child.reduce(r, pos-1, target, null);
}
holder[pos] = old;
}
- public void finish(Position r, Forest result, Phase<Tok> target, Forest[] holder) {
+ public void finish(Position r, Forest result, Phase<Tok> target) {
Parser.Table<Tok>.State<Tok> state0 = state.gotoSetNonTerminals.get(r.owner());
if (result==null) throw new Error();
if (state0!=null)
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); }
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;
}
}
+
+
+
+
+
// 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[] { }),
+
+
+
+
+
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());
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 {
pfe = pf;
}
//ystem.out.println("res=="+res);
+
if (graph) {
FileOutputStream fos = new FileOutputStream("out.dot");
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
return true;
}
System.out.println("\r\033[32mPASS\033[0m ");
+
return false;
}
}
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 ]**
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
projects / sbp.git / commitdiff