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