_____________________________________________________________________________
Immediately
+ - Repeat, Sequence, Tree
+ - simplify Forest (considerably)
+
- decent/better error messages
- fix the location stuff, it's broken
- copyright notices
-
- documentation
______________________________________________________________________________
import java.lang.reflect.*;
/** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */
-public abstract class Forest<T> {
+public abstract class Forest<T> extends PrintableTree<Forest.Body<T>> implements Iterable<Forest.Body<T>> {
/** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
public final Tree<T> expand1() throws Ambiguous, ParseFailed {
// Body //////////////////////////////////////////////////////////////////////////////
- protected static class Body<T> {
+ protected static class Body<T> extends PrintableTree<Forest<T>> implements Iterable<Forest<T>> {
private final Input.Location location;
private final T tag;
private HashSet<Tree<T>> expand(boolean toss, ArrayList<Tree<T>> toks, int i, HashSet<Tree<T>> h) {
if (singleton) {
- for(Body<T> b : (IterableForest<T>)tokens[0]) b.expand(toss, toks, i, h);
+ for(Body<T> b : tokens[0]) b.expand(toss, toks, i, h);
} else if (i==tokens.length) {
h.add(new Tree<T>(null, tag, toks.toArray(tree_hint)));
} else if (unwrap && i==tokens.length-1) {
if (tokens[i] != null)
- for(Body b : (IterableForest<T>)tokens[i])
+ for(Body b : tokens[i])
b.expand(toss, toks, 0, h);
} else {
void addTo(FastSet<Body> h) {
if (!singleton) h.add(this, true);
- else for(Body b : (IterableForest<T>)tokens[0]) b.addTo(h);
+ else for(Body b : tokens[0]) b.addTo(h);
}
- 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(" ");
- }
- }
- 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;
- }
+ protected String headToString() { return null; }
+ protected String headToJava() { return null; }
+ protected String left() { return "{"; }
+ protected String right() { return "}"; }
+ protected boolean ignoreSingleton() { return false; }
+ public Iterator<Forest<T>> iterator() { return new ArrayIterator<Forest<T>>(tokens); }
}
// Ref //////////////////////////////////////////////////////////////////////////////
- private static abstract class IterableForest<T> extends Forest<T> implements Iterable<Forest.Body<T>> {
- public abstract Iterator<Forest.Body<T>> iterator();
- }
-
/**
* This class represents a partially complete collection of
* forests to be viewed as a forest at some later date; once
* viewed, it becomes immutable
*/
- static class Ref<T> extends IterableForest<T> {
+ static class Ref<T> extends Forest<T> {
private FastSet<Forest> hp = new FastSet<Forest>();
private Forest res = null;
public Ref() { }
if (p==null) throw new Error();
if (p!=this) hp.add(p, true);
}
- public Iterator<Body<T>> iterator() { return ((IterableForest<T>)resolve()).iterator(); }
+ public Iterator<Body<T>> iterator() { return ((Forest<T>)resolve()).iterator(); }
public HashSet<Tree<T>> expand(boolean toss) { return resolve().expand(toss); }
- public String toString() { return resolve().toString(); }
public Forest resolve() {
if (hp==null) return res;
FastSet<Body> nh = new FastSet<Body>();
for(Forest<?> p : hp)
- for(Body<?> b : (IterableForest<?>)p)
+ for(Body<?> b : (Forest<?>)p)
b.addTo(nh);
res = new MultiForest(nh);
hp = null;
// Implementations //////////////////////////////////////////////////////////////////////////////
- private static class MultiForest<T> extends IterableForest<T> {
+ private static class MultiForest<T> extends Forest<T> {
private final FastSet<Body<T>> results;
private MultiForest(FastSet<Body<T>> results) { this.results = results; }
public MultiForest(Input.Location loc, T tag, Forest<T>[] tokens, boolean unwrap, boolean singleton) {
this.results = new FastSet<Body<T>>(new Body(loc, tag, tokens, unwrap, singleton));
}
public Iterator<Body<T>> iterator() { return results.iterator(); }
-
public HashSet<Tree<T>> expand(boolean toss) {
HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
for(Body<T> b : results)
if (toss && ret.size() > 1) throw new Ambiguous(this);
return ret;
}
-
- // Display //////////////////////////////////////////////////////////////////////////////
-
- private String toString = null;
- public String toString() {
- if (toString != null) return toString;
- StringBuffer ret = new StringBuffer();
- if (results.size()==1) {
- for(Forest.Body<T> r : results)
- ret.append(r);
- return toString = ret.toString();
- }
- ret.append("<?");
- boolean first = true;
- for(Forest.Body<T> r : results) {
- if (!first) ret.append(' ');
- first = false;
- ret.append(r);
- }
- ret.append("?>");
- return toString = ret.toString();
- }
}
// Statics //////////////////////////////////////////////////////////////////////////////
private static Tree[] tree_hint = new Tree[0];
private static final Forest[] emptyForestArray = new Forest[0];
+
+ protected String headToString() { return null; }
+ protected String headToJava() { return null; }
+ protected String left() { return "<?"; }
+ protected String right() { return "?>"; }
+ protected boolean ignoreSingleton() { return true; }
}
// Static Constructors //////////////////////////////////////////////////////////////////////////////
+ public abstract Sequence and(Sequence s);
+ public abstract Sequence not(Sequence s);
+
+ private void needs(Sequence s) { s.needed.add(this); needs.add(s); }
+ private void hates(Sequence s) { s.hated.add(this); hates.add(s); }
+
/** the empty sequence (matches the empty string) */
public static final Sequence empty = new Sequence.Constant.Empty();
static class Constant extends Sequence {
private final Object result;
public Constant(Element[] e, Object result, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.result = result; }
+ public Sequence and(Sequence s) { Sequence ret = new Constant(elements, result, needs, hates); ret.needs(s); return ret; }
+ public Sequence not(Sequence s) { Sequence ret = new Constant(elements, result, needs, hates); ret.hates(s); return ret; }
public <T> Forest<T> postReduce(Input.Location loc, Forest<T>[] args) {
return (Forest<T>)Forest.leaf(loc, result);
}
public Singleton(Element e, HashSet<Sequence> and, HashSet<Sequence> not) { this(new Element[] { e }, 0, and, not); }
public Singleton(Element[] e, int idx, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.idx = idx; }
public <T> Forest<T> postReduce(Input.Location loc, Forest<T>[] args) { return (Forest<T>)Forest.singleton(loc, args[idx]); }
+ public Sequence and(Sequence s) { Sequence ret = new Singleton(elements, idx, needs, hates); ret.needs(s); return ret; }
+ public Sequence not(Sequence s) { Sequence ret = new Singleton(elements, idx, needs, hates); ret.hates(s); return ret; }
}
public static class Unwrap extends Sequence {
private boolean[] drops;
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 Sequence and(Sequence s) { Sequence ret = new Unwrap(elements, drops, needs, hates); ret.needs(s); return ret; }
+ public Sequence not(Sequence s) { Sequence ret = new Unwrap(elements, drops, needs, hates); ret.hates(s); return ret; }
public <T> Forest<T> postReduce(Input.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, true, false);
/*private*/public final Object tag;
private final boolean[] drops;
private int count = 0;
+ public Sequence and(Sequence s) { Sequence ret = new RewritingSequence(tag, elements, drops, needs, hates); ret.needs(s); return ret; }
+ public Sequence not(Sequence s) { Sequence ret = new RewritingSequence(tag, elements, drops, needs, hates); ret.hates(s); return ret; }
public RewritingSequence(Object tag, Element[] e, HashSet<Sequence> and, HashSet<Sequence> not) { this(tag, e, null, and, not); }
public RewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet<Sequence> and, HashSet<Sequence> not) {
super(e, and, not);
protected String headToString() { return head==null?null:head.toString(); }
protected String headToJava() { return head==null?null:StringUtil.toJavaString(head+""); }
+ protected String left() { return "{"; }
+ protected String right() { return "}"; }
+ protected boolean ignoreSingleton() { return false; }
}
import edu.berkeley.sbp.Input.Location;
import edu.berkeley.sbp.util.*;
-public abstract class CartesianInput<Tok> implements Input<Tok> {
+public abstract class CartesianInput<Token> implements Input<Token> {
- private int line = 1;
- private int col = 0;
-
- public abstract Tok next() throws IOException;
+ public abstract Token next() throws IOException;
public abstract boolean isCR();
long then = 0;
- private Input.Location location = new LocWrap(line, col);
- public Input.Location getLocation() { return location; }
- public Tok next(int numstates, int resets, int waits) throws IOException {
- Tok t = next();
+ private CartesianLocation location = new CartesianLocation(1, 0);
+ public Input.Location getLocation() { return location; }
+
+ public Token next(int numstates, int resets, int waits) throws IOException {
+ int line = location.line;
+ int col = location.col;
+ Token t = next();
if (t==null) return null;
String s = " line "+line+", col " + col;
while(s.length() < 20) s += " ";
} else {
col++;
}
- location = new LocWrap(line, col);
+ location = new CartesianLocation(line, col);
return t;
}
-
- private class LocWrap implements Input.Location {
- public final int line;
- public final int col;
- public String toString() { return line + ":" + col; }
- public LocWrap(int line, int col) { this.line = line; this.col = col; }
- }
}
// MetaGrammar //////////////////////////////////////////////////////////////////////////////
- public Union nonTerminal(String str) { return nonTerminal(str, null, false, false); }
- public Union nonTerminal(String str, PreSequence[][] s, boolean synthetic, boolean dropAll) {
+ public Union getNonTerminal(String str) { return nonTerminal(str, null, false, false); }
+ private Union nonTerminal(String str) { return nonTerminal(str, null, false, false); }
+ public Union anonymousNonTerminal(PreSequence[][] s) {
+ return nonTerminal("anon"+(anon++), s, false, false);
+ }
+ private Union nonTerminal(String str, PreSequence[][] s, boolean synthetic, boolean dropAll) {
Union n = str.equals(startSymbol) ? g : nt.get(str);
if (n == null) nt.put(str, n = new Union(str, synthetic));
if (dropAll) this.dropAll.add(n);
else if ("epsilon".equals(head)) return Union.epsilon;
else if ("()".equals(head)) return Union.epsilon;
else if (")".equals(head)) return SELF;
- else if ("nonTerminal".equals(head)) return nonTerminal(string(tree.child(0)), null, false, false);
+ else if ("nonTerminal".equals(head)) return getNonTerminal(string(tree.child(0)));
else if ("::=".equals(head)) return nonTerminal(string(tree.child(0)), (PreSequence[][])walk(tree, 1), false, false);
else if ("!::=".equals(head)) return nonTerminal(string(tree.child(0)), (PreSequence[][])walk(tree, 1), false, true);
- else if ("(".equals(head)) return nonTerminal("anon"+(anon++), (PreSequence[][])walk(tree, 0), false, false);
+ else if ("(".equals(head)) return buildUnion((PreSequence[][])walk(tree, 0));
else if ("literal".equals(head)) { Element ret = string(string(tree.child(0))); dropAll.add(ret); return ret; }
else if ("-".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,1).toString().charAt(0));
else if ("range".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,0).toString().charAt(0));
return super.walk(tag, argo);
}
+ public Union buildUnion(PreSequence[][] p) {
+ return anonymousNonTerminal(p);
+ }
+
//////////////////////////////////////////////////////////////////////////////
public class PreSequence {
this.drops = drops==null ? new boolean[o.length] : drops;
}
- public Union buildUnion() {
- Union u = new Union("???");
+ public Union buildUnion(String s) {
+ Union u = new Union(s);
u.add(buildSequence(u));
return u;
}
+ public Union buildUnion() { return buildUnion("???"); }
public boolean unwrap = false;
public Sequence buildSequence(Union u) { return buildSequence(u, false, false); }
public Sequence buildSequence(Union u, boolean lame, boolean dropAll) {
private ArrayList<Integer> istack = new ArrayList<Integer>();
public Character next(int numstates, int resets, int waits) throws IOException {
Character ret = nextc(numstates, resets);
- if (ret==left) System.out.print("\033[31m{\033[0m");
+ if (ret==null) return null;
+ else if (ret==left) System.out.print("\033[31m{\033[0m");
else if (ret==right) System.out.print("\033[31m}\033[0m");
- else if (ret==null) return null;
else System.out.print(ret);
return ret;
}
public static class Grammar extends MetaGrammar {
private int anon = 0;
- private final Element ws = Repeat.maximal0(nonTerminal("w"));
+ private final Element ws = Repeat.maximal0(getNonTerminal("w"));
public Grammar() { dropAll.add(ws); }
public Object walk(Tree<String> tree) {
String head = tree.head();
if (tree.numChildren()==0) return super.walk(tree);
if ("{".equals(head)) {
- String s = "braced"+(anon++);
- Union u = nonTerminal(s);
+ Union u = new Union("???");
Union u2 = ((PreSequence)walk(tree, 0)).sparse(ws).buildUnion();
u2.add(Sequence.singleton(new Element[] { u }, 0, null, null));
- return nonTerminal(s,
- new PreSequence[][] {
- new PreSequence[] {
- new PreSequence(new Element[] { CharRange.leftBrace,
- ws,
- u2,
- ws,
- CharRange.rightBrace
- })
- }
- },
- false,
- false);
+ return anonymousNonTerminal(new PreSequence[][] {
+ new PreSequence[] {
+ new PreSequence(new Element[] { CharRange.leftBrace,
+ ws,
+ u2,
+ ws,
+ CharRange.rightBrace
+ })
+ }
+ });
}
return super.walk(tree);
}
protected abstract String headToString();
protected abstract String headToJava();
- protected abstract int numChildren();
+ protected abstract String left();
+ protected abstract String right();
+ protected abstract boolean ignoreSingleton();
private static final int MAXCHARS=40;
if (str.length() < MAXCHARS) return str;
String head = headToString();
StringBuffer ret = new StringBuffer();
- if (numChildren()==0) return head==null ? "{}" : head;
- ret.append(head==null?"{ ":(head+":"+nl));
+
+ Iterator<T> iterator = iterator();
+ if (!iterator.hasNext()) return head==null ? (left()+right()) : head;
+ PrintableTree t0 = iterator.next();
+ if (!iterator.hasNext() && ignoreSingleton())
+ return t0.toPrettyString(nl);
+
+ ret.append(head==null?(left()+" "):(head+":"+nl));
boolean first = true;
int len = 0;
for(T t : this) {
ret.append(s);
len += s.length();
}
- if (head==null) ret.append(" }");
+ if (head==null) ret.append(" "+right());
return ret.toString();
}
public String toString() {
StringBuffer ret = new StringBuffer();
+ int count=0;
for(T t : this) {
+ count++;
String q = t==null ? "null" : t.toString();
if (q.length() > 0) { ret.append(q); ret.append(" "); }
}
+ if (count==1 && ignoreSingleton()) return ret.toString().trim();
String tail = ret.toString().trim();
String head = headToString();
String h = (head!=null && !head.toString().equals("")) ? (tail.length() > 0 ? head+":" : head+"") : "";
- if (tail.length() > 0) tail = "{" + tail + "}";
+ if (tail.length() > 0) tail = left() + tail + right();
return h + tail;
}
projects / sbp.git / commitdiff