X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2Fmisc%2FMetaGrammar.java;fp=src%2Fedu%2Fberkeley%2Fsbp%2Fmisc%2FMetaGrammar.java;h=fd93f14e870c9fe21401761450c27a6f6c76babd;hp=7a4105dc0f2c9ba4310a9123f90bde005153d149;hb=76038cc31d71c6e7c0e6352f9c21ebd320e5c0cc;hpb=d5e1e502d49f6d59bc912f12522d4ac1e2ac7d87

diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java
index 7a4105d..fd93f14 100644
--- a/src/edu/berkeley/sbp/misc/MetaGrammar.java
+++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java
@@ -33,17 +33,21 @@ public class MetaGrammar extends StringWalker {
         public String toString() { return a.toString(); }
     }
 
-    public static Union make() throws Exception {
-        Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(meta);
+    public static Union make(Tree<String> tree, String nt) throws Exception {
+        Meta.MetaGrammarFile mgf = new MetaGrammar.Meta.MetaGrammarFile(tree);
         BuildContext bc = new BuildContext(mgf);
-        return mgf.get("s").build(bc);
+        return mgf.get(nt).build(bc);
+    }
+    public static Union make() throws Exception {
+        return make(meta, "s");
     }
+    /*
     public String toString() {
         StringBuffer ret = new StringBuffer();
         for(Union u : nt.values()) u.toString(ret);
         return ret.toString();
     }
-
+    */
     public /*private*/ static HashSet<Element> dropAll = new HashSet<Element>();
     public /*private*/ static HashMap<Element,String> carets = new HashMap<Element,String>();
 
@@ -53,10 +57,6 @@ public class MetaGrammar extends StringWalker {
 
     ////////////////////////////////////////////////////////////////////////////////
 
-    private Union g;
-    private HashMap<String,Union> nt;
-    private int anon = 0;
-    private String startSymbol;
     private static boolean strings;
 
     private static Element  set(Range.Set r) { if (strings) throw new Error(); return CharRange.set(r); }
@@ -64,51 +64,7 @@ public class MetaGrammar extends StringWalker {
     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); }
-    public MetaGrammar(String s, boolean strings) { this.strings = strings; done(s); throw new Error(); }
-    public Union done() { return done("s"); }
-    public Union done(String str) {
-        Union ret = g;
-        g = new Union(str);
-        startSymbol = str;
-        nt = new HashMap<String,Union>();
-        dropAll = new HashSet<Element>();
-        dropAll.add(leftBrace());
-        dropAll.add(rightBrace());
-        nt.put(str, g);
-        return ret;
-    }
-
-
-    // MetaGrammar //////////////////////////////////////////////////////////////////////////////
-
-    public Union       getNonTerminal(String str) { return nonTerminal(str, null, false, false); }
-    private Union       nonTerminal(String str) { return nonTerminal(str, null, false, false); }
-    public Union       anonymousNonTerminal(Sequence[][] s) {
-        return nonTerminal("anon"+(anon++), s, false, false);
-    }
-    private Union       nonTerminal(String str, Sequence[][] s, boolean synthetic, boolean dropAll) {
-        Union n = str.equals(startSymbol) ? g : nt.get(str);
-        if (n == null) nt.put(str, n = new Union(str, synthetic));
-        if (dropAll) this.dropAll.add(n);
-        if (s==null) return n;
-        HashSet<Sequence> seqs = new HashSet<Sequence>();
-        for(int i=0; i<s.length; i++) {
-            if (s[i]==null) continue;
-            HashSet<Sequence> temp = new HashSet<Sequence>();
-            for(Sequence pre : s[i]) {
-                for(Sequence sn : seqs) pre = pre.not(sn);
-                temp.add(pre);
-                n.add(pre);
-            }
-            seqs.addAll(temp);
-        }
-        //StringBuffer sb = new StringBuffer();
-        //n.toString(sb);
-        //System.out.println(sb);
-        return n;
-    }
+    private MetaGrammar() { }
 
     public static String string(Iterable<Tree<String>> children) {
         String ret = "";
@@ -122,13 +78,6 @@ public class MetaGrammar extends StringWalker {
         return ret;
     }
 
-    // hack, this doens't really work if you're nesting
-    HashSet<Element> keep = new HashSet<Element>();
-
-    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<String,Union> {
         private final Meta.MetaGrammarFile mgf;
         public BuildContext(Meta.MetaGrammarFile mgf) { this.mgf = mgf; }
@@ -159,7 +108,6 @@ public class MetaGrammar extends StringWalker {
             public String    name;
             public MetaUnion rhs;
             public MetaNonterminal(Tree<String> tree) {
-                System.err.println("MetaNonterminal("+tree+")");
                 name = string(tree.child(0));
                 rhs = rhs(tree.child(1));
             }
@@ -203,7 +151,6 @@ public class MetaGrammar extends StringWalker {
                 return u;
             }
             public MetaUnion(Tree<String> t, boolean prioritized) {
-                System.err.println("MetaUnion("+t+")");
                 //System.err.println("metaunion: " + t);
                 this.prioritized = prioritized;
                 int i = 0;
@@ -229,7 +176,7 @@ public class MetaGrammar extends StringWalker {
         }
 
         public static MetaSequence makeMetaSequence(Tree<String> t) {
-            System.err.println("MetaSequence("+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);
@@ -292,7 +239,7 @@ public class MetaGrammar extends StringWalker {
                 return ret;
             }
             private MetaConjunct(Tree<String> t) {
-                System.err.println("MetaConjunct("+t+")");
+                //System.err.println("MetaConjunct("+t+")");
                 elements = new MetaClause[t.numChildren()];
                 int i = 0; for(Tree<String> tt : t)
                     elements[i++] = MetaClause.make(tt, this);
@@ -307,7 +254,7 @@ public class MetaGrammar extends StringWalker {
                 return ret;
             }
             public static MetaConjunct make(Tree<String> t) {
-                System.err.println("MetaConjunct.make("+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);
@@ -336,7 +283,7 @@ public class MetaGrammar extends StringWalker {
             public boolean lift = false;
             public abstract Element build(BuildContext bc);
             public static MetaClause make(Tree<String> t, MetaConjunct c) {
-                System.err.println("MetaClause.make("+t+")");
+                //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);
@@ -441,216 +388,6 @@ public class MetaGrammar extends StringWalker {
 
     }
 
-    public Object walk(Tree<String> tree) {
-        String head = tree.head();
-        if (tree.numChildren()==0) return super.walk(tree);
-        if      ("\\n".equals(head)) return new Character('\n');
-        else if ("\\r".equals(head)) return new Character('\r');
-        else if ("grammar".equals(head)) { for(Tree<String> t : tree.children()) walk(t); return this; }
-        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));
-        else if ("&~".equals(head))  return ((Sequence)walk(tree,0)).not(sequence(walk(tree, 1), true));
-        else if ("epsilon".equals(head)) return Union.epsilon;
-        else if ("()".equals(head)) return Union.epsilon;
-        else if (")".equals(head)) return SELF;
-        else if ("caret".equals(head) || "^".equals(head)) {
-            String s = string(tree.child(0));
-            Element ret = CharRange.string(s, false);
-            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[][])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));
-        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.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))));
-        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(s,walk(tree,1));
-        } else if ("::".equals(head)) {
-            PreSequence p = (PreSequence)walk(tree, 1);
-            String s = string(tree.child(0));
-            if (s.equals("[]")) p.unwrap = true;
-            else p.tag = convertLabel(s);
-            return p;
-        }
-        else if ("=>".equals(head)) {
-            PreSequence p = (PreSequence)walk(tree, 0);
-            p.tag = string(tree.child(1));
-            return p;
-        }
-        else if ("[".equals(head)) {
-            Range[] rr = (Range[])walk(tree, 0);
-            Range.Set ret = new Range.Set();
-            if (rr!=null) for(Range r : rr) ret.add(r);
-            return set(ret);
-        }
-        else return super.walk(tree);
-    }
-
-    static class Keep {
-        public final String label;
-        public final Object o;
-        public Keep(String label, Object o) { this.label = label; this.o = o; }
-    }
-
-    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);
-        if (argo==null) return tag;
-        if (tag==null || "".equals(tag)) return argo;
-        return super.walk(tag, argo);
-    }
-
-    public Union buildUnion(Sequence[][] p) {
-        return anonymousNonTerminal(p);
-    }
-
-    //////////////////////////////////////////////////////////////////////////////
-
-    public class PreSequence {
-        public Element follow = null;
-        public final HashSet<Sequence> and  = new HashSet<Sequence>();
-        public final HashSet<Sequence> not  = new HashSet<Sequence>();
-        public /*final*/ Object tag;
-        public final Object[] o;
-
-        public PreSequence sparse(Object e) {
-            Object[] ret;
-            boolean[] drops;
-            if (o.length <= 1) {
-                ret = o;
-                drops = new boolean[this.drops.length];
-                System.arraycopy(this.drops, 0, drops, 0, this.drops.length);
-            } else {
-                ret = new Object[o.length * 2 - 1];
-                drops = new boolean[o.length * 2 - 1];
-                for(int i=0; i<o.length; i++) {
-                    Object oi = o[i];
-                    ret[i*2]   = oi;
-                    drops[i*2] = this.drops[i];
-                    if (i*2+1<ret.length) {
-                        ret[i*2+1] = e;
-                        drops[i*2+1] = true;
-                    }
-                }
-            }
-            PreSequence p = new PreSequence(ret, tag, drops);
-            p.not.addAll(not);
-            p.and.addAll(and);
-            return p;
-        }
-
-        public PreSequence not(Sequence s) { not.add(s); return this; }
-        public PreSequence and(Sequence s) { and.add(s); return this; }
-
-        boolean[] drops = null;
-        public PreSequence(Object o) { this(new Object[] { o }, null); }
-        public PreSequence(Object[] o) { this(o, null); }
-        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;
-        }
-
-        public Union    buildUnion(String s) {
-            Union u = new Union(s);
-            u.add(buildSequence(u));
-            return u;
-        }
-        public Union    buildUnion() { return buildUnion("???"); }
-        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, Object tag) {
-            this.tag = tag;
-            return buildSequence(u, lame, false);
-        }
-        public Sequence buildSequence(Union u, boolean lame, boolean dropAll) {
-            if (tag!=null && tag.equals("[]")) unwrap = true;
-            if (tag!=null && "()".equals(tag)) dropAll=true;
-            if (u!=null) {
-                for(Sequence s : and) u.add(s);
-                for(Sequence s : not) u.add(s);
-            }
-            HashSet<Sequence> set = new HashSet<Sequence>();
-            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) {
-                int j = 0;
-                for(int i=0; i<o.length; i++) {
-                    Object oi = o[i];
-                    if (oi instanceof Keep)    {
-                        if (!unwrap && tag==null) throw new Error("cannot have labels in an untagged sequence: " + ((Keep)oi).label);
-                        if (!keeping) { for(int k=0; k<i; k++) drops[k]=true; }
-                        drops[i] = false;
-                        keeping = true;
-                        labels[i] = ((Keep)oi).label;
-                        oi = ((Keep)oi).o;
-                    } else {
-                        if (keeping) drops[i] = true;
-                    }
-                    /*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;
-                    o2[j] = o2[j];
-                    String s = carets.get(o2[j]);
-                    if (s!=null) { tag = s; if (o.length==1) drops[j] = false; }
-                    j++;
-                }
-            }
-            Element[] expansion = o2;
-            Sequence ret = null;
-            if (dropAll || lame) ret = Sequence.drop(expansion, lame);
-            else if (unwrap)    ret = Sequence.unwrap(expansion, repeatTag(), drops);
-            else if (keeping || tag!=null) ret = Sequence.rewritingSequence(tag, expansion, labels, drops);
-            else {
-                int idx = -1;
-                for(int i=0; i<expansion.length; i++)
-                    if (!drops[i])
-                        if (idx==-1) idx = i;
-                        else throw new Error("multiple non-dropped elements in sequence: " + Sequence.drop(expansion,false));
-                if (idx != -1) ret = Sequence.singleton(expansion, idx);
-                else           ret = Sequence.drop(expansion, false);
-            }
-            for(Sequence s : and) ret = ret.and(s);
-            for(Sequence s : not) ret = ret.not(s);
-            set.add(ret);
-            if (this.follow != null) ret.follow = new Infer(this.follow);
-            return ret;
-        }
-    }
-
     public static void main(String[] args) throws Exception {
         if (args.length != 2) {
             System.err.println("usage: java " + MetaGrammar.class.getName() + " grammarfile.g com.yourdomain.package.ClassName");
@@ -676,16 +413,9 @@ public class MetaGrammar extends StringWalker {
         out.append("\n        // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED\n");
         Tree<String> 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<String> fs = new CharParser(mgf.get("s").build(new BuildContext(mgf))).parse(new FileInputStream(args[0]));
+        Forest<String> fs = new CharParser(make()).parse(new FileInputStream(args[0]));
         System.out.println(fs.expand1());
+
         //GraphViz gv = new GraphViz();
         //fs.toGraphViz(gv);
         //FileOutputStream fox = new FileOutputStream("out.dot");