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