X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2Fmisc%2FMetaGrammar.java;h=bdb80967ec27973363b4e9bc539165cbae1ca991;hp=c563ce50185457c9acbe10de1a7a9607f8f048f0;hb=fa858dc4acddd3e32126ff2558e0860315a84758;hpb=df32ec862cecf0851a7f7342582b5786d04a4771 diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java index c563ce5..bdb8096 100644 --- a/src/edu/berkeley/sbp/misc/MetaGrammar.java +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -7,6 +7,22 @@ import java.io.*; public class MetaGrammar extends StringWalker { + /** an atom which tracks the possible tokenset of some element, provided that element can only match single-token sequences */ + static class Infer extends Atom { + private final Element e; + public Infer(Element e) { this.e = e; } + public Topology top() { return (Topology)toAtom(e); } + public String toString() { return e.toString(); } + } + + /** an atom which tracks the inverse of some other atom */ + static class Invert extends Atom { + private final Atom a; + public Invert(Atom a) { this.a = a; } + public Topology top() { return a.complement(); } + public String toString() { return "~"+a; } + } + public static class Hack extends Atom { private final Atom a; static final Topology leftright = CharRange.rightBrace.union(CharRange.leftBrace); @@ -115,14 +131,14 @@ public class MetaGrammar extends StringWalker { if ("\\n".equals(head)) return new Character('\n'); else if ("\\r".equals(head)) return new Character('\r'); else if ("grammar".equals(head)) { for(Tree t : tree.children()) walk(t); return this; } - else if ("*".equals(head)) return Repeat.many0((Element)walk(tree.child(0))); - 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.maximal1((Element)walk(tree.child(0)), (Element)walk(tree.child(1))); - 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 Sequence.many0((Element)walk(tree.child(0)), repeatTag()); + else if ("+".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), repeatTag()); + else if ("+/".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag()); + else if ("*/".equals(head)) return Sequence.many0((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag()); + else if ("++/".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag()); + else if ("**".equals(head)) return Sequence.maximal0((Element)walk(tree.child(0)), repeatTag()); + else if ("++".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), repeatTag()); + else if ("?".equals(head)) return Sequence.maybe((Element)walk(tree.child(0)), repeatTag()); else if ("!".equals(head)) { Element e = (Element)walk(tree.child(0)); dropAll.add(e); return e; } else if ("&".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true)); else if ("and".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true)); @@ -136,13 +152,15 @@ public class MetaGrammar extends StringWalker { carets.put(ret, s); dropAll.add(ret); return ret; + /* } else if ("^^".equals(head)) { return new Keep(walk(tree,0)); + */ } else if ("psx".equals(head)) return ((PreSequence)walk(tree, 0)).buildSequence(); else if ("nonTerminal".equals(head)) return getNonTerminal(string(tree.child(0))); - else if ("::=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])walk(tree, 1), false, false); - else if ("=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])walk(tree, 1), false, false); - else if ("(".equals(head)) return buildUnion((Sequence[][])walk(tree, 0)); + else if ("::=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false); + else if ("=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false); + else if ("(".equals(head)) return buildUnion((Sequence[][])Reflection.lub(walk(tree, 0))); else if ("literal".equals(head)) { Element ret = string(string(tree.child(0))); dropAll.add(ret); return ret; } else if ("-".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,1).toString().charAt(0)); else if ("range".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,0).toString().charAt(0)); @@ -150,14 +168,17 @@ public class MetaGrammar extends StringWalker { 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)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1)); - else if ("~".equals(head)) return new Hack(new Atom.Invert(new Atom.Infer((Element)walk(tree, 0)))); + 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)))); else if ("ps".equals(head)) return new PreSequence((Object[])walk(tree,0), null); else if (":".equals(head)) { String s = string(tree.child(0)); - return new Keep("_".equals(s)?walk(tree,1):new PreSequence(new Object[] { walk(tree, 1) }, convertLabel(s)).buildUnion()); + return new Keep(s,walk(tree,1)); } else if ("::".equals(head)) { PreSequence p = (PreSequence)walk(tree, 1); - p.tag = convertLabel(string(tree.child(0))); + String s = string(tree.child(0)); + if (s.equals("[]")) p.unwrap = true; + else p.tag = convertLabel(s); return p; } else if ("=>".equals(head)) { @@ -175,11 +196,13 @@ public class MetaGrammar extends StringWalker { } static class Keep { - final Object o; - public Keep(Object o) { this.o = o; } + public final String label; + public final Object o; + public Keep(String label, Object o) { this.label = label; this.o = o; } } - public String convertLabel(String label) { return label; } + public Object convertLabel(String label) { return label; } + public Object repeatTag() { return null; } public Object walk(String tag, Object[] argo) { if (argo.length==0) return super.walk(tag, argo); @@ -198,7 +221,7 @@ public class MetaGrammar extends StringWalker { public Element noFollow = null; public final HashSet and = new HashSet(); public final HashSet not = new HashSet(); - public /*final*/ String tag; + public /*final*/ Object tag; public final Object[] o; public PreSequence sparse(Object e) { @@ -233,8 +256,8 @@ public class MetaGrammar extends StringWalker { boolean[] drops = null; public PreSequence(Object o) { this(new Object[] { o }, null); } public PreSequence(Object[] o) { this(o, null); } - public PreSequence(Object[] o, String tag) { this(o, tag, null); } - public PreSequence(Object[] o, String tag, boolean[] drops) { + public PreSequence(Object[] o, Object tag) { this(o, tag, null); } + public PreSequence(Object[] o, Object tag, boolean[] drops) { this.o = o; this.tag = tag; this.drops = drops==null ? new boolean[o.length] : drops; @@ -249,7 +272,7 @@ public class MetaGrammar extends StringWalker { public boolean unwrap = false; public Sequence buildSequence() { return buildSequence(null, false, false); } public Sequence buildSequence(Union u) { return buildSequence(u, false, false); } - public Sequence buildSequence(Union u, boolean lame, String tag) { + public Sequence buildSequence(Union u, boolean lame, Object tag) { this.tag = tag; return buildSequence(u, lame, false); } @@ -262,6 +285,7 @@ public class MetaGrammar extends StringWalker { } HashSet set = new HashSet(); Element[] o2 = o==null ? new Element[0] : new Element[o.length]; + Object[] labels = new Object[drops.length]; int nonDrop = 0; boolean keeping = false; if (o != null) { @@ -269,15 +293,17 @@ public class MetaGrammar extends StringWalker { for(int i=0; i