// Package-Private //////////////////////////////////////////////////////////////////////////////
- static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
- boolean lift) {
- if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
- return new One<NodeType>(region, head, children, lift);
- }
-
- static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
- boolean lift, boolean liftLeft) {
+ public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children) {
+ return create(region, head, children, new boolean[children==null ? 0 : children.length]); }
+ public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children, boolean[] lifts) {
if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
- return new One<NodeType>(region, head, children, lift, liftLeft);
+ return new One<NodeType>(region, head, children, lifts);
}
- /** create a new forest */
- public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children) {
- return Forest.create(region, head, children, false); }
-
abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
abstract void gather(HashSet<Forest<NodeType>> ignore);
abstract void edges(GraphViz.Node n);
private final Forest<NodeType>[] children;
/** if true, the last child's children are considered children of this node */
- private final boolean lift;
- private final boolean liftLeft;
+ private final boolean[] lifts;
public Input.Region getRegion() { return location; }
- private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift) {
- this(loc, head, children, lift, false);
- }
- private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift, boolean liftLeft) {
+ private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean[] lifts) {
this.location = loc;
this.head = head;
if (head==null) throw new RuntimeException("invoked Forest.create(,null,,,) -- this should never happen");
this.children = children==null ? emptyForestArray : new Forest[children.length];
if (children != null) System.arraycopy(children, 0, this.children, 0, children.length);
if (children != null) for(int i=0; i<children.length; i++) if (children[i]==null) throw new Error(i+"");
- this.lift = lift;
- this.liftLeft = liftLeft;
+ this.lifts = lifts;
}
public Tree<NodeType> expand1() throws Ambiguous {
Tree<NodeType>[] ret = new Tree[children.length];
for(int i=0; i<children.length; i++) ret[i] = children[i].expand1();
- return new Tree<NodeType>(location, head, ret, lift, liftLeft);
+ return new Tree<NodeType>(location, head, ret, lifts);
}
void gather(HashSet<Forest<NodeType>> hf) {
private void expand(final int i, Tree<NodeType>[] ta, HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore,
Tree<NodeType> bogus) {
if (i==children.length) {
- ht.add(new Tree<NodeType>(location, head, ta, lift, liftLeft));
+ ht.add(new Tree<NodeType>(location, head, ta, lifts));
} else {
HashSet<Tree<NodeType>> ht2 = new HashSet<Tree<NodeType>>();
children[i].expand(ht2, ignore, bogus);
if (edges) return;
edges = true;
for(int i=0; i<children.length; i++) {
- if (i==children.length-1 && lift && !children[i].ambiguous()) {
+ if (lifts[i] && !children[i].ambiguous()) {
children[i].edges(n);
} else {
n.edge(children[i], null);
public static Sequence create(Element e) { return create(new Element[] { e }, 0); }
/** create a sequence which drops the result of all but one of its element */
- public static Sequence create(Element[] e, int which) { return new Singleton(e, which); }
+ public static Sequence create(Element[] e, int which) {
+ return new Singleton(e, which); }
/** create a sequence which always evaluates to a constant result */
- public static Sequence create(Element[] e, Object result) { return new Constant(e, result); }
+ public static Sequence create(Object result, Element[] e) {
+ return new RewritingSequence(result, e, trues(e.length)); }
+
+ private static boolean[] trues(int length) {
+ boolean[] ret = new boolean[length];
+ for(int i=0; i<ret.length; i++) ret[i] = true;
+ return ret;
+ }
/**
* create a sequence (general form)
* @param e the elements to match
* @param drop only elements of <tt>e</tt> whose corresponding <tt>boolean</tt> in <tt>drops</tt>
* is <i>false</i> will be included in the output tree
- * @param foster if true, all children of the last child (ie
- * grandchildren) are promoted to children of this
- * node; this is very useful for matching repetitions
+ * @param lifts which (if any) child trees to lift
**/
- public static Sequence create(Object head, Element[] e, boolean[] drop, boolean foster) {
- return foster
- ? new Unwrap(e, head, drop)
- : new RewritingSequence(head, e, drop);
- }
- public static Sequence createLeft(Object head, Element[] e, boolean[] drop, boolean foster) {
- return foster
- ? new UnwrapLeft(e, head, drop)
- : new RewritingSequence(head, e, drop);
+ public static Sequence create(Object head, Element[] e, boolean[] drop) {
+ return create(head, e, drop, new boolean[e.length]); }
+ public static Sequence create(Object head, Element[] e, boolean[] drop, boolean[] lifts) {
+ if (lifts==null) lifts = new boolean[e.length];
+ return new RewritingSequence(head, e, drop, lifts);
}
/** return a new sequence identical to this one, but with a positive conjunct <tt>s</tt> */
}
}
- static class Unwrap extends Sequence {
- private boolean[] drops;
- private final Object tag;
- public Unwrap(Element[] e, Object tag) { this(e, tag, null); }
- public Unwrap(Element[] e, Object tag, boolean[] drops) { super(e); this.drops = drops; this.tag = tag; }
- Sequence _clone() { return new Unwrap(elements, tag, drops); }
- public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
- for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
- if (drops==null) return Forest.create(loc, (T)tag, args, true);
- int count = 0;
- for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
- Forest<T>[] args2 = new Forest[count];
- int j = 0;
- for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
- return Forest.create(loc, (T)tag, args2, true);
- }
- Forest epsilonForm(Input.Region loc, Grammar cache) {
- return Forest.create(loc, tag, new Forest[0], false);
- }
- }
-
- static class UnwrapLeft extends Sequence {
- private boolean[] drops;
- private final Object tag;
- public UnwrapLeft(Element[] e, Object tag) { this(e, tag, null); }
- public UnwrapLeft(Element[] e, Object tag, boolean[] drops) { super(e); this.drops = drops; this.tag = tag; }
- Sequence _clone() { return new UnwrapLeft(elements, tag, drops); }
- public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
- for(int i=0; i<args.length; i++) if (args[i]==null) throw new Error();
- if (drops==null) return Forest.create(loc, (T)tag, args, false, true);
- int count = 0;
- for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
- Forest<T>[] args2 = new Forest[count];
- int j = 0;
- for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
- return Forest.create(loc, (T)tag, args2, false, true);
- }
- Forest epsilonForm(Input.Region loc, Grammar cache) {
- return Forest.create(loc, tag, new Forest[0], false);
- }
- }
-
static class RewritingSequence extends Sequence {
private Object tag;
private final boolean[] drops;
- private int count = 0;
+ private final boolean[] lifts;
Sequence _clone() { return new RewritingSequence(tag, elements, drops); }
public RewritingSequence(Object tag, Element[] e) { this(tag, e, null); }
- public RewritingSequence(Object tag, Element[] e, boolean[] drops) {
+ public RewritingSequence(Object tag, Element[] e, boolean[] drops) { this(tag, e, drops, new boolean[e.length]); }
+ public RewritingSequence(Object tag, Element[] e, boolean[] drops, boolean[] lifts) {
super(e);
if (tag==null) throw new Error();
this.tag = tag;
this.drops = drops == null ? new boolean[e.length] : drops;
+ int count = 0;
for(int i=0; i<this.drops.length; i++) if (!this.drops[i]) count++;
+ this.lifts = new boolean[count];
+ int j = 0;
+ for(int i=0; i<this.drops.length; i++)
+ if (!this.drops[i])
+ this.lifts[j++] = lifts[i];
}
public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
- Forest<T>[] args2 = new Forest[count];
+ Forest<T>[] args2 = new Forest[lifts.length];
int j = 0;
for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
- return Forest.create(loc, (T)tag, args2, false);
+ return Forest.create(loc, (T)tag, args2, lifts);
}
public StringBuffer toString(StringBuffer sb, boolean spacing) {
int len = sb.length();
return sb;
}
Forest epsilonForm(Input.Region loc, Grammar cache) {
- return Forest.create(loc, tag, new Forest[0], false);
+ return Forest.create(loc, tag, new Forest[0], lifts);
}
}
-
}
/** get the input region that this tree was parsed from */
public Input.Region getRegion() { return location; }
- public Tree(Input.Region loc, NodeType head) { this(loc, head, null); }
- public Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children) { this(loc, head, children, false); }
+ public Tree(Input.Region loc, NodeType head) { this(loc, head, new Tree[0]); }
+ public Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children) { this(loc, head, children, new boolean[children==null?0:children.length]); }
// FIXME: fairly inefficient because we keep copying arrays
/** package-private constructor, allows setting the "lift" bit */
- Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean lift) {
- this(loc, head, children, lift, false);
- }
- Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean lift, boolean liftLeft) {
+ Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean[] lifts) {
this.location = loc;
this.ihead = head;
- // FIXME: lift+liftLeft togheter
- if (liftLeft && children != null && children.length > 0) {
- Tree<NodeType> last = children[0];
- this.children = new Tree[(children.length-1)+last.children.length];
- System.arraycopy(children, 1, this.children, last.children.length, children.length-1);
- if (last.children.length > 0)
- System.arraycopy(last.children, 0, this.children, 0, last.children.length);
- } else if (lift && children != null && children.length > 0) {
- Tree<NodeType> last = children[children.length-1];
- this.children = new Tree[(children.length-1)+last.children.length];
- System.arraycopy(children, 0, this.children, 0, children.length-1);
- if (last.children.length > 0)
- System.arraycopy(last.children, 0, this.children, children.length-1, last.children.length);
- } else {
- this.children = ArrayUtil.clone(children, Tree.class);
+
+ int count = 0;
+ for(int i=0; i<children.length; i++)
+ count += lifts[i] ? children[i].size() : 1;
+
+ this.children = new Tree[count];
+ int j = 0;
+ for(int i=0; i<children.length; i++) {
+ if (!lifts[i])
+ this.children[j++] = children[i];
+ else
+ for(int k=0; k<children[i].size(); k++)
+ this.children[j++] = children[i].child(k);
}
}
public String toString() { return escapified; } };
Element[] refs = new Element[s.length()];
for(int i=0; i<refs.length; i++) refs[i] = new CharAtom(s.charAt(i));
- ret2.add(Sequence.create(refs, s));
+ ret2.add(Sequence.create(s, refs));
ret = ret2;
}
return ret;
private static Union emptyString = new Union("()");
static {
// FIXME: force this to be dropped wherever used!
- emptyString.add(Sequence.create(new Element[0], ""));
+ emptyString.add(Sequence.create("", new Element[0]));
}
public Topology<Atom<Character>> unwrap() { return this; }
if (head.equals("Word")) return stringifyChildren(t);
if (head.equals("Elements")) return seq2((ElementNode[])Reflection.rebuild(walkChildren(t), ElementNode[].class));
if (head.equals("NonTerminalReference")) return new ReferenceNode(stringifyChildren(t.child(0)));
- //if (head.equals(")")) return new ReferenceNode(stringifyChildren(t.child(0)));
- if (head.equals("{")) return new XTree((Seq)walk(t.child(0)));
- if (head.equals("::")) return tag((String)walk(t.child(0)), (Seq)walk(t.child(1)));
- if (head.equals("++")) return plusmax((ElementNode)walk(t.child(0)));
- if (head.equals("...")) return star(new TildeNode(new AtomNode()));
- if (head.equals("+")) return plus((ElementNode)walk(t.child(0)));
- if (head.equals("++/")) return plusmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
- if (head.equals("+/")) return plusfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
- if (head.equals("**")) return starmax((ElementNode)walk(t.child(0)));
- if (head.equals("*")) return star((ElementNode)walk(t.child(0)));
- if (head.equals("**/")) return starmaxfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
- if (head.equals("*/")) return starfollow((ElementNode)walk(t.child(0)), (ElementNode)walk(t.child(1)));
- if (head.equals("?")) return question((ElementNode)walk(t.child(0)));
- if (head.equals("!")) return new DropNode((ElementNode)walk(t.child(0)));
- if (head.equals("^")) return new LiteralNode((String)walk(t.child(0)), true);
- if (head.equals("`")) {
- ElementNode ret = (ElementNode)walk(t.child(0));
- ret.lifted = true;
- return ret;
- }
+ if (head.equals(")")) return new ReferenceNode(stringifyChildren(t.child(0)), true);
+ if (head.equals("{")) return new BracedNode(walkSeq(t.child(0)));
+ if (head.equals("::")) return walkSeq(t.child(1)).tag(walkString(t.child(0)));
+ if (head.equals("...")) return new DropNode(new RepeatNode(new TildeNode(new AtomNode()), null, true, true, false));
+
+ if (head.equals("++")) return new RepeatNode(walkElement(t.child(0)), null, false, true, true);
+ if (head.equals("+")) return new RepeatNode(walkElement(t.child(0)), null, false, true, false);
+ if (head.equals("++/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)), false, true, true);
+ if (head.equals("+/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)), false, true, false);
+ if (head.equals("**")) return new RepeatNode(walkElement(t.child(0)), null, true, true, true);
+ if (head.equals("*")) return new RepeatNode(walkElement(t.child(0)), null, true, true, false);
+ if (head.equals("**/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)), true, true, true);
+ if (head.equals("*/")) return new RepeatNode(walkElement(t.child(0)), walkElement(t.child(1)), true, true, false);
+ if (head.equals("?")) return new RepeatNode(walkElement(t.child(0)), null, true, false, false);
+
+ if (head.equals("!")) return new DropNode(walkElement(t.child(0)));
+ if (head.equals("^")) return new LiteralNode(walkString(t.child(0)), true);
+ if (head.equals("`")) return walkElement(t.child(0)).lifted();
if (head.equals("Quoted")) return stringifyChildren(t);
if (head.equals("Literal")) return new LiteralNode(walkString(t.child(0)));
if (head.equals("->")) return walkSeq(t.child(0)).follow(walkElement(t.child(1)));
public Union build(String rootNonterminal) {
Context cx = new Context(this);
Union u = null;
- for(GrammarBuilder.NonTerminalNode nt : values())
+ for(GrammarAST.NonTerminalNode nt : values())
if (nt.name.equals(rootNonterminal))
return (Union)cx.get(nt.name);
return null;
els[i] = elements[i].build(cx, cnt, dropall);
}
if (tag==null && multiNonDrop)
- throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create(els, ""));
- boolean lift = false;
- if (elements.length > 0 && elements[0].lifted)
- lift = true;
+ throw new RuntimeException("multiple non-dropped elements in sequence: " + Sequence.create("", els));
+ boolean[] lifts = new boolean[elements.length];
+ for(int i=0; i<elements.length; i++)
+ lifts[i] = elements[i].lifted;
if (!multiNonDrop) {
if (idx == -1)
ret = tag==null
- ? Sequence.create(els, illegalTag)
- : Sequence.createLeft(tag, els, drops, lift);
+ ? Sequence.create(illegalTag, els)
+ : Sequence.create(tag, els, drops, lifts);
else if (tag==null) ret = Sequence.create(els, idx);
- else ret = Sequence.createLeft(tag, els, drops, lift);
+ else ret = Sequence.create(tag, els, drops, lifts);
}
if (multiNonDrop)
- ret = Sequence.createLeft(tag, els, drops, lift);
+ ret = Sequence.create(tag, els, drops, lifts);
if (this.follow != null)
ret = ret.followedBy(this.follow.toAtom(cx));
return ret;
Element[] mult = new Element[] { expr, atom('*'), expr };
Element[] paren = new Element[] { atom('('), expr, atom(')') };
- Sequence addSequence = Sequence.create("add", add, null, false);
- Sequence multSequence = Sequence.create("mult", mult, null, false);
+ Sequence addSequence = Sequence.create("add", add, null);
+ Sequence multSequence = Sequence.create("mult", mult, null);
// uncomment this line to disambiguate
//multSequence = multSequence.andnot(Sequence.create("add", add, null, false));
projects / sbp.git / commitdiff