X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=2344e15b96c2cb9f451c27f248edc3e04c15978f;hp=632729e3744b5984b6c1bf9c5a2ea923f7c72b44;hb=ae0cef03f2e46f6ae6438f9a3e60ca36ff1a4643;hpb=c7af09d552a9cf2d53a72baa975c9a73384813ea diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 632729e..2344e15 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -15,20 +15,35 @@ public abstract class Parser { 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 shiftToken(Tok t, Input.Location loc); + protected abstract Forest shiftToken(Tok t, Input.Location newloc); + + boolean helpgc = true; + + public String toString() { return pt.toString(); } /** parse input, using the table pt to drive the parser */ public Forest parse(Input input) throws IOException, ParseFailed { GSS gss = new GSS(); Input.Location loc = input.getLocation(); - 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); + GSS.Phase current = gss.new Phase(null, this, null, input.next(), loc, null); + current.newNode(null, Forest.create(null, null, null, false), pt.start, true); int count = 1; - for(;;) { + for(int idx=0;;idx++) { + Input.Location oldloc = loc; loc = input.getLocation(); current.reduce(); Forest forest = current.token==null ? null : shiftToken((Tok)current.token, loc); - GSS.Phase next = gss.new Phase(current, this, current, input.next(count, gss.resets, gss.waits), loc, forest); + GSS.Phase next = gss.new Phase(current, this, current, input.next(), loc, forest); + if (!helpgc) { + FileOutputStream fos = new FileOutputStream("out-"+idx+".dot"); + PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); + GraphViz gv = new GraphViz(); + for(Object n : next) + ((GSS.Phase.Node)n).toGraphViz(gv); + gv.dump(p); + p.flush(); + p.close(); + } count = next.size(); if (current.isDone()) return (Forest)gss.finalResult; current = next; @@ -38,7 +53,27 @@ public abstract class Parser { // Table ////////////////////////////////////////////////////////////////////////////// /** an SLR(1) parse table which may contain conflicts */ - public static class Table extends Walk.Cache { + static class Table extends Walk.Cache { + + public String toString() { + StringBuffer sb = new StringBuffer(); + sb.append("parse table"); + for(State state : all_states.values()) { + sb.append(" " + state + "\n"); + for(Topology t : state.shifts) { + sb.append(" shift \""+ + new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => "); + for(State st : state.shifts.getAll(t)) + sb.append(st.idx+" "); + sb.append("\n"); + } + for(Topology t : state.reductions) + sb.append(" reduce \""+ + new edu.berkeley.sbp.chr.CharTopology((IntegerTopology)t)+"\" => " + + state.reductions.getAll(t) + "\n"); + } + return sb.toString(); + } public final Walk.Cache cache = this; @@ -47,15 +82,22 @@ public abstract class Parser { if (hs.contains(e)) return; hs.add(e); if (e instanceof Atom) return; - for(Sequence s : (Union)e) { - hs.add(s); - for(Position p = s.firstp(); p != null; p = p.next()) - walk(p.element(), hs); - } + for(Sequence s : (Union)e) + walk(s, hs); + } + private void walk(Sequence s, HashSet hs) { + hs.add(s); + for(Position p = s.firstp(); p != null; p = p.next()) + walk(p.element(), hs); + for(Sequence ss : s.needs()) walk(ss, hs); + for(Sequence ss : s.hates()) walk(ss, hs); } /** the start state */ - public final State start; + public final State start; + + /** the state from which no reductions can be done */ + private final State dead_state; /** used to generate unique values for State.idx */ private int master_state_idx = 0; @@ -66,7 +108,7 @@ public abstract class Parser { public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); } public Table(Union ux, Topology top) { Union start0 = new Union("0"); - start0.add(new Sequence.Singleton(ux, null, null)); + start0.add(new Sequence.Singleton(ux)); for(Sequence s : start0) cache.eof.put(s, true); cache.eof.put(start0, true); @@ -78,6 +120,8 @@ public abstract class Parser { cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk()); HashSet hp = new HashSet(); reachable(start0, hp); + + this.dead_state = new State(new HashSet(), all_states, all_elements); this.start = new State(hp, all_states, all_elements); // for each state, fill in the corresponding "row" of the parse table @@ -111,13 +155,13 @@ public abstract class Parser { private boolean isRightNullable(Position p) { if (p.isLast()) return true; - if (!p.element().possiblyEpsilon(this)) return false; + if (!possiblyEpsilon(p.element())) 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 { + class State implements Comparable>, IntegerMappable, Iterable { public final int idx = master_state_idx++; private final HashSet hs; @@ -135,15 +179,15 @@ public abstract class Parser { // Interface Methods ////////////////////////////////////////////////////////////////////////////// - boolean isAccepting() { return accept; } - public Iterator iterator() { return hs.iterator(); } + boolean isAccepting() { return accept; } + public Iterator iterator() { return hs.iterator(); } - boolean canShift(Tok t) { return oshifts.contains(t); } + boolean canShift(Tok t) { return oshifts!=null && oshifts.contains(t); } void invokeShifts(Tok t, Invokable,B,C> irbc, B b, C c) { oshifts.invoke(t, irbc, b, c); } - boolean canReduce(Tok t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } + boolean canReduce(Tok t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); } void invokeReductions(Tok t, Invokable irbc, B b, C c) { if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c); else oreductions.invoke(t, irbc, b, c); @@ -213,6 +257,7 @@ 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"). + HashMapBag move = new HashMapBag(); for(Position p : hs) { Element e = p.element(); @@ -226,10 +271,22 @@ public abstract class Parser { for(Element y : move) { HashSet h = move.getAll(y); State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); - gotoSetNonTerminals.put(y, s); + // if a reduction is "lame", it should wind up in the dead_state after reducing + if (y instanceof Sequence && ((Sequence)y).lame) + ((HashMap)gotoSetNonTerminals).put(y, dead_state); + else + gotoSetNonTerminals.put(y, s); } } + public String toStringx() { + StringBuffer st = new StringBuffer(); + for(Position p : this) { + if (st.length() > 0) st.append("\n"); + st.append(p); + } + return st.toString(); + } public String toString() { StringBuffer ret = new StringBuffer(); ret.append("state["+idx+"]: "); @@ -244,10 +301,15 @@ public abstract class Parser { // Helpers ////////////////////////////////////////////////////////////////////////////// + private static void reachable(Sequence s, HashSet h) { + reachable(s.firstp(), h); + for(Sequence ss : s.needs()) reachable(ss, h); + for(Sequence ss : s.hates()) reachable(ss, h); + } private static void reachable(Element e, HashSet h) { if (e instanceof Atom) return; for(Sequence s : ((Union)e)) - reachable(s.firstp(), h); + reachable(s, h); } private static void reachable(Position p, HashSet h) { if (h.contains(p)) return;