From 225993309e6183afa9a88fc13d39df56be54b992 Mon Sep 17 00:00:00 2001 From: adam Date: Thu, 25 May 2006 02:24:33 -0400 Subject: [PATCH] checkpoint darcs-hash:20060525062433-5007d-90fbda2556bfdb1e4fb9f52bc023255ec8976f00.gz --- src/edu/berkeley/sbp/Forest.java | 2 +- src/edu/berkeley/sbp/GSS.java | 74 ++-- src/edu/berkeley/sbp/Repeat.java | 9 +- src/edu/berkeley/sbp/Sequence.java | 14 +- src/edu/berkeley/sbp/Walk.java | 2 +- src/edu/berkeley/sbp/chr/CharInput.java | 4 +- src/edu/berkeley/sbp/chr/CharTopology.java | 2 +- src/edu/berkeley/sbp/misc/MetaGrammar.java | 518 ++++++++++++++++++++++++++-- src/edu/berkeley/sbp/util/GraphViz.java | 21 +- tests/meta.g | 11 +- tests/regression.tc | 18 +- 11 files changed, 578 insertions(+), 97 deletions(-) diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 9dabf60..3790562 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -71,7 +71,7 @@ public abstract class Forest /*extends PrintableTree>*/ public GraphViz.Node toGraphViz(GraphViz gv) { if (gv.hasNode(this)) return gv.createNode(this); GraphViz.Node n = gv.createNode(this); - n.label = StringUtil.escapify(headToString()==null?"":headToString(), "\r\n"); + n.label = headToString()==null?"":headToString(); n.directed = true; n.comment = reduction==null?null:reduction+""; edges(n); diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 87bcf04..743cfd3 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -17,11 +17,10 @@ class GSS { public int resets = 0; public int waits = 0; - HashMapBag inhibited = new HashMapBag(); - HashMapBag expectedInhibit = new HashMapBag(); HashMapBag waiting = new HashMapBag(); HashMapBag performed = new HashMapBag(); HashMapBag lastperformed = new HashMapBag(); + HashMapBag expected = new HashMapBag(); /** FIXME */ public Forest.Ref finalResult; @@ -57,19 +56,18 @@ class GSS { this.pos = previous==null ? 0 : previous.pos+1; this.token = token; this.location = location; - inhibited.clear(); + performed.clear(); reset(); } public void reset() throws ParseFailed { waiting.clear(); + expected.clear(); lastperformed.clear(); lastperformed.addAll(performed); performed.clear(); hash = new IntPairMap(); singularReductions = new IntPairMap(); - expectedInhibit.clear(); - expectedInhibit.addAll(inhibited); reset = false; good = false; closed = false; @@ -105,28 +103,32 @@ class GSS { Sequence owner = reduction==null ? null : reduction.owner(); if (reduction!=null) { if (owner.hates!=null) { - for (Sequence s : lastperformed.getAll(pos)) - if (owner.hates.contains(s)) - return; 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 (inhibited.contains(pos, owner)) 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 ((owner.needed != null && owner.needed.size()>0) || - (owner.hated != null && owner.hated.size()>0) || - (owner.hates != null && owner.hates.size()>0)) + 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; + } + } } - if (reduction!=null) uninhibit(reduction, parent==null?0:parent.phase().pos); if (!owner.lame) newNode(parent, pending, state, fromEmptyReduction); if (reduction != null) { @@ -171,30 +173,6 @@ class GSS { return true; } - public void inhibit(int p, Sequence s) { - //if (inhibited.contains(p, s)) return; - if (performed.contains(p, s)) throw new Reset(); - /* - if (s.hated!=null) - for(Sequence s2 : s.hated) - uninhibit(p, s2); - */ - if (s.needed!=null) - for(Sequence s2 : s.needed) - if (performed.contains(p, s2)) - throw new Reset(); - if (performed.contains(p, s)) throw new Reset(); - } - - public void uninhibit(Position r, int p) { uninhibit(p, r.owner()); } - public void uninhibit(int p, Sequence s) { - if (performed.contains(p, s)) return; - performed.add(p, s); - if (s.hated != null) - for(Sequence seq : s.hated) - inhibit(p, seq); - } - /** perform all reduction operations */ public void reduce() throws ParseFailed { try { @@ -213,22 +191,18 @@ class GSS { reducing_list[i] = null; n.performReductions(); } - /* - if (expectedInhibit.size() > 0) { - System.out.println("\n!!!!"); - for(int i : expectedInhibit) - for(Sequence es : expectedInhibit.getAll(i)) - System.out.println(" " + i + ": " + es); - System.out.println(""); - inhibited.removeAll(expectedInhibit); - throw new Reset(); - } - */ 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(); diff --git a/src/edu/berkeley/sbp/Repeat.java b/src/edu/berkeley/sbp/Repeat.java index 4868135..2dd3928 100644 --- a/src/edu/berkeley/sbp/Repeat.java +++ b/src/edu/berkeley/sbp/Repeat.java @@ -8,9 +8,9 @@ import java.lang.reflect.*; import java.lang.ref.*; /** currently this class exports only static methods to create repetitions; there are no public instance methods or constructors */ -class Repeat extends Union { +/* FIXME make private again */ public class Repeat extends Union { - Repeat(final Element e, boolean zeroOkay, boolean manyOkay, final Element separator, boolean maximal) { + public Repeat(final Element e, boolean zeroOkay, boolean manyOkay, final Element separator, boolean maximal) { this(e, zeroOkay, manyOkay, separator, maximal, null); } Repeat(final Element e, boolean zeroOkay, boolean manyOkay, final Element separator, boolean maximal, Object tag) { super(e+(!manyOkay ? "?" : (zeroOkay ? (maximal ? "**" : "*") : (maximal ? "++" : "+")))+(separator==null?"":("/"+separator)), true); @@ -27,6 +27,9 @@ class Repeat extends Union { else add(new Sequence.Unwrap(new Element[] { e, separator, Repeat.this }, tag, new boolean[] { false, true, false })); } - if (maximal) for(Sequence s : this) s.noFollow = separator==null ? e : separator; + // FIXME: hack! + if (maximal) + for(Sequence s : this) + s.follow = new edu.berkeley.sbp.misc.MetaGrammar.Invert(new edu.berkeley.sbp.misc.MetaGrammar.Infer(separator==null ? e : separator)); } } diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index 2ba9096..68e9357 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -17,7 +17,7 @@ public abstract class Sequence extends Element implements Iterable { Sequence ret = _clone(); for(Sequence s : needs) { ret.needs.add(s); s.needed.add(ret); } for(Sequence s : hates) { ret.hates.add(s); s.hated.add(ret); } - ret.noFollow = noFollow; + ret.follow = follow; return ret; } @@ -44,8 +44,8 @@ public abstract class Sequence extends Element implements Iterable { //////////////////////////////////////////////////////////////////////////////// - public Element noFollow = null; - public final Topology noFollow() { return noFollow==null ? null : Atom.toAtom(noFollow); } + public Element follow = null; + public final Topology follow() { return follow==null ? null : Atom.toAtom(follow); } Topology toAtom() { if (elements.length!=1) throw new RuntimeException("cannot invoke toAtom() on a Sequence with " + elements.length + " elements: " + this); @@ -162,6 +162,10 @@ public abstract class Sequence extends Element implements Iterable { sb.append(elements[i].toString()); sb.append(' '); } + if (follow != null) { + sb.append("-> "); + sb.append(follow); + } return sb; } @@ -238,11 +242,11 @@ public abstract class Sequence extends Element implements Iterable { } public StringBuffer toString(StringBuffer sb, boolean spacing) { int len = sb.length(); + if (tag != null) + sb.append("\""+StringUtil.escapify(tag.toString(),"\"\r\n")+"\":: "); super.toString(sb, spacing); len = sb.length()-len; if (spacing) for(int i=0; i<50-len; i++) sb.append(' '); - sb.append(" => "); - sb.append(tag); return sb; } } diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java index 8c6ecae..cd991e8 100644 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -149,7 +149,7 @@ abstract class Walk { if (e instanceof Sequence) { Sequence s = (Sequence)e; - if (s.noFollow() != null) cs = cs.minus(s.noFollow()); + if (s.follow() != null) cs = cs.intersect(s.follow()); } if (c != null && e==me) { diff --git a/src/edu/berkeley/sbp/chr/CharInput.java b/src/edu/berkeley/sbp/chr/CharInput.java index 7953418..f86e85f 100644 --- a/src/edu/berkeley/sbp/chr/CharInput.java +++ b/src/edu/berkeley/sbp/chr/CharInput.java @@ -18,13 +18,15 @@ public class CharInput extends Cartesian.Input { public CharInput(InputStream i, String s) { this(new InputStreamReader(i), s); } boolean cr = false; + private int count = 0; public boolean isCR() { return cr; } public Character next() throws IOException { cr = false; int i = r.read(); - if (i==-1) return null; + if (i==-1) { System.err.print("\r...done \r"); return null; } char c = (char)i; cr = c=='\n'; + System.err.print(" " + (count++) + "\r"); return c; } } diff --git a/src/edu/berkeley/sbp/chr/CharTopology.java b/src/edu/berkeley/sbp/chr/CharTopology.java index d407e99..d812855 100644 --- a/src/edu/berkeley/sbp/chr/CharTopology.java +++ b/src/edu/berkeley/sbp/chr/CharTopology.java @@ -13,12 +13,12 @@ public class CharTopology extends IntegerTopology implements Functor< public String toString() { StringBuffer sb = new StringBuffer(); - sb.append('['); Range.Set ranges = getRanges(); if (ranges.size() == -1 || ranges.size() > Character.MAX_VALUE/2) { sb.append('~'); ranges = ranges.complement(); } + sb.append('['); ranges = ranges.intersect(new Range.Set(new Range(0, Character.MAX_VALUE))); for(Range r : ranges) { if (r.isMinNegInf() || r.isMaxPosInf()) throw new Error("should not happen"); diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java index 972d3a1..869e0fa 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammar.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -7,8 +7,10 @@ import java.io.*; public class MetaGrammar extends StringWalker { + public static Object repeatTag = null; + /** an atom which tracks the possible tokenset of some element, provided that element can only match single-token sequences */ - static class Infer extends Atom { + public static class Infer extends Atom { private final Element e; public Infer(Element e) { this.e = e; } public Topology top() { return (Topology)toAtom(e); } @@ -16,7 +18,7 @@ public class MetaGrammar extends StringWalker { } /** an atom which tracks the inverse of some other atom */ - static class Invert extends Atom { + public static class Invert extends Atom { private final Atom a; public Invert(Atom a) { this.a = a; } public Topology top() { return a.complement(); } @@ -28,12 +30,13 @@ public class MetaGrammar extends StringWalker { static final Topology leftright = CharRange.rightBrace.union(CharRange.leftBrace); public Hack(Atom a) { this.a = a; } public Topology top() { return a.minus(leftright); } - public String toString() { return "~"+a; } + public String toString() { return a.toString(); } } - public static Union make() throws Exception { - return ((MetaGrammar)new MetaGrammar().walk(meta)).done(); + Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(meta); + BuildContext bc = new BuildContext(mgf); + return mgf.get("s").build(bc); } public String toString() { StringBuffer ret = new StringBuffer(); @@ -54,12 +57,12 @@ public class MetaGrammar extends StringWalker { private HashMap nt; private int anon = 0; private String startSymbol; - private boolean strings; + private static boolean strings; - private Element set(Range.Set r) { if (strings) throw new Error(); return CharRange.set(r); } - private Element string(String s) { return strings ? StringInput.string(s) : CharRange.string(s); } - private Atom leftBrace() { return strings ? StringInput.leftBrace : CharRange.leftBrace; } - private Atom rightBrace() { return strings ? StringInput.rightBrace : CharRange.rightBrace; } + private static Element set(Range.Set r) { if (strings) throw new Error(); return CharRange.set(r); } + private static Element string(String s) { return strings ? StringInput.string(s) : CharRange.string(s); } + private static Atom leftBrace() { return strings ? StringInput.leftBrace : CharRange.leftBrace; } + private static Atom rightBrace() { return strings ? StringInput.rightBrace : CharRange.rightBrace; } public MetaGrammar() { this("s", false); } public MetaGrammar(String s) { this(s, false); } @@ -107,12 +110,12 @@ public class MetaGrammar extends StringWalker { return n; } - public String string(Iterable> children) { + public static String string(Iterable> children) { String ret = ""; for(Tree t : children) ret += string(t); return ret; } - public String string(Tree tree) { + public static String string(Tree tree) { String ret = ""; if (tree.head()!=null) ret += tree.head(); ret += string(tree.children()); @@ -125,6 +128,319 @@ public class MetaGrammar extends StringWalker { public Sequence sequence(Object o, boolean lame) { return new PreSequence((Element[])Reflection.lub((Object[])o), null).buildSequence(null, lame, false); } + + public static class BuildContext extends HashMap { + private final Meta.MetaGrammarFile mgf; + public BuildContext(Meta.MetaGrammarFile mgf) { this.mgf = mgf; } + public Union build(String s) { + Union ret = get(s); + if (ret != null) return ret; + return mgf.get(s).build(this); + } + } + + public static class Meta { + public static class MetaGrammarFile extends HashMap { + public MetaGrammarFile(Tree tree) { + if (!tree.head().equals("grammar")) throw new Error(); + for(Tree nt : tree.child(0)) + add(new MetaNonterminal(nt)); + } + private void add(MetaNonterminal mnt) { + this.put(mnt.name, mnt); + } + public String toString() { + String ret = ""; + for(MetaNonterminal mnt : this.values()) ret += mnt + "\n"; + return ret; + } + } + public static class MetaNonterminal { + public String name; + public MetaUnion rhs; + public MetaNonterminal(Tree tree) { + System.err.println("MetaNonterminal("+tree+")"); + name = string(tree.child(0)); + rhs = rhs(tree.child(1)); + } + public String toString() { return name + " = " + rhs; } + public Union build(BuildContext bc) { return rhs.build(bc, name); } + } + public static MetaUnion rhs(Tree t) { + return t.numChildren()==1 + ? new MetaUnion(t.child(0), false) + : new MetaUnion(t, true); + } + public static class MetaUnion implements MetaSequence { + public boolean prioritized; + public MetaSequence[] sequences; + public Sequence buildSequence(BuildContext bc) { + return Sequence.singleton(new Element[] { buildAnon(bc) }, 0); + } + public Union buildAnon(BuildContext bc) { + String s = ""; + for(int i=0; i0?"\n "+(prioritized?">":"|")+" ":"")+sequences[i].buildSequence(bc); + return build(bc, s); + } + public Union build(BuildContext bc, String name) { + Union u = bc.get(name); + if (u != null) return u; + u = new Union(name); + bc.put(name, u); + HashSet seqs = new HashSet(); + for(MetaSequence s : sequences) { + Sequence seq = s.buildSequence(bc); + if (seq != null) { + Sequence oseq = seq; + if (prioritized) + for(Sequence seqprev : seqs) + seq = seq.not(seqprev); + u.add(seq); + seqs.add(oseq); + } + } + return u; + } + public MetaUnion(Tree t, boolean prioritized) { + System.err.println("MetaUnion("+t+")"); + //System.err.println("metaunion: " + t); + this.prioritized = prioritized; + int i = 0; + this.sequences = new MetaSequence[t.numChildren()]; + for(Tree tt : t) + sequences[i++] = prioritized + ? new MetaUnion(tt, false) + : makeMetaSequence(tt); + } + public String toString() { + String ret = "\n "; + for(int i=0; i " : "\n | "); + } + return ret; + } + } + + public interface MetaSequence { + public abstract Sequence buildSequence(BuildContext bc); + } + + public static MetaSequence makeMetaSequence(Tree t) { + System.err.println("MetaSequence("+t+")"); + if ("psx".equals(t.head())) return MetaConjunct.make(t.child(0)); + if (t.head().equals("&")) return new MetaAnd(makeMetaSequence(t.child(0)), MetaConjunct.make(t.child(1)), false); + if (t.head().equals("&~")) return new MetaAnd(makeMetaSequence(t.child(0)), MetaConjunct.make(t.child(1)), true); + return null; + } + + public static class MetaAnd implements MetaSequence { + boolean not; + MetaSequence left; + MetaSequence right; + public Sequence buildSequence(BuildContext bc) { + Sequence ret = left.buildSequence(bc); + if (not) ret.not(right.buildSequence(bc)); else ret.and(right.buildSequence(bc)); + return ret; + } + public MetaAnd(MetaSequence left, MetaSequence right, boolean not) { + this.left = left; + this.right = right; + this.not = not; + } + public String toString() { return left + " &"+(not?"~":"")+" " /* FIXME */; } + } + + public static class MetaConjunct implements MetaSequence { + public boolean negated = false; + public MetaClause[] elements; + public MetaClause followedBy = null; + public String tag; + public MetaClause separator; + public Sequence buildSequence(BuildContext bc) { + Element[] els = new Element[elements.length + (separator==null?0:(elements.length-1))]; + boolean[] drops = new boolean[elements.length + (separator==null?0:(elements.length-1))]; + boolean unwrap = false; + boolean dropAll = false; + if (tag!=null && tag.equals("[]")) unwrap = true; + if (tag!=null && "()".equals(tag)) dropAll=true; + for(int i=0; i t) { + System.err.println("MetaConjunct("+t+")"); + elements = new MetaClause[t.numChildren()]; + int i = 0; for(Tree tt : t) + elements[i++] = MetaClause.make(tt, this); + } + public String toString() { + String ret = (tag==null ? "" : (tag+":: ")) + (negated ? "~" : ""); + if (elements.length > 1) ret += "("; + for(MetaClause mc : elements) ret += (" " + mc + " "); + if (separator != null) ret += " /" + separator; + if (followedBy != null) ret += " -> " + followedBy; + if (elements.length > 1) ret += ")"; + return ret; + } + public static MetaConjunct make(Tree t) { + System.err.println("MetaConjunct.make("+t+")"); + if ("/".equals(t.head())) { + MetaConjunct ret = make(t.child(0)); + ret.separator = MetaClause.make(t.child(1), ret); + return ret; + } + if ("->".equals(t.head())) { + MetaConjunct ret = make(t.child(0)); + ret.followedBy = MetaClause.make(t.child(1), ret); + return ret; + } + if ("::".equals(t.head())) { + MetaConjunct ret = make(t.child(1)); + ret.tag = string(t.child(0)); + return ret; + } + if ("ps".equals(t.head())) { + return new MetaConjunct(t.child(0)); + } + return new MetaConjunct(t); + } + } + + public static abstract class MetaClause { + public String label = null; + public boolean drop = false; + public boolean lift = false; + public abstract Element build(BuildContext bc); + public static MetaClause make(Tree t, MetaConjunct c) { + System.err.println("MetaClause.make("+t+")"); + if (t.head().equals("{")) throw new Error("metatree: " + t); + if (t.head().equals("*")) return new MetaRepeat(make(t.child(0), c), false, null, true, true); + if (t.head().equals("+")) return new MetaRepeat(make(t.child(0), c), false, null, false, true); + if (t.head().equals("?")) return new MetaRepeat(make(t.child(0), c), false, null, true, false); + if (t.head().equals("**")) return new MetaRepeat(make(t.child(0), c), true, null, true, true); + if (t.head().equals("++")) return new MetaRepeat(make(t.child(0), c), true, null, false, true); + if (t.head().equals("*/")) return new MetaRepeat(make(t.child(0), c), false, make(t.child(1), c), true, true); + if (t.head().equals("+/")) return new MetaRepeat(make(t.child(0), c), false, make(t.child(1), c), false, true); + if (t.head().equals("**/")) return new MetaRepeat(make(t.child(0), c), true, make(t.child(1), c), true, true); + if (t.head().equals("++/")) return new MetaRepeat(make(t.child(0), c), true, make(t.child(1), c), false, true); + if (t.head().equals("()")) return new MetaEpsilon(); + if (t.head().equals("[")) return new MetaRange(t.child(0)); + if (t.head().equals("literal")) return new MetaStringLiteral(t.child(0)); + if (t.head().equals("nonTerminal")) return new MetaNonterminalReference(t.child(0)); + if (t.head().equals(")")) return new MetaSelfReference(); + if (t.head().equals("(")) return new MetaParens(t.child(0)); + if (t.head().equals("~")) return new MetaInvert(t.child(0), c); + if (t.head().equals("!")) { MetaClause mc = make(t.child(0), c); mc.drop = true; return mc; } + if (t.head().equals("^")) { c.tag = string(t.child(0)); return new MetaStringLiteral(t.child(0)); } + if (t.head().equals("^^")) throw new Error("carets: " + t); + throw new Error("unknown: " + t); + } + public static class MetaRepeat extends MetaClause { + public MetaClause element, separator; + public boolean maximal, zero, many; + public Element build(BuildContext bc) { + return new Repeat(element.build(bc), zero, many, separator==null?null:separator.build(bc), maximal); + } + public MetaRepeat(MetaClause element, boolean maximal, MetaClause separator, boolean zero, boolean many) { + this.separator = separator; + this.element = element; + this.maximal = maximal; + this.zero = zero; + this.many = many; + } + public String toString() { + return element+ + ((zero&&!many)?"?":zero?"*":"+")+ + (!maximal?"":zero?"*":"+")+ + (separator==null?"":(" /"+separator)); + } + } + public static class MetaParens extends MetaClause { + public MetaUnion body; + public MetaParens(Tree t) { this.body = rhs(t); } + public String toString() { return "( " + body + " )"; } + public Element build(BuildContext bc) { return body.buildAnon(bc); } + } + /* + public static class MetaTree extends MetaClause { + public MetaConjunct body; + public MetaTree(Tree t) { this.body = MetaConjunct.make(t); } + public String toString() { return "{ " + body + " }"; } + public Element build(BuildContext bc) { + return new Union("{}");// body.buildSequence(); + } + } + */ + public static class MetaEpsilon extends MetaClause { + public String toString() { return "()"; } + public Element build(BuildContext bc) { return Union.epsilon; } + } + public static class MetaRange extends MetaClause { + Range.Set range = new Range.Set(); + public String toString() { return range.toString(); } + public Element build(BuildContext bc) { return set(range); } + public MetaRange(Tree t) { + for(Tree tt : t) { + if (tt.head().equals("range")) { + range.add(tt.child(0).head().charAt(0)); + } else if (tt.head().equals("-")) { + range.add(new Range(string(tt.child(0)).charAt(0), + string(tt.child(1)).charAt(0))); + } + } + //set = set(ret); + } + } + public static class MetaStringLiteral extends MetaClause { + public String literal; + public Element build(BuildContext bc) { return string(literal); } + public MetaStringLiteral(Tree literal) { this.literal = string(literal); this.drop = true; } + public String toString() { return "\""+StringUtil.escapify(literal, "\"\r\n\\")+"\""; } + } + public static class MetaNonterminalReference extends MetaClause { + public String name; + public MetaNonterminalReference(Tree name) { this.name = string(name); } + public Element build(BuildContext bc) { return bc.build(name); } + public String toString() { return name; } + } + public static class MetaSelfReference extends MetaClause { + public String toString() { return "(*)"; } + public Element build(BuildContext bc) { return new Union("(*)"); /* FIXME */ } + } + public static class MetaInvert extends MetaClause { + public MetaClause element; + public MetaInvert(Tree t, MetaConjunct c) { this.element = make(t, c); } + public String toString() { return "~"+element; } + public Element build(BuildContext bc) { return new Hack(new Invert(new Infer(element.build(bc)))); } + } + } + + } + public Object walk(Tree tree) { String head = tree.head(); if (tree.numChildren()==0) return super.walk(tree); @@ -166,7 +482,7 @@ public class MetaGrammar extends StringWalker { else if ("range".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,0).toString().charAt(0)); else if ("gram".equals(head)) return walk(tree, 0); else if ("psy".equals(head)) return (PreSequence)walk(tree, 0); - else if ("->".equals(head)) { PreSequence p = (PreSequence)walk(tree, 0); p.noFollow = (Element)walk(tree, 1); return p; } + else if ("->".equals(head)) { PreSequence p = (PreSequence)walk(tree, 0); p.follow = (Element)walk(tree, 1); return p; } else if ("/".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1)); else if (" /".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1)); else if ("~".equals(head)) return new Hack(new Invert(new Infer((Element)walk(tree, 0)))); @@ -218,7 +534,7 @@ public class MetaGrammar extends StringWalker { ////////////////////////////////////////////////////////////////////////////// public class PreSequence { - public Element noFollow = null; + public Element follow = null; public final HashSet and = new HashSet(); public final HashSet not = new HashSet(); public /*final*/ Object tag; @@ -330,7 +646,7 @@ public class MetaGrammar extends StringWalker { for(Sequence s : and) ret = ret.and(s); for(Sequence s : not) ret = ret.not(s); set.add(ret); - if (this.noFollow != null) ret.noFollow = new Invert(new Infer(this.noFollow)); + if (this.follow != null) ret.follow = new Infer(this.follow); return ret; } } @@ -340,7 +656,9 @@ public class MetaGrammar extends StringWalker { System.err.println("usage: java " + MetaGrammar.class.getName() + " grammarfile.g com.yourdomain.package.ClassName"); System.exit(-1); } - + //StringBuffer sbs = new StringBuffer(); + //((MetaGrammar)new MetaGrammar().walk(meta)).nt.get("e").toString(sbs); + //System.err.println(sbs); String className = args[1].substring(args[1].lastIndexOf('.')+1); String packageName = args[1].substring(0, args[1].lastIndexOf('.')); String fileName = packageName.replace('.', '/') + "/" + className + ".java"; @@ -356,17 +674,35 @@ public class MetaGrammar extends StringWalker { } out.append("\n // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED\n"); - new CharParser(MetaGrammar.make()).parse(new FileInputStream(args[0])).expand1().toJava(out); + Tree ts = new CharParser(MetaGrammar.make()).parse(new FileInputStream(args[0])).expand1(); + + Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(ts); + BuildContext bc = new BuildContext(mgf); + for(Meta.MetaNonterminal nt : mgf.values()) { + StringBuffer sb = new StringBuffer(); + nt.build(bc).toString(sb); + System.err.println(sb); + } + + Forest fs = new CharParser(mgf.get("s").build(new BuildContext(mgf))).parse(new FileInputStream(args[0])); + System.out.println(fs.expand1()); + //GraphViz gv = new GraphViz(); + //fs.toGraphViz(gv); + //FileOutputStream fox = new FileOutputStream("out.dot"); + //gv.dump(fox); + //fox.close(); + + ts.toJava(out); out.append("\n // DO NOT EDIT STUFF ABOVE: IT IS AUTOMATICALLY GENERATED\n"); for(String s = br.readLine(); s != null; s = br.readLine()) out.append(s+"\n"); br.close(); - OutputStream os = new FileOutputStream(fileName); - PrintWriter p = new PrintWriter(new OutputStreamWriter(os)); - p.println(out.toString()); - p.flush(); - os.close(); + //OutputStream os = new FileOutputStream(fileName); + //PrintWriter p = new PrintWriter(new OutputStreamWriter(os)); + //p.println(out.toString()); + //p.flush(); + //os.close(); } public static final Tree meta = @@ -555,6 +891,75 @@ public class MetaGrammar extends StringWalker { + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED new edu.berkeley.sbp.Tree(null, "grammar", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "=", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "s", new edu.berkeley.sbp.Tree[] { })}), new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "psx", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "ps", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "!", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "nonTerminal", new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, null, new edu.berkeley.sbp.Tree[] { new edu.berkeley.sbp.Tree(null, "w", new edu.berkeley.sbp.Tree[] { }), @@ -1244,3 +1649,72 @@ new edu.berkeley.sbp.Tree(null, "grammar", new edu.berkeley.sbp.Tree[] { new edu + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/src/edu/berkeley/sbp/util/GraphViz.java b/src/edu/berkeley/sbp/util/GraphViz.java index ef08fae..d5f1bcf 100644 --- a/src/edu/berkeley/sbp/util/GraphViz.java +++ b/src/edu/berkeley/sbp/util/GraphViz.java @@ -33,9 +33,14 @@ public class GraphViz { labels.add(label); n.inbound.add(this); } + public String getParentName() { + if (inbound.size()==1 && inbound.get(0).simple()) + return inbound.get(0).getParentName(); + return name(); + } public String name() { if (inbound.size()==1 && inbound.get(0).simple()) - return inbound.get(0).name()+":node_"+idx; + return inbound.get(0).getParentName()+":node_"+idx; return "node_"+idx; } public void edges(PrintWriter pw) { @@ -43,7 +48,8 @@ public class GraphViz { for(int i=0; i " + n.name() + " [color="+color+" " +(label==null?"":("label=\""+label+"\""))+ "];\n"); + pw.println(" "+name()+" -> " + n.name() + " [color="+color+" " + +(label==null?"":("label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\""))+ "];\n"); } } public int numEdges() { return edges.size(); } @@ -80,17 +86,17 @@ public class GraphViz { if (!first) pw.print("|"); first = false; pw.print(""); - pw.print(StringUtil.escapify(n.label,"\\\"")); + pw.print(StringUtil.escapify(n.label,"\\\"\r\n")); } if (!complex) pw.print("}"); - pw.print("\""); + pw.print("\" "); } else { pw.print(" label=\""); - pw.print(StringUtil.escapify(label,"\\\"")); - pw.print("\""); + pw.print(StringUtil.escapify(label,"\\\"\r\n")); + pw.print("\" "); } pw.print("color="+color); - if (comment!=null) pw.print(" comment=\""+StringUtil.escapify(comment,"\\\"")+"\" "); + if (comment!=null) pw.print(" comment=\""+StringUtil.escapify(comment,"\\\"\r\n")+"\" "); pw.print("];\n"); } } @@ -117,6 +123,7 @@ public class GraphViz { Runtime.getRuntime().exec(new String[] { "dot", "-Tsvg" }); } + public void dump(OutputStream os) { dump(new PrintWriter(new OutputStreamWriter(os))); } public void dump(PrintWriter pw) { IdentityHashMap done = new IdentityHashMap(); pw.println("digraph G { rankdir=LR; ordering=out; \n"); diff --git a/tests/meta.g b/tests/meta.g index ce2aa6f..845af52 100644 --- a/tests/meta.g +++ b/tests/meta.g @@ -1,12 +1,13 @@ +Grammar = NonTerminal +/ ws +s = !ws (grammar::Grammar) !ws +NonTerminal = Word ^"=" RHS /ws // use 'a'-'z' or 'a-z' instead of [a-z]? // EOF token? // #include (with renaming?) // ANTLR uses ! and ^ suffixes -s = !ws (grammar::Grammar) !ws -Grammar = NonTerminal +/ ws -NonTerminal = Word ^"=" RHS /ws +blah = "Grammar" RHS = (Sequence +/ (!ws "|" !ws)) +/ (!ws ">" !ws) @@ -47,7 +48,7 @@ e = (Quoted|Word) ^":" e | "(" Word ^")" /ws > ^"(" RHS ")" /ws | ^"~" e - > "^^":: "^" e + > "^^":: "^" e Word = [a-zA-Z0-9_]++ Quoted = "\"" ((~[\"\\] | escaped)+) "\"" @@ -58,5 +59,5 @@ escaped = "\n":: "\\n" w = " " | "\n" | "\r" ws = "()":: w** - | "()":: w** "//" ~[\n]* "\n" ws + | "()":: w** "//" (~[\n])* "\n" ws wp = w++ diff --git a/tests/regression.tc b/tests/regression.tc index 77af771..cdad831 100644 --- a/tests/regression.tc +++ b/tests/regression.tc @@ -20,6 +20,22 @@ //} testcase { + input "aaaaa"; + s = A + A = "a" s &~ "a" 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}}"; @@ -300,7 +316,7 @@ any = ~[]* s = smt:: !ws statement !ws statement !ws block = !"\n" !indent blockBody - &~ !"\n" !outdent !(~[\ ]) !(~[]*) + &~ !"\n" (" " !outdent " ") !(~[\ ]) !(~[]*) blockBody = statement > sbb:: statement ws blockBody -- 1.7.10.4