X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=b4ac23a0a3285023df34427c262e921a9411e241;hb=cd979dfc5968a185c12d6eedc2aa688ef4b0f8b8;hp=f6428781bed46d6511d7df89f8cbda848891a466;hpb=8a9fc9f2357e54052374cf2ef003630a486a6c0a;p=sbp.git diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index f642878..b4ac23a 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -32,8 +32,8 @@ public abstract class Parser { current.reduce(); Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); - count = next.hash.size(); - if (current.isDone()) return (Forest)current.finalResult; + count = next.size(); + if (current.isDone()) return (Forest)gss.finalResult; current = next; } } @@ -91,21 +91,13 @@ public abstract class Parser { if (start0.contains(p.owner()) && p.next()==null) state.accept = true; - if (p.isRightNullable(cache)) { + if (isRightNullable(p)) { Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache); Reduction red = new Reduction(p); Topology follow = wf.walk(p.owner()); - if (p.owner() instanceof Sequence.RewritingSequence && - (((Sequence.RewritingSequence)p.owner()).tag+"").equals("emailaddr")) { - System.out.println("follow before: " + new edu.berkeley.sbp.misc.CharToken.CharRange(follow)); - } for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element())); - if (p.owner() instanceof Sequence.RewritingSequence && - (((Sequence.RewritingSequence)p.owner()).tag+"").equals("emailaddr")) { - System.out.println("follow after: " + new edu.berkeley.sbp.misc.CharToken.CharRange(follow)); - } state.reductions.put(follow, red); if (wf.includesEof()) state.eofReductions.add(red); } @@ -121,44 +113,20 @@ public abstract class Parser { } } + private boolean isRightNullable(Position p) { + if (p.isLast()) return true; + if (!p.element().possiblyEpsilon(this)) return false; + return isRightNullable(p.next()); + } + /** a single state in the LR table and the transitions possible from it */ public class State implements Comparable, IntegerMappable, Iterable { - public int toInt() { return idx; } - - public boolean lame() { - for(Position p : this) - for(Position p2 = p; p2!=null; p2=p2.next()) - if (p2.isLast() && !p2.owner().lame) - return false; - return true; - } - /* - public boolean isResolvable(Token t) { - boolean found = false; - for(Reduction r : getReductions(t)) { - Position p = r.position; - if (!p.isRightNullable(cache)) continue; - if (p.owner().firstp()==p) continue; - if (found) { - // found two items meeting criteria #1 - return false; - } else { - found = true; - continue; - } - if (p.element()==null) continue; - Topology first = new Walk.First(top(), cache).walk(p.element()); - if (first.contains(t)) - } - } - */ - public final int idx = master_state_idx++; private final HashSet hs; - private transient HashMap gotoSetNonTerminals = new HashMap(); + public transient HashMap gotoSetNonTerminals = new HashMap(); private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); private TopologicalBag reductions = new TopologicalBag(); @@ -171,17 +139,16 @@ public abstract class Parser { // Interface Methods ////////////////////////////////////////////////////////////////////////////// - public boolean isAccepting() { return accept; } - - public boolean canShift(Token t) { return oshifts.contains(t); } - public boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } - + boolean isAccepting() { return accept; } public Iterator iterator() { return hs.iterator(); } - public void invokeShifts(Token t, Invokable irbc, B b, C c) { + boolean canShift(Token t) { return oshifts.contains(t); } + void invokeShifts(Token t, Invokable irbc, B b, C c) { oshifts.invoke(t, irbc, b, c); } - public void invokeReductions(Token t, Invokable irbc, B b, C c) { + + boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } + void invokeReductions(Token t, Invokable irbc, B b, C c) { if (t==null) for(Reduction r : eofReductions) irbc.invoke(r, b, c); else oreductions.invoke(t, irbc, b, c); } @@ -268,7 +235,6 @@ public abstract class Parser { } public String toString() { - //return "state["+idx+"]"; StringBuffer ret = new StringBuffer(); ret.append("state["+idx+"]: "); for(Position p : this) ret.append("{"+p+"} "); @@ -276,6 +242,7 @@ public abstract class Parser { } public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } + public int toInt() { return idx; } } /** @@ -284,9 +251,7 @@ public abstract class Parser { */ public class Reduction { // FIXME: cleanup; almost everything in here could go in either Sequence.Position.getRewrite() or else in GSS.Reduct - public final int numPop; /*private*/ final Position position; - private final Forest[] holder; // to avoid constant reallocation public int hashCode() { return position.hashCode(); } public boolean equals(Object o) { if (o==null) return false; @@ -297,57 +262,16 @@ public abstract class Parser { } public Reduction(Position p) { this.position = p; - this.numPop = p.pos; - this.holder = new Forest[numPop]; } public String toString() { return "[reduce " + position + "]"; } private Forest zero = null; public Forest zero() { if (zero != null) return zero; - if (numPop > 0) throw new Error(); + if (position.pos > 0) throw new Error(); return zero = position.rewrite(null); } - public void reduce(GSS.Phase.Node parent) { - if (numPop==0) finish(parent, zero(), parent.phase()); - else reduce(parent, numPop-1, parent.phase()); - } - - public void reduce(GSS.Phase.Node parent, GSS.Phase.Node onlychild) { - if (numPop<=0) throw new Error("called wrong form of reduce()"); - int pos = numPop-1; - Forest old = holder[pos]; - holder[pos] = parent.pending(); - if (pos==0) { - System.arraycopy(holder, 0, position.holder, 0, holder.length); - finish(onlychild, position.rewrite(parent.phase().getLocation()), parent.phase()); - } else { - reduce(onlychild, pos-1, parent.phase()); - } - holder[pos] = old; - } - - // FIXME: this could be more elegant and/or cleaner and/or somewhere else - private void reduce(GSS.Phase.Node parent, int pos, GSS.Phase target) { - Forest old = holder[pos]; - holder[pos] = parent.pending(); - if (pos==0) { - System.arraycopy(holder, 0, position.holder, 0, holder.length); - for(int i=0; i