class GSS {
Input input;
- public GSS(Input input) { this.input = input; }
+ private Parser parser;
+ public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
public Input getInput() { return input; }
- // FIXME: right now, these are the performance bottleneck
- HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
-
- /** FIXME */
- Forest.Many finalResult;
+ int numNewNodes = 0;
+ int numOldNodes = 0;
+ int viewPos = 0;
+ int numReductions = 0;
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
- class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+ class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+
+ // FIXME: right now, these are the performance bottleneck
+ private HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
- public PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
+ public Forest.Many finalResult;
+ private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
- public void invoke(State st, Result result, Object o) {
- //shifts++;
+ public void addReduction(Reduction r) {
+ //System.out.println("+ " + r);
+ parser.spin();
+ reductionQueue.add(r);
+ }
+ public void invoke(State st, Result result) {
+ parser.spin();
good |= next.newNode(result, st, false);
}
final Tok token;
final int pos;
- public IntPairMap<Node> hash; /* ALLOC */
- private boolean good;
+ public IntPairMap<Node> hash = new IntPairMap<Node>(); /* ALLOC */
+ private boolean good = false;
private Phase next = null;
private Phase prev;
private Input.Location location;
private Forest forest;
- public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
- Input.Location nextLocation, Forest forest) throws ParseFailed {
+ public Phase(State startState) throws ParseFailed, IOException {
+ this(null, null);
+ Result primordealResult = new Result(null, null, null);
+ newNode(primordealResult, startState, true);
+ }
+ public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
+ this.location = input.getLocation();
+ this.token = (Tok)input.next();
this.prevLocation = prev==null ? location : prev.getLocation();
this.prev = prev;
this.forest = forest;
- this.pos = previous==null ? 0 : previous.pos+1;
- this.token = token;
- this.location = location;
- this.nextLocation = nextLocation;
- performed.clear();
- hash = new IntPairMap<Node>();
- good = false;
- finalResult = null;
+ this.pos = prev==null ? 0 : prev.pos+1;
+ this.nextLocation = input.getLocation();
if (prev != null) prev.shift(this, forest);
+ numReductions = 0;
+
+ int minPhasePos = Integer.MAX_VALUE;
+ int maxOrd = -1;
+ Reduction best = null;
+ //System.out.println("==============================================================================");
+ while(!reductionQueue.isEmpty()) {
+ Reduction r = reductionQueue.poll();
+ //System.out.println("- " + r);
+ if (r.parentPhase() != null)
+ if (r.parentPhase().pos > minPhasePos)
+ throw new Error();
+ r.perform();
+ if (r.parentPhase() != null) {
+ if (r.parentPhase().pos < minPhasePos) {
+ minPhasePos = r.parentPhase().pos;
+ maxOrd = r.reduction().ord;
+ best = r;
+ } else if (r.parentPhase().pos == minPhasePos) {
+ /*
+ if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
+ throw new Error("\n"+r+"\n"+best+"\n"+
+ Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
+ "\n"+(r.reduction().ord-best.reduction().ord));
+ */
+ maxOrd = r.reduction().ord;
+ best = r;
+ }
+ }
+ numReductions++;
+ }
+ if (token==null) shift(null, null);
}
- public boolean isFrontier() { return next==null; }
public boolean isDone() throws ParseFailed {
if (token != null) return false;
if (token==null && finalResult==null)
public Input.Location getLocation() { return location; }
public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); }
public Input.Location getNextLocation() { return nextLocation; }
+ public boolean isFrontier() { return hash!=null; }
/** perform all shift operations, adding promoted nodes to <tt>next</tt> */
- public void shift(Phase next, Forest result) throws ParseFailed {
- // this massively improves GC performance
- if (prev!=null) prev.hash = null;
+ private void shift(Phase next, Forest result) throws ParseFailed {
this.next = next;
+ // this massively improves GC performance
+ if (prev != null) {
+ IntPairMap<Node> h = prev.hash;
+ prev.hash = null;
+ prev.performed = null;
+ for(Node n : h)
+ n.check();
+ }
+ numOldNodes = hash.size();
for(Node n : hash.values()) {
if (token == null && n.state().isAccepting()) {
if (finalResult==null) finalResult = new Forest.Many();
finalResult.merge(r.getForest());
}
if (token == null) continue;
- n.state().invokeShifts(token, this, new Result(result, n, null), null);
+ n.state().invokeShifts(token, this, new Result(result, n, null));
}
- for(Node n : hash.values()) n.check();
+ numNewNodes = next==null ? 0 : next.hash.size();
+ viewPos = this.pos;
if (!good && token!=null) ParseFailed.error("unexpected character", this);
if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
+ for(Node n : hash) n.check();
}
- /** perform all reduction operations */
- public void reduce() throws ParseFailed {
- while(!reductionQueue.isEmpty())
- reductionQueue.poll().perform();
- }
-
- public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {
+ void newNodeFromReduction(Result result, State state, Position reduction) {
int pos = result.phase().pos;
Sequence owner = reduction.owner();
- for(Sequence s : owner.hates)
+ for(Sequence s : owner.hates())
if (performed.contains(pos, s))
return;
- for(Sequence s : owner.needs)
+ for(Sequence s : owner.needs())
if (!performed.contains(pos, s))
return;
if (owner.needed_or_hated && !performed.contains(pos, owner))
performed.add(pos, owner);
if (state!=null)
- newNode(result, state, fromEmptyReduction);
+ newNode(result, state, reduction.pos<=0);
}
/** add a new node (merging with existing nodes if possible)
* @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
- public boolean newNode(Result result, State state, boolean fromEmptyReduction) {
+ private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
Node p = hash.get(state, result.phase());
- if (p != null) { p.merge(result); return true; }
+ if (p != null) { p.addResult(result); return true; }
do {
if (token != null && state.canShift(token)) break;
if (state.isAccepting()) break;
if (token==null) break;
if (!state.canReduce(token)) return false;
} while(false);
- new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
+ Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
+ for(Object s : state.also)
+ newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
return true;
}
public boolean isTransparent() { return false; }
public boolean isHidden() { return false; }
+ public void dumpGraphViz(String filename) throws IOException {
+ FileOutputStream fos = new FileOutputStream(filename);
+ PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
+ GraphViz gv = new GraphViz();
+ for(Object n : this)
+ ((Node)n).toGraphViz(gv);
+ gv.dump(p);
+ p.flush();
+ p.close();
+ }
+
}
}
/** a node in the GSS */
final class Node
- implements Invokable<Position, Boolean, Result>,
+ implements Invokable<Position, Result>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
/** which GSS.Phase this Node belongs to */
- public GSS.Phase phase() { return phase; }
+ public GSS.Phase phase() { return phase; }
public Iterator<Result> iterator() { return results.iterator(); }
public Parser.Table.State state() { return state; }
public int toInt() { return idx; }
- public boolean merge(Result r) {
- if (results.contains(r)) return true;
- results.add(r);
- r.addChild(this);
- if (fromEmptyReduction) return false;
- state.invokeReductions(phase().getToken(), this, false, r);
- return false;
- }
+ boolean destroyed = false;
- private boolean destroyed = false;
- public boolean check() {
+ public void check() {
+ if (destroyed) return;
boolean dead = true;
// - all nodes must have a parent
// - non-doomed nodes must either:
// - be on the frontier or
// - have a non-doomed node closer to the frontier than themself
-
if (phase.isFrontier()) dead = false;
for(Result r : children)
- if (state.doomed) { if (r.usedByAnyNode()) dead = false; }
- else { if (r.usedByNonDoomedNode()) dead = false; }
+ if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } }
+ else { if (r.usedByNonDoomedNode()) { dead = false; break; } }
dead |= results.size()==0;
- if (!dead || destroyed) return dead;
+ if (!dead || destroyed) return;
destroyed = true;
while(children.size()>0)
for(Result r : children) {
for(Result r : results) {
results.remove(r);
r.removeChild(this);
- r.check();
break;
}
- return dead;
+ results = null;
+ children = null;
}
//////////////////////////////////////////////////////////////////////
//private FastSet<Result> results = new FastSet<Result>();
private HashSet<Result> results = new HashSet<Result>();
private HashSet<Result> children = new HashSet<Result>();
- public void removeChild(Result child) { children.remove(child); }
- public void removeResult(Result result) { results.remove(result); }
- public void addChild(Result child) { children.add(child); }
- public final void invoke(Position r, Boolean emptyProductions, Result only) {
+ public final void invoke(Position r, Result only) {
+ boolean emptyProductions = only==null;
if (emptyProductions != (r.pos==0)) return;
- if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase());
+ if (r.pos==0) new Result(r.zero(phase().getLocation().createRegion(phase().getLocation())), this, r, phase());
else reduce(r, r.pos-1, phase(), only);
}
private void reduce(Position r, int pos, GSS.Phase target, Result only) {
Forest[] holder = r.holder;
Forest old = holder[pos];
+ if (results==null) return; // FIXME: this should not happen
for(Result res : results)
if (only == null || res == only) {
Node child = res.parent();
holder[pos] = old;
}
- void finish(Position r, Forest forest, GSS.Phase target) {
- Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
- Result result = new Result(forest, this, r);
- target.newNodeFromReduction(result, state0, r.pos<=0, r);
- }
-
Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
this.phase = phase;
this.state = state;
this.fromEmptyReduction = fromEmptyReduction;
- results.add(result);
- result.addChild(this);
if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
phase.hash.put(state, result.phase(), this);
+ addResult(result);
+ state.invokeEpsilonReductions(phase().token, this);
+ }
- for(Object s : state.also)
- phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction);
+ // Add/Remove Children/Results //////////////////////////////////////////////////////////////////////////////
- state.invokeReductions(phase().token, this, true, null);
- if (!fromEmptyReduction)
- state.invokeReductions(phase().getToken(), this, false, null);
+ public void removeChild(Result child) {
+ if (children==null) return;
+ children.remove(child);
+ check();
+ }
+ public void removeResult(Result result) {
+ if (results==null) return;
+ results.remove(result);
+ check();
+ }
+ public void addChild(Result child) {
+ if (children==null) return; // FIXME: this should not happen
+ children.add(child);
+ }
+ public void addResult(Result r) {
+ if (results.contains(r)) return;
+ results.add(r);
+ r.addChild(this);
+ if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r);
}
// GraphViz //////////////////////////////////////////////////////////////////////////////
/** a parser which translates an Input<Token> into a Forest<NodeType> */
public abstract class Parser<Token, NodeType> {
+
protected final Table<Token> pt;
/** create a parser to parse the grammar with start symbol <tt>u</tt> */
public Parser(Union u, Topology<Token> top) { this.pt = new Table<Token>(u, top); }
- Parser(Table<Token> pt) { this.pt = pt; }
/** implement this method to create the output forest corresponding to a lone shifted input token */
public abstract Forest<NodeType> shiftToken(Token t, Input.Location newloc);
- boolean helpgc = true;
-
public String toString() { return pt.toString(); }
- /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
- public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
- GSS gss = new GSS(input);
- Input.Location loc = input.getLocation();
- Token tok = input.next();
- GSS.Phase current = gss.new Phase<Token>(null, null, tok, loc, input.getLocation(), null);
- current.newNode(new Result(Forest.create(loc.createRegion(loc), null, null, false), null, null), pt.start, true);
- int count = 1;
- for(int idx=0;;idx++) {
- Input.Location oldloc = loc;
- current.reduce();
- Forest forest = current.token==null ? null : shiftToken((Token)current.token, loc);
- loc = input.getLocation();
- Token nextToken = input.next();
- GSS.Phase next = gss.new Phase<Token>(current, current, nextToken, loc, input.getLocation(), forest);
-
- /*
- FileOutputStream fos = new FileOutputStream("out-"+idx+".dot");
- PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
- GraphViz gv = new GraphViz();
- for(Object n : current)
- ((Node)n).toGraphViz(gv);
- gv.dump(p);
- p.flush();
- p.close();
- */
-
- count = next.size();
- if (current.isDone()) return (Forest<NodeType>)gss.finalResult;
- current = next;
+ private boolean verbose = false;;
+ private static final char[] spin = new char[] { '-', '\\', '|', '/' };
+ private int spinpos = 0;
+ private long last = 0;
+ void spin() {
+ if (verbose) {
+ long now = System.currentTimeMillis();
+ if (now-last < 100) return;
+ last = now;
+ System.err.print("\r " + spin[spinpos++ % (spin.length)]+ANSI.clreol()+"\r");
}
}
- // Table //////////////////////////////////////////////////////////////////////////////
-
- /** an SLR(1) parse table which may contain conflicts */
- static class Table<Token> extends Walk.Cache {
-
- public String toString() {
- StringBuffer sb = new StringBuffer();
- sb.append("parse table");
- for(State<Token> state : all_states) {
- sb.append(" " + state + "\n");
- for(Topology<Token> t : state.shifts) {
- sb.append(" shift \""+
- new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => ");
- for(State st : state.shifts.getAll(t))
- sb.append(st.idx+" ");
- sb.append("\n");
+ /** parse <tt>input</tt>, and return the shared packed parse forest (or throw an exception) */
+ public Forest<NodeType> parse(Input<Token> input) throws IOException, ParseFailed {
+ verbose = System.getProperty("sbp.verbose", null) != null;
+ spinpos = 0;
+ try {
+ GSS gss = new GSS(input, this);
+ for(GSS.Phase current = gss.new Phase<Token>(pt.start); ;) {
+
+ if (verbose) {
+ String s;
+ s = " " + spin[spinpos++ % (spin.length)]+" parsing ";
+ s += input.getName();
+ s += " "+input.getLocation();
+ while(s.indexOf(':') != -1 && s.indexOf(':') < 8) s = " " + s;
+ String y = "@"+gss.viewPos+" ";
+ while(y.length() < 9) y = " " + y;
+ s += y;
+ //s += " doom="+Node.doomedNodes;
+ //while(s.length() < 40) s = s + " ";
+ s += " nodes="+gss.numOldNodes;
+ while(s.length() < 50) s = s + " ";
+ s += " shifted="+gss.numNewNodes;
+ while(s.length() < 60) s = s + " ";
+ s += " reductions="+gss.numReductions;
+ System.err.print("\r"+s+ANSI.clreol()+"\r");
}
- for(Topology<Token> t : state.reductions)
- sb.append(" reduce \""+
- new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => " +
- state.reductions.getAll(t) + "\n");
- for(Sequence s : state.gotoSetNonTerminals.keySet())
- sb.append(" goto "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n");
+
+ // FIXME: make sure all the locations line up properly in here
+ if (current.isDone()) return (Forest<NodeType>)current.finalResult;
+ Forest forest = shiftToken((Token)current.token, input.getLocation());
+ current = gss.new Phase<Token>(current, forest);
}
- return sb.toString();
+ } finally {
+ if (verbose)
+ System.err.print("\r \r");
}
+ }
- public final Walk.Cache cache = this;
- private void walk(Element e, HashSet<SequenceOrElement> hs) {
- if (e==null) return;
- if (hs.contains(e)) return;
- hs.add(e);
- if (e instanceof Atom) return;
- for(Sequence s : (Union)e)
- walk(s, hs);
- }
- private void walk(Sequence s, HashSet<SequenceOrElement> 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);
- }
+ // Table //////////////////////////////////////////////////////////////////////////////
+
+ /** an SLR(1) parse table which may contain conflicts */
+ static class Table<Token> extends Cache {
/** the start state */
public final State<Token> start;
HashSet<State<Token>> all_states = new HashSet<State<Token>>();
HashMap<HashSet<Position>,State<Token>> doomed_states = new HashMap<HashSet<Position>,State<Token>>();
HashMap<HashSet<Position>,State<Token>> normal_states = new HashMap<HashSet<Position>,State<Token>>();
- HashSet<SequenceOrElement> all_elements = new HashSet<SequenceOrElement>();
/** 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) {
+ super(ux, top);
Union start0 = new Union("0");
- start0.add(new Sequence.Singleton(ux));
-
- for(Sequence s : start0) cache.eof.put(s, true);
- cache.eof.put(start0, true);
+ Sequence seq0 = new Sequence.Singleton(ux);
+ start0.add(seq0);
+ buildFollowSet(seq0, top, true);
// construct the set of states
- walk(start0, all_elements);
- for(SequenceOrElement e : all_elements)
- cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk());
- for(SequenceOrElement e : all_elements)
- cache.ys2.addAll(e, new Walk.YieldSet2(e, cache).walk());
HashSet<Position> hp = new HashSet<Position>();
reachable(start0, hp);
state.accept = true;
if (isRightNullable(p)) {
- Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache);
- Topology follow = wf.walk(p.owner());
+ Topology<Token> follow = (Topology<Token>)follow(p.owner());
for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) {
- Atom set = new Walk.EpsilonFollowSet(new edu.berkeley.sbp.chr.CharAtom(top.empty().complement()),
- new edu.berkeley.sbp.chr.CharAtom(top.empty()),
- cache).walk(p2.element());
- follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element()));
+ if (!(p2.element() instanceof Union)) throw new Error("impossible");
+ Union u = (Union)p2.element();
+ Atom set = new edu.berkeley.sbp.chr.CharAtom(new edu.berkeley.sbp.chr.CharTopology((Topology<Character>)epsilonFollowSet(u)));
+ Element p2e = p2.element();
+ if (p2e instanceof Union)
+ for(Sequence p2es : ((Union)p2e))
+ follow = follow.intersect(follow(p2es));
if (set != null) follow = follow.intersect(set.getTokenTopology());
}
state.reductions.put(follow, p);
- if (wf.includesEof()) state.eofReductions.add(p);
+ if (followEof.contains(p.owner())) state.eofReductions.add(p);
}
// if the element following this position is an atom, copy the corresponding
}
// crude algorithm to assing an ordinal ordering to every position
+ // al will be sorted in DECREASING order (al[0] >= al[1])
ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
for(State s : all_states) {
for(Object po : s) {
if (al.contains(p)) continue;
int i=0;
for(; i<al.size(); i++) {
- if (p.compareTo(al.get(i), cache) > 0)
+ if (comparePositions(p, al.get(i)) < 0)
break;
}
al.add(i, p);
}
}
- for(int i=0; i<al.size(); i++)
- al.get(i).ord = i;
- }
+ // FIXME: this actually pollutes the "pure" objects (the ones that should not be modified by the Parser)
+ // sort in increasing order...
+ OUTER: while(true) {
+ for(int i=0; i<al.size(); i++)
+ for(int j=i+1; j<al.size(); j++)
+ if (comparePositions(al.get(i), al.get(j)) > 0) {
+ Sequence.Position p = al.remove(j);
+ al.add(i, p);
+ continue OUTER;
+ }
+ break;
+ }
+
+ int j = 1;
+ int pk = 0;
+ for(int i=0; i<al.size(); i++) {
+ boolean inc = false;
+ for(int k=pk; k<i; k++) {
+ if (comparePositions(al.get(k), al.get(i)) > 0)
+ { inc = true; break; }
+ }
+ inc = true;
+ if (inc) {
+ j++;
+ pk = i;
+ }
+ al.get(i).ord = j;
+ }
- private boolean isRightNullable(Position p) {
- if (p.isLast()) return true;
- if (!possiblyEpsilon(p.element())) return false;
- return isRightNullable(p.next());
+ /*
+ for(int i=0; i<al.size(); i++)
+ if (isRightNullable(al.get(i)))
+ System.out.println(al.get(i).ord + " " + al.get(i));
+ */
+ //mastercache = this;
}
/** a single state in the LR table and the transitions possible from it */
-
class State<Token> implements IntegerMappable, Iterable<Position> {
public final int idx = master_state_idx++;
private final HashSet<Position> hs;
public HashSet<State<Token>> also = new HashSet<State<Token>>();
- public transient HashMap<Sequence,State<Token>> gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
+ public transient HashMap<Sequence,State<Token>> gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
private transient TopologicalBag<Token,State<Token>> gotoSetTerminals = new TopologicalBag<Token,State<Token>>();
- private TopologicalBag<Token,Position> reductions = new TopologicalBag<Token,Position>();
- private HashSet<Position> eofReductions = new HashSet<Position>();
- private TopologicalBag<Token,State<Token>> shifts = new TopologicalBag<Token,State<Token>>();
- private boolean accept = false;
+ private TopologicalBag<Token,Position> reductions = new TopologicalBag<Token,Position>();
+ private HashSet<Position> eofReductions = new HashSet<Position>();
+ private TopologicalBag<Token,State<Token>> shifts = new TopologicalBag<Token,State<Token>>();
+ private boolean accept = false;
- private VisitableMap<Token,State<Token>> oshifts = null;
- private VisitableMap<Token,Position> oreductions = null;
+ private VisitableMap<Token,State<Token>> oshifts = null;
+ private VisitableMap<Token,Position> oreductions = null;
// Interface Methods //////////////////////////////////////////////////////////////////////////////
- boolean isAccepting() { return accept; }
- public Iterator<Position> iterator() { return hs.iterator(); }
-
- boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
- <B,C> void invokeShifts(Token t, Invokable<State<Token>,B,C> irbc, B b, C c) {
- oshifts.invoke(t, irbc, b, c);
+ boolean isAccepting() { return accept; }
+ public Iterator<Position> iterator() { return hs.iterator(); }
+ boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
+ void invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
+ boolean canReduce(Token t) {
+ return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
+ void invokeEpsilonReductions(Token t, Node node) {
+ if (t==null) for(Position r : eofReductions) node.invoke(r, null);
+ else oreductions.invoke(t, node, null);
}
-
- boolean canReduce(Token t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
- <B,C> void invokeReductions(Token t, Invokable<Position,B,C> irbc, B b, C c) {
- if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c);
- else oreductions.invoke(t, irbc, b, c);
+ void invokeReductions(Token t, Node node, Result b) {
+ //System.err.println("\rinvokage: " + this);
+ if (t==null) for(Position r : eofReductions) node.invoke(r, b);
+ else oreductions.invoke(t, node, b);
}
// Constructor //////////////////////////////////////////////////////////////////////////////
/**
* create a new state consisting of all the <tt>Position</tt>s in <tt>hs</tt>
* @param hs the set of <tt>Position</tt>s comprising this <tt>State</tt>
- * @param all_elements the set of all elements (Atom instances need not be included)
+ * @param all the set of all elements (Atom instances need not be included)
*
* In principle these two steps could be merged, but they
* are written separately to highlight these two facts:
for(Sequence s : p.owner().needs()) {
if (hs.contains(s.firstp())) continue;
HashSet<Position> h2 = new HashSet<Position>();
- reachable(s.firstp(), h2);
+ reachable(s, h2);
also.add(mkstate(h2, true));
}
for(Sequence s : p.owner().hates()) {
((TopologicalBag)gotoSetTerminals).put(r, mkstate(h, doomed));
}
- // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction),
- // compute the closure over every position in this set which is followed by a symbol
- // which could yield the Element in question.
+ // Step 2: for every Sequence, compute the closure over every position in this set which
+ // is followed by a symbol which could yield the Sequence.
//
// "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<SequenceOrElement,Position> move = new HashMapBag<SequenceOrElement,Position>();
- for(Position p : hs) {
- Element e = p.element();
- if (e==null) continue;
- for(SequenceOrElement y : cache.ys2.getAll(e)) {
- //System.out.println(e + " yields " + y);
- HashSet<Position> hp = new HashSet<Position>();
- reachable(p.next(), hp);
- move.addAll(y, hp);
- }
- }
- OUTER: for(SequenceOrElement y : move) {
+ HashMapBag<Sequence,Position> move = new HashMapBag<Sequence,Position>();
+ for(Position p : hs)
+ if (!p.isLast() && p.element() instanceof Union)
+ for(Sequence s : ((Union)p.element())) {
+ HashSet<Position> hp = new HashSet<Position>();
+ reachable(p.next(), hp);
+ move.addAll(s, hp);
+ }
+ OUTER: for(Sequence y : move) {
+ // if a reduction is "lame", it should wind up in the dead_state after reducing
HashSet<Position> h = move.getAll(y);
State<Token> s = mkstate(h, doomed);
- // if a reduction is "lame", it should wind up in the dead_state after reducing
- if (y instanceof Sequence) {
- for(Position p : hs) {
- if (p.element() != null && (p.element() instanceof Union)) {
- Union u = (Union)p.element();
- for(Sequence seq : u)
- if (seq.needs.contains((Sequence)y) || seq.hates.contains((Sequence)y)) {
- // FIXME: what if there are two "routes" to get to the sequence?
- ((HashMap)gotoSetNonTerminals).put((Sequence)y, dead_state);
- continue OUTER;
- }
- }
- }
- gotoSetNonTerminals.put((Sequence)y, s);
- }
+ for(Position p : hs)
+ if (p.element() != null && (p.element() instanceof Union))
+ for(Sequence seq : ((Union)p.element()))
+ if (seq.needs.contains(y) || seq.hates.contains(y)) {
+ // FIXME: assumption that no sequence is ever both usefully (non-lamely) matched
+ // and also directly lamely matched
+ ((HashMap)gotoSetNonTerminals).put(y, dead_state);
+ continue OUTER;
+ }
+ gotoSetNonTerminals.put(y, s);
}
}
}
return st.toString();
}
+
public String toString() {
StringBuffer ret = new StringBuffer();
ret.append("state["+idx+"]: ");
return ret.toString();
}
- public Walk.Cache cache() { return cache; }
public int toInt() { return idx; }
}
+
+ public String toString() {
+ StringBuffer sb = new StringBuffer();
+ sb.append("parse table");
+ for(State<Token> state : all_states) {
+ sb.append(" " + state + "\n");
+ for(Topology<Token> t : state.shifts) {
+ sb.append(" shift \""+
+ new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => ");
+ for(State st : state.shifts.getAll(t))
+ sb.append(st.idx+" ");
+ sb.append("\n");
+ }
+ for(Topology<Token> t : state.reductions)
+ sb.append(" reduce \""+
+ new edu.berkeley.sbp.chr.CharTopology((IntegerTopology<Character>)t)+"\" => " +
+ state.reductions.getAll(t) + "\n");
+ for(Sequence s : state.gotoSetNonTerminals.keySet())
+ sb.append(" goto "+state.gotoSetNonTerminals.get(s)+" from " + s + "\n");
+ }
+ return sb.toString();
+ }
}
// Helpers //////////////////////////////////////////////////////////////////////////////
h.add(p);
if (p.element() != null) reachable(p.element(), h);
}
-
+ //public static Cache mastercache = null;
}
// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
package edu.berkeley.sbp;
-import edu.berkeley.sbp.*;
-import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Parser.Table.*;
import edu.berkeley.sbp.Sequence.Position;
-import java.io.*;
-import java.util.*;
-import java.lang.reflect.*;
final class Reduction implements Comparable<Reduction> {
- public Position position;
- public GSS.Phase phase;
- public Forest result;
- public Node node;
- boolean done = false;
+ private Position reduction;
+ private GSS.Phase phase;
+ private Forest forest;
+ private Node parent;
- public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
- this.position = position;
- this.result = result;
+ public Reduction(Node parent, Position reduction, Forest forest, GSS.Phase target) {
+ this.reduction = reduction;
+ this.forest = forest;
this.phase = target;
- this.node = node;
- target.reductionQueue.add(this);
- }
-
- public void perform() {
- if (done) return;
- done = true;
- node.finish(position, result, phase);
+ this.parent = parent;
+ target.addReduction(this);
}
public int compareTo(Reduction r) {
- int ret = compareTo0(r);
- if (ret != 0) return -1 * ret;
- return (position.ord - r.position.ord);
- }
-
- private static boolean isRightNullable(Walk.Cache c, Position p) {
- if (p.isLast()) return true;
- if (!c.possiblyEpsilon(p.element())) return false;
- return isRightNullable(c, p.next());
- }
-
- public static boolean canKill(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- Boolean b = me.canKill.get(him);
- if (b!=null) return b;
- for(Sequence killer : him.hates()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
- if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
+ if (parent.phase()!=null || r.parent.phase()!=null) {
+ if (parent.phase()==null) return 1;
+ if (r.parent.phase()==null) return -1;
+ if (parent.phase().pos < r.parent.phase().pos) return 1;
+ if (parent.phase().pos > r.parent.phase().pos) return -1;
}
- me.canKill.put(him, false);
- return false;
+ /*
+ int master = Parser.mastercache.comparePositions(reduction(), r.reduction());
+ if (master != 0 && master != signum(reduction.ord - r.reduction.ord))
+ throw new Error("master="+master+" and a="+reduction.ord+" and b="+r.reduction.ord+"\n"+reduction+"\n"+r.reduction);
+ */
+ return reduction.ord - r.reduction.ord;
}
- public static final int LESS_THAN = -1;
- public static final int EQUAL_TO = 0;
- public static final int GREATER_THAN = 1;
-
- public int compareTo0(Reduction n) {
- if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
- if (targetPhase()==null) return LESS_THAN;
- if (n.targetPhase()==null) return GREATER_THAN;
- if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
- if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
- return 0;
+ private int signum(int x) {
+ if (x==0) return 0;
+ if (x<0) return -1;
+ return 1;
}
- public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
- public GSS.Phase targetPhase() { return node.phase(); }
- public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- Boolean b = me.canNeed.get(him);
- if (b!=null) return b;
- for(Sequence needer : him.needs()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
- if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
- }
- me.canNeed.put(him, false);
- return false;
- }
+ public void perform() { new Result(forest, parent, reduction, phase); }
+ public GSS.Phase parentPhase() { return parent.phase(); }
+ public Position reduction() { return reduction; }
+ public GSS.Phase targetPhase() { return phase; }
+ public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction.ord+":"+ reduction+" "+reduction.owner(); }
}
private Forest f;
private Node parent;
- private GSS.Phase phase;
- private Position reduction;
private HashSet<Node> children = new HashSet<Node>();
private boolean destroyed = false;
private int usedByNonDoomedNode = 0;
- public Position reduction() { return reduction; }
- public GSS.Phase phase() { return phase; }
+ public GSS.Phase phase() { return parent==null ? null : parent.phase(); }
public Forest getForest() { return f; }
public Node parent() { return parent; }
public void addChild(Node child) {
usedByNonDoomedNode += child.state().doomed ? 0 : 1;
}
public void removeChild(Node child) {
+ if (!children.contains(child)) return;
children.remove(child);
usedByNonDoomedNode -= child.state().doomed ? 0 : 1;
+ check();
}
public boolean usedByAnyNode() { return children.size() > 0; }
if (destroyed) return;
if (parent==null) return; // never destroy the "primordeal" result
destroyed = true;
- if (parent() != null) {
- parent().removeChild(this);
- parent().check();
- }
- OUTER: while(true) {
+ parent.removeChild(this);
+ while(children.size() > 0)
for(Node n : children) {
children.remove(n);
n.removeResult(this);
- n.check();
- continue OUTER;
+ break;
}
- break;
- }
}
public Result(Forest f, Node parent, Position reduction) {
+ this(f, parent, reduction, null);
+ }
+ public Result(Forest f, Node parent, Position reduction, GSS.Phase target) {
this.f = f;
- this.reduction = reduction;
this.parent = parent;
if (parent != null) parent.addChild(this);
- if (parent != null) phase = parent.phase();
+ if (reduction == null) return;
+ Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction.owner());
+ target.newNodeFromReduction(this, state0, reduction);
}
// GraphViz //////////////////////////////////////////////////////////////////////////////
public Iterator<Element> iterator() { return new ArrayIterator<Element>(elements); }
protected Sequence(Element[] elements) {
this.elements = elements;
- this.firstp = new Position(0);
+ for(int i=0; i<elements.length; i++)
+ if (elements[i]==null)
+ throw new RuntimeException("cannot have nulls in a sequence: " + this);
+ this.firstp = new Position(0, null);
}
// DO NOT MESS WITH THE FOLLOWING LINE!!!
class Position implements IntegerMappable {
public int ord = -1;
- public int compareTo(Position p, Walk.Cache cache) {
- Position position = this;
- Position rposition = p;
- int ret = 0;
- if (Reduction.canKill(cache, position, rposition) &&
- Reduction.canKill(cache, rposition, position)) throw new Error();
- if (Reduction.canKill(cache, position, rposition)) ret = 1;
- else if (Reduction.canKill(cache, rposition, position)) ret = -1;
- if (Reduction.canNeed(cache, position, rposition)) ret = 1;
- else if (Reduction.canNeed(cache, rposition, position)) ret = -1;
- return ret;
- }
private Forest zero = null;
public Forest zero(Input.Region reg) {
if (zero != null) return zero;
- if (pos > 0) throw new Error();
+ if (pos > 0) throw new RuntimeException("Position.zero(): pos>0");
return zero = rewrite(reg);
}
-
final int pos;
private final Position next;
private final Position prev;
final Forest[] holder;
- private Position(int pos) {
+ private Position(int pos, Position prev) {
this.pos = pos;
- this.next = pos==elements.length ? null : new Position(pos+1);
+ this.next = pos==elements.length ? null : new Position(pos+1, this);
this.holder = new Forest[elements.length];
this.prev = prev;
}
if (holder[i]==null) holder[i] = elements[i].epsilonForm(loc);
if (holder[i]==null) throw new Error("bad " + i);
}
- Forest<T> ret = Sequence.this.postReduce(loc, holder, this);
- //for(int k=0; k<pos; k++) holder[k] = null; // to help GC
- return ret;
+ return Sequence.this.postReduce(loc, holder, this);
}
public String toString() {
Forest<T>[] args2 = new Forest[count];
int j = 0;
for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
- //System.out.println("reduce \""+tag+"\"");
return Forest.create(loc, (T)tag, args2, false);
}
public StringBuffer toString(StringBuffer sb, boolean spacing) {