X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=fac14b0e78e251ff76b6f12254eb9b17cae4fce4;hp=1afa523124cdc0de855e0180db47a41bda410daf;hb=9ded11559a1b6f817e99355b1c9e2c88042e91d4;hpb=8e38701ecbc92deab21c4c224052ae128b279738 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 1afa523..fac14b0 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -37,7 +37,7 @@ public abstract class Parser { GSS gss = new GSS(); Token.Location loc = input.getLocation(); GSS.Phase current = gss.new Phase(null, input.next(), loc); - current.newNode(null, null, pt.start, true, null); + current.newNode(null, null, pt.start, true); for(;;) { loc = input.getLocation(); GSS.Phase next = gss.new Phase(current, input.next(), loc); @@ -128,12 +128,22 @@ public abstract class Parser { if (start0.contains(p.owner()) && p.next()==null) state.accept = true; - // FIXME: how does right-nullability interact with follow restrictions? - // all right-nullable rules get a reduction [Johnstone 2000] if (p.isRightNullable(cache)) { 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); + + 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); } @@ -142,6 +152,10 @@ public abstract class Parser { if (p.element() != null && p.element() instanceof Atom) state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()))); } + for(State state : all_states.values()) { + state.oreductions = state.reductions.optimize(); + state.oshifts = state.shifts.optimize(); + } } /** a single state in the LR table and the transitions possible from it */ @@ -179,15 +193,26 @@ public abstract class Parser { private TopologicalBag shifts = new TopologicalBag(); private boolean accept = false; + private VisitableMap oshifts = null; + private VisitableMap oreductions = null; + // Interface Methods ////////////////////////////////////////////////////////////////////////////// - public boolean canShift(Token t) { return shifts.contains(t); } - public Iterable getShifts(Token t) { return shifts.get(t); } public boolean isAccepting() { return accept; } - public Iterable getReductions(Token t) { return t==null ? eofReductions : reductions.get(t); } - public Iterable getEofReductions() { return eofReductions; } + + public boolean canShift(Token t) { return oshifts.contains(t); } + public boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } + public Iterator iterator() { return hs.iterator(); } + public 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) { + if (t==null) for(Reduction r : eofReductions) irbc.invoke(r, b, c); + else oreductions.invoke(t, irbc, b, c); + } + // Constructor ////////////////////////////////////////////////////////////////////////////// /** @@ -311,55 +336,50 @@ public abstract class Parser { } public String toString() { return "[reduce " + position + "]"; } - public Forest reduce(GSS.Phase.Node parent) { - if (numPop==0) return finish(parent, zero(), parent.phase()); - return reduce(parent, numPop-1, null, parent.phase()); + private Forest zero = null; + public Forest zero() { + if (zero != null) return zero; + if (numPop > 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 Forest reduce(GSS.Phase.Node parent, GSS.Phase.Node onlychild) { + 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(); - Forest rex = null; if (pos==0) { - if (rex==null) { - System.arraycopy(holder, 0, position.holder, 0, holder.length); - rex = position.rewrite(parent.phase().getLocation()); - } + 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()); } - return reduce(onlychild, pos-1, rex, parent.phase()); - } - - private Forest zero = null; - public Forest zero() { - if (zero != null) return zero; - if (numPop > 0) throw new Error(); - return zero = position.rewrite(null); + holder[pos] = old; } // FIXME: this could be more elegant and/or cleaner and/or somewhere else - private Forest reduce(GSS.Phase.Node parent, int pos, Forest rex, GSS.Phase target) { - if (pos>=0) holder[pos] = parent.pending(); + private void reduce(GSS.Phase.Node parent, int pos, GSS.Phase target) { + Forest old = holder[pos]; + holder[pos] = parent.pending(); if (pos==0) { - if (rex==null) { - System.arraycopy(holder, 0, position.holder, 0, holder.length); - rex = position.rewrite(target.getLocation()); - } - for(GSS.Phase.Node child : parent.parents()) - reduce(child, pos-1, rex, target); - } else if (pos>0) { - for(GSS.Phase.Node child : parent.parents()) - reduce(child, pos-1, rex, target); + System.arraycopy(holder, 0, position.holder, 0, holder.length); + for(int i=0; i