X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=d4d5415972c984141db742da684e523a41e4736d;hp=3bafbfe427e33176572a1301ce1d99a40f8fe2b1;hb=24112db237318c030b4d4f457d90c34fd69d652b;hpb=cf349fcf2f460e53ad5f9dd0397eb382c4aa92b2 diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 3bafbfe..d4d5415 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -8,27 +8,42 @@ import java.util.*; /** a parser which translates streams of Tokens of type T into a Forest */ public abstract class Parser { - private final Table pt; + protected final Table pt; /** create a parser to parse the grammar with start symbol u */ protected Parser(Union u, Topology top) { this.pt = new Table(u, top); } - protected Parser(Table pt) { this.pt = pt; } + 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, Token.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(Token.Stream input) throws IOException, ParseFailed { + public Forest parse(Input input) throws IOException, ParseFailed { GSS gss = new GSS(); - Token.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); + Input.Location loc = input.getLocation(); + 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; @@ -40,6 +55,26 @@ public abstract class Parser { /** an SLR(1) parse table which may contain conflicts */ 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; private void walk(Element e, HashSet hs) { @@ -47,11 +82,15 @@ 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 */ @@ -59,19 +98,19 @@ public abstract class Parser { /** used to generate unique values for State.idx */ private int master_state_idx = 0; + HashMap,State> all_states = new HashMap,State>(); /** 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 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); // construct the set of states - HashMap,State> all_states = new HashMap,State>(); HashSet all_elements = new HashSet(); walk(start0, all_elements); for(Element e : all_elements) @@ -102,21 +141,22 @@ 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(); - } + if (top instanceof IntegerTopology) + for(State state : all_states.values()) { + state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor()); + state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor()); + } } 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; @@ -229,6 +269,14 @@ public abstract class Parser { } } + 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+"]: "); @@ -243,10 +291,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;