X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=5b31b3103459251c690eaa34f5000717b2217ba5;hp=046e725fcd90da6543f03d7eee099f4b4a97071c;hb=888e9ccbab5f458a727c16da9d9291fd8951d909;hpb=0a0227b9180534d2a431f3d6e08a398bde2244c4 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 046e725..5b31b31 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -9,20 +9,19 @@ import java.util.*; import java.lang.reflect.*; /** a parser which translates streams of Tokens of type T into a Forest */ -public class Parser { +public abstract class Parser { private final Table pt; - //public Parser( Topology top) { this(new Table( top)); } - //public Parser(String s, Topology top) { this(new Table(s, top)); } - /** * create a parser to parse the grammar with start symbol u - * @param top a "sample" Topology that can be cloned (FIXME, demanding this is lame) */ - public Parser(Union u, Topology top) { this(new Table(u, top)); } + protected Parser(Union u) { this.pt = new Table(u, top()); } + protected Parser(Table pt) { this.pt = pt; } + + public abstract Forest shiftedToken(T t, Token.Location loc); + public abstract Topology top(); - Parser(Table pt) { this.pt = pt; } /** 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 { return parse(input).expand1(); } @@ -30,12 +29,15 @@ public 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(); - current.shift(next); + Forest forest = current.token==null ? null : shiftedToken((T)current.token, loc); + current.shift(next, forest); if (current.isDone()) return (Forest)current.finalResult; current.checkFailure(); current = next; @@ -51,7 +53,7 @@ public 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 { @@ -72,19 +74,16 @@ public class Parser { /** an SLR(1) parse table which may contain conflicts */ static class Table { - private final Union start0 = new Top(); + private final Union start0 = new Union("0"); private final Sequence start0seq; - static class Top extends Union { public Top() { super("0"); } } public final Walk.Cache cache = new Walk.Cache(); public HashSet closure() { HashSet hp = new HashSet(); - start0.reachable(hp); + 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; } private void walk(Element e, HashSet hs) { if (e==null) return; @@ -123,12 +122,16 @@ public class Parser { public Table(Topology top) { this("s", top); } public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); } public Table(Union u, Topology top) { + cache.eof.put(start0, true); start0seq = new Sequence.Singleton(u, null, null); + cache.eof.put(start0seq, true); start0.add(start0seq); // construct the set of states HashMap,State> all_states = new HashMap,State>(); HashSet all_elements = walk(); + all_elements.add(start0); + all_elements.add(start0seq); for(Element e : all_elements) cache.ys.put(e, new Walk.YieldSet(e, cache).walk()); this.start = new State(closure(), all_states, all_elements); @@ -138,13 +141,13 @@ public class Parser { for(Position p : state.hs) { // the Grammar's designated "last position" is the only accepting state - if (p==lastPosition()) + if (p==start0seq.firstp().next()) 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.fresh(), p.owner(), all_elements, 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); if (wf.includesEof()) state.eofReductions.add(red, true); @@ -153,7 +156,7 @@ public class Parser { // if the element following this position is an atom, copy the corresponding // set of rows out of the "master" goto table and into this state's shift table if (p.element() != null && p.element() instanceof Atom) - state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).top())); + state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()))); } } @@ -223,8 +226,8 @@ public class Parser { if (position.isLast() || !(position.element() instanceof Atom)) continue; Atom a = (Atom)position.element(); HashSet hp = new HashSet(); - position.next().reachable(hp); - bag0.addAll(a.top(), /*clo.walk()*/hp); + reachable(position.next(), hp); + bag0.addAll(a, hp); } // Step 1b: for each _minimal, contiguous_ set of characters having an identical next-position @@ -262,7 +265,7 @@ public class Parser { if (ys != null) { for(Element y : ys) { HashSet hp = new HashSet(); - p.next().reachable(hp); + reachable(p.next(), hp); move.addAll(y, hp); } } @@ -334,4 +337,19 @@ public 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); + } + }