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