X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=18bec5a0aebfa2c5179116f1c92617f1162dd04b;hp=1afa523124cdc0de855e0180db47a41bda410daf;hb=21da21b94e794fa4d7c7207327764895d92ea528;hpb=8e38701ecbc92deab21c4c224052ae128b279738 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 1afa523..18bec5a 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -1,12 +1,9 @@ package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; -import edu.berkeley.sbp.*; import edu.berkeley.sbp.Sequence.Position; -import edu.berkeley.sbp.*; import java.io.*; import java.util.*; -import java.lang.reflect.*; /** a parser which translates streams of Tokens of type T into a Forest */ public abstract class Parser { @@ -17,63 +14,29 @@ public abstract class Parser { protected Parser(Union u) { this.pt = new Table(u, top()); } protected Parser(Table pt) { this.pt = pt; } + /** implement this method to create the output forest corresponding to a lone shifted input token */ public abstract Forest shiftedToken(T t, Token.Location loc); - public abstract Topology top(); - - /** parse input for a exactly one unique result, throwing Ambiguous if not unique or Failed if none */ - public Tree parse1(Token.Stream input) throws IOException, Failed, Ambiguous { - Forest ret = parse(input); - try { return ret.expand1(); } - catch (Ambiguous a) { - System.out.println("while expanding:"); - System.out.println(ret); - throw a; - } - } + /** this method must return an empty topology of the input token type */ + public abstract Topology top(); /** parse input, using the table pt to drive the parser */ - public Forest parse(Token.Stream input) throws IOException, Failed { + public Forest parse(Token.Stream input) throws IOException, ParseFailed { 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); + GSS.Phase current = gss.new Phase(null, this, null, input.next(1, 0, 0), loc, null); + current.newNode(null, Forest.leaf(null, null), pt.start, true); + int count = 1; for(;;) { loc = input.getLocation(); - GSS.Phase next = gss.new Phase(current, input.next(), loc); current.reduce(); Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); - current.shift(next, forest); + 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; - current.checkFailure(); current = next; } } - - - // Exceptions ////////////////////////////////////////////////////////////////////////////// - - public static class Failed extends Exception { - private final Token.Location location; - private final String message; - public Failed() { this("", null); } - public Failed(String message, Token.Location loc) { this.location = loc; this.message = message; } - public Token.Location getLocation() { return location; } - public String toString() { return message + (location==null ? "" : (" at " + location)); } - } - - public static class Ambiguous extends RuntimeException { - public final Forest ambiguity; - public Ambiguous(Forest ambiguity) { this.ambiguity = ambiguity; } - public String toString() { - StringBuffer sb = new StringBuffer(); - sb.append("unresolved ambiguity "/*"at " + ambiguity.getLocation() + ":"*/); - for(Object result : ambiguity.expand(false)) - sb.append("\n " + result); - return sb.toString(); - } - } - // Table ////////////////////////////////////////////////////////////////////////////// @@ -81,7 +44,7 @@ public abstract class Parser { static class Table extends Walk.Cache { public final Walk.Cache cache = this; - + private void walk(Element e, HashSet hs) { if (e==null) return; if (hs.contains(e)) return; @@ -115,7 +78,7 @@ public abstract class Parser { HashSet all_elements = new HashSet(); walk(start0, all_elements); for(Element e : all_elements) - cache.ys.put(e, new Walk.YieldSet(e, cache).walk()); + cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); this.start = new State(hp, all_states, all_elements); @@ -128,12 +91,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)) { + if (isRightNullable(p)) { 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,11 +115,31 @@ 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(); + } + } + + 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, Iterable { + + 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; @@ -179,15 +172,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 ////////////////////////////////////////////////////////////////////////////// /** @@ -252,27 +256,14 @@ public abstract class Parser { // "yields" [in one or more step] is used instead of "produces" [in exactly one step] // to avoid having to iteratively construct our set of States as shown in most // expositions of the algorithm (ie "keep doing XYZ until things stop changing"). - /* - for(Element e : all_elements) { - if (e instanceof Atom) continue; - HashSet h = new Walk.Closure(null, g.cache).closure(e, hs); - State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); - if (gotoSetNonTerminals.get(e) != null) - throw new Error("this should not happen"); - gotoSetNonTerminals.put(e, s); - } - */ HashMapBag move = new HashMapBag(); for(Position p : hs) { Element e = p.element(); if (e==null) continue; - HashSet ys = cache.ys.get(e); - if (ys != null) { - for(Element y : ys) { - HashSet hp = new HashSet(); - reachable(p.next(), hp); - move.addAll(y, hp); - } + for(Element y : cache.ys.getAll(e)) { + HashSet hp = new HashSet(); + reachable(p.next(), hp); + move.addAll(y, hp); } } for(Element y : move) { @@ -282,7 +273,13 @@ public abstract class Parser { } } - public String toString() { return "state["+idx+"]"; } + public String toString() { + //return "state["+idx+"]"; + StringBuffer ret = new StringBuffer(); + ret.append("state["+idx+"]: "); + for(Position p : this) ret.append("{"+p+"} "); + return ret.toString(); + } public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } } @@ -311,55 +308,51 @@ 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