1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
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.*;
9 import java.lang.annotation.*;
10 import java.lang.reflect.*;
14 * The inner classes of this class represent nodes in the Abstract
15 * Syntax Tree of a grammar.
17 public class GrammarAST {
19 public static interface ImportResolver {
20 public InputStream getImportStream(String importname);
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>
27 public static Union getMetaGrammar() {
28 return buildFromAST(MetaGrammar.meta, "s", null);
32 * Create a grammar from a parse tree and binding resolver
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
38 public static Union buildFromAST(Tree grammarAST, String startingNonterminal, ImportResolver resolver) {
39 return new GrammarAST(resolver, "").buildGrammar(grammarAST, startingNonterminal);
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");
51 private static Object illegalTag = ""; // this is the tag that should never appear in the non-dropped output FIXME
53 // Instance //////////////////////////////////////////////////////////////////////////////
55 private final String prefix;
56 private final ImportResolver resolver;
58 public GrammarAST(ImportResolver resolver, String prefix) {
60 this.resolver = resolver;
63 // Methods //////////////////////////////////////////////////////////////////////////////
65 private Union buildGrammar(Tree t, String rootNonTerminal) {
67 if (o instanceof Union) return (Union)o;
68 return ((GrammarAST.GrammarNode)o).build(rootNonTerminal);
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);
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)));
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)));
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));
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);
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) };
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);
164 if (head.equals("#import")) {
165 if (resolver != null) {
166 String fileName = (String)stringifyChildren(t.child(0));
168 String newPrefix = t.size()<2 ? "" : (walkString(t.child(1))+".");
169 InputStream fis = resolver.getImportStream(fileName);
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);
178 throw new RuntimeException("no resolver given");
181 throw new RuntimeException("unknown head: \"" + head + "\" => " + (head.equals("...")));
185 // Nodes //////////////////////////////////////////////////////////////////////////////
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);
197 public GrammarNode(Object[] nt) { add(nt); }
198 private void add(Object o) {
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);
207 else if (o instanceof GrammarNode)
208 for(NonTerminalNode n : ((GrammarNode)o).values())
211 public String toString() {
213 for(NonTerminalNode nt : values()) ret += nt + ", ";
216 public Union build(String rootNonterminal) {
217 BuildContext cx = new BuildContext(this);
219 for(GrammarAST.NonTerminalNode nt : values())
220 if (nt.name.equals(rootNonterminal))
221 return (Union)cx.get(nt.name);
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);
235 pw.println(" public static class " + nt.name + "{");
236 pw.println(fieldDeclarations);
238 pw.println(" public static " + nt.name + " walk"+nt.name+"(Tree t) {");
239 pw.println(" int i = 0;");
240 pw.println(walkCode);
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\");");
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;
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; }
277 /** elements of the sequence */
278 ElementNode[] elements;
279 /** follow-set, if explicit */
281 /** tag to add when building the AST */
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;
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)
294 if (tag==null) return true;
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))
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();
315 // FIXME: this whole mechanism is sketchy
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)));
328 elements[j] = replace;
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);
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);
351 this.elements = elements;
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);
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();
375 boolean multiNonDrop = false;
376 for(int i=0; i<drops.length; 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);
385 els[i] = elements[i].build(cx, cnt, dropall);
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();
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);
401 ret = Sequence.create(tag, els, drops, lifts);
402 if (this.follow != null)
403 ret = ret.followedBy(this.follow.toAtom(cx));
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());
421 public final void emitCode(EmitContext cx,
422 StringBuffer fieldDeclarations,
423 StringBuffer walkCode) {
424 if (isDropped(cx)) return;
426 // parse just the literal text, create an int/float/char/string
427 // FIXME: how do we know which one?
428 walkCode.append(" stringify");
431 _emitCode(cx, fieldDeclarations, walkCode);
432 walkCode.append(" i++;");
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);
438 /** a union, produced by a ( .. | .. | .. ) construct */
439 private class UnionNode extends ElementNode {
441 /** each component of a union is a sequence */
442 public Seq[][] sequences;
444 /** if the union is a NonTerminal specified as Foo*=..., this is true */
447 /** if the union is a NonTerminal specified as Foo* /ws=..., then this is "ws" */
448 public String sep = null;
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;
458 public boolean isTagless() {
459 for (Seq[] ss : sequences)
461 if (!s.isTagless()) return false;
465 public String[] getPossibleEmitClasses() {
466 HashSet<String> cl = new HashSet<String> ();
467 for(Seq[] ss : sequences)
470 String cls = s.getEmitClass();
471 if (cls != null) cl.add(cls);
474 return (String[])cl.toArray(new String[0]);
477 public void _emitCode(EmitContext cx,
478 StringBuffer fieldDeclarations,
479 StringBuffer walkCode) {
480 throw new RuntimeException("not implemented " + this.getClass().getName());
483 public String getFieldName() { return null; }
484 public boolean isLifted() { return false; }
485 public boolean isDropped(Context cx) {
486 for(Seq[] seqs : sequences)
488 if (!seq.isDropped(cx))
492 public Atom toAtom(BuildContext cx) {
494 for(Seq[] ss : sequences)
496 ret = ret==null ? s.toAtom(cx) : (Atom)ret.union(s.toAtom(cx));
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) {
505 urep = new Union(null, false);
506 urep.add(Sequence.create(cnt.name, new Element[0]));
508 ? Sequence.create(new Element[] { u }, 0)
509 : Sequence.create(new Element[] { cx.get(sep), u }, 1));
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++)
518 group[j].build(cx, u2, cnt, dropall);
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});
528 if (sequences.length==1) break;
529 Sequence seq = Sequence.create(u2);
530 for(Sequence s : bad2) seq = seq.andnot(s);
532 bad2.add(Sequence.create(u2));
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;
548 public NonTerminalNode resolve(Context cx) {
549 NonTerminalNode ret = cx.grammar.get(nonTerminal);
550 if (ret==null) throw new RuntimeException("undefined nonterminal: " + nonTerminal);
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);
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+"\"");
564 public String getFieldName() { return StringUtil.uncapitalize(nonTerminal); }
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;
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);
586 public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall) { return CharAtom.string(string); }
589 /** an atom (usually a character class) */
590 private class AtomNode extends ElementNode {
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);
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;
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);
621 public Element build(BuildContext cx, NonTerminalNode cnt, boolean dropall, Object repeatTag) {
623 ? Repeat.repeat(e.build(cx, null, dropall), zero, many, sep==null ? null : sep.build(cx, null, dropall), repeatTag)
625 ? Repeat.repeatMaximal(e.toAtom(cx), zero, many, repeatTag)
626 : Repeat.repeatMaximal(e.build(cx, null, dropall), zero, many, sep.toAtom(cx), repeatTag);
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);
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);
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); }
660 private class DropNode extends ElementNodeWrapper {
661 public DropNode(ElementNode e) { super(e); }
662 public boolean isDropped(Context cx) { return true; }
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; }
672 //////////////////////////////////////////////////////////////////////////////
674 public class Context {
675 public HashMap<String,Union> map = new HashMap<String,Union>();
676 public GrammarNode grammar;
678 public Context(GrammarNode g) { this.grammar = g; }
682 public class EmitContext extends Context {
683 public EmitContext(GrammarNode g) { super(g); }
686 public class BuildContext extends Context {
687 public BuildContext(Tree t) { }
688 public BuildContext(GrammarNode g) { super(g); }
689 public Union build() {
691 for(NonTerminalNode nt : grammar.values()) {
692 Union u = get(nt.name);
693 if ("s".equals(nt.name))
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);
705 throw new Error("warning could not find " + name);
707 ret = new Union(name, false);
709 nt.getUnionNode().buildIntoPreallocatedUnion(this, nt, nt.isDropped(this), ret);