From a82ff8c049dd265ecf1d115d60e1be8ecb81a4c1 Mon Sep 17 00:00:00 2001 From: adam Date: Mon, 26 Mar 2007 01:44:07 -0400 Subject: [PATCH] move Walk.java->Cache.java darcs-hash:20070326054407-5007d-11bbf12fea0a13b8fa9bbf4193278de9ae4750a3.gz --- src/edu/berkeley/sbp/Cache.java | 190 +++++++++++++++++++++++ src/edu/berkeley/sbp/ParseFailed.java | 2 +- src/edu/berkeley/sbp/Walk.java | 270 --------------------------------- 3 files changed, 191 insertions(+), 271 deletions(-) create mode 100644 src/edu/berkeley/sbp/Cache.java delete mode 100644 src/edu/berkeley/sbp/Walk.java diff --git a/src/edu/berkeley/sbp/Cache.java b/src/edu/berkeley/sbp/Cache.java new file mode 100644 index 0000000..454f584 --- /dev/null +++ b/src/edu/berkeley/sbp/Cache.java @@ -0,0 +1,190 @@ +// 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.Sequence.Position; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +class Cache { + private Union root; + private Topology top; + + public HashMap follow = new HashMap(); + public HashSet followEof = new HashSet(); + public final HashMap possiblyEpsilon = new HashMap(); + public HashSet all = new HashSet(); + + public Cache(Union root, Topology top) { + this.root = root; + this.top = top; + } + + // Follow ////////////////////////////////////////////////////////////////////////////// + + public Topology follow(Sequence s) { return follow.get(s); } + + public void buildFollowSet(Sequence seq, Topology followTopology, boolean eof) { + all.add(seq); + Topology old = follow.get(seq); + if (old==null) old = followTopology; + else old = old.union(followTopology); + if (seq.follow != null) old = old.intersect(seq.follow.getTokenTopology()); + if (follow.get(seq) != null && follow.get(seq).containsAll(old) && (!eof || followEof.contains(seq))) + return; + follow.put(seq, old); + if (eof) followEof.add(seq); + + for(Position p = seq.firstp().last().prev(); p!=null; p = p.prev()) { + all.add(p.element()); + if (p.element() instanceof Union) + for(Sequence s2 : ((Union)p.element())) { + buildFollowSet(s2, followTopology, eof); + for(Sequence ss : s2.needs()) buildFollowSet(ss, followTopology, eof); + for(Sequence ss : s2.hates()) buildFollowSet(ss, followTopology, eof); + } + if (!possiblyEpsilon(p.element())) { + followTopology = followTopology.empty(); + eof = false; + } + followTopology = followTopology.union(first(p.element(), new HashSet())); + } + } + + public Topology epsilonFollowSet(Union u) { + Topology ret = top.empty(); + for(Sequence s : u) + ret = ret.union(epsilonFollowSet(s, new HashSet())); + return ret; + } + public Topology epsilonFollowSet(Sequence seq, HashSet seen) { + Topology ret = seq.follow==null ? top.empty().complement() : seq.follow.getTokenTopology(); + if (seen.contains(seq)) return ret; + seen.add(seq); + for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) { + if (!(p.element() instanceof Union)) continue; + Topology t = top.empty(); + for(Sequence s : ((Union)p.element())) + if (possiblyEpsilon(s)) + t = t.union(epsilonFollowSet(s, seen)); + ret = ret.intersect(t); + } + return ret; + } + + public Topology first(SequenceOrElement e, HashSet seen) { + if (e instanceof Atom) return ((Atom)e).getTokenTopology(); + Topology ret = top.empty(); + if (e instanceof Union) { + for(Sequence s : ((Union)e)) ret = ret.union(first(s, seen)); + } else { + Sequence seq = (Sequence)e; + if (seen.contains(seq)) return top.empty(); + seen.add(seq); + for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) { + ret = ret.union(first(p.element(), seen)); + if (!possiblyEpsilon(p.element())) break; + } + } + return ret; + } + + // Epsilon-Ness ////////////////////////////////////////////////////////////////////////////// + + final boolean possiblyEpsilon(SequenceOrElement e) { + Boolean ret = possiblyEpsilon.get(e); + if (ret != null) return ret.booleanValue(); + ret = possiblyEpsilon(e, new HashMap()); + possiblyEpsilon.put(e, ret); + return ret; + } + + private boolean possiblyEpsilon(SequenceOrElement e, HashMap hm) { + if (hm.get(e) != null) return hm.get(e); + hm.put(e, false); + boolean ret = false; + if (e instanceof Atom) ret = false; + else if (e instanceof Union) { for(Sequence s : (Union)e) ret |= possiblyEpsilon(s, hm); } + else if (e instanceof Sequence) { + ret = true; + Sequence s = (Sequence)e; + for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next()) + ret &= possiblyEpsilon(p.element(), hm); + } + hm.put(e, ret); + return ret; + } + + public boolean isRightNullable(Position p) { + if (p.isLast()) return true; + if (!possiblyEpsilon(p.element())) return false; + return isRightNullable(p.next()); + } + + public boolean isNulledSubsequence(Sequence parent, Sequence potentialSubSequence) { + HashSet eq = new HashSet(); + gatherNulledSubsequences(parent, eq); + return eq.contains(potentialSubSequence); + } + private void gatherNulledSubsequences(Sequence seq, HashSet eq) { + if (eq.contains(seq)) return; + eq.add(seq); + Position p = seq.firstp(); + for(; !p.isLast(); p = p.next()) { + if (!p.isLast() && isRightNullable(p.next()) && p.element() instanceof Union) + for(Sequence s : ((Union)p.element())) + gatherNulledSubsequences(s, eq); + if (!possiblyEpsilon(p.element())) break; + } + } + + // Position Ordinality Comparisons ////////////////////////////////////////////////////////////////////////////// + + public boolean canKill(Position mep, Position himp) { + if (!isRightNullable(mep)) return false; + if (!isRightNullable(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()) + if (isNulledSubsequence(killer, me)) + { me.canKill.put(him, true); return true; } + me.canKill.put(him, false); + return false; + } + + public boolean canNeed(Position mep, Position himp) { + if (!isRightNullable(mep)) return false; + if (!isRightNullable(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()) + if (isNulledSubsequence(needer, me)) + { me.canNeed.put(him, true); return true; } + me.canNeed.put(him, false); + return false; + } + + public int comparePositions(Position position, Position rposition) { + int ret = 0; + if (canKill(position, rposition) && canKill(rposition, position)) throw new Error(); + if (canKill(position, rposition)) ret = -1; + else if (canKill(rposition, position)) ret = 1; + else if (canNeed(position, rposition)) ret = -1; + else if (canNeed(rposition, position)) ret = 1; + /* + else if (isNulledSubsequence(position.owner(), rposition.owner()) && isNulledSubsequence(rposition.owner(), position.owner())) ret = 0; + else if (isNulledSubsequence(position.owner(), rposition.owner())) ret = 1; + else if (isNulledSubsequence(rposition.owner(), position.owner())) ret = -1; + */ + return ret; + } + +} + diff --git a/src/edu/berkeley/sbp/ParseFailed.java b/src/edu/berkeley/sbp/ParseFailed.java index 9870746..2cc9f49 100644 --- a/src/edu/berkeley/sbp/ParseFailed.java +++ b/src/edu/berkeley/sbp/ParseFailed.java @@ -84,7 +84,7 @@ public class ParseFailed extends Exception { else if (p.pos-raise > 0) barf(sb, n, indent, false, 1); */ - if (!new Walk.Cache().possiblyEpsilon(p.element())) + if (!new Cache(null, null).possiblyEpsilon(p.element())) break; p = p.next(); raise++; diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java deleted file mode 100644 index e2ac662..0000000 --- a/src/edu/berkeley/sbp/Walk.java +++ /dev/null @@ -1,270 +0,0 @@ -// 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.Sequence.Position; -import java.io.*; -import java.util.*; -import java.lang.reflect.*; -import java.lang.ref.*; - -/** a traversal of the grammar performed by mapping from SequenceOrElements to a lattice and computing the resulting LUB */ -abstract class Walk { - protected HashSet acc = new HashSet(); - protected abstract T bottom(SequenceOrElement e); - - protected final Cache c; - public Walk() { this(null); } - public Walk(Cache c) { this.c = c; } - - public T walkSequence(Sequence s) { - T ret = bottom(s); - for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next()) - ret = sequence(s, ret, walk(p.element())); - return ret; - } - - public T walkAtom(Atom r) { return walk(r); } - public T union(Union u, T a, T b) { return bottom(u); } - public T sequence(Sequence s, T a, T b) { return bottom(s); } - protected T walk(SequenceOrElement e) { - if (acc.contains(e)) return bottom(e); - acc.add(e); - return walk2(e); - } - - protected T walk2(SequenceOrElement e) { - if (e instanceof Atom) return walkAtom((Atom)e); - else if (e instanceof Sequence) return walkSequence((Sequence)e); - else if (e instanceof Union) { - T ret = bottom(e); - for(Sequence s : (Union)e) - ret = union((Union)e, ret, walk(s)); - return ret; - } else { - throw new Error("unknown element of class " + e.getClass().getName() + ": " + e); - } - } - - static class YieldSet extends Walk> { - private final SequenceOrElement e; - public final HashSet walk() { return walk(e); } - public YieldSet(SequenceOrElement e, Cache c) { super(c); this.e = e; } - public HashSet bottom(SequenceOrElement e) { return acc; } - public HashSet walkSequence(Sequence seq) { return bottom(seq); } - public HashSet walkAtom(Atom r) { - c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r)); - return super.walkAtom(r); - } - protected HashSet walk2(SequenceOrElement e) { - HashSet ret = super.walk2(e); - if (e instanceof Union) - for(Sequence s : (Union)e) { - for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss)); - for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss)); - } - return ret; - } - } - - static class YieldSet2 extends Walk> { - private final SequenceOrElement e; - public final HashSet walk() { return walk(e); } - public YieldSet2(SequenceOrElement e, Cache c) { super(c); this.e = e; } - public HashSet bottom(SequenceOrElement e) { return acc; } - public HashSet walkSequence(Sequence seq) { return bottom(seq); } - public HashSet walkAtom(Atom r) { - c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r)); - return super.walkAtom(r); - } - } - - static class EquivalentTo extends Walk> { - private final Sequence s; - private final HashSet eq = new HashSet(); - public final HashSet walk() { return walk(s); } - public EquivalentTo(Sequence e, Cache c) { - super(c); this.s = e; - } - public HashSet bottom(SequenceOrElement e) { return eq; } - public HashSet 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 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 PossiblyEpsilon extends Walk { - public Boolean walkAtom(Atom r) { return false; } - public Boolean sequence(Sequence s, Boolean a, Boolean b) { return new Boolean(a && b); } - public Boolean union(Union u, Boolean a, Boolean b) { return new Boolean(a || b); } - public Boolean bottom(SequenceOrElement e) { return (e instanceof Union) ? false : true; } - private HashMap hm = new HashMap(); - protected Boolean walk(SequenceOrElement e) { - if (hm.get(e) != null) return hm.get(e); - hm.put(e, false); - Boolean ret = walk2(e); - hm.put(e, ret); - return ret; - } - } - - static class EpsilonFollowSet extends Walk { - 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 ////////////////////////////////////////////////////////////////////////////// - - static abstract class WalkTokenSet extends Walk> { - public Topology cs; - public WalkTokenSet(Topology cs) { this.cs = cs; } - public WalkTokenSet(Topology cs, Cache c) { super(c); this.cs = cs; } - public Topology bottom(SequenceOrElement e) { return cs; } - public Topology walkAtom(Atom r) { cs = cs.union(r.getTokenTopology()); return cs; } - } - - // feature: intersect with "first" set of all positive conjuncts - static class First extends WalkTokenSet { - public First(Topology cs, Walk.Cache cache) { super(cs, cache); } - public Topology walkSequence(Sequence seq) { - for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) { - walk(p.element()); - if (!c.possiblyEpsilon(p.element())) break; - } - return cs; - } - } - - static class Follow extends WalkTokenSet { - private final SequenceOrElement me; - private final HashSet all; - private boolean eof = false; - public boolean includesEof() { return eof; } - public Follow(Topology cs, SequenceOrElement me, HashSet all, Cache c) { - super(cs, c); this.me = me; this.all = all; } - public Topology bottom(SequenceOrElement e) { return cs; } - public Topology walkSequence(Sequence seq) { return cs; } - public Topology walkAtom(Atom r) { return walk((SequenceOrElement)r); } - public Topology walk(SequenceOrElement e) { - if (acc.contains(e)) return bottom(e); - acc.add(e); - - if (c != null) { - Topology cached = (Topology)c.follow.get(e); - if (cached != null) { - cs = cs.union(cached); - eof |= c.eof.get(e); - return cs; - } - } - - Topology cso = cs; - boolean eofo = eof; - eof = c.eof.get(e) != null && c.eof.get(e).booleanValue(); - cs = cso.empty(); - - for(SequenceOrElement x : all) { - boolean matched = false; - if (!(x instanceof Sequence)) continue; - Sequence a = (Sequence)x; - Position mp = null; - for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) { - if (matched) cs = cs.union(c.first(pos.element(), cs.empty())); - if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; } - boolean good = false; - if (e instanceof Atom) { - Topology top = c.atoms.get(pos.element()); - if (top==null) continue; - if (!(top.containsAll(((Atom)e)))) continue; - } else { - if (c.ys.contains(pos.element(),e)) good = true; - } - if (good) { - mp = pos; - matched = true; - } - } - if (matched) walk(a); - } - - if (e instanceof Sequence) { - Sequence s = (Sequence)e; - if (s.follow != null) cs = cs.intersect(s.follow.getTokenTopology()); - } - - if (c != null && e==me) { - c.follow.put(e, cs); - c.eof.put(e, eof); - } - - cso = cso.union(cs); - cs = cso; - eofo |= eof; - eof = eofo; - - return cs; - } - } - - static class Cache { - public final HashMap possiblyEpsilon = new HashMap(); - public HashMap eof = new HashMap(); - public HashMap follow = new HashMap(); - public HashMapBag ys = new HashMapBag(); - public HashMapBag ys2 = new HashMapBag(); - public HashMap atoms = new HashMap(); - public Topology first(SequenceOrElement e, Topology empty) { - return new Walk.First(empty, this).walk(e); - } - final boolean possiblyEpsilon(SequenceOrElement e) { - Walk.Cache cache = this; - Boolean ret = possiblyEpsilon.get(e); - if (ret != null) return ret.booleanValue(); - ret = new Walk.PossiblyEpsilon().walk(e) ? Boolean.TRUE : Boolean.FALSE; - possiblyEpsilon.put(e, ret); - return ret; - } - } -} -- 1.7.10.4