From 4692c8e9ba0c4b44ac5222f5bf5168703c478cbd Mon Sep 17 00:00:00 2001 From: adam Date: Sun, 27 May 2007 16:29:27 -0400 Subject: [PATCH] factor Pos out of Position in preparation for serialiable parse tables darcs-hash:20070527202927-5007d-184aeac36ac45d70ca6bd96d3c266556f9397b67.gz --- src/edu/berkeley/sbp/GSS.java | 19 +++----- src/edu/berkeley/sbp/Node.java | 11 +++-- src/edu/berkeley/sbp/ParseFailed.java | 4 +- src/edu/berkeley/sbp/Parser.java | 25 ++++++---- src/edu/berkeley/sbp/Reduction.java | 15 +++--- src/edu/berkeley/sbp/Result.java | 7 +-- src/edu/berkeley/sbp/Sequence.java | 86 ++++++++++++++++++++++----------- 7 files changed, 101 insertions(+), 66 deletions(-) diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index a726297..c418f4e 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -5,6 +5,7 @@ import edu.berkeley.sbp.*; 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.*; @@ -26,7 +27,7 @@ class GSS { class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { // FIXME: right now, these are the performance bottleneck - private HashMapBag performed = new HashMapBag(); + private HashMapBag performed = new HashMapBag(); public Forest.Many finalResult; private PriorityQueue reductionQueue = new PriorityQueue(); @@ -71,7 +72,6 @@ class GSS { numReductions = 0; int minPhasePos = Integer.MAX_VALUE; - int maxOrd = -1; Reduction best = null; //System.out.println("=============================================================================="); while(!reductionQueue.isEmpty()) { @@ -84,7 +84,6 @@ class GSS { 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) { /* @@ -93,7 +92,6 @@ class GSS { Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+ "\n"+(r.reduction().ord-best.reduction().ord)); */ - maxOrd = r.reduction().ord; best = r; } } @@ -160,19 +158,18 @@ class GSS { 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) diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index b6f4585..2cb33a9 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -5,13 +5,14 @@ import edu.berkeley.sbp.*; 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, + implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { @@ -67,17 +68,17 @@ final class Node private HashSet results = new HashSet(); private HashSet children = new HashSet(); - 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 diff --git a/src/edu/berkeley/sbp/ParseFailed.java b/src/edu/berkeley/sbp/ParseFailed.java index 8000712..3ff8178 100644 --- a/src/edu/berkeley/sbp/ParseFailed.java +++ b/src/edu/berkeley/sbp/ParseFailed.java @@ -3,6 +3,7 @@ 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.*; @@ -67,7 +68,8 @@ public class ParseFailed extends Exception { boolean alldone = false; boolean go = false; boolean force = false; - for(Position p : (Iterable)parent.state()) { + for(Pos pp : (Iterable)parent.state().positions()) { + Position p = (Position)pp; if (skip) p = p.next(); int raise = 0; done = false; diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 8af8005..861c323 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -3,6 +3,7 @@ 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.*; @@ -192,7 +193,7 @@ public abstract class Parser { // al will be sorted in DECREASING order (al[0] >= al[1]) ArrayList al = new ArrayList(); 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; @@ -269,33 +270,35 @@ public abstract class Parser { private final transient HashSet hs; public HashSet> conjunctStates = new HashSet>(); - HashMap> gotoSetNonTerminals = new HashMap>(); + HashMap> gotoSetNonTerminals = new HashMap>(); private transient TopologicalBag> gotoSetTerminals = new TopologicalBag>(); - private TopologicalBag reductions = new TopologicalBag(); - private HashSet eofReductions = new HashSet(); + private TopologicalBag reductions = new TopologicalBag(); + private HashSet eofReductions = new HashSet(); private TopologicalBag> shifts = new TopologicalBag>(); private boolean accept = false; private VisitableMap> oshifts = null; - private VisitableMap oreductions = null; + private VisitableMap oreductions = null; public final boolean doomed; // Interface Methods ////////////////////////////////////////////////////////////////////////////// public boolean doomed() { return doomed; } boolean isAccepting() { return accept; } - public Iterator iterator() { return hs.iterator(); } + + Iterable 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); } @@ -399,10 +402,12 @@ public abstract class Parser { 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); } } diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java index 5e59a4e..676097e 100644 --- a/src/edu/berkeley/sbp/Reduction.java +++ b/src/edu/berkeley/sbp/Reduction.java @@ -2,15 +2,16 @@ package edu.berkeley.sbp; import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.Sequence.Pos; final class Reduction implements Comparable { - 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; @@ -27,10 +28,10 @@ final class Reduction implements Comparable { } /* 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) { @@ -41,7 +42,7 @@ final class Reduction implements Comparable { 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; } } diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java index 95baeba..a86c608 100644 --- a/src/edu/berkeley/sbp/Result.java +++ b/src/edu/berkeley/sbp/Result.java @@ -3,6 +3,7 @@ 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 { @@ -46,15 +47,15 @@ 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); } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index 1c76aef..25d091f 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -24,10 +24,26 @@ public abstract class Sequence implements Iterable, SequenceOrElement { HashMap canNeed = new HashMap(); HashMap canKill = new HashMap(); - 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 */ @@ -118,32 +134,59 @@ public abstract class Sequence implements Iterable, SequenceOrElement { // 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, 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 Forest 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 Forest 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]; } @@ -161,7 +204,7 @@ public abstract class Sequence implements Iterable, SequenceOrElement { // Position ///////////////////////////////////////////////////////////////////////////////// - final Forest rewrite(Input.Region loc, Grammar cache) { + public final Forest rewrite(Input.Region loc, Grammar cache) { if (this==firstp()) epsilonForm(loc, cache); for(int i=0; i, SequenceOrElement { } private static int master_position_idx = 0; + // toString ////////////////////////////////////////////////////////////////////////////// public String toString() { return toString(new StringBuffer(), false).toString(); } @@ -215,22 +259,6 @@ public abstract class Sequence implements Iterable, SequenceOrElement { // 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 Forest postReduce(Input.Region loc, Forest[] args, Position p) { - return (Forest)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); } @@ -243,7 +271,7 @@ public abstract class Sequence implements Iterable, SequenceOrElement { } 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); } -- 1.7.10.4