From 2afdfe14e78fa0597186614937c679a09d74ecdf Mon Sep 17 00:00:00 2001 From: adam Date: Thu, 19 Apr 2007 23:22:13 -0400 Subject: [PATCH] UnwrapLeft, error reporting improvements darcs-hash:20070420032213-5007d-58297faff26b5faaa0c685e67e00b505735e9fc6.gz --- src/edu/berkeley/sbp/Forest.java | 18 +++++-- src/edu/berkeley/sbp/Input.java | 3 ++ src/edu/berkeley/sbp/Node.java | 8 ++-- src/edu/berkeley/sbp/ParseFailed.java | 29 ++++++----- src/edu/berkeley/sbp/Parser.java | 85 ++++++++++++++++++++++++--------- src/edu/berkeley/sbp/Result.java | 2 +- src/edu/berkeley/sbp/Sequence.java | 26 ++++++++++ src/edu/berkeley/sbp/Tree.java | 12 ++++- 8 files changed, 137 insertions(+), 46 deletions(-) diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index cf64ed2..34982bd 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -28,11 +28,18 @@ public abstract class Forest implements GraphViz.ToGraphViz { // Package-Private ////////////////////////////////////////////////////////////////////////////// - static Forest create(Input.Region region, NodeType head, Forest[] children, boolean lift) { + static Forest create(Input.Region region, NodeType head, Forest[] children, + boolean lift) { if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen"); return new One(region, head, children, lift); } + static Forest create(Input.Region region, NodeType head, Forest[] children, + boolean lift, boolean liftLeft) { + if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen"); + return new One(region, head, children, lift, liftLeft); + } + /** create a new forest */ public static Forest create(Input.Region region, NodeType head, Forest[] children) { return Forest.create(region, head, children, false); } @@ -53,10 +60,14 @@ public abstract class Forest implements GraphViz.ToGraphViz { /** if true, the last child's children are considered children of this node */ private final boolean lift; + private final boolean liftLeft; public Input.Region getRegion() { return location; } private One(Input.Region loc, NodeType head, Forest[] children, boolean lift) { + this(loc, head, children, lift, false); + } + private One(Input.Region loc, NodeType head, Forest[] children, boolean lift, boolean liftLeft) { this.location = loc; this.head = head; if (head==null) throw new RuntimeException("invoked Forest.create(,null,,,) -- this should never happen"); @@ -64,12 +75,13 @@ public abstract class Forest implements GraphViz.ToGraphViz { if (children != null) System.arraycopy(children, 0, this.children, 0, children.length); if (children != null) for(int i=0; i expand1() throws Ambiguous { Tree[] ret = new Tree[children.length]; for(int i=0; i(location, head, ret, lift); + return new Tree(location, head, ret, lift, liftLeft); } void gather(HashSet> hf) { @@ -83,7 +95,7 @@ public abstract class Forest implements GraphViz.ToGraphViz { private void expand(final int i, Tree[] ta, HashSet> ht, HashSet> ignore, Tree bogus) { if (i==children.length) { - ht.add(new Tree(location, head, ta, lift)); + ht.add(new Tree(location, head, ta, lift, liftLeft)); } else { HashSet> ht2 = new HashSet>(); children[i].expand(ht2, ignore, bogus); diff --git a/src/edu/berkeley/sbp/Input.java b/src/edu/berkeley/sbp/Input.java index 7a2df1a..ac2c486 100644 --- a/src/edu/berkeley/sbp/Input.java +++ b/src/edu/berkeley/sbp/Input.java @@ -19,6 +19,9 @@ public interface Input { /** a short string describing where the input is coming from, such as a filename */ public String getName(); + /** might called by Parser when it is done with the input */ + public void close(); + /** * Optional: If possible, this method will return a * rendering of the input region (for example, if the input is a diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index b216d3f..b6f4585 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -33,11 +33,11 @@ final class Node // - be on the frontier or // - have a non-doomed node closer to the frontier than themself if (phase.isFrontier()) dead = false; - for(Result r : children) - if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } - else { if (r.usedByNonDoomedNode()) { dead = false; break; } } + else for(Result r : children) + if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } + else { if (r.usedByNonDoomedNode()) { dead = false; break; } } dead |= results.size()==0; - if (!dead || destroyed) return; + if (!dead) return; destroyed = true; while(children.size()>0) for(Result r : children) { diff --git a/src/edu/berkeley/sbp/ParseFailed.java b/src/edu/berkeley/sbp/ParseFailed.java index 8e759a8..8000712 100644 --- a/src/edu/berkeley/sbp/ParseFailed.java +++ b/src/edu/berkeley/sbp/ParseFailed.java @@ -138,25 +138,24 @@ public class ParseFailed extends Exception { return ANSI.purple(ret.toString()); } - static void error(String message, GSS.Phase phase) throws ParseFailed { - error(message, phase.getLocation(), phase.getToken(), - phase, phase.getRegion(), phase.getGSS().getInput(), phase.getGSS()); + static void error(String message, GSS.Phase phase, Object token, Input.Region region) throws ParseFailed { + error(message, + token, + phase, + region, + phase.getGSS().getInput(), + phase.getGSS()); } - static void error(String message, - Input.Location loc, - Object token, - Iterable nodes, - Input.Region region, - Input input, - GSS gss) throws ParseFailed{ + private static void error(String message, + Object token, + Iterable nodes, + Input.Region region, + Input input, + GSS gss) throws ParseFailed{ String lookAhead = token==null ? "" : token.toString(); StringBuffer ret = new StringBuffer(); ret.append(ANSI.bold(ANSI.red(message))); - if (token != null) { - ret.append(" \'"); - ret.append(ANSI.cyan(StringUtil.escapify(token+"", "\\\'\r\n"))); - ret.append("\'"); - } + String toks = token+""; ret.append(" at "); ret.append(ANSI.yellow(region+"")); if (input != null) { diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index de96760..0b2229d 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -30,33 +30,21 @@ public abstract class Parser { public Forest parse(Input input) throws IOException, ParseFailed { verbose = System.getProperty("sbp.verbose", null) != null; spinpos = 0; + GSS gss = new GSS(input, this); try { - GSS gss = new GSS(input, this); for(GSS.Phase current = gss.new Phase(pt.start); ;) { - - if (verbose) { - // FIXME: clean this up - String s; - s = " " + spin[spinpos++ % (spin.length)]+" parsing "; - s += input.getName(); - s += " "+input.getLocation(); - while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s; - String y = "@"+gss.viewPos+" "; - while(y.length() < 9) y = " " + y; - s += y; - s += " nodes="+gss.numOldNodes; - while(s.length() < 50) s = s + " "; - s += " shifted="+gss.numNewNodes; - while(s.length() < 60) s = s + " "; - s += " reductions="+gss.numReductions; - System.err.print("\r"+s+ANSI.clreol()+"\r"); - } - + if (verbose) debug(current.token, gss, input); if (current.isDone()) return (Forest)current.finalResult; - Forest forest = shiftToken((Token)current.token, current.getRegion()); + Input.Region region = current.getLocation().createRegion(current.getNextLocation()); + Forest forest = shiftToken((Token)current.token, region); current = gss.new Phase(current, forest); } - } finally { if (verbose) System.err.print("\r"+ANSI.clreol()); } + } finally { + if (verbose) { + System.err.print("\r"+ANSI.clreol()); + debug(null, gss, input); + } + } } // Spinner ////////////////////////////////////////////////////////////////////////////// @@ -73,6 +61,52 @@ public abstract class Parser { System.err.print("\r " + spin[spinpos++ % (spin.length)]+"\r"); } + private int _last = -1; + private String buf = ""; + private void debug(Object t, GSS gss, Input input) { + //FIXME + int c = t==null ? -1 : ((t+"").charAt(0)); + int last = _last; + _last = c; + switch(c) { + case edu.berkeley.sbp.chr.CharAtom.left: + buf += "\033[31m{\033[0m"; + break; + case edu.berkeley.sbp.chr.CharAtom.right: + buf += "\033[31m}\033[0m"; + break; + case -1: // FIXME + case '\n': + if (verbose) { + if (last==' ') buf += ANSI.blue("\\n"); + System.err.println("\r"+ANSI.clreol()+"\r"+buf); + buf = ""; + } + break; + default: + buf += ANSI.cyan(""+((char)c)); + break; + } + if (t==null) return; + + // FIXME: clean this up + String s; + s = " " + spin[spinpos++ % (spin.length)]+" parsing "; + s += input.getName(); + s += " "+input.getLocation(); + while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s; + String y = "@"+gss.viewPos+" "; + while(y.length() < 9) y = " " + y; + s += y; + s += " nodes="+gss.numOldNodes; + while(s.length() < 50) s = s + " "; + s += " shifted="+gss.numNewNodes; + while(s.length() < 60) s = s + " "; + s += " reductions="+gss.numReductions; + while(s.length() < 78) s = s + " "; + System.err.print("\r"+ANSI.invert(s+ANSI.clreol())+"\r"); + } + // Table ////////////////////////////////////////////////////////////////////////////// /** an SLR(1) parse table which may contain conflicts */ @@ -253,6 +287,7 @@ public abstract class Parser { // Interface Methods ////////////////////////////////////////////////////////////////////////////// + public boolean doomed() { return doomed; } boolean isAccepting() { return accept; } public Iterator iterator() { return hs.iterator(); } boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); } @@ -382,6 +417,12 @@ public abstract class Parser { } public int toInt() { return idx; } + public String toString() { + StringBuffer ret = new StringBuffer(); + for(Position p : hs) + ret.append(p+"\n"); + return ret.toString(); + } } } diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java index d333f41..95baeba 100644 --- a/src/edu/berkeley/sbp/Result.java +++ b/src/edu/berkeley/sbp/Result.java @@ -40,7 +40,7 @@ final class Result implements GraphViz.ToGraphViz { parent.removeChild(this); while(children.size() > 0) for(Node n : children) { - children.remove(n); + removeChild(n); n.removeResult(this); break; } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index 968d78f..c41be4f 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -54,6 +54,11 @@ public abstract class Sequence implements Iterable, SequenceOrElement { ? new Unwrap(e, head, drop) : new RewritingSequence(head, e, drop); } + public static Sequence createLeft(Object head, Element[] e, boolean[] drop, boolean foster) { + return foster + ? new UnwrapLeft(e, head, drop) + : new RewritingSequence(head, e, drop); + } /** return a new sequence identical to this one, but with a positive conjunct s */ public Sequence and(Sequence s) { @@ -256,6 +261,27 @@ public abstract class Sequence implements Iterable, SequenceOrElement { } } + static class UnwrapLeft extends Sequence { + private boolean[] drops; + private final Object tag; + public UnwrapLeft(Element[] e, Object tag) { this(e, tag, null); } + public UnwrapLeft(Element[] e, Object tag, boolean[] drops) { super(e); this.drops = drops; this.tag = tag; } + Sequence _clone() { return new UnwrapLeft(elements, tag, drops); } + public Forest postReduce(Input.Region loc, Forest[] args, Position p) { + for(int i=0; i[] args2 = new Forest[count]; + int j = 0; + for(int i=0; i // FIXME: fairly inefficient because we keep copying arrays /** package-private constructor, allows setting the "lift" bit */ Tree(Input.Region loc, NodeType head, Tree[] children, boolean lift) { + this(loc, head, children, lift, false); + } + Tree(Input.Region loc, NodeType head, Tree[] children, boolean lift, boolean liftLeft) { this.location = loc; this.ihead = head; - if (lift && children != null && children.length > 0) { + // FIXME: lift+liftLeft togheter + if (liftLeft && children != null && children.length > 0) { + Tree last = children[0]; + this.children = new Tree[(children.length-1)+last.children.length]; + System.arraycopy(children, 1, this.children, last.children.length, children.length-1); + if (last.children.length > 0) + System.arraycopy(last.children, 0, this.children, 0, last.children.length); + } else if (lift && children != null && children.length > 0) { Tree last = children[children.length-1]; this.children = new Tree[(children.length-1)+last.children.length]; System.arraycopy(children, 0, this.children, 0, children.length-1); -- 1.7.10.4