src/edu/berkeley/sbp/meta/GrammarAST.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp.meta;
   4 import edu.berkeley.sbp.util.*;
   5 import edu.berkeley.sbp.*;
   6 import edu.berkeley.sbp.chr.*;
   7 import edu.berkeley.sbp.misc.*;
   8 import java.util.*;
   9 import java.lang.annotation.*;
  10 import java.lang.reflect.*;
  11 import java.io.*;
  12
  13 /**
  14  *  The inner classes of this class represent nodes in the Abstract
  15  *  Syntax Tree of a grammar.
  16  */
  17 public class GrammarAST {
  18
  19     public static interface ImportResolver {
  20         public InputStream getImportStream(String importname);
  21     }
  22
  23     /**
  24      *  Returns a Union representing the metagrammar (<tt>meta.g</tt>); the Tree produced by
  25      *  parsing with this Union should be provided to <tt>buildFromAST</tt>
  26      */
  27     public static Union getMetaGrammar() {
  28         return buildFromAST(MetaGrammar.meta, "s", null);
  29     }
  30
  31     /**
  32      *  Create a grammar from a parse tree and binding resolver
  33      *
  34      *  @param t   a tree produced by parsing a grammar using the metagrammar
  35      *  @param s   the name of the "start symbol"
  36      *  @param gbr a GrammarBindingResolver that resolves grammatical reductions into tree-node-heads
  37      */
  38     public static Union buildFromAST(Tree grammarAST, String startingNonterminal, ImportResolver resolver) {
  39         return new GrammarAST(resolver, "").buildGrammar(grammarAST, startingNonterminal);
  40     }
  41
  42     public static void emitCode(PrintWriter pw, Tree grammarAST, String startingNonterminal, ImportResolver resolver) {
  43         GrammarAST ga = new GrammarAST(resolver, "");
  44         Object o = ga.walk(grammarAST);
  45         GrammarAST.GrammarNode gn = (GrammarAST.GrammarNode)o;
  46         EmitContext ecx = ga.new EmitContext(gn);
  47         gn.emitCode(ecx, pw, "com.foo", "ClassName");
  48     }
  49
  50     private static Object illegalTag = ""; // this is the tag that should never appear in the non-dropped output FIXME
  51
  52     // Instance //////////////////////////////////////////////////////////////////////////////
  53
  54     private final String prefix;
  55     private final ImportResolver resolver;
  56
  57     public GrammarAST(ImportResolver resolver, String prefix) {
  58         this.prefix = prefix;
  59         this.resolver = resolver;
  60     }
  61
  62     // Methods //////////////////////////////////////////////////////////////////////////////
  63
  64     private Union buildGrammar(Tree t, String rootNonTerminal) {
  65         Object o = walk(t);
  66         if (o instanceof Union) return (Union)o;
  67         return ((GrammarAST.GrammarNode)o).build(rootNonTerminal);
  68     }
  69
  70     private Object[] walkChildren(Tree t) {
  71         Object[] ret = new Object[t.size()];
  72         for(int i=0; i<ret.length; i++)
  73             ret[i] = walk(t.child(i));
  74         return Reflection.lub(ret);
  75     }
  76     private static String stringifyChildren(Tree t) {
  77         StringBuffer sb = new StringBuffer();
  78         for(int i=0; i<t.size(); i++) {
  79             sb.append(t.child(i).head());
  80             sb.append(stringifyChildren(t.child(i)));
  81         }
  82         return sb.toString();
  83     }
  84     private static String unescape(Tree t) {
  85         StringBuffer sb = new StringBuffer();
  86         for(int i=0; i<t.size(); i++)
  87             sb.append(t.child(i).head()+stringifyChildren(t.child(i)));
  88         return sb.toString();
  89     }
  90
  91     private ElementNode walkElement(Tree t) { return (ElementNode)walk(t); }
  92     private String      walkString(Tree t) { return (String)walk(t); }
  93     private Seq         walkSeq(Tree t) { return (Seq)walk(t); }
  94     private Object walk(Tree t) {
  95         String head = (String)t.head();
  96         while(head.indexOf('.') > 0)
  97             head = head.substring(head.indexOf('.')+1);
  98         if (head==null) throw new RuntimeException("head is null: " + t);
  99         if (head.equals("|")) return walkChildren(t);
 100         if (head.equals("RHS")) return walkChildren(t);
 101         if (head.equals("Grammar")) return new GrammarNode(walkChildren(t));
 102         if (head.equals("(")) return new UnionNode((Seq[][])walkChildren(t.child(0)));
 103         if (head.equals("Word")) return stringifyChildren(t);
 104         if (head.equals("Elements")) return new Seq((ElementNode[])Reflection.rebuild(walkChildren(t), ElementNode[].class));
 105         if (head.equals("NonTerminalReference")) return new ReferenceNode(stringifyChildren(t.child(0)));
 106         if (head.equals(")"))   return new ReferenceNode(stringifyChildren(t.child(0)), true);
 107         if (head.equals(":"))   return new LabelNode(stringifyChildren(t.child(0)), walkElement(t.child(1)));
 108         if (head.equals("::"))  return walkSeq(t.child(1)).tag(walkString(t.child(0)));
 109         if (head.equals("...")) return new DropNode(new RepeatNode(new TildeNode(new AtomNode()), null, true,  true,  false));
 110
 111         if (head.equals("++"))  return new RepeatNode(walkElement(t.child(0)), null,                      false, true,  true);
 112         if (head.equals("+"))   return new RepeatNode(walkElement(t.child(0)), null,                      false, true,  false);
 113         if (head.equals("++/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   false, true,  true);
 114         if (head.equals("+/"))  return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   false, true,  false);
 115         if (head.equals("**"))  return new RepeatNode(walkElement(t.child(0)), null,                      true,  true,  true);
 116         if (head.equals("*"))   return new RepeatNode(walkElement(t.child(0)), null,                      true,  true,  false);
 117         if (head.equals("**/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   true,  true,  true);
 118         if (head.equals("*/"))  return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)),   true,  true,  false);
 119         if (head.equals("?"))   return new RepeatNode(walkElement(t.child(0)), null,                      true,  false, false);
 120
 121         if (head.equals("!"))   return new DropNode(walkElement(t.child(0)));
 122         if (head.equals("^"))   return new LiteralNode(walkString(t.child(0)), true);
 123         if (head.equals("`"))   return new BacktickNode(walkElement(t.child(0)));
 124         if (head.equals("Quoted")) return stringifyChildren(t);
 125         if (head.equals("Literal")) return new LiteralNode(walkString(t.child(0)));
 126         if (head.equals("->")) return walkSeq(t.child(0)).follow(walkElement(t.child(1)));
 127         if (head.equals("DropNT")) return new NonTerminalNode(walkString(t.child(0)), (Seq[][])walkChildren(t.child(1)), false, null, true, false);
 128         if (head.equals("=")) return new NonTerminalNode(walkString(t.child(0)), (Seq[][])walk(t.child(2)),
 129                                                          true, t.size()==2 ? null : walkString(t.child(1)), false, false);
 130         if (head.equals("&"))   return walkSeq(t.child(0)).and(walkSeq(t.child(1)));
 131         if (head.equals("&~"))  return walkSeq(t.child(0)).andnot(walkSeq(t.child(1)));
 132         if (head.equals("/"))   return (walkSeq(t.child(0))).separate(walkElement(t.child(1)));
 133         if (head.equals("()"))  return new LiteralNode("");
 134         if (head.equals("["))   return new AtomNode((char[][])Reflection.rebuild(walkChildren(t), char[][].class));
 135         if (head.equals("\\{")) return new DropNode(new AtomNode(new char[] { CharAtom.left, CharAtom.left }));
 136         if (head.equals("\\}")) return new DropNode(new AtomNode(new char[] { CharAtom.right, CharAtom.right }));
 137         if (head.equals(">>"))  return new DropNode(new AtomNode(new char[] { CharAtom.left, CharAtom.left }));
 138         if (head.equals("<<"))  return new DropNode(new AtomNode(new char[] { CharAtom.right, CharAtom.right }));
 139         if (head.equals("~"))   return new TildeNode(walkElement(t.child(0)));
 140         if (head.equals("~~"))  return new Seq(new RepeatNode(new TildeNode(new AtomNode()), null, true,  true,  false)).andnot(walkSeq(t.child(0)));
 141         if (head.equals("Range")) {
 142             if (t.size()==2 && ">".equals(t.child(0).head())) return new char[] { CharAtom.left, CharAtom.left };
 143             if (t.size()==2 && "<".equals(t.child(0).head())) return new char[] { CharAtom.right, CharAtom.right };
 144             if (t.size()==1) return new char[] { unescape(t).charAt(0), unescape(t).charAt(0) };
 145             return new char[] { unescape(t).charAt(0), unescape(t).charAt(1) };
 146         }
 147         if (head.equals("\"\"")) return "";
 148         if (head.equals("\n"))   return "\n";
 149         if (head.equals("\t"))   return "\t";
 150         if (head.equals("\r"))   return "\r";
 151         if (head.equals("SubGrammar")) return GrammarAST.buildFromAST(t.child(0), "s", resolver);
 152         if (head.equals("NonTerminal"))
 153             return new NonTerminalNode(walkString(t.child(0)),
 154                                        (Seq[][])walkChildren(t.child(1)), false, null, false, false);
 155         if (head.equals("Colons")) {
 156             String tag = walkString(t.child(0));
 157             Seq[][] seqs = (Seq[][])walk(t.child(1));
 158             for(Seq[] seq : seqs)
 159                 for(int i=0; i<seq.length; i++)
 160                     seq[i] = seq[i].tag(tag);
 161             return new NonTerminalNode(tag, seqs, false, null, false, true);
 162         }
 163         if (head.equals("#import")) {
 164             if (resolver != null) {
 165                 String fileName = (String)stringifyChildren(t.child(0));
 166                 try {
 167                     String newPrefix = t.size()<2 ? "" : (walkString(t.child(1))+".");
 168                     InputStream fis = resolver.getImportStream(fileName);
 169                     if (fis==null)
 170                         throw new RuntimeException("unable to find #include file \""+fileName+"\"");
 171                     Tree tr = new CharParser(getMetaGrammar()).parse(fis).expand1();
 172                     return (GrammarNode)new GrammarAST(resolver, newPrefix).walk(tr);
 173                 } catch (Exception e) {
 174                     throw new RuntimeException("while parsing " + fileName, e);
 175                 }
 176             } else {
 177                 throw new RuntimeException("no resolver given");
 178             }
 179         }
 180         throw new RuntimeException("unknown head: \"" + head + "\" => " + (head.equals("...")));
 181     }
 182
 183
 184     // Nodes //////////////////////////////////////////////////////////////////////////////
 185
 186     /** Root node of a grammar's AST; a set of named nonterminals */
 187     private class GrammarNode extends HashMap<String,NonTerminalNode> {
 188         public GrammarNode(NonTerminalNode[] nonterminals) {
 189             for(NonTerminalNode nt : nonterminals) {
 190                 if (nt==null) continue;
 191                 if (this.get(nt.name)!=null)
 192                     throw new RuntimeException("duplicate definition of nonterminal \""+nt.name+"\"");
 193                 this.put(nt.name, nt);
 194             }
 195         }
 196         public  GrammarNode(Object[] nt) { add(nt); }
 197         private void add(Object o) {
 198             if (o==null) return;
 199             else if (o instanceof Object[]) for(Object o2 : (Object[])o) add(o2);
 200             else if (o instanceof NonTerminalNode) {
 201                 NonTerminalNode nt = (NonTerminalNode)o;
 202                 if (this.get(nt.name)!=null)
 203                     throw new RuntimeException("duplicate definition of nonterminal \""+nt.name+"\"");
 204                 this.put(nt.name, nt);
 205             }
 206             else if (o instanceof GrammarNode)
 207                 for(NonTerminalNode n : ((GrammarNode)o).values())
 208                     add(n);
 209         }
 210         public String toString() {
 211             String ret = "[ ";
 212             for(NonTerminalNode nt : values()) ret += nt + ", ";
 213             return ret + " ]";
 214         }
 215         public Union build(String rootNonterminal) {
 216             BuildContext cx = new BuildContext(this);
 217             Union u = null;
 218             for(GrammarAST.NonTerminalNode nt : values())
 219                 if (nt.name.equals(rootNonterminal))
 220                     return (Union)cx.get(nt.name);
 221             return null;
 222         }
 223         public void emitCode(EmitContext cx, PrintWriter pw, String packageName, String className) {
 224             pw.println("package " + packageName + ";");
 225             pw.println("public class " + className + " {");
 226             // FIXME: root walking method
 227             //pw.println("  public static XXX walk() root");
 228             for(NonTerminalNode nt : values()) {
 229                 if (!(nt.name.charAt(0) >= 'A' && nt.name.charAt(0) <= 'Z')) continue;
 230                 StringBuffer fieldDeclarations = new StringBuffer();
 231                 StringBuffer walkCode = new StringBuffer();
 232                 nt.getUnionNode().emitCode(cx, fieldDeclarations, walkCode);
 233                 if (nt.tagged) {
 234                     pw.println("  public static class " + nt.name + "{");
 235                     pw.println(fieldDeclarations);
 236                     pw.println("  }");
 237                     pw.println("  public static " + nt.name + " walk"+nt.name+"(Tree t) {");
 238                     pw.println("    int i = 0;");
 239                     pw.println(walkCode);
 240                     pw.println("  }");
 241                 } else {
 242                     // FIXME; list who extends it
 243                     pw.println("  public static interface " + nt.name + "{ }");
 244                     // FIXME: what on earth is this going to be?
 245                     pw.println("  public static " + nt.name + " walk"+nt.name+"(Tree t) {");
 246                     pw.println("    throw new Error(\"FIXME\");");
 247                     pw.println("  }");
 248                 }
 249             }
 250             pw.println("}");
 251         }
 252     }
 253
 254     /** a NonTerminal is always a union at the top level */
 255     private class NonTerminalNode {
 256         public final boolean alwaysDrop;
 257         public final String  name;
 258         public final ElementNode elementNode;
 259         public final UnionNode unionNode;
 260         public final boolean tagged;
 261         public NonTerminalNode(String name, Seq[][] sequences, boolean rep, String sep, boolean alwaysDrop, boolean tagged) {
 262             this.name = prefix + name;
 263             this.alwaysDrop = alwaysDrop;
 264             this.tagged = tagged;
 265             this.unionNode = new UnionNode(sequences, rep, sep==null?null:(prefix + sep));
 266             this.elementNode = alwaysDrop ? new DropNode(unionNode) : unionNode;
 267         }
 268         public boolean isDropped(Context cx) { return alwaysDrop; }
 269         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return cx.get(name); }
 270         public ElementNode getElementNode() { return elementNode; }
 271         public UnionNode   getUnionNode() { return unionNode; }
 272     }
 273
 274     /** a sequence */
 275     private class Seq {
 276         /** elements of the sequence */
 277         ElementNode[] elements;
 278         /** follow-set, if explicit */
 279         ElementNode follow;
 280         /** tag to add when building the AST */
 281         String tag = null;
 282         /** positive conjuncts */
 283         HashSet<Seq> and = new HashSet<Seq>();
 284         /** negative conjuncts */
 285         HashSet<Seq> not = new HashSet<Seq>();
 286         public boolean alwaysDrop = false;
 287
 288         public boolean isTagless() {
 289             if (alwaysDrop) return true;
 290             for(int i=0; i<elements.length; i++)
 291                 if ((elements[i] instanceof LiteralNode) && ((LiteralNode)elements[i]).caret)
 292                     return false;
 293             if (tag==null) return true;
 294             return false;
 295         }
 296
 297         public boolean isDropped(Context cx) {
 298             if (alwaysDrop) return true;
 299             if (tag!=null) return false;
 300             for(int i=0; i<elements.length; i++)
 301                 if (!elements[i].isDropped(cx) || ((elements[i] instanceof LiteralNode) && ((LiteralNode)elements[i]).caret))
 302                     return false;
 303             return true;
 304         }
 305         public Seq(ElementNode e) { this(new ElementNode[] { e }); }
 306         public Seq(ElementNode[] elements) { this(elements, true); }
 307         public Seq(ElementNode[] el, boolean check) {
 308             this.elements = new ElementNode[el.length];
 309             System.arraycopy(el, 0, elements, 0, el.length);
 310             for(int i=0; i<elements.length; i++) {
 311                 if (elements[i]==null)
 312                     throw new RuntimeException();
 313             }
 314             // FIXME: this whole mechanism is sketchy
 315             if (check)
 316                 for(int i=0; i<elements.length; i++) {
 317                     if ((elements[i] instanceof ReferenceNode) && ((ReferenceNode)elements[i]).parenthesized) {
 318                         ReferenceNode rn = (ReferenceNode)elements[i];
 319                         ElementNode replace = null;
 320                         for(int j=0; j<elements.length; j++) {
 321                             if (!(elements[j] instanceof ReferenceNode)) continue;
 322                             ReferenceNode rn2 = (ReferenceNode)elements[j];
 323                             if (rn2.nonTerminal.equals(rn.nonTerminal) && !rn2.parenthesized) {
 324                                 if (replace == null) {
 325                                     replace = new UnionNode(new Seq(rn2).andnot(new Seq(elements, false)));
 326                                 }
 327                                 elements[j] = replace;
 328                             }
 329                         }
 330                     }
 331                 }
 332         }
 333         public Atom toAtom(BuildContext cx) {
 334             if (elements.length != 1)
 335                 throw new Error("you attempted to use ->, **, ++, or a similar character-class"+
 336                                 " operator on a [potentially] multicharacter production");
 337             return elements[0].toAtom(cx);
 338         }
 339         public Seq tag(String tag) { this.tag = tag; return this; }
 340         public Seq follow(ElementNode follow) { this.follow = follow; return this; }
 341         public Seq and(Seq s) { and.add(s); s.alwaysDrop = true; return this; }
 342         public Seq andnot(Seq s) { not.add(s); s.alwaysDrop = true; return this; }
 343         public Seq separate(ElementNode sep) {
 344             ElementNode[] elements = new ElementNode[this.elements.length * 2 - 1];
 345             for(int i=0; i<this.elements.length; i++) {
 346                 elements[i*2] = this.elements[i];
 347                 if (i<this.elements.length-1)
 348                     elements[i*2+1] = new DropNode(sep);
 349             }
 350             this.elements = elements;
 351             return this;
 352         }
 353         public Sequence build(BuildContext cx, Union u, NonTerminalNode cnt, boolean dropall) {
 354             Sequence ret = build0(cx, cnt, dropall);
 355             for(Seq s : and) ret = ret.and(s.build(cx, null, cnt, true));
 356             for(Seq s : not) ret = ret.andnot(s.build(cx, null, cnt, true));
 357             if (u!=null) u.add(ret);
 358             return ret;
 359         }
 360         public Sequence build0(BuildContext cx, NonTerminalNode cnt, boolean dropall) {
 361             boolean[] drops = new boolean[elements.length];
 362             Element[] els = new Element[elements.length];
 363             dropall |= isDropped(cx);
 364             for(int i=0; i<elements.length; i++) {
 365                 if (dropall) drops[i] = true;
 366                 else         drops[i] = elements[i].isDropped(cx);
 367                 if (elements[i] instanceof LiteralNode && ((LiteralNode)elements[i]).caret) {
 368                     if (tag != null) throw new RuntimeException("cannot have multiple tags in a sequence: " + this);
 369                     tag = ((LiteralNode)elements[i]).getLiteralTag();
 370                 }
 371             }
 372             Sequence ret = null;
 373             int idx = -1;
 374             boolean multiNonDrop = false;
 375             for(int i=0; i<drops.length; i++)
 376                 if (!drops[i])
 377                     if (idx==-1) idx = i;
 378                     else multiNonDrop = true;
 379             for(int i=0; i<elements.length; i++) {
 380                 if (!multiNonDrop && i==idx && tag!=null && elements[i] instanceof RepeatNode) {
 381                     els[i] = ((RepeatNode)elements[i]).build(cx, cnt, dropall, tag);
 382                     tag = null;
 383                 } else
 384                     els[i] = elements[i].build(cx, cnt, dropall);
 385             }
 386             if (tag==null && multiNonDrop)
 387                 throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create("", els));
 388             boolean[] lifts = new boolean[elements.length];
 389             for(int i=0; i<elements.length; i++)
 390                 lifts[i] = elements[i].isLifted();
 391             if (!multiNonDrop) {
 392                 if (idx == -1)
 393                     ret = tag==null
 394                         ? Sequence.create(illegalTag, els)
 395                         : Sequence.create(tag, els, drops, lifts);
 396                 else if (tag==null) ret = Sequence.create(els, idx);
 397                 else ret = Sequence.create(tag, els, drops, lifts);
 398             }
 399             if (multiNonDrop)
 400                 ret = Sequence.create(tag, els, drops, lifts);
 401             if (this.follow != null)
 402                 ret = ret.followedBy(this.follow.toAtom(cx));
 403             return ret;
 404         }
 405     }
 406
 407     /** a node in the AST which is resolved into an Element */
 408     private abstract class ElementNode {
 409         /** the field name to be used when synthesizing AST classes; null if none suggested */
 410         public String getFieldName() { return null; }
 411         public boolean isLifted() { return false; }
 412         public boolean isDropped(Context cx) { return false; }
 413         //public abstract boolean isTagless();
 414         public boolean isTagless() { return false; }
 415         public void _emitCode(EmitContext cx,
 416                               StringBuffer fieldDeclarations,
 417                               StringBuffer walkCode) {
 418             throw new RuntimeException("not implemented " + this.getClass().getName());
 419         }
 420         public final void emitCode(EmitContext cx,
 421                                    StringBuffer fieldDeclarations,
 422                                    StringBuffer walkCode) {
 423             if (isDropped(cx)) return;
 424             if (isTagless()) {
 425                 // parse just the literal text, create an int/float/char/string
 426                 // FIXME: how do we know which one?
 427                 walkCode.append("      stringify");
 428             } else {
 429             }
 430             _emitCode(cx, fieldDeclarations, walkCode);
 431             walkCode.append("      i++;");
 432         }
 433         public Atom toAtom(BuildContext cx) { throw new Error("can't convert a " + this.getClass().getName() + " to an atom: " + this); }
 434         public abstract Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall);
 435     }
 436
 437     /** a union, produced by a ( .. | .. | .. ) construct */
 438     private class UnionNode extends ElementNode {
 439
 440         /** each component of a union is a sequence */
 441         public Seq[][] sequences;
 442
 443         /** if the union is a NonTerminal specified as Foo*=..., this is true */
 444         public boolean rep;
 445
 446         /** if the union is a NonTerminal specified as Foo* /ws=..., then this is "ws" */
 447         public String  sep = null;
 448
 449         public UnionNode(Seq seq) { this(new Seq[][] { new Seq[] { seq } }); }
 450         public UnionNode(Seq[][] sequences) { this(sequences, false, null); }
 451         public UnionNode(Seq[][] sequences, boolean rep, String sep) {
 452             this.sequences = sequences;
 453             this.rep = rep;
 454             this.sep = sep;
 455         }
 456
 457         public boolean isTagless() {
 458             for (Seq[] ss : sequences)
 459                 for (Seq s : ss)
 460                     if (!s.isTagless()) return false;
 461             return true;
 462         }
 463
 464         public String[] getPossibleEmitClasses() {
 465             HashSet<String> cl = new HashSet<String> ();
 466             for(Seq[] ss : sequences)
 467                 for(Seq s : ss) {
 468                     /*
 469                     String cls = s.getEmitClass();
 470                     if (cls != null) cl.add(cls);
 471                     */
 472                 }
 473             return (String[])cl.toArray(new String[0]);
 474         }
 475
 476         public void _emitCode(EmitContext cx,
 477                               StringBuffer fieldDeclarations,
 478                               StringBuffer walkCode) {
 479             throw new RuntimeException("not implemented " + this.getClass().getName());
 480         }
 481
 482         public String getFieldName() { return null; }
 483         public boolean isLifted() { return false; }
 484         public boolean isDropped(Context cx) {
 485             for(Seq[] seqs : sequences)
 486                 for(Seq seq : seqs)
 487                     if (!seq.isDropped(cx))
 488                         return false;
 489             return true;
 490         }
 491         public Atom toAtom(BuildContext cx) {
 492             Atom ret = null;
 493             for(Seq[] ss : sequences)
 494                 for(Seq s : ss)
 495                     ret = ret==null ? s.toAtom(cx) : (Atom)ret.union(s.toAtom(cx));
 496             return ret;
 497         }
 498
 499         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) {
 500             return buildIntoPreallocatedUnion(cx, cnt, dropall, new Union(null, false)); }
 501         public Element buildIntoPreallocatedUnion(BuildContext cx, NonTerminalNode cnt, boolean dropall, Union u) {
 502             Union urep = null;
 503             if (rep) {
 504                 urep = new Union(null, false);
 505                 urep.add(Sequence.create(cnt.name, new Element[0]));
 506                 urep.add(sep==null
 507                          ? Sequence.create(new Element[] { u }, 0)
 508                          : Sequence.create(new Element[] { cx.get(sep), u }, 1));
 509             }
 510             HashSet<Sequence> bad2 = new HashSet<Sequence>();
 511             for(int i=0; i<sequences.length; i++) {
 512                 Seq[] group = sequences[i];
 513                 Union u2 = new Union(null, false);
 514                 if (sequences.length==1) u2 = u;
 515                 for(int j=0; j<group.length; j++)
 516                     if (!rep)
 517                         group[j].build(cx, u2, cnt, dropall);
 518                     else {
 519                         Union u3 = new Union(null, false);
 520                         group[j].build(cx, u3, cnt, dropall);
 521                         Sequence s = Sequence.create(cnt.name,
 522                                                      new Element[] { u3, urep },
 523                                                      new boolean[] { false, false },
 524                                                      new boolean[] { false, true});
 525                         u2.add(s);
 526                     }
 527                 if (sequences.length==1) break;
 528                 Sequence seq = Sequence.create(u2);
 529                 for(Sequence s : bad2) seq = seq.andnot(s);
 530                 u.add(seq);
 531                 bad2.add(Sequence.create(u2));
 532             }
 533             return u;
 534         }
 535     }
 536
 537     /** reference to a NonTerminal by name */
 538     private class ReferenceNode extends ElementNode {
 539         public String nonTerminal;
 540         public boolean parenthesized;
 541         public ReferenceNode() { }
 542         public ReferenceNode(String nonTerminal) { this(nonTerminal, false); }
 543         public ReferenceNode(String nonTerminal, boolean parenthesized) {
 544             this.nonTerminal = nonTerminal.indexOf('.')==-1 ? (prefix + nonTerminal) : nonTerminal;
 545             this.parenthesized = parenthesized;
 546         }
 547         public NonTerminalNode resolve(Context cx) {
 548             NonTerminalNode ret = cx.grammar.get(nonTerminal);
 549             if (ret==null) throw new RuntimeException("undefined nonterminal: " + nonTerminal);
 550             return ret;
 551         }
 552         public Atom toAtom(BuildContext cx) {
 553             ElementNode ret = cx.grammar.get(nonTerminal).getElementNode();
 554             if (ret == null) throw new RuntimeException("unknown nonterminal \""+nonTerminal+"\"");
 555             return ret.toAtom(cx);
 556         }
 557         public boolean isDropped(Context cx) { return resolve(cx).isDropped(cx); }
 558         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) {
 559             Element ret = cx.get(nonTerminal);
 560             if (ret == null) throw new RuntimeException("unknown nonterminal \""+nonTerminal+"\"");
 561             return ret;
 562         }
 563         public String getFieldName() { return StringUtil.uncapitalize(nonTerminal); }
 564     }
 565
 566     /** a literal string */
 567     private class LiteralNode extends ElementNode {
 568         private String string;
 569         private final String thePrefix = prefix;
 570         private boolean caret;
 571         public LiteralNode(String string) { this(string, false); }
 572         public LiteralNode(String string, boolean caret) {
 573             this.string = string;
 574             this.caret = caret;
 575         }
 576         public String getLiteralTag() { return caret ? thePrefix+string : null; }
 577         public String toString() { return "\""+string+"\""; }
 578         public boolean isDropped(Context cx) { return true; }
 579         public Atom toAtom(BuildContext cx) {
 580             if (string.length()!=1) return super.toAtom(cx);
 581             Range.Set set = new Range.Set();
 582             set.add(string.charAt(0), string.charAt(0));
 583             return CharAtom.set(set);
 584         }
 585         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return CharAtom.string(string); }
 586     }
 587
 588     /** an atom (usually a character class) */
 589     private class AtomNode extends ElementNode {
 590         char[][] ranges;
 591         public AtomNode() { this(new char[0][]); }
 592         public AtomNode(char[][] ranges) { this.ranges = ranges; }
 593         public AtomNode(char[] range) { this.ranges = new char[][] { range }; }
 594         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return toAtom(cx); }
 595         public Atom toAtom(BuildContext cx) {
 596             Range.Set set = new Range.Set();
 597             for(char[] r : ranges) set.add(r[0], r[1]);
 598             return CharAtom.set(set);
 599         }
 600     }
 601
 602     /** a repetition */
 603     private class RepeatNode extends ElementNode {
 604         public ElementNode e, sep;
 605         public final boolean zero, many, max;
 606         public RepeatNode(ElementNode e, ElementNode sep, boolean zero, boolean many, boolean max) {
 607             this.e = e; this.sep = sep; this.zero = zero; this.many = many; this.max = max;
 608         }
 609         public Atom toAtom(BuildContext cx) { return sep==null ? e.toAtom(cx) : super.toAtom(cx); }
 610         public boolean isDropped(Context cx) { return e.isDropped(cx); }
 611         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) {
 612             Element ret = build(cx, cnt, dropall, illegalTag);
 613             String must = "must be tagged unless they appear within a dropped expression or their contents are dropped: ";
 614             if (!dropall && !isDropped(cx) && !e.isDropped(cx))
 615                 if (!many)      throw new RuntimeException("options (?) " + must + ret);
 616                 else if (zero)  throw new RuntimeException("zero-or-more repetitions (*) " + must + ret);
 617                 else            throw new RuntimeException("one-or-more repetitions (+) " + must + ret);
 618             return ret;
 619         }
 620         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall, Object repeatTag) {
 621             return (!max)
 622                 ? Repeat.repeat(e.build(cx, null, dropall), zero, many, sep==null ? null : sep.build(cx, null, dropall), repeatTag)
 623                 : sep==null
 624                 ? Repeat.repeatMaximal(e.toAtom(cx), zero, many, repeatTag)
 625                 : Repeat.repeatMaximal(e.build(cx, null, dropall), zero, many, sep.toAtom(cx), repeatTag);
 626         }
 627     }
 628
 629     /** helper class for syntactic constructs that wrap another construct */
 630     private abstract class ElementNodeWrapper extends ElementNode {
 631         protected ElementNode _e;
 632         public ElementNodeWrapper(ElementNode e) { this._e = e; }
 633         public boolean isDropped(Context cx) { return _e.isDropped(cx); }
 634         public Atom toAtom(BuildContext cx) { return _e.toAtom(cx); }
 635         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return _e.build(cx, cnt, dropall); }
 636         public String getFieldName() { return _e.getFieldName(); }
 637         public void _emitCode(EmitContext cx, StringBuffer fieldDeclarations, StringBuffer walkCode) {
 638             _e._emitCode(cx, fieldDeclarations, walkCode);
 639         }
 640     }
 641
 642     /** a backtick node indicating that, when building the AST, the node's children should be inserted here */
 643     private class BacktickNode extends ElementNodeWrapper {
 644         public BacktickNode(ElementNode e) { super(e); }
 645         public boolean isLifted() { return true; }
 646         public String getFieldName() { throw new Error("FIXME: backtick isn't a single field"); }
 647         public void _emitCode(EmitContext cx, StringBuffer fieldDeclarations, StringBuffer walkCode) {
 648             _e._emitCode(cx, fieldDeclarations, walkCode);
 649         }
 650     }
 651
 652     /** negation */
 653     private class TildeNode extends ElementNodeWrapper {
 654         public TildeNode(ElementNode e) { super(e); }
 655         public Atom toAtom(BuildContext cx) { return (Atom)((Topology<Character>)_e.toAtom(cx).complement()); }
 656         public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return toAtom(cx); }
 657     }
 658
 659     private class DropNode extends ElementNodeWrapper {
 660         public DropNode(ElementNode e) { super(e); }
 661         public boolean isDropped(Context cx) { return true; }
 662     }
 663
 664     /** provides a label on the fields of a Seq */
 665     private class LabelNode extends ElementNodeWrapper {
 666         public final String label;
 667         public LabelNode(String label, ElementNode e) { super(e); this.label = label; }
 668         public String getFieldName() { return label; }
 669     }
 670
 671     //////////////////////////////////////////////////////////////////////////////
 672
 673     public class Context {
 674         public HashMap<String,Union> map = new HashMap<String,Union>();
 675         public GrammarNode grammar;
 676         public Context() {  }
 677         public Context(GrammarNode g) { this.grammar = g; }
 678     }
 679
 680
 681     public class EmitContext extends Context {
 682         public EmitContext(GrammarNode g) { super(g); }
 683     }
 684
 685     public class BuildContext extends Context {
 686         public BuildContext(Tree t) { }
 687         public BuildContext(GrammarNode g) { super(g); }
 688         public Union build() {
 689             Union ret = null;
 690             for(NonTerminalNode nt : grammar.values()) {
 691                 Union u = get(nt.name);
 692                 if ("s".equals(nt.name))
 693                     ret = u;
 694             }
 695             return ret;
 696         }
 697         public Union peek(String name) { return map.get(name); }
 698         public void  put(String name, Union u) { map.put(name, u); }
 699         public Union get(String name) {
 700             Union ret = map.get(name);
 701             if (ret != null) return ret;
 702             NonTerminalNode nt = grammar.get(name);
 703             if (nt==null) {
 704                 throw new Error("warning could not find " + name);
 705             } else {
 706                 ret = new Union(name, false);
 707                 map.put(name, ret);
 708                 nt.getUnionNode().buildIntoPreallocatedUnion(this, nt, nt.isDropped(this), ret);
 709             }
 710             return ret;
 711         }
 712
 713     }
 714
 715 }