X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=3fad1ddacd8c1e7a257d17193b9fcff3973b24b4;hp=6bf274d30ecb6bde3135d9fce9061321c9a63d47;hb=72d5880c192b7fbd525c97ded4cf11e935c58cc8;hpb=96a2822a729e563a64173f22dc184bc972a200ef diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 6bf274d..3fad1dd 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -13,24 +13,11 @@ public abstract class Parser { private final Table pt; - private static void reachable(Element e, HashSet h) { - if (e instanceof Atom) return; - for(Sequence s : ((Union)e)) - reachable(s.firstp(), h); - } - private static void reachable(Position p, HashSet h) { - if (h.contains(p)) return; - h.add(p); - if (p.element() != null) reachable(p.element(), h); - } - - /** - * create a parser to parse the grammar with start symbol u - */ + /** create a parser to parse the grammar with start symbol u */ protected Parser(Union u) { this.pt = new Table(u, top()); } protected Parser(Table pt) { this.pt = pt; } - public abstract Forest shiftedToken(T t); + public abstract Forest shiftedToken(T t, Token.Location loc); public abstract Topology top(); @@ -40,12 +27,14 @@ public abstract class Parser { /** parse input, using the table pt to drive the parser */ public Forest parse(Token.Stream input) throws IOException, Failed { GSS gss = new GSS(); - GSS.Phase current = gss.new Phase(null, input.next()); + Token.Location loc = input.getLocation(); + GSS.Phase current = gss.new Phase(null, input.next(), loc); current.newNode(null, null, pt.start, true, null); for(;;) { - GSS.Phase next = gss.new Phase(current, input.next()); + 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); + Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); current.shift(next, forest); if (current.isDone()) return (Forest)current.finalResult; current.checkFailure(); @@ -62,7 +51,7 @@ public abstract class Parser { 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 + "\n" + location.getContext())); } + public String toString() { return message + (location==null ? "" : (" at " + location)); } } public static class Ambiguous extends RuntimeException { @@ -80,23 +69,10 @@ public abstract class Parser { // Table ////////////////////////////////////////////////////////////////////////////// - static class Top extends Union { public Top() { super("0"); } } - /** an SLR(1) parse table which may contain conflicts */ - static class Table { + static class Table extends Walk.Cache { - private final Union start0 = new Top(); - private final Sequence start0seq; - - public final Walk.Cache cache = new Walk.Cache(); - - public HashSet closure() { - HashSet hp = new HashSet(); - reachable(start0, hp); - return hp; - } - public Position firstPosition() { return start0seq.firstp(); } - public Position lastPosition() { Position ret = start0seq.firstp(); while(!ret.isLast()) ret = ret.next(); return ret; } + public final Walk.Cache cache = this; private void walk(Element e, HashSet hs) { if (e==null) return; @@ -109,21 +85,6 @@ public abstract class Parser { walk(p.element(), hs); } } - public HashSet walk() { - HashSet ret = new HashSet(); - walk(start0, ret); - return ret; - } - - /* - public String toString() { - StringBuffer sb = new StringBuffer(); - for(Element e : walk()) - if (e instanceof Union) - ((Union)e).toString(sb); - return sb.toString(); - } - */ /** the start state */ public final State start; @@ -134,23 +95,29 @@ public abstract class Parser { /** construct a parse table for the given grammar */ public Table(Topology top) { this("s", top); } public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); } - public Table(Union u, Topology top) { - start0seq = new Sequence.Singleton(u, null, null); - start0.add(start0seq); + public Table(Union ux, Topology top) { + Union start0 = new Union("0"); + start0.add(new Sequence.Singleton(ux, null, null)); + + for(Sequence s : start0) cache.eof.put(s, true); + cache.eof.put(start0, true); // construct the set of states HashMap,State> all_states = new HashMap,State>(); - HashSet all_elements = walk(); + HashSet all_elements = new HashSet(); + walk(start0, all_elements); for(Element e : all_elements) cache.ys.put(e, new Walk.YieldSet(e, cache).walk()); - this.start = new State(closure(), all_states, all_elements); + HashSet hp = new HashSet(); + reachable(start0, hp); + this.start = new State(hp, all_states, all_elements); // for each state, fill in the corresponding "row" of the parse table for(State state : all_states.values()) for(Position p : state.hs) { // the Grammar's designated "last position" is the only accepting state - if (p==lastPosition()) + if (start0.contains(p.owner()) && p.next()==null) state.accept = true; // FIXME: how does right-nullability interact with follow restrictions? @@ -236,7 +203,7 @@ public abstract class Parser { Atom a = (Atom)position.element(); HashSet hp = new HashSet(); reachable(position.next(), hp); - bag0.addAll(a, /*clo.walk()*/hp); + bag0.addAll(a, hp); } // Step 1b: for each _minimal, contiguous_ set of characters having an identical next-position @@ -346,4 +313,19 @@ public abstract class Parser { } private static final Forest[] emptyForestArray = new Forest[0]; + + + // Helpers ////////////////////////////////////////////////////////////////////////////// + + private static void reachable(Element e, HashSet h) { + if (e instanceof Atom) return; + for(Sequence s : ((Union)e)) + reachable(s.firstp(), h); + } + private static void reachable(Position p, HashSet h) { + if (h.contains(p)) return; + h.add(p); + if (p.element() != null) reachable(p.element(), h); + } + }