From 72cc02d0f08922a98b9f2139e814b6c33b275a43 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 4 Jan 2006 05:06:22 -0500 Subject: [PATCH 1/1] checkpoint darcs-hash:20060104100622-5007d-3d2f309f5b19c93a8736b0a1e2dc606b00bd4522.gz --- src/edu/berkeley/sbp/GSS.java | 30 ++++++++++++++---------------- src/edu/berkeley/sbp/Parser.java | 6 +++--- src/edu/berkeley/sbp/util/FastSet.java | 2 +- tests/regression.tc | 18 +++++++++--------- 4 files changed, 27 insertions(+), 29 deletions(-) diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 6db929b..0b6064d 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -35,6 +35,8 @@ class GSS { /** the token immediately after this phase */ public final Token token; + boolean reducing = false; + /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */ private final int pos; @@ -81,8 +83,7 @@ class GSS { private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { p.holder.merge(pending); if (p.parents().contains(parent)) return; - p.parents().add(parent, true); - if (p!=parent && !fromEmptyReduction) p.queueReductions(parent); + p.addParent(parent, fromEmptyReduction); } private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { do { @@ -105,7 +106,6 @@ class GSS { } - boolean reducing = false; /** perform all reduction operations */ public void reduce() { reducing = true; @@ -154,13 +154,13 @@ class GSS { //n.queueEmptyReductions(); //} //error.append(" after: " +pendingReductions+ "\n"); - error.append(" candidate states:\n"); - for(Phase.Node n : hash.values()) { + //error.append(" candidate states:\n"); + //for(Phase.Node n : hash.values()) { //for(Sequence.Position p : n.state) error.append(" " + p + "\n"); //error.append(" --\n"); - for(Parser.Table.Reduction r : n.state.getReductions(token)) error.append(" " + r + "\n"); + //for(Parser.Table.Reduction r : n.state.getReductions(token)) error.append(" " + r + "\n"); //error.append(" ==\n"); - } + //} next.error = error.toString(); } @@ -174,6 +174,11 @@ class GSS { /** a node in the GSS */ public final class Node extends FastSet { + public void addParent(Node parent, boolean fromEmptyReduction) { + parents().add(parent, true); + if (this!=parent && !fromEmptyReduction) queueReductions(parent); + } + private Forest.Ref holder = null; private boolean allqueued = false; @@ -189,7 +194,8 @@ class GSS { public final Phase phase = Phase.this; public HashMap cache() { - return cache==null ? (cache = new HashMap()) : cache; } + return cache==null ? (cache = new HashMap()) : cache; + } public Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; } public Forest pending() { return Phase.this.closed ? holder().resolve() : holder; } public FastSet parents() { return this; } @@ -218,13 +224,6 @@ class GSS { // ultimate parent of the last pop, so we need to // cache instances here as a way of avoiding // recreating them. - - // currently we have this weird problem where we - // have to do an individual reduct for each child - // when the reduction length is one (ie the - // children wind up being children of the newly - // created node rather than part of the popped - // sequence if (r.numPop <= 0) continue; if (r.numPop == 1) { Forest ret = n.cache().get(r); @@ -269,5 +268,4 @@ class GSS { private static long code(Parser.Table.State state, Phase start) { return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); } - public boolean yak = false; } diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 58d0bc2..6f1098e 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -134,7 +134,7 @@ public abstract class Parser { Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache); Reduction red = new Reduction(p); state.reductions.put(wf.walk(p.owner()), red); - if (wf.includesEof()) state.eofReductions.add(red, true); + if (wf.includesEof()) state.eofReductions.add(red); } // if the element following this position is an atom, copy the corresponding @@ -168,14 +168,14 @@ public abstract class Parser { } */ - public final int idx = master_state_idx++; + public final int idx = master_state_idx++; private final HashSet hs; private transient HashMap gotoSetNonTerminals = new HashMap(); private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); private TopologicalBag reductions = new TopologicalBag(); - private FastSet eofReductions = new FastSet(); + private HashSet eofReductions = new HashSet(); private TopologicalBag shifts = new TopologicalBag(); private boolean accept = false; diff --git a/src/edu/berkeley/sbp/util/FastSet.java b/src/edu/berkeley/sbp/util/FastSet.java index 086f636..d3be774 100644 --- a/src/edu/berkeley/sbp/util/FastSet.java +++ b/src/edu/berkeley/sbp/util/FastSet.java @@ -7,7 +7,7 @@ public /*final*/ class FastSet implements Iterator, Iterable { private Object[] array; private T only = null; - private int i = 0; + private int i = -1; private int size = 0; public Iterator iterator() { i=0; return this; } diff --git a/tests/regression.tc b/tests/regression.tc index c2206ee..a249286 100644 --- a/tests/regression.tc +++ b/tests/regression.tc @@ -263,6 +263,15 @@ testcase { idl ::= [a-d] } +testcase { + input "aa bb"; + output "{q:{{a a}} q:{{b b}}}"; + + s ::= q */ ws + ws ::= " "* + q ::= [a-z]++ => "q" +} + //testcase { // // input " @@ -319,12 +328,3 @@ testcase { // // //} - -testcase { - input "aa bb"; - output "{q:{{a a}} q:{{b b}}}"; - - s ::= q */ ws - ws ::= " "* - q ::= [a-z]++ => "q" -} \ No newline at end of file -- 1.7.10.4