import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Parser.Table.*;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
import java.lang.reflect.*;
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>();
+ private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
public Forest.Many finalResult;
private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
numReductions = 0;
int minPhasePos = Integer.MAX_VALUE;
- int maxOrd = -1;
Reduction best = null;
//System.out.println("==============================================================================");
while(!reductionQueue.isEmpty()) {
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) {
/*
Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
"\n"+(r.reduction().ord-best.reduction().ord));
*/
- maxOrd = r.reduction().ord;
best = r;
}
}
return getLocation().createRegion(getNextLocation());
}
- void newNodeFromReduction(Result result, State state, Position reduction) {
+ void newNodeFromReduction(Result result, State state, Pos reduction) {
int pos = result.phase().pos;
- Sequence owner = reduction.owner();
- for(Sequence s : owner.hates())
+ for(int s : reduction.hates())
if (performed.contains(pos, s))
return;
- for(Sequence s : owner.needs())
+ for(int s : reduction.needs())
if (!performed.contains(pos, s))
return;
- if (owner.needed_or_hated && !performed.contains(pos, owner))
- performed.add(pos, owner);
+ if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
+ performed.add(pos, reduction.provides());
if (state!=null)
- newNode(result, state, reduction.pos<=0);
+ newNode(result, state, reduction.numPops()<=0);
}
/** add a new node (merging with existing nodes if possible)
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Parser.Table.*;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
import java.lang.reflect.*;
/** a node in the GSS */
final class Node
- implements Invokable<Position, Result>,
+ implements Invokable<Pos, Result>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
private HashSet<Result> results = new HashSet<Result>();
private HashSet<Result> children = new HashSet<Result>();
- public final void invoke(Position r, Result only) {
+ public final void invoke(Pos r, Result only) {
boolean emptyProductions = only==null;
- if (emptyProductions != (r.pos==0)) return;
- if (r.pos!=0) reduce(r, r.pos-1, phase(), only);
+ if (emptyProductions != (r.numPops()==0)) return;
+ if (r.numPops()!=0) reduce(r, r.numPops()-1, phase(), only);
else {
Input.Region region = phase().getLocation().createRegion(phase().getLocation());
new Result(r.rewrite(region, phase().parser().cache()), this, r, phase());
}
}
- private void reduce(Position r, int pos, GSS.Phase target, Result only) {
+ private void reduce(Pos 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
package edu.berkeley.sbp;
import edu.berkeley.sbp.*;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.GSS.Phase;
import edu.berkeley.sbp.Node;
import edu.berkeley.sbp.util.*;
boolean alldone = false;
boolean go = false;
boolean force = false;
- for(Position p : (Iterable<Position>)parent.state()) {
+ for(Pos pp : (Iterable<Pos>)parent.state().positions()) {
+ Position p = (Position)pp;
if (skip) p = p.next();
int raise = 0;
done = false;
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.io.*;
import java.util.*;
// 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) {
+ for(Object po : s.positions()) {
Sequence.Position p = (Sequence.Position)po;
if (al.contains(p)) continue;
int i=0;
private final transient HashSet<Position> hs;
public HashSet<State<Token>> conjunctStates = new HashSet<State<Token>>();
- HashMap<Sequence,State<Token>> gotoSetNonTerminals = new HashMap<Sequence,State<Token>>();
+ HashMap<Pos,State<Token>> gotoSetNonTerminals = new HashMap<Pos,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,Pos> reductions = new TopologicalBag<Token,Pos>();
+ private HashSet<Pos> eofReductions = new HashSet<Pos>();
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,Pos> oreductions = null;
public final boolean doomed;
// Interface Methods //////////////////////////////////////////////////////////////////////////////
public boolean doomed() { return doomed; }
boolean isAccepting() { return accept; }
- public Iterator<Position> iterator() { return hs.iterator(); }
+
+ Iterable<Position> positions() { return hs; }
+
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);
+ if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
else oreductions.invoke(t, node, null);
}
void invokeReductions(Token t, Node node, Result b) {
- if (t==null) for(Position r : eofReductions) node.invoke(r, b);
+ if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
else oreductions.invoke(t, node, b);
}
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);
+ for(Position pp = y.firstp(); pp != null; pp = pp.next())
+ ((HashMap)gotoSetNonTerminals).put(pp, dead_state);
continue OUTER;
}
- gotoSetNonTerminals.put(y, s);
+ for(Position pp = y.firstp(); pp != null; pp = pp.next())
+ gotoSetNonTerminals.put(pp, s);
}
}
package edu.berkeley.sbp;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
final class Reduction implements Comparable<Reduction> {
- private Position reduction;
+ private Pos reduction;
private GSS.Phase phase;
private Forest forest;
private Node parent;
- public Reduction(Node parent, Position reduction, Forest forest, GSS.Phase target) {
+ public Reduction(Node parent, Pos reduction, Forest forest, GSS.Phase target) {
this.reduction = reduction;
this.forest = forest;
this.phase = target;
}
/*
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);
+ 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;
+ return reduction.compareTo(r.reduction);
}
private int signum(int x) {
public void perform() { new Result(forest, parent, reduction, phase); }
public GSS.Phase parentPhase() { return parent.phase(); }
- public Position reduction() { return reduction; }
+ public Pos 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(); }
+ public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction; }
}
package edu.berkeley.sbp;
import edu.berkeley.sbp.util.*;
import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.Sequence.Pos;
import java.util.*;
final class Result implements GraphViz.ToGraphViz {
}
}
- public Result(Forest f, Node parent, Position reduction) {
+ public Result(Forest f, Node parent, Pos reduction) {
this(f, parent, reduction, null);
}
- public Result(Forest f, Node parent, Position reduction, GSS.Phase target) {
+ public Result(Forest f, Node parent, Pos reduction, GSS.Phase target) {
this.f = f;
this.parent = parent;
if (parent != null) parent.addChild(this);
if (reduction == null) return;
- Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction.owner());
+ Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction);
target.newNodeFromReduction(this, state0, reduction);
}
HashMap<Sequence,Boolean> canNeed = new HashMap<Sequence,Boolean>();
HashMap<Sequence,Boolean> canKill = new HashMap<Sequence,Boolean>();
- final Position firstp;
+ final Position firstp;
Atom follow = null;
+ private static int global_sernum = 0;
+ private int sernum = global_sernum++;
+ int[] needs_int() {
+ int[] ret = new int[needs.size()];
+ int i = 0;
+ for(Sequence s : needs) ret[i++] = s.sernum;
+ return ret;
+ }
+ int[] hates_int() {
+ int[] ret = new int[hates.size()];
+ int i = 0;
+ for(Sequence s : hates) ret[i++] = s.sernum;
+ return ret;
+ }
+
+
// Static Constructors //////////////////////////////////////////////////////////////////////////////
/** create a sequence of one element */
// Position //////////////////////////////////////////////////////////////////////////////
- /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
- class Position implements IntegerMappable {
+ static abstract class Pos implements IntegerMappable, Comparable<Pos>, Serializable {
+ final Forest[] holder;
+ Pos(int len) { this.holder = new Forest[len]; }
- public int ord = -1;
+ public abstract int provides();
+ public abstract int[] needs();
+ public abstract int[] hates();
+ public abstract boolean owner_needed_or_hated();
+
+ public abstract int numPops();
+ public abstract <T> Forest<T> rewrite(Input.Region loc, Grammar cache);
+ }
- private Forest zero = null;
+ /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
+ class Position extends Pos implements IntegerMappable {
/*
- public Forest zero(Input.Region reg) {
- if (zero != null) return zero;
- if (pos > 0) throw new RuntimeException("Position.zero(): pos>0");
- return zero = rewrite(reg);
+ public Pos getPos() {
+ return new DumbPos(elements.length, provides(), needs(), hates(), owner_needed_or_hated(), numPops(),
+ public int provides();
+ public int[] needs();
+ public int[] hates();
+ public boolean owner_needed_or_hated();
+ public int numPops();
+ public <T> Forest<T> rewrite(Input.Region loc, Grammar cache)
+ };
}
*/
+ public int ord = -1;
+ public int ord() { return ord; }
+ public int numPops() { return pos; }
+
final int pos;
private final Position next;
private final Position prev;
- final Forest[] holder;
+
+ public int provides() { return owner().sernum; }
+ public int[] needs() { return owner().needs_int(); }
+ public int[] hates() { return owner().hates_int(); }
+ public boolean owner_needed_or_hated() { return owner().needed_or_hated; }
private Position(int pos, Position prev) {
+ super(elements.length);
this.pos = pos;
this.next = pos==elements.length ? null : new Position(pos+1, this);
- this.holder = new Forest[elements.length];
this.prev = prev;
}
+ public int compareTo(Pos p) {
+ return ord - ((Position)p).ord;
+ }
+
boolean isFirst() { return pos==0; }
+ public int pos() { return pos; }
/** the element immediately after this Position, or null if this is the last Position */
public Element element() { return pos>=elements.length ? null : elements[pos]; }
// Position /////////////////////////////////////////////////////////////////////////////////
- final <T> Forest<T> rewrite(Input.Region loc, Grammar cache) {
+ public final <T> Forest<T> rewrite(Input.Region loc, Grammar cache) {
if (this==firstp()) epsilonForm(loc, cache);
for(int i=0; i<pos; i++) if (holder[i]==null) throw new Error("realbad " + i);
for(int i=pos; i<elements.length; i++) {
}
private static int master_position_idx = 0;
+
// toString //////////////////////////////////////////////////////////////////////////////
public String toString() { return toString(new StringBuffer(), false).toString(); }
// Specialized Subclasses //////////////////////////////////////////////////////////////////////////////
- static class Constant extends Sequence {
- private final Object result;
- public Constant(Element[] e, Object result) {
- super(e);
- if (result==null) throw new Error("constant sequences may not have result==null");
- this.result = result;
- }
- Sequence _clone() { return new Constant(elements, result); }
- public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
- return (Forest<T>)Forest.create(loc, result, null, false);
- }
- Forest epsilonForm(Input.Region loc, Grammar cache) {
- return Forest.create(loc, result, null, false);
- }
- }
-
static class Singleton extends Sequence {
private final int idx;
public Singleton(Element e) { this(new Element[] { e }, 0); }
}
static class RewritingSequence extends Sequence {
- private Object tag;
+ private final Object tag;
private final boolean[] drops;
private final boolean[] lifts;
Sequence _clone() { return new RewritingSequence(tag, elements, drops); }
projects / sbp.git / commitdiff