From fc1e5069ec5401c425dd29b77b04285916b62d10 Mon Sep 17 00:00:00 2001 From: adam Date: Sun, 15 Jan 2006 16:29:42 -0500 Subject: [PATCH] checkpoint darcs-hash:20060115212942-5007d-9bf581dedf6761912ec0f010bdeb3019e690307a.gz --- TODO | 4 +- src/edu/berkeley/sbp/Forest.java | 72 ++++++++----------------- src/edu/berkeley/sbp/Sequence.java | 14 +++++ src/edu/berkeley/sbp/Tree.java | 3 ++ src/edu/berkeley/sbp/misc/CartesianInput.java | 27 ++++------ src/edu/berkeley/sbp/misc/MetaGrammar.java | 21 +++++--- src/edu/berkeley/sbp/tib/Tib.java | 32 +++++------ src/edu/berkeley/sbp/util/PrintableTree.java | 21 ++++++-- 8 files changed, 96 insertions(+), 98 deletions(-) diff --git a/TODO b/TODO index 1d62802..47593cb 100644 --- a/TODO +++ b/TODO @@ -1,11 +1,13 @@ _____________________________________________________________________________ Immediately + - Repeat, Sequence, Tree + - simplify Forest (considerably) + - decent/better error messages - fix the location stuff, it's broken - copyright notices - - documentation ______________________________________________________________________________ diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index e4572ec..0a20228 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -7,7 +7,7 @@ import java.util.*; import java.lang.reflect.*; /** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */ -public abstract class Forest { +public abstract class Forest extends PrintableTree> implements Iterable> { /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */ public final Tree expand1() throws Ambiguous, ParseFailed { @@ -28,7 +28,7 @@ public abstract class Forest { // Body ////////////////////////////////////////////////////////////////////////////// - protected static class Body { + protected static class Body extends PrintableTree> implements Iterable> { private final Input.Location location; private final T tag; @@ -48,14 +48,14 @@ public abstract class Forest { private HashSet> expand(boolean toss, ArrayList> toks, int i, HashSet> h) { if (singleton) { - for(Body b : (IterableForest)tokens[0]) b.expand(toss, toks, i, h); + for(Body b : tokens[0]) b.expand(toss, toks, i, h); } else if (i==tokens.length) { h.add(new Tree(null, tag, toks.toArray(tree_hint))); } else if (unwrap && i==tokens.length-1) { if (tokens[i] != null) - for(Body b : (IterableForest)tokens[i]) + for(Body b : tokens[i]) b.expand(toss, toks, 0, h); } else { @@ -74,38 +74,26 @@ public abstract class Forest { void addTo(FastSet h) { if (!singleton) h.add(this, true); - else for(Body b : (IterableForest)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 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> iterator() { return new ArrayIterator>(tokens); } } // Ref ////////////////////////////////////////////////////////////////////////////// - private static abstract class IterableForest extends Forest implements Iterable> { - public abstract Iterator> 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 extends IterableForest { + static class Ref extends Forest { private FastSet hp = new FastSet(); private Forest res = null; public Ref() { } @@ -114,14 +102,13 @@ public abstract class Forest { if (p==null) throw new Error(); if (p!=this) hp.add(p, true); } - public Iterator> iterator() { return ((IterableForest)resolve()).iterator(); } + public Iterator> iterator() { return ((Forest)resolve()).iterator(); } public HashSet> expand(boolean toss) { return resolve().expand(toss); } - public String toString() { return resolve().toString(); } public Forest resolve() { if (hp==null) return res; FastSet nh = new FastSet(); for(Forest p : hp) - for(Body b : (IterableForest)p) + for(Body b : (Forest)p) b.addTo(nh); res = new MultiForest(nh); hp = null; @@ -131,14 +118,13 @@ public abstract class Forest { // Implementations ////////////////////////////////////////////////////////////////////////////// - private static class MultiForest extends IterableForest { + private static class MultiForest extends Forest { private final FastSet> results; private MultiForest(FastSet> results) { this.results = results; } public MultiForest(Input.Location loc, T tag, Forest[] tokens, boolean unwrap, boolean singleton) { this.results = new FastSet>(new Body(loc, tag, tokens, unwrap, singleton)); } public Iterator> iterator() { return results.iterator(); } - public HashSet> expand(boolean toss) { HashSet> ret = new HashSet>(); for(Body b : results) @@ -146,32 +132,16 @@ public abstract class Forest { 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 r : results) - ret.append(r); - return toString = ret.toString(); - } - ret.append(" 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 boolean ignoreSingleton() { return true; } } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index b31b307..68e311e 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -12,6 +12,12 @@ public abstract class Sequence extends Element implements Iterable { // 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(); @@ -174,6 +180,8 @@ public abstract class Sequence extends Element implements Iterable { static class Constant extends Sequence { private final Object result; public Constant(Element[] e, Object result, HashSet and, HashSet 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 Forest postReduce(Input.Location loc, Forest[] args) { return (Forest)Forest.leaf(loc, result); } @@ -191,12 +199,16 @@ public abstract class Sequence extends Element implements Iterable { public Singleton(Element e, HashSet and, HashSet not) { this(new Element[] { e }, 0, and, not); } public Singleton(Element[] e, int idx, HashSet and, HashSet not) { super(e, and, not); this.idx = idx; } public Forest postReduce(Input.Location loc, Forest[] args) { return (Forest)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 and, HashSet not) { super(e, and, not); this.drops = null; } public Unwrap(Element[] e, boolean[] drops, HashSet and, HashSet 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 Forest postReduce(Input.Location loc, Forest[] args) { for(int i=0; i { /*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 and, HashSet not) { this(tag, e, null, and, not); } public RewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet and, HashSet not) { super(e, and, not); diff --git a/src/edu/berkeley/sbp/Tree.java b/src/edu/berkeley/sbp/Tree.java index 102817c..2ab70c8 100644 --- a/src/edu/berkeley/sbp/Tree.java +++ b/src/edu/berkeley/sbp/Tree.java @@ -39,4 +39,7 @@ public class Tree extends PrintableTree> implements Iterable> 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; } } diff --git a/src/edu/berkeley/sbp/misc/CartesianInput.java b/src/edu/berkeley/sbp/misc/CartesianInput.java index 928b236..a78df9a 100644 --- a/src/edu/berkeley/sbp/misc/CartesianInput.java +++ b/src/edu/berkeley/sbp/misc/CartesianInput.java @@ -7,19 +7,19 @@ import edu.berkeley.sbp.*; import edu.berkeley.sbp.Input.Location; import edu.berkeley.sbp.util.*; -public abstract class CartesianInput implements Input { +public abstract class CartesianInput implements Input { - 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 += " "; @@ -35,14 +35,7 @@ public abstract class CartesianInput implements Input { } 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; } - } } diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java index 7f4120f..4348dec 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammar.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -63,8 +63,12 @@ public class MetaGrammar extends StringWalker { // 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); @@ -117,10 +121,10 @@ public class MetaGrammar extends StringWalker { 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)); @@ -173,6 +177,10 @@ public class MetaGrammar extends StringWalker { return super.walk(tag, argo); } + public Union buildUnion(PreSequence[][] p) { + return anonymousNonTerminal(p); + } + ////////////////////////////////////////////////////////////////////////////// public class PreSequence { @@ -221,11 +229,12 @@ public class MetaGrammar extends StringWalker { 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) { diff --git a/src/edu/berkeley/sbp/tib/Tib.java b/src/edu/berkeley/sbp/tib/Tib.java index b2383ac..3c3e184 100644 --- a/src/edu/berkeley/sbp/tib/Tib.java +++ b/src/edu/berkeley/sbp/tib/Tib.java @@ -55,9 +55,9 @@ public class Tib implements Input { private ArrayList istack = new ArrayList(); 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; } @@ -137,29 +137,25 @@ public class Tib implements Input { 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 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); } diff --git a/src/edu/berkeley/sbp/util/PrintableTree.java b/src/edu/berkeley/sbp/util/PrintableTree.java index 73b7f02..180d2ea 100644 --- a/src/edu/berkeley/sbp/util/PrintableTree.java +++ b/src/edu/berkeley/sbp/util/PrintableTree.java @@ -9,7 +9,9 @@ public abstract class PrintableTree implements Iterable 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; @@ -20,8 +22,14 @@ public abstract class PrintableTree implements Iterable 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 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) { @@ -35,20 +43,23 @@ public abstract class PrintableTree implements Iterable 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; } -- 1.7.10.4