From: adam Date: Mon, 30 Jan 2006 08:54:04 +0000 (-0500) Subject: checkpoint X-Git-Tag: tag_for_25-Mar~301 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=5d18f5606c9296e6b0c5749f05fc68f358ace2f6;hp=1a249057cbfd2180910e46672eafee3af46ae470 checkpoint darcs-hash:20060130085404-5007d-fb82bfe313a6ab5ad4e0fe6c7ca2b935760755ad.gz --- diff --git a/src/edu/berkeley/sbp/Atom.java b/src/edu/berkeley/sbp/Atom.java index a5f7e87..70c2904 100644 --- a/src/edu/berkeley/sbp/Atom.java +++ b/src/edu/berkeley/sbp/Atom.java @@ -12,6 +12,7 @@ public abstract class Atom extends Element implements Topology { protected abstract Topology top(); public abstract String toString(); + public StringBuffer toString(StringBuffer sb) { sb.append(this); return sb; } // Topology Thunks ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java index 7be02af..33bfd8d 100644 --- a/src/edu/berkeley/sbp/Element.java +++ b/src/edu/berkeley/sbp/Element.java @@ -10,13 +10,9 @@ import java.lang.ref.*; /** the root superclass for all components of the grammar (terminals, nonterminals, literals, etc) */ public abstract class Element { + abstract StringBuffer toString(StringBuffer sb); + /** if this element always matches exactly one token, return a topology covering exactly those possible tokens, otherwise null */ - Forest epsilonForm() { throw new Error("no epsilon form: " + this); } - final boolean possiblyEpsilon(Walk.Cache cache) { - Boolean ret = cache==null ? null : cache.possiblyEpsilon.get(this); - if (ret != null) return ret.booleanValue(); - ret = new Walk.PossiblyEpsilon().walk(this) ? Boolean.TRUE : Boolean.FALSE; - if (cache != null) cache.possiblyEpsilon.put(this, ret); - return ret; - } + Forest epsilonForm() { return null; } + } diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 8124590..89a16ed 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -293,6 +293,7 @@ class GSS { else state.invokeReductions(token, this, this, n2); } + public void performEmptyReductions() { state.invokeReductions(token, this, null, null); } public final void invoke(Position r, Node n, Node n2) { if (n==null || n2==null || r.pos==0) { if (r.pos==0) { @@ -351,8 +352,6 @@ class GSS { target.newNode(this, result, state0, r.pos<=0, r); } - public void performEmptyReductions() { state.invokeReductions(token, this, null, null); } - private Node(Node parent, Forest pending, State state) { this.state = state; this.holder().merge(pending); diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 4c01e33..0c9ed84 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -111,7 +111,7 @@ public abstract class Parser { private boolean isRightNullable(Position p) { if (p.isLast()) return true; - if (!p.element().possiblyEpsilon(this)) return false; + if (!possiblyEpsilon(p.element())) return false; return isRightNullable(p.next()); } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index 3ac811e..6b615dc 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -72,12 +72,10 @@ public abstract class Sequence extends Element implements Iterable { // DO NOT MESS WITH THE FOLLOWING LINE!!! private Forest.Ref epsilonForm = null; - private boolean eps = false; Forest epsilonForm() { - if (epsilonForm==null) { - epsilonForm = new Forest.Ref(); - epsilonForm.merge(firstp().rewrite2(null)); - } + if (epsilonForm!=null) return epsilonForm; + epsilonForm = new Forest.Ref(); + epsilonForm.merge(firstp().rewrite(null, false)); return epsilonForm; } @@ -123,12 +121,9 @@ public abstract class Sequence extends Element implements Iterable { // Position ///////////////////////////////////////////////////////////////////////////////// - final Forest rewrite(Input.Location loc) { - if (this==firstp()) return epsilonForm(); - return rewrite2(loc); - } - - final Forest rewrite2(Input.Location loc) { + final Forest rewrite(Input.Location loc) { return rewrite(loc, true); } + private final Forest rewrite(Input.Location loc, boolean epsilonCheck) { + if (epsilonCheck && this==firstp()) return epsilonForm(); for(int i=0; i { + /** + * Since every cycle in a non-degenerate grammar contains at + * least one Union, every instance of this class must be able to + * display itself in both "long form" (list of the long forms of + * its alternatives) and "short form" (some abbreviation). + * + * @param shortForm the "short form" display; usually + * @param synthetic if true, this Union's "long form" is "obvious" and should not be displayed when printing the grammar + */ + public Union(String shortForm) { this(shortForm, false); } + public Union(String shortForm, boolean synthetic) { + this.shortForm = shortForm; + this.synthetic = synthetic; + } + /** display form for the Union (ie not including the RHS) */ final String shortForm; @@ -25,77 +40,47 @@ public class Union extends Element implements Iterable { /** adds an alternative */ public void add(Sequence s) { alternatives.add(s); + + // FIXME: does this make sense? for(Sequence n : s.needs) add(n); for(Sequence n : s.hates) add(n); } - /** - * Since every cycle in a non-degenerate grammar contains at - * least one Union, every instance of this class must be able to - * display itself in both "long form" (list of the long forms of - * its alternatives) and "short form" (some abbreviation). - * - * @param shortForm the "short form" display; usually - * @param synthetic if true, this Union's "long form" is "obvious" and should not be displayed when printing the grammar - */ - public Union(String shortForm) { this(shortForm, false); } - public Union(String shortForm, boolean synthetic) { - this.shortForm = shortForm; - this.synthetic = synthetic; - } + // Epsilon Form ////////////////////////////////////////////////////////////////////////////// + // FIXME public static Union epsilon = new Union("()"); static { epsilon.add(Sequence.empty); } + // FIXME private Forest.Ref epsilonForm = null; Forest epsilonForm() { if (epsilonForm != null) return epsilonForm; epsilonForm = new Forest.Ref(); - for(Sequence s : this) - if (s.possiblyEpsilon(null)) + for(Sequence s : this) { + // FIXME FIXME FIXME + if (new Walk.Cache().possiblyEpsilon(s)) epsilonForm.merge(s.epsilonForm()); + } return epsilonForm; } // Display ////////////////////////////////////////////////////////////////////////////// public String toString() { return shortForm; } - private static String pad(int i,String s) { return s.length() >= i ? s : pad(i-1,s)+" "; } - public void toString(StringBuffer sb) { - if (synthetic) return; + public StringBuffer toString(StringBuffer sb) { + if (synthetic) return sb; boolean first = true; if (alternatives.size()==0) { - sb.append(pad(15, shortForm) + "::= "); + sb.append(StringUtil.pad(15, shortForm) + " = "); } else for(Sequence s : this) { - sb.append(pad(15, first ? shortForm : "") + (first ? "::= " : " | ")); + sb.append(StringUtil.pad(15, first ? shortForm : "") + (first ? " = " : " | ")); first = false; sb.append(s.toString()); sb.append('\n'); } sb.append('\n'); - } - - // SubUnion ////////////////////////////////////////////////////////////////////////////// - - /** FIXME this is kind of a hack */ - public class Subset extends Union { - private final Set exclude; - public Subset(String shortForm, Set exclude) { super(shortForm, true); this.exclude = exclude; } - public Iterator iterator() { - final Iterator it = Union.this.iterator(); - return new Iterator() { - private Sequence next = it.hasNext() ? it.next() : null; - public boolean hasNext() { return next != null; } - public Sequence next() { - Sequence ret = next; - do { - next = it.hasNext() ? it.next() : null; - } while (next != null && (next instanceof Sequence) && exclude.contains((Sequence)next)); - return ret; - } - public void remove() { throw new Error(); } - }; - } + return sb; } } diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java index 04e36ae..8c6ecae 100644 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -90,7 +90,7 @@ abstract class Walk { public Topology sequence(Sequence seq) { for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) { walk(p.element()); - if (!p.element().possiblyEpsilon(c)) break; + if (!c.possiblyEpsilon(p.element())) break; } return cs; } @@ -130,7 +130,7 @@ abstract class Walk { 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 && pos.element().possiblyEpsilon(c)); continue; } + if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; } boolean good = false; if (e instanceof Atom) { Topology top = c.atoms.get(pos.element()); @@ -175,5 +175,13 @@ abstract class Walk { public Topology first(Element e, Topology empty) { return new Walk.First(empty, this).walk(e); } + final boolean possiblyEpsilon(Element 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; + } } } diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java index 0493cb1..9f67307 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammar.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -277,8 +277,8 @@ public class MetaGrammar extends StringWalker { } else { if (keeping) drops[i] = true; } - if (oi==SELF) o2[j] = u.new Subset("(("+u+"))", set); - else o2[j] = (Element)oi; + /*if (oi==SELF) o2[j] = u.new Subset("(("+u+"))", set); + else*/ o2[j] = (Element)oi; if (MetaGrammar.dropAll.contains(o2[j])) drops[j] = true; nonDrop += drops[j] ? 0 : 1; diff --git a/src/edu/berkeley/sbp/util/StringUtil.java b/src/edu/berkeley/sbp/util/StringUtil.java index 5e39447..41e67e9 100644 --- a/src/edu/berkeley/sbp/util/StringUtil.java +++ b/src/edu/berkeley/sbp/util/StringUtil.java @@ -3,6 +3,10 @@ package edu.berkeley.sbp.util; /** miscellaneous string utilities */ public class StringUtil { + public static String pad(int i,String s) { + return s.length() >= i ? s : pad(i-1,s)+" "; + } + public static String join(String[] s, String sep) { StringBuffer ret = new StringBuffer(); for(int i=0; i