/** 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);
public InnerAmbiguous(Forest<?> f) { this.f = f; }
}
- static interface TreeConsumer<T> {
- public void addTree(Tree<T> t);
- }
- static class HashSetTreeConsumer<T> extends HashSet<Tree<T>> implements TreeConsumer<T> {
- public void addTree(Tree<T> t) {
- super.add(t);
- }
- }
-
static <T> Forest<T> singleton(Input.Location loc, Position p) {
- return create(loc, null, new Forest[] { }, new Object[0], false, true, p); }
- static <T> Forest<T> singleton(Input.Location loc, Forest<T> body, Position p) {
- //return create(loc, null, new Forest[] { body }, false, true, p);
- return body;
- }
- static <T> Forest<T> leaf(Input.Location loc, T tag, Position p) { return create(loc, tag, null, null, false, false, p); }
- public static <T> Forest<T> create(Input.Location loc, T tag, Forest<T>[] tokens, Object[] labels, boolean unwrap, boolean singleton, Position p) {
- return new MyBody<T>(loc, tag, tokens, labels, unwrap, singleton, p);
+ return create(loc, null, new Forest[] { }, false, true, p); }
+ static <T> Forest<T> singleton(Input.Location loc, Forest<T> body, Position p) { return body; }
+ static <T> Forest<T> leaf(Input.Location loc, T tag, Position p) { return create(loc, tag, null, false, false, p); }
+ public static <T> Forest<T> create(Input.Location loc, T tag, Forest<T>[] tokens, boolean unwrap, boolean singleton, Position p) {
+ return new MyBody<T>(loc, tag, tokens, unwrap, singleton, p);
}
// Body //////////////////////////////////////////////////////////////////////////////
- protected static interface Body<T> extends GraphViz.ToGraphViz {
- void expand(int i, TreeMaker<T> h);
+ public /*protected*/ static interface Body<T> extends GraphViz.ToGraphViz {
+ void expand(int i, TreeBuilder<T> h);
}
public abstract void edges(GraphViz.Node n);
public boolean ambiguous() { return false; }
- protected static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
+ public /*protected*/ static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
public boolean isTransparent() { return false; }
public boolean isHidden() { return false; }
if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
tokens[i].edges(n);
} else {
- n.edge(tokens[i], labels==null?null:labels[i]);
+ n.edge(tokens[i], null);
}
}
}
private final Input.Location location;
private final T tag;
private final Forest<T>[] tokens;
- private final Object[] labels;
private final boolean unwrap;
private final boolean singleton;
private final Sequence.Position reduction;
- private MyBody(Input.Location loc, T tag, Forest<T>[] tokens, Object[] labels, boolean unwrap, boolean singleton, Position reduction) {
+ private MyBody(Input.Location loc, T tag, Forest<T>[] tokens, boolean unwrap, boolean singleton, Position reduction) {
this.location = loc;
this.tag = tag;
this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
this.unwrap = unwrap;
this.singleton = singleton;
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);
}
}
- public void expand(final int i, final TreeMaker<T> h) {
+ public void expand(final int i, final TreeBuilder<T> h) {
if (singleton) {
tokens[0].visit(h, null, i);
return;
tokens[i].visit(h, null, 0);
} else {
- tokens[i].visit(new TreeMaker<T>(h.toss) {
+ tokens[i].visit(new TreeBuilder<T>(h.toss) {
public void start(T head, Input.Location loc) { }
- public void addTree(Tree<T> t, Object label) { toks.add(t); labs.add(label); }
+ public void addTree(Tree<T> t) { toks.add(t); }
public void finish(T head, Input.Location loc) {
int old = h.toks.size();
- h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint), labs.toArray(string_hint)), labels==null?null:labels[i]);
+ h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint)));
expand(i+1, h);
while(h.toks.size() > old) h.toks.remove(h.toks.size()-1);
- while(h.labs.size() > old) h.labs.remove(h.labs.size()-1);
}
}, null, null);
}
}
public abstract <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c);
- private static class TreeMaker2<T> extends TreeMaker<T> {
- private TreeConsumer<T> tc;
- public TreeMaker2(boolean toss, TreeConsumer<T> tc) { super(toss); this.tc = tc; }
- public void finish(T head, Input.Location loc) { tc.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint), labs.toArray(string_hint)));; }
- public void start(T head, Input.Location loc) { }
- public void addTree(Tree<T> t, Object label) { toks.add(t); labs.add(label); }
- }
- private static abstract class TreeMaker<T> implements Invokable<Forest.Body<T>,Boolean,Integer>/*, TreeConsumer<T>*/ {
- public ArrayList<Tree<T>> toks = new ArrayList<Tree<T>>();
- public ArrayList<Object> labs = new ArrayList<Object>();
- private boolean toss;
- protected T head;
- public TreeMaker(boolean toss) { this.toss = toss; }
- public abstract void start(T head, Input.Location loc);
- public abstract void finish(T head, Input.Location loc);
- public abstract void addTree(Tree<T> t, Object label);
- public void invoke(Forest.Body<T> bod, Boolean o, Integer i) {
- if (i==null) {
- ArrayList<Tree<T>> toks = this.toks;
- this.toks = new ArrayList<Tree<T>>();
- ArrayList<Object> labs = this.labs;
- this.labs = new ArrayList<Object>();
- bod.expand(0, this);
- this.toks = toks;
- this.labs = labs;
- } else {
- bod.expand(i, this);
- }
- }
- }
// Statics //////////////////////////////////////////////////////////////////////////////
* @param drops only elements of <tt>e</tt> whose corresponding <tt>boolean</tt> in <tt>drops</tt>
* is <i>false</i> will be included in the output tree
**/
- public static Sequence rewritingSequence(Object tag, Element[] e, Object[] labs, boolean[] drops) {
- return new RewritingSequence(tag, e, labs, drops); }
+ public static Sequence rewritingSequence(Object tag, Element[] e, boolean[] drops) {
+ return new RewritingSequence(tag, e, drops); }
////////////////////////////////////////////////////////////////////////////////
Sequence _clone() { return new Unwrap(elements, drops); }
public <T> Forest<T> postReduce(Input.Location loc, Forest<T>[] args, Position p) {
for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
- if (drops==null) return Forest.create(loc, (T)tag, args, new Object[args.length], true, false, p);
+ if (drops==null) return Forest.create(loc, (T)tag, args, true, false, p);
int count = 0;
for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
Forest<T>[] args2 = new Forest[count];
int j = 0;
for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
- return Forest.create(loc, (T)tag, args2, new Object[args.length], true, false, p);
+ return Forest.create(loc, (T)tag, args2, true, false, p);
}
}
static class RewritingSequence extends Sequence {
/*private*/public final Object tag;
private final boolean[] drops;
- private final Object[] labs;
private int count = 0;
- Sequence _clone() { return new RewritingSequence(tag, elements, labs, drops); }
- public RewritingSequence(Object tag, Element[] e, Object[] labs) { this(tag, e, labs, null); }
- public RewritingSequence(Object tag, Element[] e, Object[] labs, boolean[] drops) {
+ Sequence _clone() { return new RewritingSequence(tag, elements, drops); }
+ public RewritingSequence(Object tag, Element[] e) { this(tag, e, null); }
+ public RewritingSequence(Object tag, Element[] e, boolean[] drops) {
super(e);
this.tag = tag;
this.drops = drops == null ? new boolean[e.length] : drops;
for(int i=0; i<this.drops.length; i++) if (!this.drops[i]) count++;
- this.labs = labs;
}
public <T> Forest<T> postReduce(Input.Location loc, Forest<T>[] args, Position p) {
Forest<T>[] args2 = new Forest[count];
- Object[] labs2 = new Object[count];
int j = 0;
- for(int i=0; i<args.length; i++) if (!drops[i]) { labs2[j] = labs==null?null:labs[i]; args2[j++] = args[i]; }
+ for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
//System.out.println("reduce \""+tag+"\"");
- return Forest.create(loc, (T)tag, args2, labs2, false, false, p);
+ return Forest.create(loc, (T)tag, args2, false, false, p);
}
public StringBuffer toString(StringBuffer sb, boolean spacing) {
int len = sb.length();
final T head;
Tree<T>[] children;
- Object[] labels;
final Input.Location location;
public T head() { return head; }
public Iterable<Tree<T>> children() { return new ArrayIterator(children); }
public Iterator<Tree<T>> iterator() { return new ArrayIterator(children); }
public Tree<T> child(int i) { return children[i]; }
- public Object label(int i) { return labels[i]; }
public Input.Location getLocation() { return location; }
public Tree(Input.Location loc, T head) { this(loc, head, null); }
- public Tree(Input.Location loc, T head, Tree<T>[] children) { this(loc, head, children, null); }
- public Tree(Input.Location loc, T head, Tree<T>[] children, Object[] labels) {
+ public Tree(Input.Location loc, T head, Tree<T>[] children) {
this.location = loc;
this.head = head;
Tree<T>[] children2 = children==null ? new Tree[0] : new Tree[children.length];
if (children != null) System.arraycopy(children, 0, children2, 0, children.length);
this.children = children2;
-
- Object[] labels2 = labels==null ? new Object[0] : new Object[labels.length];
- if (labels != null) System.arraycopy(labels, 0, labels2, 0, labels.length);
- this.labels = labels2;
}
protected String headToString() { return head==null?null:head.toString(); }
return (T[])ret.toArray(new Object[0]);
}
}
+
}
public CharParser(Union u) { super(u, new CharTopology()); }
public Forest<String> shiftToken(Character ct, Location loc) {
- return Forest.create(loc, ct.toString(), null, null, false, false, null);
+ return Forest.create(loc, ct.toString(), null, false, false, null);
}
}
public Object repeatTag() { return new Tree.ArrayBuildingTreeFunctor<Object>(); }
- public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
- MetaGrammar.Production p = new MetaGrammar.Production(tag, nonTerminalName, els, labels, drops);
+ public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
+ MetaGrammar.Production p = new MetaGrammar.Production(tag, nonTerminalName, els, drops);
for(Method m : _allMethods)
if (new MetaGrammar.Target(m).isCompatible(p))
return new MetaGrammar.Target(m).makeSequence(p);
return new MetaGrammar.Target(c).makeSequence(p);
return null;
}
- public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
- MetaGrammar.Production p = new MetaGrammar.Production(tag, nonTerminalName, els, labels, drops);
- Sequence ret = tryResolveTag(tag, nonTerminalName, els, labels, drops);
+ public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
+ MetaGrammar.Production p = new MetaGrammar.Production(tag, nonTerminalName, els, drops);
+ Sequence ret = tryResolveTag(tag, nonTerminalName, els, drops);
if (ret != null) return ret;
String message = "could not find a Java method/class/ctor matching tag \""+tag+
"\", nonterminal \""+nonTerminalName+"\" with " + els.length + " arguments";
if (harsh) {
throw new RuntimeException(message);
} else {
- return Sequence.rewritingSequence(tag, els, labels, drops);
+ return Sequence.rewritingSequence(tag, els, drops);
}
}
public class GrammarBindingResolver {
public Object repeatTag() { return null; }
- public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
+ public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
return null; }
- public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
+ public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
return null; }
}
public static class Production {
public String tag;
public String nonTerminal;
- public Object[] labels;
public boolean[] drops;
public Element[] elements;
public int count = 0;
- public Production(String tag, String nonTerminal, Element[] elements, Object[] labels, boolean[] drops) {
+ public Production(String tag, String nonTerminal, Element[] elements, boolean[] drops) {
this.tag = tag;
this.elements = elements;
this.nonTerminal = nonTerminal;
- this.labels = labels;
this.drops = drops;
for(int i=0; i<drops.length; i++)
if (!drops[i])
}
public Sequence makeSequence(Production p) {
return Sequence.rewritingSequence(new TargetReducer(buildSequence(p), _bindable, isRaw()),
- p.elements, p.labels, p.drops);
+ p.elements, p.drops);
}
}
public Sequence build0(Context cx, boolean lame, NonTerminalNode cnt) {
boolean dropAll = lame;
if (tag!=null && "()".equals(tag)) dropAll = true;
- Object[] labels = new Object[elements.length];
boolean[] drops = new boolean[elements.length];
Element[] els = new Element[elements.length];
for(int i=0; i<elements.length; i++) {
- labels[i] = elements[i].getLabel();
drops[i] = elements[i].drop();
els[i] = elements[i].build(cx, cnt);
if (elements[i].getOwnerTag() != null)
Sequence ret = null;
if (dropAll) ret = Sequence.drop(els, false);
else {
- ret = cx.rm.tryResolveTag(tag, cnt==null?null:cnt.name, els, labels, drops);
+ ret = cx.rm.tryResolveTag(tag, cnt==null?null:cnt.name, els, drops);
if (ret == null) {
int idx = -1;
for(int i=0; i<els.length; i++)
public class TaggingGrammarBindingResolver extends GrammarBindingResolver {
public Object repeatTag() { return null; }
- public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
+ public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
if (tag==null) return null;
- return Sequence.rewritingSequence(tag, els, labels, drops);
+ return Sequence.rewritingSequence(tag, els, drops);
}
- public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
- return Sequence.rewritingSequence(tag, els, labels, drops);
+ public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, boolean[] drops) {
+ return Sequence.rewritingSequence(tag, els, drops);
}
}
--- /dev/null
+package edu.berkeley.sbp.util;
+import edu.berkeley.sbp.*;
+import java.util.*;
+
+public abstract class TreeBuilder<T> implements Invokable<Forest.Body<T>,Boolean,Integer> {
+ public ArrayList<Tree<T>> toks = new ArrayList<Tree<T>>();
+ public boolean toss;
+ protected T head;
+ public TreeBuilder(boolean toss) { this.toss = toss; }
+ public abstract void start(T head, Input.Location loc);
+ public abstract void finish(T head, Input.Location loc);
+ public abstract void addTree(Tree<T> t);
+ public void invoke(Forest.Body<T> bod, Boolean o, Integer i) {
+ if (i==null) {
+ ArrayList<Tree<T>> toks = this.toks;
+ this.toks = new ArrayList<Tree<T>>();
+ bod.expand(0, this);
+ this.toks = toks;
+ } else {
+ bod.expand(i, this);
+ }
+ }
+}