From: adam Date: Mon, 2 Jan 2006 03:49:24 +0000 (-0500) Subject: convered maximal to use character lookahead X-Git-Tag: tag_for_25-Mar~475 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=0516ea34996c86664928ef948013b749876b87ec convered maximal to use character lookahead darcs-hash:20060102034924-5007d-d76e881205902ded81ca8826b94b9e865e1e232c.gz --- diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java index 5f55be6..b440257 100644 --- a/src/edu/berkeley/sbp/Element.java +++ b/src/edu/berkeley/sbp/Element.java @@ -14,6 +14,7 @@ public abstract class Element { abstract void reachable(HashSet rp); abstract Topology toAtom(); + public Topology noFollow() { return 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); diff --git a/src/edu/berkeley/sbp/Repeat.java b/src/edu/berkeley/sbp/Repeat.java index 48ac386..bc6626a 100644 --- a/src/edu/berkeley/sbp/Repeat.java +++ b/src/edu/berkeley/sbp/Repeat.java @@ -20,48 +20,47 @@ public class Repeat extends Union { public static Repeat many1(Element e) { return new Repeat(e, false, true); } /** repeat one or more times, separated by sep */ public static Repeat many1(Element e, Element sep) { return new Repeat(e, false, true, sep); } - public static Maximal maximal(Element e) { return new Maximal(e); } + /** repeat zero or more times, matching a maximal sequence of atoms */ + public static Repeat maximal0(Element e) { return new Repeat(e, true, true, null, true); } + /** repeat one or more times, matching a maximal sequence of atoms */ + public static Repeat maximal1(Element e) { return new Repeat(e, false, true, null, true); } + /** repeat one or more times, separated by sep, matching a maximal sequence of atoms */ + public static Repeat maximal1(Element e, Element sep) { return new Repeat(e, false, true, sep, true); } // Instance ////////////////////////////////////////////////////////////////////////////// final boolean zeroOkay, manyOkay; final Element e; final Element separator; + final boolean maximal; Repeat(final Element e, boolean zeroOkay, boolean manyOkay) { this(e, zeroOkay, manyOkay, null); } - Repeat(final Element e, boolean zeroOkay, boolean manyOkay, Element separator) { + Repeat(final Element e, boolean zeroOkay, boolean manyOkay, Element separator) { this(e, zeroOkay, manyOkay, separator, false); } + Repeat(final Element e, boolean zeroOkay, boolean manyOkay, final Element separator, boolean maximal) { super(e+(!manyOkay ? "?" : (zeroOkay ? "*" : "+"))+(separator==null?"":("/"+separator.toString())), true); this.e = e; + this.maximal = maximal; this.zeroOkay = zeroOkay; this.manyOkay = manyOkay; this.separator = separator; + Union who = this; + if (maximal) { + who = new Union(this+"++"); + add(new Sequence.Singleton(who, null, null) { + public Topology noFollow() { return separator==null ? e.toAtom() : separator.toAtom(); } + }); + } if (zeroOkay) { - add(new Sequence.Constant.Empty()); - if (manyOkay) add(new Sequence.Singleton(many1(e, separator), null, null)); - else add(new Sequence.Singleton(e, null, null)); + who.add(new Sequence.Constant.Empty()); + if (manyOkay) who.add(new Sequence.Singleton(many1(e, separator), null, null)); + else who.add(new Sequence.Singleton(e, null, null)); } else { - add(new Sequence.RewritingSequence(null, new Element[] { e }, null, null)); + who.add(new Sequence.RewritingSequence(null, new Element[] { e }, null, null)); if (this.separator==null) { - add(new Sequence.Unwrap(new Element[] { e, Repeat.this }, null, null)); + who.add(new Sequence.Unwrap(new Element[] { e, Repeat.this }, null, null)); } else { - add(new Sequence.Unwrap(new Element[] { e, this.separator, Repeat.this }, new boolean[] { false, true, false }, null, null)); + who.add(new Sequence.Unwrap(new Element[] { e, this.separator, Repeat.this }, new boolean[] { false, true, false }, null, null)); } } } - - static class MaximalSequence extends Sequence.Singleton { - private final Element e; - public String toString() { return e+"@"; } - public Topology noFollow() { return e.toAtom(); } - public MaximalSequence(Element e) { - super(e, null, null); - this.e = e; - } - } - static class Maximal extends Union { - public Maximal(final Element e) { - super(e+"+", true); - add(new MaximalSequence(e)); - } - } } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index a5149f2..d252604 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -38,8 +38,7 @@ public abstract class Sequence extends Element implements Iterable { public Topology noFollow() { return null; } Topology toAtom() { - if (elements.length>1) throw new RuntimeException("cannot invoke toAtom() on a Sequence with " + elements.length + " elements: " + this); - if (elements.length==0) return null; + if (elements.length!=1) throw new RuntimeException("cannot invoke toAtom() on a Sequence with " + elements.length + " elements: " + this); return elements[0].toAtom(); } diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java index a7a7630..db0db7d 100644 --- a/src/edu/berkeley/sbp/Union.java +++ b/src/edu/berkeley/sbp/Union.java @@ -23,10 +23,10 @@ public class Union extends Element implements Iterable { Topology ret = null; for(Sequence s : this) { Topology a = s.toAtom(); - if (a==null) continue; if (ret==null) ret = a.dup(); - else ret.add(a.dup()); + else ret = ret.union(a.dup()); } + if (ret==null) throw new RuntimeException("confusion on " + this); return ret; } diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java index cfd9c31..8b6eae6 100644 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -164,14 +164,11 @@ abstract class Walk { if (matched) walk(a); } - if (e instanceof Repeat.MaximalSequence || e instanceof Repeat.Maximal) - cs.remove(new Last(cs.fresh(), c).walk(e)); - /* if (e instanceof Sequence) { Sequence s = (Sequence)e; - if (s.noFollow() != null) cs.remove(s.noFollow()); + if (s.noFollow() != null) cs.remove(s.noFollow().dup()); } - */ + if (c != null && e==me) { c.follow.put(e, cs.dup()); c.eof.put(e, eof); diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java index 861b5a9..85b17ee 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammar.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -96,8 +96,8 @@ public class MetaGrammar extends StringWalker { else if ("+".equals(head)) return Repeat.many1((Element)walk(tree.child(0))); else if ("+/".equals(head)) return Repeat.many1((Element)walk(tree.child(0)), (Element)walk(tree.child(1))); else if ("*/".equals(head)) return Repeat.many0((Element)walk(tree.child(0)), (Element)walk(tree.child(1))); - else if ("**".equals(head)) return Repeat.maximal(Repeat.many0((Element)walk(tree.child(0)))); - else if ("++".equals(head)) return Repeat.maximal(Repeat.many1((Element)walk(tree.child(0)))); + else if ("**".equals(head)) return Repeat.maximal0((Element)walk(tree.child(0))); + else if ("++".equals(head)) return Repeat.maximal1((Element)walk(tree.child(0))); else if ("?".equals(head)) return Repeat.maybe((Element)walk(tree.child(0))); else if ("&".equals(head)) return ((PreSequence)walk(tree,0)).and(new PreSequence((Element[])Reflection.lub((Object[])walk(tree, 1)), null).buildSequence(null, true, false)); @@ -300,6 +300,9 @@ public class MetaGrammar extends StringWalker { + + + // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }), new Tree(null, "grammar", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "s", new Tree[] { })}), @@ -746,9 +749,9 @@ new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }), new Tree(null, "nonTerminal", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), new Tree(null, "s", new Tree[] { })})})})})})}), new Tree(null, "!::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { })}), - new Tree(null, null, new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, " ", new Tree[] { })})}), - new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\n", new Tree[] { })})}), - new Tree(null, "qprod", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\r", new Tree[] { })})})})})}), + new Tree(null, null, new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "ps", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "[", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, " ", new Tree[] { })}), + new Tree(null, "range", new Tree[] { new Tree(null, "\r", new Tree[] { })}), + new Tree(null, "range", new Tree[] { new Tree(null, "\n", new Tree[] { })})})})})})})})}), new Tree(null, "::=", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), new Tree(null, "o", new Tree[] { }), new Tree(null, "r", new Tree[] { }), @@ -846,3 +849,6 @@ new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }), + + + diff --git a/src/edu/berkeley/sbp/tib/Tib.java b/src/edu/berkeley/sbp/tib/Tib.java index 9b4b974..39f6071 100644 --- a/src/edu/berkeley/sbp/tib/Tib.java +++ b/src/edu/berkeley/sbp/tib/Tib.java @@ -289,10 +289,8 @@ public class Tib implements Token.Stream { public static class Grammar extends MetaGrammar { private int anon = 0; - private final Element ws = Repeat.maximal(Repeat.many0(nonTerminal("w"))); - public Grammar() { - dropAll.add(ws); - } + private final Element ws = Repeat.maximal0(nonTerminal("w")); + public Grammar() { dropAll.add(ws); } public Object walk(Tree tree) { String head = tree.head(); if (tree.numChildren()==0) return super.walk(tree); diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java index 7812a51..2a1bb53 100644 --- a/src/edu/berkeley/sbp/util/TopologicalBag.java +++ b/src/edu/berkeley/sbp/util/TopologicalBag.java @@ -27,7 +27,7 @@ public class TopologicalBag implements MapBag,V> { public void add(Topology t, V v) { put(t, v); } public void addAll(Topology k, Iterable vi) { putAll(k, vi); } - public void putAll(Topology k, Iterable vi) { for(V v : vi) put(k, v); } + public void putAll(Topology k, Iterable vi) { if (vi!=null) for(V v : vi) put(k, v); } public void put(Topology t, V v) { for(Topology ht : h.keySet()) { if (t.disjoint(ht)) continue; @@ -59,7 +59,9 @@ public class TopologicalBag implements MapBag,V> { TopologicalBag ret = new TopologicalBag(); for(Topology ht : h.keySet()) { if (ht.disjoint(t)) continue; - ret.putAll(ht.intersect(t), h.get(ht)); + Iterable it = h.get(ht); + Topology tk = ht.intersect(t); + ret.putAll(tk, it); } return ret; }