X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FParser.java;h=5c399cc95c63246761ec4581af29816c2a664167;hp=851831345cc1571c3758f5101523f325a6634fe7;hb=c4431d19cc5ddaae29d22c8c56366b53b0bad352;hpb=cbae71f601dd5831cc6bf74a7407cbe067cc604a diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 8518313..5c399cc 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -13,9 +13,7 @@ public abstract class Parser { private final Table pt; - /** - * 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; } @@ -24,7 +22,15 @@ public abstract class Parser { /** 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(); } + 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; + } + } /** parse input, using the table pt to drive the parser */ public Forest parse(Token.Stream input) throws IOException, Failed { @@ -72,9 +78,9 @@ public abstract class Parser { // Table ////////////////////////////////////////////////////////////////////////////// /** an SLR(1) parse table which may contain conflicts */ - static class Table { + static class Table extends Walk.Cache { - public final Walk.Cache cache = new Walk.Cache(); + public final Walk.Cache cache = this; private void walk(Element e, HashSet hs) { if (e==null) return; @@ -88,16 +94,6 @@ public abstract class Parser { } } - /* - 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; @@ -138,7 +134,7 @@ public abstract class Parser { 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); + if (wf.includesEof()) state.eofReductions.add(red); } // if the element following this position is an atom, copy the corresponding @@ -151,14 +147,35 @@ public abstract class Parser { /** a single state in the LR table and the transitions possible from it */ public class State implements Comparable, Iterable { - public final int idx = master_state_idx++; + /* + public boolean isResolvable(Token t) { + boolean found = false; + for(Reduction r : getReductions(t)) { + Position p = r.position; + if (!p.isRightNullable(cache)) continue; + if (p.owner().firstp()==p) continue; + if (found) { + // found two items meeting criteria #1 + return false; + } else { + found = true; + continue; + } + if (p.element()==null) continue; + Topology first = new Walk.First(top(), cache).walk(p.element()); + if (first.contains(t)) + } + } + */ + + public final int idx = master_state_idx++; private final HashSet hs; private transient HashMap gotoSetNonTerminals = new HashMap(); private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); private TopologicalBag reductions = new TopologicalBag(); - private FastSet eofReductions = new FastSet(); + private HashSet eofReductions = new HashSet(); private TopologicalBag shifts = new TopologicalBag(); private boolean accept = false; @@ -167,7 +184,8 @@ public abstract class Parser { 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 reductions.get(t); } + public Iterable getReductions(Token t) { return t==null ? eofReductions : reductions.get(t); } + public boolean hasReductions(Token t) { return t==null ? eofReductions.size()>0 : reductions.has(t); } public Iterable getEofReductions() { return eofReductions; } public Iterator iterator() { return hs.iterator(); } @@ -277,7 +295,7 @@ public abstract class Parser { public class Reduction { // FIXME: cleanup; almost everything in here could go in either Sequence.Position.getRewrite() or else in GSS.Reduct public final int numPop; - private final Position position; + /*private*/ final Position position; private final Forest[] holder; // to avoid constant reallocation public int hashCode() { return position.hashCode(); } public boolean equals(Object o) { @@ -293,33 +311,46 @@ public abstract class Parser { this.holder = new Forest[numPop]; } public String toString() { return "[reduce " + position + "]"; } - public Forest reduce(Forest f, GSS.Phase.Node parent, GSS.Phase.Node onlychild, GSS.Phase target, Forest rex) { - holder[numPop-1] = f; - return reduce(parent, numPop-2, rex, onlychild, target); + + private Forest zero = null; + public Forest zero() { + if (zero != null) return zero; + if (numPop > 0) throw new Error(); + return zero = position.rewrite(null); } - public Forest reduce(GSS.Phase.Node parent, GSS.Phase.Node onlychild, GSS.Phase target, Forest rex) { - return reduce(parent, numPop-1, rex, onlychild, target); + + public void reduce(GSS.Phase.Node parent) { + if (numPop==0) finish(parent, zero(), parent.phase()); + else reduce(parent, numPop-1, parent.phase()); } - // 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.Node onlychild, GSS.Phase target) { - if (pos>=0) holder[pos] = parent.pending(); - if (pos<=0 && rex==null) { + 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; + holder[pos] = parent.pending(); + if (pos==0) { System.arraycopy(holder, 0, position.holder, 0, holder.length); - rex = position.rewrite(target.getLocation()); + finish(onlychild, position.rewrite(parent.phase().getLocation()), parent.phase()); + } else { + reduce(onlychild, pos-1, parent.phase()); } - if (pos >=0) { - if (onlychild != null) - reduce(onlychild, pos-1, rex, null, target); - else - for(GSS.Phase.Node child : parent.parents()) - reduce(child, pos-1, rex, null, target); + } + + // FIXME: this could be more elegant and/or cleaner and/or somewhere else + private void reduce(GSS.Phase.Node parent, int pos, GSS.Phase target) { + holder[pos] = parent.pending(); + if (pos==0) { + System.arraycopy(holder, 0, position.holder, 0, holder.length); + Forest rex = position.rewrite(target.getLocation()); + for(GSS.Phase.Node child : parent.parents()) finish(child, rex, target); } else { - State state = parent.state.gotoSetNonTerminals.get(position.owner()); - if (state!=null) - target.newNode(parent, rex, state, numPop<=0, parent.phase); + for(GSS.Phase.Node child : parent.parents()) reduce(child, pos-1, target); } - return rex; + } + private void finish(GSS.Phase.Node parent, Forest result, GSS.Phase target) { + State state = parent.state.gotoSetNonTerminals.get(position.owner()); + if (state!=null) + target.newNode(parent, result, state, numPop<=0, parent.phase()); } } }