src/edu/berkeley/sbp/misc/Demo.java

   1 package edu.berkeley.sbp.misc;
   2 import edu.berkeley.sbp.util.*;
   3 import edu.berkeley.sbp.*;
   4 import edu.berkeley.sbp.chr.*;
   5 import java.util.*;
   6 import java.lang.annotation.*;
   7 import java.lang.reflect.*;
   8 import java.io.*;
   9
  10 public class Demo {
  11
  12     public static boolean harsh = false;
  13
  14     public static void main(String[] s) throws Exception {
  15
  16         ReflectiveMeta m = new ReflectiveMeta();
  17         Tree<String> res = new CharParser(MetaGrammar.make()).parse(new FileInputStream(s[0])).expand1();
  18         MetaGrammar.Meta.MetaGrammarFile mgf = m.new MetaGrammarFile(res);
  19         MetaGrammar.BuildContext bc = new MetaGrammar.BuildContext(mgf);
  20
  21         Union meta = mgf.get("s").build(bc);
  22         Tree t = new CharParser(meta).parse(new FileInputStream(s[1])).expand1();
  23
  24         Union u = Demo.make(t, "s");
  25
  26         System.err.println();
  27         System.err.println("== parsing with parsed grammar =================================================================================");
  28         t = new CharParser((Union)u).parse(new FileInputStream(s[1])).expand1();
  29         System.out.println(t.toPrettyString());
  30
  31         System.err.println("== parsing with parsed-parsed grammar ==========================================================================");
  32         t = new CharParser(new Context(t, m).build()).parse(new FileInputStream(s[1])).expand1();
  33         System.out.println(t.toPrettyString());
  34     }
  35
  36     public static class ReflectiveMetaPlain extends ReflectiveMeta {
  37         public Object repeatTag() { return null; }
  38         public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
  39             return null; }
  40         public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
  41             return Sequence.rewritingSequence(tag, els, labels, drops);
  42         }
  43     }
  44
  45     public static class ReflectiveMeta extends MetaGrammar.Meta {
  46         private final Class _cl;
  47         private final Class[] _inner;
  48         public ReflectiveMeta() {
  49             this(MG.class,
  50                  new Class[] {
  51                      MG.Grammar.class,
  52                      MG.NonTerminal.class,
  53                      MG.AnonUn.class,
  54                      MG.Range.class,
  55                      MG.El.class,
  56                      MG.Seq.class,
  57                      MG.NonTerminalReference.class,
  58                      MG.StringLiteral.class,
  59                      MG.XTree.class,
  60                      MG.CharClass.class
  61                  });
  62         }
  63         public ReflectiveMeta(Class c, Class[] inner) {
  64             this._cl = c;
  65             this._inner = inner;
  66         }
  67         private boolean match(Method m, String s) { return match(m.getAnnotation(tag.class), null, s); }
  68         private boolean match(tag t, Class c, String s) {
  69             if (t==null) return false;
  70             if (t.value().equals(s)) return true;
  71             if (c != null && t.equals("") && c.getSimpleName().equals(s)) return true;
  72             return false;
  73         }
  74         private boolean match(nonterminal t, Class c, String s) {
  75             if (t==null) return false;
  76             if (t.value().equals(s)) return true;
  77             if (c != null && t.equals("") && c.getSimpleName().equals(s)) return true;
  78             return false;
  79         }
  80         private boolean match(Class c, String s, String nonTerminalName) {
  81             if (match((tag)c.getAnnotation(tag.class), c, s)) return true;
  82             if (match((nonterminal)c.getAnnotation(nonterminal.class), c, nonTerminalName)) return true;
  83             return false;
  84         }
  85         public boolean match(Constructor con, String s, String nonTerminalName) {
  86             Class c = con.getDeclaringClass();
  87             if (match((tag)con.getAnnotation(tag.class), null, s)) return true;
  88             if (match((nonterminal)con.getAnnotation(nonterminal.class), c, s)) return true;
  89             return false;
  90         }
  91         public Object repeatTag() {
  92             return new Reducer() {
  93                     public String toString() { return ""; }
  94                     public Object reduce(Tree t) {
  95                         Object[] ret = new Object[t.numChildren()];
  96                         for(int i=0; i<t.numChildren(); i++) {
  97                             Tree tc = t.child(i);
  98                             if (tc.head() != null && tc.head() instanceof Reducer)
  99                                 ret[i] = ((Reducer)tc.head()).reduce(tc);
 100                             else if (tc.numChildren() == 0)
 101                                 ret[i] = tc.head();
 102                             else {
 103                                 System.err.println("FIXME: don't know what to do about " + tc);
 104                                 ret[i] = null;
 105                             }
 106                         }
 107                         return ret;
 108                     }
 109                 };
 110         }
 111         public Sequence tryResolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
 112             Production p = new Production(tag, nonTerminalName, els, labels, drops);
 113             for(Method m : _cl.getMethods())
 114                 if (new TargetMethod(m).isCompatible(p))
 115                     return new TargetMethod(m).makeSequence(p);
 116             for(Class c : _inner)
 117                 for(Constructor con : c.getConstructors())
 118                     if (new TargetConstructor(con).isCompatible(p))
 119                         return new TargetConstructor(con).makeSequence(p);
 120             for(Class c : _inner)
 121                 if (new TargetClass(c).isCompatible(p))
 122                     return new TargetClass(c).makeSequence(p);
 123             return null;
 124         }
 125         public Sequence resolveTag(String tag, String nonTerminalName, Element[] els, Object[] labels, boolean[] drops) {
 126             Sequence ret = tryResolveTag(tag, nonTerminalName, els, labels, drops);
 127             if (ret != null) return ret;
 128             String message = "could not find a Java method/class/ctor matching tag \""+tag+
 129                 "\", nonterminal \""+nonTerminalName+"\" with " + els.length + " arguments";
 130             if (harsh) {
 131                 throw new RuntimeException(message);
 132             } else {
 133                 System.err.println(message);
 134                 return Sequence.rewritingSequence(tag, els, labels, drops);
 135             }
 136         }
 137     }
 138
 139
 140     /**
 141      *  Constructors, classes, and methods with this attribute will
 142      *  match every production of the nonterminal called "value()"
 143      *  that is arg-compatible.  If value() is undefined, then the
 144      *  class/constructor/method name is used.
 145      */
 146     @Retention(RetentionPolicy.RUNTIME) public static @interface nonterminal { String value() default ""; }
 147
 148     @Retention(RetentionPolicy.RUNTIME) public static @interface raw { }
 149
 150     /**
 151      *  Constructors, classes, and methods with this attribute will
 152      *  match every tree tagged with "value()" that is arg-compatible.
 153      *  If value() is undefined, then the class/constructor/method
 154      *  name is used.
 155      */
 156     @Retention(RetentionPolicy.RUNTIME) public static @interface tag         { String value() default ""; }
 157
 158     /**
 159      *  If any parameter to a method or field in a class has a named
 160      *  arg-tag, that parameter/field matches the child of the tree
 161      *  which either has that label or else is a reference to a
 162      *  nonterminal with the corresponding name.
 163      *
 164      *  The remaining non-named arg-tags match the remaining children
 165      *  of the tree in sequential order.
 166      *
 167      *  If any arg-tagged parameters/fields remain, the match fails.
 168      *  If there were no arg-tagged parameters-fields, it is as if all
 169      *  of them were non-named and arg-tagged.
 170      *
 171      *  A method/constructor is arg-compatible if all of its arguments
 172      *  are arg-compatible.
 173      *
 174      *  A class is arg-compatible if all of its fields are
 175      *  arg-compatible, or if one of its constructors is arg-compatible.
 176      *
 177      */
 178     @Retention(RetentionPolicy.RUNTIME) public static @interface arg         { String value() default ""; }
 179
 180     public static class Production {
 181         public String tag;
 182         public String nonTerminal;
 183         public Object[] labels;
 184         public boolean[] drops;
 185         public Element[] elements;
 186         public int count = 0;
 187         public Production(String tag, String nonTerminal, Element[] elements, Object[] labels, boolean[] drops) {
 188             this.tag = tag;
 189             this.elements = elements;
 190             this.nonTerminal = nonTerminal;
 191             this.labels = labels;
 192             this.drops = drops;
 193             for(int i=0; i<drops.length; i++)
 194                 if (!drops[i])
 195                     count++;
 196         }
 197     }
 198
 199     public static abstract class Target {
 200         public abstract String getName();
 201         public abstract tag getTag();
 202         public abstract nonterminal getNonTerminal();
 203         public abstract int[] buildSequence(Production p);
 204         public boolean isCompatible(Production p) {
 205             tag t = getTag();
 206             if (t != null &&
 207                 (t.value().equals(p.tag) ||
 208                  (t.value().equals("") && getName().equals(p.tag))))
 209                 return buildSequence(p)!=null;
 210
 211             nonterminal n = getNonTerminal();
 212             if (n != null &&
 213                 (n.value().equals(p.nonTerminal) ||
 214                  (n.value().equals("") && getName().equals(p.nonTerminal))))
 215                 return buildSequence(p)!=null;
 216
 217             return false;
 218         }
 219         public int[] buildSequence(Production p, String[] names, arg[] argtags) {
 220             int argTagged = 0;
 221             for(int i=0; i<argtags.length; i++)
 222                 if (argtags[i] != null)
 223                     argTagged++;
 224
 225             // FIXME: can be smarter here
 226             if (names.length==p.count) {
 227                 int[] ret = new int[p.count];
 228                 for(int i=0; i<p.count; i++) ret[i] = i;
 229                 return ret;
 230             } else if (argTagged==p.count) {
 231                 int[] ret = new int[argtags.length];
 232                 int j = 0;
 233                 for(int i=0; i<argtags.length; i++)
 234                     ret[i] = argtags[i]==null ? -1 : (j++);
 235                 return ret;
 236             } else {
 237                 return null;
 238             }
 239         }
 240         public Sequence makeSequence(Production p) {
 241             return Sequence.rewritingSequence(new TargetReducer(p), p.elements, p.labels, p.drops);
 242         }
 243         public abstract Object plant(Object[] fields, int[] map);
 244         public boolean isRaw() { return false; }
 245         public Object invokeRaw(Tree t) { return null; }
 246         public class TargetReducer implements Reducer {
 247             private Production p;
 248             private int[] map;
 249             public TargetReducer(Production p) {
 250                 this.p = p;
 251                 this.map = buildSequence(p);
 252             }
 253             public String toString() { return "reducer-"+Target.this; }
 254             public Object reduce(Tree t) {
 255                 if (isRaw()) return invokeRaw(t);
 256                 Object[] objects = new Object[t.numChildren()];
 257                 for(int i=0; i<t.numChildren(); i++) {
 258                     Tree tc = t.child(i);
 259                     if (tc.head() != null && tc.head() instanceof Reducer)
 260                         objects[i] = ((Reducer)tc.head()).reduce(tc);
 261                     else if (tc.numChildren() == 0)
 262                         objects[i] = tc.head();
 263                     else {
 264                         System.err.println("FIXME: don't know what to do about " + tc);
 265                         objects[i] = null;
 266                     }
 267                 }
 268                 System.err.println("input tree: " + t);
 269                 return plant(objects, map);
 270             }
 271         }
 272     }
 273
 274     public static interface Reducer {
 275         public Object reduce(Tree t);
 276     }
 277
 278     public static class TargetClass extends Target {
 279         public final Class _class;
 280         public TargetClass(Class _class) { this._class = _class; }
 281         public String getName() { return _class.getSimpleName(); }
 282         public tag getTag() { return (tag)_class.getAnnotation(tag.class); }
 283         public nonterminal getNonTerminal() { return (nonterminal)_class.getAnnotation(nonterminal.class); }
 284         public String toString() { return _class.getSimpleName(); }
 285         public int[] buildSequence(Production p) {
 286             Field[]  f       = _class.getDeclaredFields();
 287             String[] names   = new String[f.length];
 288             arg[]    argtags = new arg[f.length];
 289             for(int i=0; i<f.length; i++) {
 290                 names[i]   = f[i].getName();
 291                 argtags[i] = f[i].getAnnotation(arg.class);
 292             }
 293             int[] ret = buildSequence(p, names, argtags);
 294             if (ret!=null) return ret;
 295             for(Constructor c : _class.getConstructors())
 296                 if (new TargetConstructor(c).buildSequence(p)!=null)
 297                     return new TargetConstructor(c).buildSequence(p);
 298             return null;
 299         }
 300         public Object plant(Object[] fields, int[] map) {
 301             try {
 302                 Object ret = _class.newInstance();
 303                 Field[] f = _class.getFields();
 304                 int j = 0;
 305                 for(int i=0; i<f.length; i++)
 306                     if (map[i] != -1) {
 307                         Object tgt = Reflection.lub(fields[map[i]]);
 308                         if (f[i].getType() == String.class) tgt = stringify(tgt);
 309                         // FUGLY
 310                         tgt = coerce(tgt, f[i].getType());
 311                         System.err.println("setting a " + f[i].getType().getName() + " to " + Reflection.show(tgt));
 312                         f[i].set(ret, tgt);
 313                     }
 314                 return ret;
 315             } catch (Exception e) {
 316                 e.printStackTrace();
 317                 throw new RuntimeException(e);
 318             }
 319         }
 320     }
 321
 322     public static String stringify(Object o) {
 323         if (o==null) return "";
 324         if (!(o instanceof Object[])) return o.toString();
 325         Object[] arr = (Object[])o;
 326         StringBuffer ret = new StringBuffer();
 327         for(int i=0; i<arr.length; i++)
 328             ret.append(arr[i]);
 329         return ret.toString();
 330     }
 331
 332     public static class TargetConstructor extends Target {
 333         public final Constructor _ctor;
 334         public TargetConstructor(Constructor _ctor) { this._ctor = _ctor; }
 335         public String getName() { return _ctor.getName(); }
 336         public tag getTag() { return (tag)_ctor.getAnnotation(tag.class); }
 337         public nonterminal getNonTerminal() { return (nonterminal)_ctor.getAnnotation(nonterminal.class); }
 338         public String toString() { return _ctor.getName(); }
 339         public int[] buildSequence(Production p) {
 340             Annotation[][] annotations = _ctor.getParameterAnnotations();
 341             int len = annotations.length;
 342             int ofs = 0;
 343             String name = _ctor.getDeclaringClass().getName();
 344             /*
 345             if (name.indexOf('$') > name.lastIndexOf('.')) {
 346                 len--;
 347                 ofs++;
 348             }
 349             */
 350             String[] names   = new String[len];
 351             arg[]    argtags = new arg[len];
 352             for(int i=0; i<names.length; i++)
 353                 for(Annotation a : annotations[i+ofs])
 354                     if (a instanceof arg)
 355                         argtags[i+ofs] = (arg)a;
 356             return buildSequence(p, names, argtags);
 357         }
 358         public Object plant(Object[] fields, int[] map) {
 359             try {
 360                 Class[] argTypes = _ctor.getParameterTypes();
 361                 Object[] args = new Object[argTypes.length];
 362                 int j = 0;
 363                 for(int i=0; i<args.length; i++)
 364                     if (map[i] != -1) {
 365                         Object tgt = Reflection.lub(fields[map[i]]);
 366                         if (argTypes[i] == String.class) tgt = stringify(tgt);
 367                         // FUGLY
 368                         tgt = coerce(tgt, argTypes[i]);
 369                         System.err.println("setting a " + argTypes[i].getName() + " to " + Reflection.show(tgt));
 370                         args[i] = tgt;
 371                     }
 372                 return _ctor.newInstance(args);
 373             } catch (Exception e) {
 374                 throw new RuntimeException(e);
 375             }
 376         }
 377     }
 378     public static class TargetMethod extends Target {
 379         public final Method _method;
 380         public TargetMethod(Method _method) { this._method = _method; }
 381         public String getName() { return _method.getName(); }
 382         public String toString() { return _method.getName(); }
 383         public tag getTag() { return (tag)_method.getAnnotation(tag.class); }
 384         public nonterminal getNonTerminal() { return (nonterminal)_method.getAnnotation(nonterminal.class); }
 385         public int[] buildSequence(Production p) {
 386             Annotation[][] annotations = _method.getParameterAnnotations();
 387             String[] names   = new String[annotations.length];
 388             arg[]    argtags = new arg[annotations.length];
 389             for(int i=0; i<names.length; i++)
 390                 for(Annotation a : annotations[i])
 391                     if (a instanceof arg)
 392                         argtags[i] = (arg)a;
 393             int[] ret = buildSequence(p, names, argtags);
 394             return ret;
 395         }
 396         public boolean isRaw() { return _method.isAnnotationPresent(raw.class); }
 397         public Object invokeRaw(Tree t) {
 398             try {
 399                 return _method.invoke(null, new Object[] { t });
 400             } catch (Exception e) {
 401                 throw new RuntimeException(e);
 402             }
 403         }
 404         public Object plant(Object[] fields, int[] map) {
 405             try {
 406                 Class[] argTypes = _method.getParameterTypes();
 407                 Object[] args = new Object[argTypes.length];
 408                 int j = 0;
 409                 for(int i=0; i<args.length; i++)
 410                     if (map[i] != -1) {
 411                         Object tgt = Reflection.lub(fields[map[i]]);
 412                         if (argTypes[i] == String.class) tgt = stringify(tgt);
 413                         // FUGLY
 414                         tgt = coerce(tgt, argTypes[i]);
 415                         System.err.println("setting a " + argTypes[i].getName() + " to " + Reflection.show(tgt));
 416                         args[i] = tgt;
 417                     }
 418                 System.err.println("invoking " + _method + " with " + Reflection.show(args));
 419                 return _method.invoke(null, args);
 420             } catch (Exception e) {
 421                 throw new RuntimeException(e);
 422             }
 423         }
 424     }
 425
 426     public static Object coerce(Object o, Class c) {
 427         if (o==null) return null;
 428         if (c.isInstance(o)) return o;
 429         if (c == char.class) {
 430             return o.toString().charAt(0);
 431         }
 432
 433         if (o.getClass().isArray() &&
 434             o.getClass().getComponentType().isArray() &&
 435             o.getClass().getComponentType().getComponentType() == String.class &&
 436             c.isArray() &&
 437             c.getComponentType() == String.class) {
 438             String[] ret = new String[((Object[])o).length];
 439             for(int i=0; i<ret.length; i++) {
 440                 StringBuffer sb = new StringBuffer();
 441                 for(Object ob : (Object[])(((Object[])o)[i]))
 442                     sb.append(ob);
 443                 ret[i] = sb.toString();
 444             }
 445             return ret;
 446         }
 447
 448         if (c.isArray() && (c.getComponentType().isInstance(o))) {
 449             Object[] ret = (Object[])Array.newInstance(c.getComponentType(), 1);
 450             ret[0] = o;
 451             return ret;
 452         }
 453
 454         if (o.getClass().isArray() && c.isArray()) {
 455             boolean ok = true;
 456             for(int i=0; i<((Object[])o).length; i++) {
 457                 Object ob = (((Object[])o)[i]);
 458                 if (ob != null) {
 459                     System.err.println("no hit with " + c.getComponentType().getName() + " on " + Reflection.show(((Object[])o)[i]));
 460                     ok = false;
 461                 }
 462             }
 463             if (ok) {
 464                 System.err.println("hit with " + c.getComponentType().getName());
 465                 return Array.newInstance(c.getComponentType(), ((Object[])o).length);
 466             }
 467         }
 468         return o;
 469     }
 470
 471     public static Union cached = null;
 472     public static Union make() {
 473         if (cached != null) return cached;
 474         try {
 475             ReflectiveMeta m = new ReflectiveMeta();
 476             Tree<String> res = new CharParser(MetaGrammar.make()).parse(new FileInputStream("tests/meta.g")).expand1();
 477             MetaGrammar.Meta.MetaGrammarFile mgf = m.new MetaGrammarFile(res);
 478             MetaGrammar.BuildContext bc = new MetaGrammar.BuildContext(mgf);
 479             Union meta = mgf.get("s").build(bc);
 480             Tree t = new CharParser(meta).parse(new FileInputStream("tests/meta.g")).expand1();
 481             return cached = make(t, "s");
 482         } catch (Exception e) {
 483             throw new RuntimeException(e);
 484         }
 485     }
 486     public static Union make(Tree t, String s) { return make(t, s, new ReflectiveMeta()); }
 487     public static Union make(Tree t, String s, ReflectiveMeta rm) {
 488         Reducer red = (Reducer)t.head();
 489         MG.Grammar g = (MG.Grammar)red.reduce(t);
 490         Context cx = new Context(g,rm);
 491         Union u = null;
 492         for(MG.NonTerminal nt : g.nonterminals) {
 493             System.out.println(nt.name);
 494             Union el = (Union)cx.get(nt.name);
 495             StringBuffer st = new StringBuffer();
 496             el.toString(st);
 497             System.err.println(st);
 498             if (nt.name.equals(s)) u = el;
 499         }
 500         return u;
 501     }
 502
 503     public static class MG {
 504         public static @tag("grammar") class Grammar {
 505             public NonTerminal get(String s) {
 506                 for(NonTerminal nt : nonterminals)
 507                     if (nt.name.equals(s))
 508                         return nt;
 509                 return null;
 510             }
 511             public @arg("NonTerminal") NonTerminal[] nonterminals;
 512             public String toString() {
 513                 String ret = "[ ";
 514                 for(NonTerminal nt : nonterminals) ret += nt + ", ";
 515                 return ret + " ]";
 516             }
 517         }
 518         public abstract static class Un extends El {
 519             public Seq[][] sequences;
 520             public void build(Context cx, Union u) {
 521                 HashSet<Sequence> bad2 = new HashSet<Sequence>();
 522                 for(int i=0; i<sequences.length; i++) {
 523                     Seq[] group = sequences[i];
 524                     Union u2 = new Union();
 525                     if (sequences.length==1) u2 = u;
 526                     for(int j=0; j<group.length; j++) {
 527                         group[j].build(cx, u2, false);
 528                     }
 529                     if (sequences.length==1) break;
 530                     Sequence seq = Sequence.singleton(u2);
 531                     for(Sequence s : bad2) {
 532                         s.lame = true;
 533                         seq = seq.not(s);
 534                     }
 535                     u.add(seq);
 536                     bad2.add(Sequence.singleton(u2));
 537                 }
 538             }
 539         }
 540         public static class NonTerminal extends Un {
 541             public String  name = null;
 542             public @nonterminal("NonTerminal") NonTerminal(@arg("Word") String name,
 543                                                            @arg("RHS") Seq[][] sequences) {
 544                 this.name = name;
 545                 this.sequences = sequences;
 546             }
 547             public Element build(Context cx) { return cx.get(name); }
 548         }
 549
 550         public static class AnonUn extends Un {
 551             public @tag("(") AnonUn(Seq[][] sequences) {
 552                 this.sequences = sequences;
 553             }
 554             public Element build(Context cx) {
 555                 Union ret = new Union();
 556                 build(cx, ret);
 557                 return ret;
 558             }
 559         }
 560
 561         //public static @tag void range(char c) { }
 562         public static class Range {
 563             public @tag("range") Range(char only) { first = only; last = only; }
 564             public @tag("-")     Range(char first, char last) { this.first = first; this.last = last; }
 565             public char first;
 566             public char last;
 567         }
 568         public static abstract class El {
 569             public String getLabel() { return null; }
 570             public String getOwnerTag() { return null; }
 571             public boolean drop() { return false; }
 572             public abstract Element build(Context cx);
 573         }
 574         public static class Drop extends El {
 575             public El e;
 576             public Drop(El e) { this.e = e; }
 577             public String getLabel() { return null; }
 578             public boolean drop() { return true; }
 579             public String getOwnerTag() { return e.getOwnerTag(); }
 580             public Element build(Context cx) { return e.build(cx); }
 581         }
 582         public static class Label extends El {
 583             public String label;
 584             public El e;
 585             public Label(String label, El e) { this.e = e; this.label = label; }
 586             public String getLabel() { return label; }
 587             public String getOwnerTag() { return e.getOwnerTag(); }
 588             public Element build(Context cx) { return e.build(cx); }
 589         }
 590         public static /*abstract*/ class Seq {
 591             HashSet<Seq> and = new HashSet<Seq>();
 592             HashSet<Seq> not = new HashSet<Seq>();
 593             El[] elements;
 594             El follow;
 595             String tag = null;
 596             boolean lame;
 597             public Seq(El e) { this(new El[] { e }); }
 598             public Seq(El[] elements) { this.elements = elements; }
 599             public Seq tag(String tag) { this.tag = tag; return this; }
 600             public Seq follow(El follow) { this.follow = follow; return this; }
 601             public Seq dup() {
 602                 Seq ret = new Seq(elements);
 603                 ret.and.addAll(and);
 604                 ret.not.addAll(not);
 605                 ret.follow = follow;
 606                 ret.tag = tag;
 607                 return ret;
 608             }
 609             public Seq and(Seq s) { and.add(s); s.lame = true; return this; }
 610             public Seq andnot(Seq s) { not.add(s); s.lame = true; return this; }
 611             public Seq separate(El sep) {
 612                 El[] elements = new El[this.elements.length * 2 - 1];
 613                 for(int i=0; i<this.elements.length; i++) {
 614                     elements[i*2]   = this.elements[i];
 615                     if (i<this.elements.length-1)
 616                         elements[i*2+1] = new Drop(sep);
 617                 }
 618                 this.elements = elements;
 619                 return this;
 620             }
 621             public Sequence build(Context cx, Union u, boolean lame) {
 622                 Sequence ret = build0(cx, lame || this.lame);
 623                 for(Seq s : and) { Sequence dork = s.build(cx, u, true); ret = ret.and(dork); }
 624                 for(Seq s : not) { Sequence dork = s.build(cx, u, true); ret = ret.not(dork); }
 625                 u.add(ret);
 626                 ret.lame = lame;
 627                 return ret;
 628             }
 629             public Sequence build0(Context cx, boolean lame) {
 630                 boolean unwrap = false;
 631                 boolean dropAll = lame;
 632                 if (tag!=null && tag.equals("[]")) unwrap  = true;
 633                 if (tag!=null && "()".equals(tag)) dropAll = true;
 634                 Object[] labels = new Object[elements.length];
 635                 boolean[] drops = new boolean[elements.length];
 636                 Element[] els = new Element[elements.length];
 637                 for(int i=0; i<elements.length; i++) {
 638                     labels[i] = elements[i].getLabel();
 639                     drops[i]  = elements[i].drop();
 640                     els[i] = elements[i].build(cx);
 641                     if (elements[i].getOwnerTag() != null)
 642                         tag = elements[i].getOwnerTag();
 643                 }
 644                 Sequence ret = null;
 645                 if (dropAll)     ret = Sequence.drop(els, false);
 646                 else if (unwrap) ret = Sequence.unwrap(els, cx.rm.repeatTag(), drops);
 647                 else if (tag!=null) {
 648                     ret = cx.rm.resolveTag(tag, cx.cnt, els, labels, drops);
 649                 } else {
 650                     int idx = -1;
 651                     for(int i=0; i<els.length; i++)
 652                         if (!drops[i])
 653                             if (idx==-1) idx = i;
 654                             else throw new Error("multiple non-dropped elements in sequence: " + Sequence.drop(els,false));
 655                     if (idx != -1) ret = Sequence.singleton(els, idx);
 656                     else           ret = Sequence.drop(els, false);
 657                 }
 658                 if (this.follow != null)
 659                     ret.follow = MetaGrammar.infer(this.follow.build(cx));
 660                 ret.lame = this.lame;
 661                 return ret;
 662             }
 663         }
 664         public static @tag("&")   Seq  and(Seq s,         El[] elements) { return s.and(seq(elements)); }
 665         public static @tag("&~")  Seq  andnot(Seq s,      El[] elements) { return s.andnot(seq(elements)); }
 666         public static @tag("->")  Seq  arrow(Seq s, El e)                { return s.follow(e); }
 667         public static @tag("::")  Seq  tag(String tagname, Seq s)        { return s.tag(tagname); }
 668         public static @tag("/")   Seq  slash(Seq s, El e)                { return s.separate(e); }
 669
 670         public static @tag("ps")  Seq  seq(El[] elements)                { return new Seq(elements); }
 671         public static @tag        Seq  psx(Seq s)                        { return s; }
 672         public static @tag(":")   El   colon(String s, El e)             { return new Label(s, e); }
 673         public static @tag(")")   void close(String foo)                 { throw new Error("not supported"); }
 674         public static @tag("()")  El   epsilon()                         { return new Constant(Union.epsilon); }
 675
 676         public static @tag("nonTerminal") class NonTerminalReference extends El {
 677             public @arg String nonTerminal;
 678             public Element build(Context cx) {
 679                 return cx.get(nonTerminal);
 680             }
 681         }
 682
 683         public static class StringLiteral        extends Constant {
 684             public @tag("literal") StringLiteral(String string) { super(CharRange.string(string)); }
 685             public boolean drop() { return true; }
 686         }
 687
 688         public static                     class CharClass            extends El {
 689             Range[] ranges;
 690             public @tag("[") CharClass(Range[] ranges) { this.ranges = ranges; }
 691             public Element build(Context cx) {
 692                 edu.berkeley.sbp.util.Range.Set set = new edu.berkeley.sbp.util.Range.Set();
 693                 for(Range r : ranges)
 694                         set.add(r.first, r.last);
 695                 return CharRange.set(set);
 696             }
 697         }
 698
 699         public static @tag("{")           class XTree                 extends El {
 700             public @arg Seq body;
 701             public Element build(Context cx) {
 702                 throw new Error();
 703             }
 704         }
 705
 706         public static class Rep extends El {
 707             public El e, sep;
 708             public boolean zero, many, max;
 709             public Rep(El e, El sep, boolean zero, boolean many, boolean max) {
 710                 this.e = e; this.sep = sep; this.zero = zero; this.many = many; this.max = max;}
 711             public Element build(Context cx) {
 712                 return (!max)
 713                     ? Sequence.repeat(e.build(cx),        zero, many, sep==null ? null : sep.build(cx), cx.rm.repeatTag())
 714                     : sep==null
 715                     ? Sequence.repeatMaximal(MetaGrammar.infer(e.build(cx)), zero, many,                                   cx.rm.repeatTag())
 716                     : Sequence.repeatMaximal(e.build(cx),                    zero, many, MetaGrammar.infer(sep.build(cx)), cx.rm.repeatTag());
 717             }
 718         }
 719         public static class Constant extends El {
 720             Element constant;
 721             public Constant(Element constant) { this.constant = constant; }
 722             public Element build(Context cx) { return constant; }
 723         }
 724         public abstract static class PostProcess extends El {
 725             El e;
 726             public PostProcess(El e) { this.e = e; }
 727             public Element build(Context cx) { return postProcess(e.build(cx)); }
 728             public abstract Element postProcess(Element e);
 729         }
 730
 731         // FIXME: it would be nice if we could hoist this into "Rep"
 732         public static @tag("++")  El plusmax(final El e)                     { return new Rep(e, null, false, true, true); }
 733         public static @tag("+")   El plus(final El e)                        { return new Rep(e, null, false, true, false); }
 734         public static @tag("++/") El plusmaxfollow(final El e, final El sep) { return new Rep(e, sep,  false, true, true); }
 735         public static @tag("+/")  El plusfollow(final El e, final El sep)    { return new Rep(e, sep,  false, true, false); }
 736         public static @tag("**")  El starmax(final El e)                     { return new Rep(e, null, true,  true, true); }
 737         public static @tag("*")   El star(final El e)                        { return new Rep(e, null, true,  true, false); }
 738         public static @tag("**/") El starmaxfollow(final El e, final El sep) { return new Rep(e, sep,  true,  true, true); }
 739         public static @tag("*/")  El starfollow(final El e, final El sep)    { return new Rep(e, sep,  true,  true, false); }
 740         public static @tag("?")   El question(final El e)                    { return new Rep(e, null, true,  true, false); }
 741
 742         public static @tag("!")   El bang(final El e)                        { return new Drop(e); }
 743
 744         public static @tag("^")   El caret(final String s) {
 745             return new Drop(new Constant(CharRange.string(s)) {
 746                     public String getOwnerTag() { return s; }
 747                 });
 748         }
 749
 750         public static @tag("~")   El tilde(final El e) {
 751             return new PostProcess(e) {
 752                     public Element postProcess(Element e) {
 753                         return MetaGrammar.infer((Topology<Character>)Atom.toAtom(e).complement());
 754                     } }; }
 755
 756         public static @tag("^^")  void doublecaret(final El e)                 { throw new Error("not implemented"); }
 757
 758         //public static @tag("(")   El subexpression(Seq[][] rhs)                { return new NonTerminal(rhs); }
 759
 760         public static @nonterminal("Word")    String word(String s) { return s; }
 761         public static @nonterminal("Quoted")  String quoted(String s) { return s; }
 762         public static @nonterminal("escaped") String c(char c) { return c+""; }
 763         public static @tag("\"\"")            String emptystring() { return ""; }
 764         public static @tag("\n")              String retur() { return "\n"; }
 765         public static @tag("\r")              String lf() { return "\r"; }
 766
 767     }
 768     public static class Context {
 769         HashMap<String,Union> map = new HashMap<String,Union>();
 770         private MG.Grammar grammar;
 771         public String cnt = null;
 772         private ReflectiveMeta rm;
 773         public Context(MG.Grammar g, ReflectiveMeta rm) {
 774             this.grammar = g;
 775             this.rm = rm;
 776         }
 777         public Union build() {
 778             Union ret = null;
 779             for(MG.NonTerminal nt : grammar.nonterminals) {
 780                 Union u = get(nt.name);
 781                 if ("s".equals(nt.name))
 782                     ret = u;
 783             }
 784             return ret;
 785         }
 786         public Context(Tree t, ReflectiveMeta rm) {
 787             this.rm = rm;
 788             Reducer red = (Reducer)t.head();
 789             this.grammar = (MG.Grammar)red.reduce(t);
 790         }
 791         public Union peek(String name) { return map.get(name); }
 792         public void  put(String name, Union u) { map.put(name, u); }
 793         public Union get(String name) {
 794             Union ret = map.get(name);
 795             if (ret != null) return ret;
 796             ret = new Union(name);
 797             map.put(name, ret);
 798             MG.NonTerminal nt = grammar.get(name);
 799             if (nt==null) {
 800                 System.err.println("*** warning could not find " + name);
 801             } else {
 802                 String old = cnt;
 803                 cnt = name;
 804                 nt.build(this, ret);
 805                 cnt = old;
 806             }
 807             return ret;
 808         }
 809
 810     }
 811 }