cd bin; $(ghc) -i../src/ -c ../src/HaskellDemo.hs $(link) -o HaskellDemo.o
cd bin; for A in *.hs; do $(ghc) -c $$A $(link); done
cd bin; $(ghc) $(linkopts) $(link) -o HaskellDemo *.o
+
+
+ghcroot = /usr/local/brian/ghc
+ghc = $(ghcroot)/compiler/ghc-inplace
+ghclibs = $(ghcroot)/rts/HSrts.jar:$(ghcroot)/libraries/base/HSbase.jar:$(ghcroot)/libraries/stm/HSstm.jar
+
+bin/Main.class: src/Main.lhs src/SBP.lhs
+ cd src; $(ghc) -fglasgow-exts -cpp -odir ../bin -c -java SBP.lhs
+ cd src; $(ghc) -fglasgow-exts -cpp -odir ../bin -java Main.lhs
+
+go: bin/Main.class edu.berkeley.sbp.jar
+ java -cp bin:$(ghclibs):edu.berkeley.sbp.jar Main
\ No newline at end of file
_____________________________________________________________________________
Immediately
- - Check if the only remaining stack is lame
- - write a testcase for this
+ - comparison test is probably chewing up most of the time
+ - Check if the only remaining stack is lame (hopeful/nothopeful)
+ - write a testcase for this
- circular gramars
s = A
A = A | "b"
-
- foo.add(x)
foo.add(y.andnot(x)) ==> this is broken
-
- Annotation Tutorial
..................................................
- - evil problems with: (x y? z /ws)
- - it gets even more evil than that
- - basically, follow restrictions are not honored when the element
- matches against the empty string
+ - serializable parse tables?
+ - Treewalker code compiler?
______________________________________________________________________________
v1.1
- precedes restrictions ("<-")
-
- MUST HAVE BETTER ERROR MESSAGES
- use for developing java15.g
-
- java15.g
- once this is ready, do big announcement
-
- - topology no longer needed as an arg to parser?
-
- broader regression testing (for stuff like error messages, etc)
-
- More topology untangling [later]
- - tib: use the lexer only for indentation increases/decreases
- grammar highlighting?
-
- Forest needs a "manual access" API
- the unwrap bit in Forest makes it really hard to expose an API for forests
--- /dev/null
+\begin{code}
+module Main
+where
+import SBP
+main = do t <- parseFile "../fleeterpreter/fleet.g" "../fleeterpreter/demo.fleet"
+ putStrLn $ "hi"
+ putStrLn $ show (prettyPrintTree t)
+\end{code}
+
+
+
+
+\begin{code}
--
-- These bindings are highly experimental and subject to change
-- without notice. You've been warned.
--
+module SBP(Tree(Tree),Location(Location),Region(Region),parseFile,prettyPrintTree)
+ where
+
+#if defined(java_HOST_OS)
+
+#define CONCAT(x,y) x/**/y
+#define DEFINE_OBJECT(s,name) \
+data CONCAT(name,_); \
+type name = Object CONCAT(name,_); \
+foreign import jvm s CONCAT(_,name) :: JClass; \
+instance JType_ CONCAT(name,_) where jClass_ _ = CONCAT(_,name);
-module SBP
+import Foreign
+import Foreign.Java
+import Text.PrettyPrint.HughesPJ
+
+data Location = Location Int Int
+data Region = Region Location Location
+
+data Tree = Tree String [Tree] Region
+instance Show Tree
where
+ show t@(Tree _ _ _) = show $ prettyPrintTree $ t
+
+coalesceFlatHeadlessNodes t@(Tree s children r)
+ | s==[], flat t = Tree (concat $ map (\(Tree s _ _) -> s) children) [] r
+ | otherwise = Tree s (map coalesceFlatHeadlessNodes children) r
+ where
+ flat (Tree _ children _) = not (any id $ map notFlatComponent children)
+ notFlatComponent (Tree _ [] _) = False
+ notFlatComponent (Tree _ _ _) = True
+
+prettyPrintTree (Tree "" [] _) = empty
+prettyPrintTree (Tree s [] _) = text s
+prettyPrintTree t@(Tree s children _)
+ | s==[] = (text "{") <+> ((prettyPrintTreeList children) <+> (text "}"))
+ | otherwise = ((text s) <> (text ":")) <+> prettyPrintTreeList children
+ where
+ prettyPrintTreeList children = (vcat $ map prettyPrintTree children)
+
+nullRegion = (Region (Location 0 0) (Location 0 0))
+
+foreign import jvm type "edu.berkeley.sbp.Tree" JTree#
+data JTree = JTree JTree#
+
+foreign import jvm safe "edu.berkeley.sbp.misc.RegressionTests.main" regressionTests :: IO ()
+foreign import jvm safe "edu.berkeley.sbp.misc.HaskellHelper.help" haskellHelper :: JString -> JString -> IO JTree
+foreign import jvm safe "edu.berkeley.sbp.misc.HaskellHelper.isNull" isNull :: (Object a) -> IO Bool
+foreign import jvm safe "getHead" getHead :: JTree -> IO (Object a)
+foreign import jvm safe "child" getChild :: JTree -> Int32 -> IO JTree
+foreign import jvm safe "size" size :: JTree -> IO Int32
+foreign import jvm safe "toString" jtoString :: (Object a) -> IO JString
+
+toString o = do isn <- isNull o
+ if isn then return ""
+ else do str <- jtoString o
+ return (unpackJString str)
+
+
+haskify :: JTree -> IO Tree
+haskify t =
+ do head <- getHead t
+ str <- toString head
+ numChildren <- size t
+ children <- if numChildren == 0
+ then do return []
+ else do children <- mapM (\i -> getChild t i)
+ $ take (fromIntegral numChildren)
+ $ iterate (+1) 0
+ h <- mapM haskify children
+ return h
+ return $ Tree str children nullRegion
+
+parseFile ::
+ String -> -- grammar *.g file
+ String -> -- file to be parsed
+ IO Tree
+
+parseFile g f = do g' <- packJString g
+ f' <- packJString f
+ tree <- haskellHelper g' f'
+ x <- haskify tree
+ return x
+
+#else
import Header_Java;
import Class_edu_berkeley_sbp_misc_HaskellHelper;
import Class_java_lang_Object;
return $ Tree str children nullRegion
) :: JVM Tree)
-
+#endif
+\end{code}
/** An "ambiguity node"; this is immutable once it has been "looked at" */
static class Many<NodeType> extends Forest<NodeType> {
- HashSet<Node> parents = new HashSet<Node>();
private FastSet<Forest<NodeType>> hp = new FastSet<Forest<NodeType>>();
private boolean touched = false;
/** implements Tomita's Graph Structured Stack */
class GSS {
- public static Queue<Node> removals = new LinkedList<Node>();
-
- static String note = "";
- static int single_newnode = 0;
- static int toplevel_reductions = 0;
- static int multi_newnode = 0;
- static int waiting_newnode = 0;
- static int shifts = 0;
-
- static int count = 0;
- static int reductions = 0;
- int resets = 0;
- int waits = 0;
-
Input input;
-
public GSS(Input input) { this.input = input; }
-
- private Node[] reducing_list = null;
+ public Input getInput() { return input; }
// FIXME: right now, these are the performance bottleneck
- HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
- HashMapBag<Integer,Sequence> lastperformed = new HashMapBag<Integer,Sequence>();
- HashMapBag<Integer,Sequence> expected = new HashMapBag<Integer,Sequence>();
-
+
/** FIXME */
Forest.Many finalResult;
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
- class Phase<Tok> implements Invokable<State, Forest, Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+ class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
- public int pos() { return pos; }
- public boolean closed() { return closed; }
- public Tok token() { return token; }
+ public ArrayList<Reduction> reductionQueue = new ArrayList<Reduction>();
- public Iterator<Node> iterator() { return hash.iterator(); }
- public void invoke(State st, Forest result, Node n) {
- shifts++;
- good |= next.newNode(n, result, st, false);
+ public void invoke(State st, Result result, Object o) {
+ //shifts++;
+ good |= next.newNode(result, st, false);
}
/** the token immediately after this phase */
final Tok token;
+ final int pos;
- private final int pos;
-
- boolean reducing;
public IntPairMap<Node> hash; /* ALLOC */
- private boolean closed;
private boolean good;
- private Phase next = null;
+ Phase next = null;
private Phase prev;
private Input.Location location;
private Input.Location nextLocation;
private Input.Location prevLocation;
- public final Parser parser;
-
private Forest forest;
- public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location,
+ public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
Input.Location nextLocation, Forest forest) throws ParseFailed {
this.prevLocation = prev==null ? location : prev.getLocation();
this.prev = prev;
this.forest = forest;
- this.parser = parser;
this.pos = previous==null ? 0 : previous.pos+1;
this.token = token;
this.location = location;
this.nextLocation = nextLocation;
performed.clear();
- reset();
- }
-
- public void reset() throws ParseFailed {
- waiting.clear();
- expected.clear();
- lastperformed.clear();
- lastperformed.addAll(performed);
- performed.clear();
hash = new IntPairMap<Node>();
- reset = false;
good = false;
- closed = false;
- reducing = false;
finalResult = null;
if (prev != null) prev.shift(this, forest);
}
-
public boolean isDone() throws ParseFailed {
if (token != null) return false;
if (token==null && finalResult==null)
- ParseFailed.error("unexpected end of file",
- getLocation(),
- token,
- hash.values(),
- getLocation().createRegion(getLocation()),
- input,
- GSS.this);
+ ParseFailed.error("unexpected end of file", this);
return true;
}
public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); }
public Input.Location getNextLocation() { return nextLocation; }
- /** add a new node (merging with existing nodes if possible)
- * @param parent the parent of the new node
- * @param result the SPPF result corresponding to the new node
- * @param state the state that the new node is in
- * @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(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
- Node p = hash.get(state, parent==null?null:parent.phase());
- if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction);
- else return newNode3(parent, pending, state, fromEmptyReduction);
- }
- public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
- int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
- Sequence owner = reduction==null ? null : reduction.owner();
- if (reduction!=null) {
- if (owner.hates!=null) {
- for (Sequence s : performed.getAll(pos))
- if (owner.hates.contains(s))
- return;
- for (Sequence s : lastperformed.getAll(pos))
- if (owner.hates.contains(s)) {
- //System.out.println("now expecting ["+pos+"] => " + s);
- expected.add(pos, s);
- return;
- }
- }
- if (owner.needs != null)
- for(Sequence s : owner.needs)
- if (!performed.contains(pos, s)) {
- waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
- return;
- }
- if (!performed.contains(pos, owner)) {
- performed.add(pos, owner);
- if (owner.hated != null)
- for(Sequence seq : owner.hated)
- if (performed.contains(pos, seq)) {
- performed.remove(pos, seq);
- reset = true;
- }
+ /** 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;
+ this.next = next;
+ for(Node n : hash.values()) {
+ if (token == null && n.state().isAccepting()) {
+ if (finalResult==null) finalResult = new Forest.Many();
+ for(Result r : n)
+ finalResult.merge(r.getForest());
}
+ if (token == null) continue;
+ n.state().invokeShifts(token, this, new Result(result, n, null), null);
}
- newNode(parent, pending, state, fromEmptyReduction);
- if (reduction != null) {
- boolean redo = true;
- while(redo) {
- redo = false;
- for(Waiting w : waiting.getAll(owner)) {
- if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
- waiting.remove(owner, w);
- w.perform();
- redo = true;
- break;
- }
+ if (!good && token!=null) ParseFailed.error("unexpected character", this);
+ if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
+ }
+
+ /** perform all reduction operations */
+ public void reduce() throws ParseFailed {
+ Reduction last = null;
+ while(!reductionQueue.isEmpty()) {
+ Reduction r = null;
+
+ // ugly
+ OUTER: for(int i=0; i<reductionQueue.size(); i++) {
+ for(int j=0; j<reductionQueue.size(); j++) {
+ if (i==j) continue;
+ if (reductionQueue.get(i).compareTo(reductionQueue.get(j)) > 0)
+ continue OUTER;
}
+ r = reductionQueue.get(i);
+ reductionQueue.remove(r);
+ break;
+ }
+
+ /*
+ if (last == null) last = r;
+ else if (r.compareTo(last) > 0) last = r;
+ else if (r.compareTo(last) < 0) {
+ if (r.targetPhase() != null)
+ System.out.println("err " + last.compareTo(r) + " " + last.targetPhase().pos() +
+ " " + r.targetPhase().pos() + " " + pos);
}
+ */
+
+ r.perform();
}
}
- private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
- if (p.merge(parent, pending)) return true;
- p.addParent(parent, true);
- if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
- return true;
+ public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {
+ int pos = result.phase().pos;
+ Sequence owner = reduction.owner();
+ for(Sequence s : owner.hates)
+ if (performed.contains(pos, s))
+ return;
+ 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);
}
- private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
+ /** add a new node (merging with existing nodes if possible)
+ * @param parent the parent of the new node
+ * @param result the SPPF result corresponding to the new node
+ * @param state the state that the new node is in
+ * @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) {
+ Node p = hash.get(state, result.phase());
+ if (p != null) { p.merge(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;
- //if (count > 1) break;
- //if (r.numPop == 0) break;
- //r.reduce(pending, parent, null, Phase.this, null);
- //return;
} while(false);
-
- Node n = new Node(Phase.this, parent, pending, state); // ALLOC
- if (reducing) {
- n.performEmptyReductions();
- if (!fromEmptyReduction) n.performReductions(parent);
- }
+ new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
return true;
}
- public LinkedList<Node> reductionQueue = new LinkedList<Node>();
-
- /** perform all reduction operations */
- public void reduce() throws ParseFailed {
- try {
- reducing = true;
- if (reducing_list==null || reducing_list.length < hash.size())
- reducing_list = new Node[hash.size() * 4];
- hash.toArray(reducing_list);
- int num = hash.size();
- for(int i=0; i<num; i++) {
- Node n = reducing_list[i];
- n.performEmptyReductions();
- // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
- }
- for(int i=0; i<num; i++) {
- reductionQueue.add(reducing_list[i]);
- reducing_list[i] = null;
- }
- while(!reductionQueue.isEmpty()) {
- reductionQueue.remove().performReductions();
- }
- if (reset) {
- reset = false;
- resets++;
- throw new Reset();
- }
- for(int i : expected)
- for(Sequence s : expected.getAll(i))
- if (!performed.contains(i, s)) {
- //System.out.println("resetting due to pos="+i+": " + s + " " + System.identityHashCode(s));
- resets++;
- throw new Reset();
- }
- } catch (Reset r) {
- reset();
- reduce();
- }
- count = 0;
- }
-
- private boolean reset = false;
- class Reset extends RuntimeException { }
-
- /** 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 && parser.helpgc) {
- //prev.hash = null;
- //System.out.println("\r" + /*shifts + " " + */ single_newnode /*+ "/"+multi_newnode + " " + waiting_newnode*/);
- //System.out.println("\r" + shifts + " " + note);
- //System.out.println("\r" + shifts);
- //System.out.println("\r" + toplevel_reductions);
- //System.out.println("\r" + multi_newnode);
- single_newnode = 0;
- note = "";
- multi_newnode = 0;
- toplevel_reductions = 0;
- waiting_newnode = 0;
- shifts = 0;
- }
- this.next = next;
- closed = true;
- Forest res = null;
- boolean ok = false;
- int count = 0;
- for(Node n : hash.values()) {
- if (token == null && n.state().isAccepting()) {
- if (finalResult==null) finalResult = new Forest.Many();
- for(Object f : n.results())
- finalResult.merge((Forest)f);
- }
- if (token == null) continue;
- n.state().invokeShifts(token, this, result, n);
- }
- //System.out.println(next.hash.size());
- if (!good && token!=null)
- ParseFailed.error("unexpected character",
- getLocation(),
- token,
- hash.values(),
- getRegion(),
- input,
- GSS.this);
-
- if (token==null && finalResult==null)
- ParseFailed.error("unexpected end of file",
- getLocation(),
- token,
- hash.values(),
- getLocation().createRegion(getLocation()),
- input,
- GSS.this);
- }
-
-
- class Waiting {
- Node parent;
- Forest pending;
- State state;
- boolean fromEmptyReduction;
- Position reduction;
- public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
- waits++;
- this.parent = parent;
- this.pending = pending;
- this.state = state;
- this.fromEmptyReduction = fromEmptyReduction;
- this.reduction = reduction;
- }
- public void perform() {
- //System.out.println("performing: " + reduction.position);
- waiting_newnode++;
- newNode(parent, pending, state, fromEmptyReduction, reduction);
- }
- }
-
-
public int toInt() { return pos+1; }
public int size() { return hash==null ? 0 : hash.size(); }
+ public int pos() { return pos; }
+ public Tok getToken() { return token; }
+ public Iterator<Node> iterator() { return hash.iterator(); }
+ public GSS getGSS() { return GSS.this; }
// GraphViz //////////////////////////////////////////////////////////////////////////////
import java.lang.reflect.*;
/** a node in the GSS */
-final class Node implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
+final class Node
+ implements Invokable<Position, Boolean, Result>,
+ IntegerMappable,
+ GraphViz.ToGraphViz,
+ Iterable<Result> {
- public static int node_idx = 0;
-
- private final GSS.Phase phase;
-
- public FastSet<Node> setx = new FastSet<Node>();
- public FastSet<Node> childs = new FastSet<Node>();
-
- private boolean allqueued = false;
-
- /** what state this node is in */
- public final Parser.Table.State state;
-
- /** which GSS.Phase this Node belongs to (node that Node is also a non-static inner class of GSS.Phase) */
+ /** which GSS.Phase this Node belongs to */
public GSS.Phase phase() { return phase; }
+ public Iterator<Result> iterator() { return results.iterator(); }
+ public Parser.Table.State state() { return state; }
- private HashSet<Forest.Many> resultMap = new HashSet<Forest.Many>();
- public Iterable<Forest.Many> results() { return resultMap; }
- public Iterable<Node> parents() { return setx; }
- public void addParent(Node n, boolean b) {
- if (n==null) return;
- setx.add(n, b);
- n.childs.add(this, true);
- //else
- //System.out.println("************ evilstate: " + this);
- }
- public boolean merge(Node parent, Forest result) {
- // FIXME: inefficient!
- for(Forest.Many f : results()) {
- if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) {
- f.merge(result);
- return true;
- }
- }
- Forest.Many f = new Forest.Many();
- f.parents.add(parent);
- f.merge(result);
- resultMap.add(f);
- addParent(parent, true);
- return false;
- }
+ public int toInt() { return idx; }
- public void performReductions() {
- if (allqueued) return;
- allqueued = true;
- state.invokeReductions(phase().token(), this, this, null);
+ public boolean merge(Result r) {
+ if (results.contains(r)) return true;
+ results.add(r);
+ if (fromEmptyReduction) return false;
+ state.invokeReductions(phase().getToken(), this, false, r);
+ return false;
}
- public void performReductions(Node n2) {
- if (!allqueued) phase().reductionQueue.add(this);//performReductions();
- else state.invokeReductions(phase().token(), this, this, n2);
- }
+ //////////////////////////////////////////////////////////////////////
- public Parser.Table.State state() { return state; }
+ private static int node_idx = 0;
+ private final int idx = node_idx++;
- public void performEmptyReductions() { state.invokeReductions(phase().token, this, null, null); }
- public final void invoke(Position r, Node n, Node n2) {
- //reductions++;
- //if (r.pos==1) single_newnode++;
- //if (r.pos>1) multi_newnode++;
- if (n==null || n2==null || r.pos==0) {
- if (r.pos==0) {
- if (n==null) n = this;
- else return;
- }
- if (n==null) return;
- Forest[] holder = new Forest[r.pos];
- if (r.pos==0) n.finish(r, r.zero(n.phase().getLocation().createRegion(n.phase().getLocation())), n.phase());
- else n.reduce(r, r.pos-1, n.phase(), null);
- } else {
- if (r.pos<=0) throw new Error("called wrong form of reduce()");
- int pos = r.pos-1;
- n.reduce(r, pos, n.phase(), n2);
- }
+ private final GSS.Phase phase;
+ private final Parser.Table.State state;
+ private final boolean fromEmptyReduction;
+ //private FastSet<Result> results = new FastSet<Result>();
+ private HashSet<Result> results = new HashSet<Result>();
+
+ public final void invoke(Position r, Boolean emptyProductions, Result only) {
+ if (emptyProductions != (r.pos==0)) return;
+ if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase());
+ else reduce(r, r.pos-1, phase(), only);
}
- public void reduce(Position r, int pos, GSS.Phase target, Node only) {
+ private void reduce(Position r, int pos, GSS.Phase target, Result only) {
Forest[] holder = r.holder;
Forest old = holder[pos];
-
- //toplevel_reductions++;
- HashSet<Forest> rr = new HashSet<Forest>();
- for(Forest result : results()) {
- rr.add(result);
- }
- //System.out.println(r);
- for(Forest result : rr) {
- for(Node child : ((Forest.Many<?>)result).parents) {
- if (only != null && child!=only) continue;
- holder[pos] = result;
- if (pos==0) child.finish(r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
- else child.reduce(r, pos-1, target, null);
+ for(Result res : results)
+ if (only == null || res == only) {
+ Node child = res.parent();
+ holder[pos] = res.getForest();
+ if (pos>0) child.reduce(r, pos-1, target, null);
+ else {
+ Reduction reduction =
+ new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
+ target.reductionQueue.add(reduction);
+ }
}
- }
+
holder[pos] = old;
}
- public void finish(Position r, Forest result, GSS.Phase target) {
+ void finish(Position r, Forest forest, GSS.Phase target) {
Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner());
- if (result==null) throw new Error();
- if (state0!=null)
- target.newNode(this, result, state0, r.pos<=0, r);
+ Result result = new Result(forest, this, r);
+ target.newNodeFromReduction(result, state0, r.pos<=0, r);
}
- Node(GSS.Phase phase, Node parent, Forest pending, State state) {
+ Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) {
this.phase = phase;
this.state = state;
- this.merge(parent, pending);
- GSS.Phase start = parent==null ? null : parent.phase();
- if (parent != null) addParent(parent, true);
- if (phase.hash.get(state, start) != null) throw new Error("severe problem!");
- phase.hash.put(state, start, this);
+ this.fromEmptyReduction = fromEmptyReduction;
+ results.add(result);
+ if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
+ phase.hash.put(state, result.phase(), this);
+
+ for(Object s : state.also)
+ phase.newNode(result, (State)s, fromEmptyReduction);
+
+ state.invokeReductions(phase().token, this, true, null);
+ if (!fromEmptyReduction)
+ state.invokeReductions(phase().getToken(), this, false, null);
}
- public int toInt() { return idx; }
- private final int idx = node_idx++;
// GraphViz //////////////////////////////////////////////////////////////////////////////
n.label = ""+state.toStringx();
n.shape = "rectangle";
boolean hasparents = false;
- for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); }
- for(Forest result : results()) n.edge(result, "");
+ //for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); }
+ //for(Forest result : resultMap) n.edge(result, "");
n.color = !hasparents ? "blue" : /*state.evil ? "red" :*/ "green";
((GraphViz.Group)phase().toGraphViz(gv)).add(n);
return n;
if (count <= 0) {
barf(sb, n, indent, skip, loc);
} else {
+ /*
+ FIXME: removed
for(Node nn : (Iterable<Node>)n.parents())
barf(sb, nn, indent, skip, count-1, n.phase().getLocation());
+ */
}
}
static <Tok> void barf(HashMap<Element,Input.Location> sb, Node n, int indent, boolean skip, Input.Location loc) {
//if (!p.isLast() && !p.next().isLast()) continue;
if (((p.isFirst() || p.isLast()) && !force)/* || p.owner().name==null*/ ||
!important(p)) {
+ /*
+ FIXME: removed
for(Node n2 : n.parents())
- complain(n2, errors, force /*| p.isFirst()*/, indent);
+ complain(n2, errors, force
+ //| p.isFirst()
+ , indent);
+ */
} else {
String seqname = p.owner()/*.name*/+"";
HashSet<String> hs = errors.get(seqname);
return ANSI.purple(ret.toString());
}
+ static void error(String message, GSS.Phase phase) throws ParseFailed {
+ error(message, phase.getLocation(), phase.getToken(),
+ phase, phase.getRegion(), phase.getGSS().getInput(), phase.getGSS());
+ }
static void error(String message,
Input.Location loc,
Object token,
GSS gss = new GSS(input);
Input.Location loc = input.getLocation();
Token tok = input.next();
- GSS.Phase current = gss.new Phase<Token>(null, this, null, tok, loc, input.getLocation(), null);
- current.newNode(null, Forest.create(loc.createRegion(loc), null, null, false), pt.start, true);
+ 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;
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, this, current, nextToken, loc, input.getLocation(), forest);
+ GSS.Phase next = gss.new Phase<Token>(current, current, nextToken, loc, input.getLocation(), forest);
if (!helpgc) {
FileOutputStream fos = new FileOutputStream("out-"+idx+".dot");
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
/** used to generate unique values for State.idx */
private int master_state_idx = 0;
HashMap<HashSet<Position>,State<Token>> all_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); }
cache.eof.put(start0, true);
// construct the set of states
- HashSet<SequenceOrElement> all_elements = new HashSet<SequenceOrElement>();
walk(start0, all_elements);
for(SequenceOrElement e : all_elements)
cache.ys.addAll(e, new Walk.YieldSet(e, cache).walk());
HashSet<Position> hp = new HashSet<Position>();
reachable(start0, hp);
- this.dead_state = new State<Token>(new HashSet<Position>(), all_states, all_elements);
- this.start = new State<Token>(hp, all_states, all_elements);
+ this.dead_state = new State<Token>(new HashSet<Position>());
+ this.start = new State<Token>(hp);
// for each state, fill in the corresponding "row" of the parse table
for(State<Token> state : all_states.values())
if (isRightNullable(p)) {
Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache);
Topology follow = wf.walk(p.owner());
- for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next())
+ 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 (set != null) follow = follow.intersect(set.getTokenTopology());
+ }
state.reductions.put(follow, p);
if (wf.includesEof()) state.eofReductions.add(p);
}
/** a single state in the LR table and the transitions possible from it */
- class State<Token> implements Comparable<State<Token>>, IntegerMappable, Iterable<Position> {
+ 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>>();
private transient TopologicalBag<Token,State<Token>> gotoSetTerminals = new TopologicalBag<Token,State<Token>>();
/**
* 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_states the set of states already constructed (to avoid recreating states)
* @param all_elements the set of all elements (Atom instances need not be included)
*
* In principle these two steps could be merged, but they
* for non-Atom Elements.
* </ul>
*/
- public State(HashSet<Position> hs,
- HashMap<HashSet<Position>,State<Token>> all_states,
- HashSet<SequenceOrElement> all_elements) {
+ public State(HashSet<Position> hs) { this(hs, false); }
+ public boolean special;
+ public State(HashSet<Position> hs, boolean special) {
this.hs = hs;
+ this.special = special;
// register ourselves in the all_states hash so that no
// two states are ever created with an identical position set
- all_states.put(hs, this);
+ ((HashMap)all_states).put(hs, this);
+
+ for(Position p : hs) {
+ if (!p.isFirst()) continue;
+ for(Sequence s : p.owner().needs()) {
+ if (hs.contains(s.firstp())) continue;
+ HashSet<Position> h2 = new HashSet<Position>();
+ reachable(s.firstp(), h2);
+ also.add((State<Token>)(all_states.get(h2) == null ? (State)new State<Token>(h2,true) : (State)all_states.get(h2)));
+ }
+ for(Sequence s : p.owner().hates()) {
+ if (hs.contains(s.firstp())) continue;
+ HashSet<Position> h2 = new HashSet<Position>();
+ reachable(s, h2);
+ also.add((State<Token>)(all_states.get(h2) == null ? (State)new State<Token>(h2,true) : (State)all_states.get(h2)));
+ }
+ }
// Step 1a: examine all Position's in this state and compute the mappings from
// sets of follow tokens (tokens which could follow this position) to sets
for(Topology<Token> r : bag0) {
HashSet<Position> h = new HashSet<Position>();
for(Position p : bag0.getAll(r)) h.add(p);
- gotoSetTerminals.put(r, all_states.get(h) == null ? new State<Token>(h, all_states, all_elements) : all_states.get(h));
+ ((TopologicalBag)gotoSetTerminals).put(r, all_states.get(h) == null
+ ? new State<Token>(h) : all_states.get(h));
}
// Step 2: for every non-Atom element (ie every Element which has a corresponding reduction),
}
OUTER: for(SequenceOrElement y : move) {
HashSet<Position> h = move.getAll(y);
- State<Token> s = all_states.get(h) == null ? new State<Token>(h, all_states, all_elements) : all_states.get(h);
+ State<Token> s = all_states.get(h) == null ? (State)new State<Token>(h) : (State)all_states.get(h);
// if a reduction is "lame", it should wind up in the dead_state after reducing
if (y instanceof Sequence) {
for(Position p : hs) {
return ret.toString();
}
- public int compareTo(State<Token> s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; }
+ public Walk.Cache cache() { return cache; }
public int toInt() { return idx; }
}
}
private static void reachable(Sequence s, HashSet<Position> h) {
reachable(s.firstp(), h);
- for(Sequence ss : s.needs()) reachable(ss, h);
- for(Sequence ss : s.hates()) reachable(ss, h);
+ //for(Sequence ss : s.needs()) reachable(ss, h);
+ //for(Sequence ss : s.hates()) reachable(ss, h);
}
private static void reachable(Element e, HashSet<Position> h) {
if (e instanceof Atom) return;
--- /dev/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;
+
+ public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
+ this.position = position;
+ this.result = result;
+ this.phase = target;
+ this.node = node;
+ }
+
+ public void perform() {
+ if (done) return;
+ done = true;
+ node.finish(position, result, phase);
+ }
+
+ public String toString() { return position+""; }
+
+ public int compareTo(Reduction r) {
+ int ret = compareTo0(r);
+ if (ret == 0) {
+ Walk.Cache cache = node.state().cache();
+ if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
+ if (canKill(cache, position, r.position)) ret = 1;
+ else if (canKill(cache, r.position, position)) ret = -1;
+ if (canNeed(cache, position, r.position)) ret = 1;
+ else if (canNeed(cache, r.position, position)) ret = -1;
+ }
+ return -1 * ret;
+ }
+
+ private 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 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();
+ for(Sequence killer : him.hates()) {
+ HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
+ if (eq2.contains(me)) return true;
+ }
+ return false;
+ }
+
+ 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;
+ }
+ public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
+ public GSS.Phase targetPhase() { return node.phase(); }
+
+ public 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();
+ for(Sequence needer : him.needs()) {
+ HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
+ if (eq2.contains(me)) return true;
+ }
+ return false;
+ }
+}
--- /dev/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.*;
+
+class Result {
+
+ private Forest f;
+ private Node parent;
+ private GSS.Phase phase;
+ private Position reduction;
+
+ public Position reduction() { return reduction; }
+ public GSS.Phase phase() { return phase; }
+ public Forest getForest() { return f; }
+ public Node parent() { return parent; }
+
+ public Result(Forest f, Node parent, Position reduction) {
+ this.f = f;
+ this.reduction = reduction;
+ this.parent = parent;
+ if (parent != null) phase = parent.phase();
+ }
+
+}
\ No newline at end of file
protected final Element[] elements;
+ public boolean needed_or_hated = false;
+
final HashSet<Sequence> hated = new HashSet<Sequence>();
final HashSet<Sequence> needs = new HashSet<Sequence>();
////////////////////////////////////////////////////////////////////////////////
/** return a new sequence identical to this one, but with a positive conjunct <tt>s</tt> */
- public Sequence and(Sequence s) { Sequence ret = dup(); ret.needs.add(s); return ret; }
+ public Sequence and(Sequence s) { Sequence ret = dup(); ret.needs.add(s); s.needed_or_hated=true; return ret; }
/** return a new sequence identical to this one, but with a negative conjunct <tt>s</tt> */
- public Sequence andnot(Sequence s) { Sequence ret = dup(); ret.hates.add(s); s.hated.add(ret); return ret; }
+ public Sequence andnot(Sequence s) { Sequence ret = dup(); ret.hates.add(s); s.hated.add(ret); s.needed_or_hated=true; return ret; }
/** return a new sequence identical to this one, but with a follow-set restricted to <tt>a</tt> */
public Sequence followedBy(Atom a) { Sequence ret = dup(); ret.follow = a; return ret; }
+ boolean hatesAny(Iterable<Sequence> it) {
+ if (hates.isEmpty()) return false;
+ for(Sequence s : it) if (hates.contains(s)) return true;
+ return false;
+ }
+
Iterable<Sequence> needs() { return needs; }
Iterable<Sequence> hates() { return hates; }
}
}
+ static class EquivalentTo extends Walk<HashSet<Sequence>> {
+ private final Sequence s;
+ private final HashSet<Sequence> eq = new HashSet<Sequence>();
+ public final HashSet<Sequence> walk() { return walk(s); }
+ public EquivalentTo(Sequence e, Cache c) {
+ super(c); this.s = e;
+ }
+ public HashSet<Sequence> bottom(SequenceOrElement e) { return eq; }
+ public HashSet<Sequence> walkSequence(Sequence seq) {
+ eq.add(seq);
+ Position p = seq.firstp();
+ for(; !p.isLast(); p = p.next()) {
+ if (!p.isLast() && isRightNullable(p.next()))
+ walk(p.element());
+ if (!c.possiblyEpsilon(p.element())) break;
+ }
+ return eq;
+ }
+ public HashSet<Sequence> walkAtom(Atom r) {
+ return eq;
+ }
+ private boolean isRightNullable(Position p) {
+ if (p.isLast()) return true;
+ if (!c.possiblyEpsilon(p.element())) return false;
+ return isRightNullable(p.next());
+ }
+ }
+
// Boolean //////////////////////////////////////////////////////////////////////////////
}
}
+ static class EpsilonFollowSet extends Walk<Atom> {
+ Atom all;
+ Atom empty;
+ public EpsilonFollowSet(Atom a, Atom empty, Cache c) {
+ super(c);
+ this.all = all;
+ this.empty = empty;
+ }
+ public Atom walkAtom(Atom r) { return all; }
+ public Atom walkSequence(Sequence s) {
+ if (s.follow==null) return all;
+ return s.follow;
+ }
+ public Atom sequence(Sequence s, Atom a, Atom b) {
+ throw new RuntimeException();
+ }
+ public Atom union(Union u, Atom a, Atom b) {
+ /*
+ if (a==null) return b;
+ if (b==null) return a;
+ */
+ if (a==null || b==null) return all;
+ return (Atom)a.union(b);
+ }
+ public Atom bottom(SequenceOrElement e) {
+ return (e instanceof Union) ? empty : all;
+ }
+ }
// Input-Set //////////////////////////////////////////////////////////////////////////////
public class HaskellHelper {
public static void main(String[] argv) throws Throwable {
- main(argv[0], argv[1]);
+ help(argv[0], argv[1]);
}
- public static Tree main(String grammarFile, String targetFile) throws Throwable {
+ public static boolean isNull(Object o) { return o==null; }
+ public static Tree help(String grammarFile, String targetFile) throws Throwable {
try {
Tree<String> res = new CharParser(MetaGrammar.newInstance()).parse(new FileInputStream(grammarFile)).expand1();
Union meta = Grammar.create(res, "s",
--- /dev/null
+// circular test cases
+//testcase {
+// input "x";
+// output "a:{x}";
+//
+// s = a1:: a
+// a = s1:: s
+// a = ^"x"
+//}
+//
+//testcase {
+// input "x";
+// output "x";
+// output "s2:{s2:{s0 s0} x}";
+// output "s2:{s0 x}";
+//
+//
+// s = s2:: s s
+// s = ^"x"
+// s = s0:: ()
+//}
--- /dev/null
+//////////////////////////////////////////////////////////////////////////////
+// performance hogs
+//
+//testcase {
+// input "aaaaaXaaaa";
+// output "";
+// s = ManyA &~ EndsWithZ
+// EndsWithZ = Anything "Z"
+// ManyA = () | "a" ManyA
+// Anything = () | ("a" | "X" | "Z") Anything
+//}
+
+//testcase {
+// input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
+// output "";
+// s = ManyA
+// ManyA = ()
+// | A ManyA! & ManyAB
+// A = "a"
+// ManyAB = ()
+// | "a" ManyAB
+// | "b" ManyAB
+//}
-//testcase {
-// input "x";
-// output "a:{x}";
-//
-// s = a1:: a
-// a = s1:: s
-// a = ^"x"
-//}
-//
-//testcase {
-// input "x";
-// output "x";
-// output "s2:{s2:{s0 s0} x}";
-// output "s2:{s0 x}";
-//
-//
-// s = s2:: s s
-// s = ^"x"
-// s = s0:: ()
-//}
-
testcase {
input "aaaaa";
s = A
| "a" A &~ "a" s
}
-//testcase {
-// input "a";
-// output "yes:{}";
-// s = A
-// A = "a" s &~ "a" A
-// | "a" A &~ "a" s
-// | ()
-//}
-
testcase {
input "ab c";
output "1:{{a b} {c}}";
x = ~[]
s = xbx:: x* b x*
b = abab:: [ab][ab]
- &~ ( "aa" | "bb" )
+ &~ ("aa"|"bb")
}
testcase {
idl = [a-d]
}
-//testcase {
-// input "a*b*c";
-// output "times:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}";
-// w = " "
-// l = id
-// s = l "=" r => "assign"
-// | r
-// r = l
-// | l "=" r => "assign"
-// | r "+" r => "plus"
-// | (r) "*" r => "times"
-// | "(" r ")"
-// | r r => "times"
-// id = idl++ => "stringify"
-// idl = [a-d]
-//}
-
testcase {
input "a+b*c";
output "plus:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}";
}
-
-
testcase {
input "abc ";
x = [123]
}
-
-//testcase {
-// input "ab";
-//
-// s = a:"a" b:"b"
-//}
-
-
-testcase {
- input "a c";
- s = first:: A WSA B? WSB C
- A = "a"
- B = "b"
- C = "c"
- WSA = WSA:: " "**
- WSB = () -> ~" "
- | WSB:: " "++
-}
-
-//testcase {
-// input "aaaaaXaaaa";
-// output "";
-// s = ManyA &~ EndsWithZ
-// EndsWithZ = Anything "Z"
-// ManyA = () | "a" ManyA
-// Anything = () | ("a" | "X" | "Z") Anything
-//}
-
-testcase {
- input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
- output "";
- s = ManyA
- ManyA = ()
- | A ManyA! & ManyAB
- A = "a"
- ManyAB = ()
- | "a" ManyAB
- | "b" ManyAB
-}
-
testcase {
input "aaaaaaaa";
output "";
AAs = () | AAs "aa"
}
+// make sure follow restrictions are honored
+// when a string matches the empty string
+testcase {
+ input "xxx";
+ s = x:: "x" A "x" C "x"
+ A = B
+ B = "y"
+ | () -> ~"x"
+ C = D -> ~"x"
+ D = ()
+}
+testcase {
+ input "axxxxxc";
+ output "q:{a {x x x x x} c}";
+ s = q:: A ws B? ws C
+ ws = [x]**
+ A = a:: "a"
+ B = b:: "b"
+ C = c:: "c"
+}