- public Object walk(Tree<String> tree) {
- String head = tree.head();
- if (tree.numChildren()==0) return super.walk(tree);
- if ("\\n".equals(head)) return new Character('\n');
- else if ("\\r".equals(head)) return new Character('\r');
- else if ("grammar".equals(head)) { for(Tree<String> t : tree.children()) walk(t); return this; }
- else if ("*".equals(head)) return Sequence.many0((Element)walk(tree.child(0)), repeatTag());
- else if ("+".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), repeatTag());
- else if ("+/".equals(head)) return Sequence.many1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("*/".equals(head)) return Sequence.many0((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("++/".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), (Element)walk(tree.child(1)), repeatTag());
- else if ("**".equals(head)) return Sequence.maximal0((Element)walk(tree.child(0)), repeatTag());
- else if ("++".equals(head)) return Sequence.maximal1((Element)walk(tree.child(0)), repeatTag());
- else if ("?".equals(head)) return Sequence.maybe((Element)walk(tree.child(0)), repeatTag());
- else if ("!".equals(head)) { Element e = (Element)walk(tree.child(0)); dropAll.add(e); return e; }
- else if ("&".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true));
- else if ("and".equals(head)) return ((Sequence)walk(tree,0)).and(sequence(walk(tree, 1), true));
- else if ("&~".equals(head)) return ((Sequence)walk(tree,0)).not(sequence(walk(tree, 1), true));
- else if ("epsilon".equals(head)) return Union.epsilon;
- else if ("()".equals(head)) return Union.epsilon;
- else if (")".equals(head)) return SELF;
- else if ("caret".equals(head) || "^".equals(head)) {
- String s = string(tree.child(0));
- Element ret = CharRange.string(s, false);
- carets.put(ret, s);
- dropAll.add(ret);
- return ret;
- /*
- } else if ("^^".equals(head)) {
- return new Keep(walk(tree,0));
- */
- } else if ("psx".equals(head)) return ((PreSequence)walk(tree, 0)).buildSequence();
- else if ("nonTerminal".equals(head)) return getNonTerminal(string(tree.child(0)));
- else if ("::=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false);
- else if ("=".equals(head)) return nonTerminal(string(tree.child(0)), (Sequence[][])Reflection.lub(walk(tree, 1)), false, false);
- else if ("(".equals(head)) return buildUnion((Sequence[][])Reflection.lub(walk(tree, 0)));
- else if ("literal".equals(head)) { Element ret = string(string(tree.child(0))); dropAll.add(ret); return ret; }
- else if ("-".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,1).toString().charAt(0));
- else if ("range".equals(head)) return new Range(walk(tree, 0).toString().charAt(0), walk(tree,0).toString().charAt(0));
- else if ("gram".equals(head)) return walk(tree, 0);
- else if ("psy".equals(head)) return (PreSequence)walk(tree, 0);
- else if ("->".equals(head)) { PreSequence p = (PreSequence)walk(tree, 0); p.follow = (Element)walk(tree, 1); return p; }
- else if ("/".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1));
- else if (" /".equals(head)) return ((PreSequence)walk(tree, 0)).sparse((Element)walk(tree, 1));
- else if ("~".equals(head)) return new Hack(new Invert(new Infer((Element)walk(tree, 0))));
- else if ("ps".equals(head)) return new PreSequence((Object[])walk(tree,0), null);
- else if (":".equals(head)) {
- String s = string(tree.child(0));
- return new Keep(s,walk(tree,1));
- } else if ("::".equals(head)) {
- PreSequence p = (PreSequence)walk(tree, 1);
- String s = string(tree.child(0));
- if (s.equals("[]")) p.unwrap = true;
- else p.tag = convertLabel(s);
- return p;
- }
- else if ("=>".equals(head)) {
- PreSequence p = (PreSequence)walk(tree, 0);
- p.tag = string(tree.child(1));
- return p;
- }
- else if ("[".equals(head)) {
- Range[] rr = (Range[])walk(tree, 0);
- Range.Set ret = new Range.Set();
- if (rr!=null) for(Range r : rr) ret.add(r);
- return set(ret);
- }
- else return super.walk(tree);
- }
-
- static class Keep {
- public final String label;
- public final Object o;
- public Keep(String label, Object o) { this.label = label; this.o = o; }
- }
-
- public Object convertLabel(String label) { return label; }
- public Object repeatTag() { return null; }
-
- public Object walk(String tag, Object[] argo) {
- if (argo.length==0) return super.walk(tag, argo);
- if (argo==null) return tag;
- if (tag==null || "".equals(tag)) return argo;
- return super.walk(tag, argo);
- }
-
- public Union buildUnion(Sequence[][] p) {
- return anonymousNonTerminal(p);
- }
-
- //////////////////////////////////////////////////////////////////////////////
-
- public class PreSequence {
- public Element follow = null;
- public final HashSet<Sequence> and = new HashSet<Sequence>();
- public final HashSet<Sequence> not = new HashSet<Sequence>();
- public /*final*/ Object tag;
- public final Object[] o;
-
- public PreSequence sparse(Object e) {
- Object[] ret;
- boolean[] drops;
- if (o.length <= 1) {
- ret = o;
- drops = new boolean[this.drops.length];
- System.arraycopy(this.drops, 0, drops, 0, this.drops.length);
- } else {
- ret = new Object[o.length * 2 - 1];
- drops = new boolean[o.length * 2 - 1];
- for(int i=0; i<o.length; i++) {
- Object oi = o[i];
- ret[i*2] = oi;
- drops[i*2] = this.drops[i];
- if (i*2+1<ret.length) {
- ret[i*2+1] = e;
- drops[i*2+1] = true;
- }
- }
- }
- PreSequence p = new PreSequence(ret, tag, drops);
- p.not.addAll(not);
- p.and.addAll(and);
- return p;
- }
-
- public PreSequence not(Sequence s) { not.add(s); return this; }
- public PreSequence and(Sequence s) { and.add(s); return this; }
-
- boolean[] drops = null;
- public PreSequence(Object o) { this(new Object[] { o }, null); }
- public PreSequence(Object[] o) { this(o, null); }
- public PreSequence(Object[] o, Object tag) { this(o, tag, null); }
- public PreSequence(Object[] o, Object tag, boolean[] drops) {
- this.o = o;
- this.tag = tag;
- this.drops = drops==null ? new boolean[o.length] : drops;
- }
-
- public Union buildUnion(String s) {
- Union u = new Union(s);
- u.add(buildSequence(u));
- return u;
- }
- public Union buildUnion() { return buildUnion("???"); }
- public boolean unwrap = false;
- public Sequence buildSequence() { return buildSequence(null, false, false); }
- public Sequence buildSequence(Union u) { return buildSequence(u, false, false); }
- public Sequence buildSequence(Union u, boolean lame, Object tag) {
- this.tag = tag;
- return buildSequence(u, lame, false);
- }
- public Sequence buildSequence(Union u, boolean lame, boolean dropAll) {
- if (tag!=null && tag.equals("[]")) unwrap = true;
- if (tag!=null && "()".equals(tag)) dropAll=true;
- if (u!=null) {
- for(Sequence s : and) u.add(s);
- for(Sequence s : not) u.add(s);
- }
- HashSet<Sequence> set = new HashSet<Sequence>();
- Element[] o2 = o==null ? new Element[0] : new Element[o.length];
- Object[] labels = new Object[drops.length];
- int nonDrop = 0;
- boolean keeping = false;
- if (o != null) {
- int j = 0;
- for(int i=0; i<o.length; i++) {
- Object oi = o[i];
- if (oi instanceof Keep) {
- if (!unwrap && tag==null) throw new Error("cannot have labels in an untagged sequence: " + ((Keep)oi).label);
- if (!keeping) { for(int k=0; k<i; k++) drops[k]=true; }
- drops[i] = false;
- keeping = true;
- labels[i] = ((Keep)oi).label;
- oi = ((Keep)oi).o;
- } else {
- if (keeping) drops[i] = true;
- }
- /*if (oi==SELF) o2[j] = u.new Subset("(("+u+"))", set);
- else*/ o2[j] = (Element)oi;
-
- if (MetaGrammar.dropAll.contains(o2[j])) drops[j] = true;
- nonDrop += drops[j] ? 0 : 1;
- o2[j] = o2[j];
- String s = carets.get(o2[j]);
- if (s!=null) { tag = s; if (o.length==1) drops[j] = false; }
- j++;
- }
- }
- Element[] expansion = o2;
- Sequence ret = null;
- if (dropAll || lame) ret = Sequence.drop(expansion, lame);
- else if (unwrap) ret = Sequence.unwrap(expansion, repeatTag(), drops);
- else if (keeping || tag!=null) ret = Sequence.rewritingSequence(tag, expansion, labels, drops);
- else {
- int idx = -1;
- for(int i=0; i<expansion.length; i++)
- if (!drops[i])
- if (idx==-1) idx = i;
- else throw new Error("multiple non-dropped elements in sequence: " + Sequence.drop(expansion,false));
- if (idx != -1) ret = Sequence.singleton(expansion, idx);
- else ret = Sequence.drop(expansion, false);
- }
- for(Sequence s : and) ret = ret.and(s);
- for(Sequence s : not) ret = ret.not(s);
- set.add(ret);
- if (this.follow != null) ret.follow = new Infer(this.follow);
- return ret;
- }
- }
-