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