From: adam Date: Mon, 12 Dec 2005 07:23:16 +0000 (-0500) Subject: initial import X-Git-Tag: tag_for_25-Mar~618 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=0a0227b9180534d2a431f3d6e08a398bde2244c4 initial import darcs-hash:20051212072316-5007d-b2da724d7a4090bc581c289fdec49c2a295abbdc.gz --- 0a0227b9180534d2a431f3d6e08a398bde2244c4 diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..acf93e9 --- /dev/null +++ b/LICENSE @@ -0,0 +1,24 @@ +* Copyright (c) 2005, Regents of the University of California +* All rights reserved. +* Redistribution and use in source and binary forms, with or without +* modification, are permitted provided that the following conditions are met: +* +* * Redistributions of source code must retain the above copyright +* notice, this list of conditions and the following disclaimer. +* * Redistributions in binary form must reproduce the above copyright +* notice, this list of conditions and the following disclaimer in the +* documentation and/or other materials provided with the distribution. +* * Neither the name of the University of California, Berkeley nor the +* names of its contributors may be used to endorse or promote products +* derived from this software without specific prior written permission. +* +* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND ANY +* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +* DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY +* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES +* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND +* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..40ad504 --- /dev/null +++ b/Makefile @@ -0,0 +1,48 @@ + +java = java + +regress: + make boot + rm edu.berkeley.sbp.jar + make test + +profile: edu.berkeley.sbp.jar + $(java) -agentlib:yjpagent \ + -cp $< edu.berkeley.sbp.misc.RegressionTests \ + -profile \ + tests/meta.g \ + tests/testcase.g \ + tests/regression.tc + +test: edu.berkeley.sbp.jar + $(java) -cp $< edu.berkeley.sbp.misc.RegressionTests \ + tests/meta.g \ + tests/testcase.g \ + tests/regression.tc + +boot: edu.berkeley.sbp.jar + cd src; \ + $(java) -cp ../$< \ + edu.berkeley.sbp.misc.MetaGrammar \ + ../tests/meta.g \ + edu.berkeley.sbp.misc.MetaGrammar + +edu.berkeley.sbp.jar: $(shell find src -name \*.java) + mkdir -p bin + javac -d bin -sourcepath src $^ + cd bin; jar cf ../$@ . + +javadoc: + rm -rf doc/api + mkdir -p doc/api + javadoc -sourcepath src -public -d doc/api `find src -name \*.java` + +clean: + rm -rf doc/api edu.berkeley.sbp.jar bin edu.berkeley.sbp.tar.gz + +upload: + make clean + make javadoc + darcs dist + echo '' > index.html + rsync -are ssh --progress --verbose --delete ./ argus.cs.berkeley.edu:public_html/sbp/ diff --git a/README b/README new file mode 100644 index 0000000..fd7dd4c --- /dev/null +++ b/README @@ -0,0 +1,78 @@ +============================================================================== +Scannerless Boolean Parser + +Adam Megacz +12-Dec-2005 + +______________________________________________________________________________ +Requirements + + Java 1.5.0 + + The core grammar structures will always require generics (and thus + Java 1.5 to compile and probably at least that version in order to + run, although there are some hacks out there that might make it + possible to execute the compiled bytecode on Java 1.2+). + + Being able to run a "precompiled" parser for a fixed grammar on any + jdk1.1+ JVM is a very high priority for the near future. + + +______________________________________________________________________________ +Makefile targets + + make edu.berkeley.sbp.jar -- compile the code + make test -- run regression tests + make javadoc -- generate javadoc in doc/api/ + make boot -- bootstrap the metagrammar by compiling tests/meta.g + into src/edu/berkeley/sbp/misc/MetaGrammar.java + +______________________________________________________________________________ +Browsing the code + + Rule #1: the JavaDoc is your friend + Rule #2: the JavaDoc IS YOUR FRIEND + + I've put substantially more effort into the public methods and their + corresponding javadoc comments than anything else. The generated + javadoc is by far your best bet at getting up to speed quickly. + Specifically, read the "long form" package comment for + edu.berkeley.sbp, which gets placed at the bottom of this: + + doc/api/edu/berkeley/sbp/package-summary.html + + README -- this file + TODO -- stuff to do in the future + src/ + edu/ + berkeley/ + sbp/ -- core API: grammar, trees, and forests + misc -- regression testing and sample code + util -- some nifty data structures not specific to parsing + tib -- Text with Indentation and Braces (experimental/undocumented) + doc/ + api/ -- generated javadocs go here + tests/ + meta.g -- the tentative metagrammar, written in itself + testcase.g -- the grammar for testcases (extends meta.g) + regression.tc -- some test cases (formatted according to testcase.g) + + +______________________________________________________________________________ +Using the code + + The public methods in edu.berkeley.sbp.* are considered very stable; + they are highly unlikely to change in future releases. Everything + else should be considered at-your-own-risk, especially non-public + (ie package/private/protected methods). + + Currently I would not recommend extending any of the subclasses of + Element. + + What I call the "tentative metagrammar" (meta.g) is definately going + to change at least somewhat in the near future, although I doubt it + would be anything drastic enough to require more than a few minutes + to update a grammar description. + + The TIB stuff is super experimental; I'm not even sure if I'll keep + it around. Use at your own risk. diff --git a/TODO b/TODO new file mode 100644 index 0000000..4931457 --- /dev/null +++ b/TODO @@ -0,0 +1,110 @@ + +______________________________________________________________________________ +pre-1.0 + + - Javadoc comments + + - switch maximal to not-followed-by (~/~) + + - should Union.add() be there? + - should Atom.top() be there? + + - fix the location stuff, it's broken + - decent/better error messages + + - finalize metagrammar + - Java grammar + - TeX (math?) + - URL (RFC) + - RFC2822 (email message/headers) + + - WIKI!!! TEX!!! + +______________________________________________________________________________ +Undecided + + - public API for hates/needs + + - clean up the whole Walk situation + - cleaner solution to "maximal"? + - "lift" cases: + - right now I can only lift the last child in a forest... begs + the question of what the right representation for Forests is + if we need to be able to do lift operations on it. + + +______________________________________________________________________________ +post-1.0 + + - Implement a k-token peek buffer (for each state, see if it "dead + ends" during the next k Phases based solely on state -- ignoring + result SPPF) + + - Arrange for the SPPF corresponding to dropped subtrees to never be + generated (or merged, etc) + + - Is there any way we can avoid creating a GSS.Node instance for + nodes which are transient in the sense that they have only one + eligible reduction? + + - Implement "GLR syntactic predicates" -- the ability to do + arbitrary lookahead (ie "followed-by" and "not-followed-by" for + arbitrary patterns). This enables generalized longest-match and + lets us drop the Maximal hack. + + - Re-read Rekers, particularly the stuff on optimal sharing + + - Isolate the Element objects from Parse.Table/GSS so we can move + towards compilation. + + - consider allowing a Forest.Body to represent some other Tree whose + Body's should be [recursively] considered part of this Forest. + + - perhaps not: right now we have a nice situation where + Forest.Ref instances become immutable once iterator()ed. This + also gives us a strong place to to culling with the certainty + that we won't throw out a Body which would later be salvaged + by some yet-to-be-added dependency. + + - Figure out if there is a way to: + + - allow unwrapping of children other than the very last one. + + - fold repetitions into an array form in Forest, before + conversion to Tree. The major problem here is that multiple + tree-arrays are possible, all of different lengths. Worse, + even if they're all the same length, not all elements belong + in the same "possibility vector" as all others. You + essentially need a GSS to represent the array, which perhaps + is what the unfolded form was in the first place. + + - Wikipedia grammar (needs to be both lexerless and boolean) + + - Boolean Parsing + => Ordered Choice (";" operator) + + - bring back in parse-table phase resolution of precedence (just + like associativity). This can be inferred from the use of ">" + when the rules are in one of these special forms: + + E ::= E _ + > _ E + + E ::= _ E + > E _ E + + E ::= E _ E + > E _ E + + where "_" is anything and "E" is the defining nonterminal. + Essentially what we're looking for is the situation where the + leftmost portion of one rule produces another rule, and the + rightmost portion of the latter produces the former. + + I'm not 100% certain that this is as "strong" as the prefer/avoid + form (try to prove this, you probably can), but it's "what people + intend" most of the time. + + - implement Johnstone's algorithm for "reduced, resolved LR + tables" to eliminate superfluous reductions on + epsilon-transitions. diff --git a/doc/jargon.txt b/doc/jargon.txt new file mode 100644 index 0000000..c622090 --- /dev/null +++ b/doc/jargon.txt @@ -0,0 +1,112 @@ +______________________________________________________________________________ +Definitions + + Token -- an indivisible datum. Most things in SBP are parameterized + over a token type. + + Tree -- a tree of Tokens; each node consists of a Token (called the + node's "head") and zero or more children (which are in + turn Trees). To use a Haskell-like notation, + + data Tree a = Tree a [Tree] + + Note that (1) this is not the algebraic type most + commonly used for trees and (2) this model of trees is + not simply specific to the data structures used to + implement SBP -- the parser assumes that everything it + deals with is a Token, Tree, or Forest (see below). + + Forest -- a set of trees. There is an implicit assumption here that + a Forest can be represented efficiently when its + constituent trees share supertrees and subtrees. + + SBP does not yet commit to a specific model of Forests, + and the API exposes little more than the ability to expand + a Forest into a set of Trees. This may change. + + One key issue to resolve is how to efficiently represent + trees with a huge number of children where only a subset + of these children are shared (this effectively requires a + Tomita-style SPPF just for the child-list). Currently + this issue is sidestepped by the fact that the "raw" parse + forest will never have a tree of arity greater than the + longest production rule (and therefore not unreasonably + long); the "unfolding" transformation used to create + arrays out of EBNF-repetition productions takes place + during the Forest-to-TreeSet expansion. Clearly this is + not an ideal long-term solution. + + Element -- a pattern which: + + 1. matches a sequence of zero or more Trees + 2. uses the matched Trees to create a sequence of output Forests + + The restriction that the result of an Element can only be + zero or one Trees (rather than zero or more) is one which + we hope to lift soon. + + Atom -- an Element which matches exactly one Token. An Atom is + effectively a (possibly infinite) set of Tokens; matching + is a membership-test. + + Sequence -- an Element which matches the juxtaposition of zero or + more sub-Elements, and which creates its output Tree by + composing the output Trees of those sub-Elements. + + Position -- within a specific Sequence, a Position is the + imaginary space before or after one of the elements + (ie at the beginning of the sequence, at the end, or + between two elements). Positions correspond exactly + to the automata-theoretic notion of an LR "item", but + "item" is such a horribly chosen and vague name that + I just couldn't bring myself to perpetuate it. Note + that Positions and Locations have no relationship to + each other. + + Union -- an Element which matches exactly one of a set of one or + more sub-Elements; its output forest is union + + Location -- a specific location in the input tree. This notion + still needs to be formalized; for example, not all + nodes in the output Forest have a sensible notion of + Location. + + +______________________________________________________________________________ +Tree Notation + +The following notation is used for Tree (Trees of Strings); it +can be generalized to Tree where X maps onto Strings (ie +Tree, etc). + + Tree ::= Head // equivalent to Head:{} + | "{" Body "}" // equivalent to "":{} + | Head ":" "{" Body "}" + | Head ":" (Tree) // ":" is right-associative + + Head ::= "\"\"" // the empty string + | "\"" [~\"]+ "\"" // Strings containing spaces, braces, quotes, or colons + | [~\":{}\r\n\ ]+ // non-empty strings of "normal" characters + + Body ::= Tree */ (" "+) // zero or more Trees separated by whitespace + +Example: + + a:{b {e f:g:h} g} + + "a" + / | \ + "b" "" "g" + | + "f" + | + "g" + | + "h" + +______________________________________________________________________________ +Forest Notation + +This has not yet been finalized + + diff --git a/doc/osq.lunch.talk.pdf b/doc/osq.lunch.talk.pdf new file mode 100644 index 0000000..31ca8d2 Binary files /dev/null and b/doc/osq.lunch.talk.pdf differ diff --git a/doc/preprint.pdf b/doc/preprint.pdf new file mode 100644 index 0000000..6600afd Binary files /dev/null and b/doc/preprint.pdf differ diff --git a/doc/sbp.html b/doc/sbp.html new file mode 100644 index 0000000..fe6ac8f --- /dev/null +++ b/doc/sbp.html @@ -0,0 +1,242 @@ + +The Scannerless Boolean Parser (SBP) + + + +
+ +
+ +SBP: the Scannerless Boolean Parser +
+ +

What is it?

+ +The Scannerless Boolean Parser (SBP) is a scannerless parser for boolean +grammars (a superset of context-free grammars). It is written in +Java and emits Java source code. + +

What is interesting about it?

+ +SBP deliberately sacrifices performance in favor of ease of extensibility. +

+ +Since it is an implementation of the (modified) Lang-Tomita +GLR algorithm, SBP supports all context-free languages. +

+ +It is scannerless +(does not require a lexer). This allows it to easily handle languages +which have non-regular lexical structure or lack a clear lexer-parser +distinction, such as TeX, XML, RFC1738 (URLs), ASN.1, SMTP headers, +and Wiki markup. +

+ +In addition to the juxtaposition and union operators provided in +context-free languages, JTP supports grammars which use the +intersection operator (conjunctive +grammars) and the complement operator (boolean +grammars). + +

What features does it have?

+ +Features fully implemented are in green; +those partially implemented are in orange; +those unimplemented (but planned) are in red. + +
  • An implementation of the Lang-Tomita GLR parsing algorithm +
      +
    • Including Johnstone & Scott's RNGLR algorithm for epsilon-productions + +
    • Visser's extensions + for scannerless parsing +
      • Follow, Avoid, Prefer, Reject constraints +
      • Character ranges +
      • Automatic insertion of whitespace/comments +
      + +
    • Any topological space can be + used as an alphabet (need not be discrete) +
      • Unicode +
      • Trees +
      + +
    • Associativity constraints on n-ary operators + +
    + +
  • Ability to parse a wide variety of grammars in + O(n3) time: + +
      +
    • all context-free grammars + +
    • epsilon productions, included in the parse forest + +
    • circularities, included in the parse forest. + +
    • Regular expression operators ( + *, + ?, + + + ) + +
    • conjunctive grammars + (intersection operator) + +
    • boolean grammars (intersection, intersect-with-complement, and + generalized-complement) +
    + + +
  • Facilitates experimenting with grammars + +
      +
    • Interpreted mode, in which the + parse table is interpreted directly, eliminating the + need for a compiler and making it easier for grammars + to operate on grammars. + +
    • Simple + API + makes it easy to generate, analyze, and modify grammars + programmatically. + +
        +
      • Components of a grammar (nonterminals, + productions, etc) represented as objects +
      • composite elements implement Iterable<T> +
      + +
    • Compiled mode, in which Java + source code is emitted; compiling this code yields a + parser. The resulting parser is much faster. +
    + + +
+ +

What is it deliberately missing?

+ +
  • Semantic actions; the only option is to return a parse forest. +
      +
    • This keeps the grammar specification language-neutral. +
    • A grammar can, however, indicate that certain parts of the parse tree should be dropped. +
    +
+ +

What features would be nice to have?

+ +
    +
  • Drop Farshi's algorithm and use GRMLR. + Done! + +
  • An implementation of the McPeak-Necula + optimization for bounded-depth determinism. + +
  • Lazy parse trees, to decrease the space requirements from + o(n) to o(1) [but still O(n)]. + +
  • Consider implementing + Aycock-Horspool unrolling. Improves performance with + only highly localized increase in algorithmic complexity. + Subsumes many other optimizations. + +
+ +

What are the long term goals?

+ +As we come to a more mature understanding of the pragmatic aspects of +boolean grammars, a long-term goal is to migrate support for these +features to existing high-performance GLR implementations (Elkhound, bison-glr). + +

Where can I read more about it?

+ +
  • The README file is the best place to start +
  • After that, be sure to read jargon.txt +
  • The javadoc + is the best description of the API +
  • There's a tentative metagrammar, + written in itself. +
  • You can also get slides + from my talk at the OSQ Lunch on 02-Nov-2005, though some of + the stuff (specifically what SBP can and cannot do) is + outdated. +
  • A preprint of one of my conference + submissions. +
+ +

Where can I get it?

+ +The color coding above accurately reflects the state of the +implementation (11-Dec-2005). However, in its current state it is a +bit messy, and may require a bit of fiddling to get it to do what you +want. This situation should improve in the next few weeks as I am +done adding features (for now) and am currently focusing on +reliability, cleanliness, and performance. +

+ +SBP is available under the BSD license. +

+ +You can download a snapshot (11-Dec-2005) here. The parser-generator +requires Java 1.5 or later; the Java code it emits should run on any Java 1.1+ JVM. After unpacking +the archive, simply type make to compile SBP and run the +regression tests. + +

+ + \ No newline at end of file diff --git a/index.html b/index.html new file mode 100644 index 0000000..36be89b --- /dev/null +++ b/index.html @@ -0,0 +1 @@ + diff --git a/src/edu/berkeley/sbp/Atom.java b/src/edu/berkeley/sbp/Atom.java new file mode 100644 index 0000000..0722d0b --- /dev/null +++ b/src/edu/berkeley/sbp/Atom.java @@ -0,0 +1,30 @@ +package edu.berkeley.sbp; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; + +/** an element which matches exactly one input token */ +public abstract class Atom extends Element { + + private final Topology rt; + + public Atom(Topology rt) { this.rt = rt; } + + Topology top() { return rt; } + + void reachable(HashSet h) { /* do-nothing */ } + + /** equality is based on the underlying Topology */ + public int hashCode() { return rt.hashCode(); } + + /** equality is based on the underlying Topology */ + public boolean equals(Object o) { return o != null && o instanceof Atom && ((Atom)o).rt.equals(rt); } + + /** declared abstract to force subclasses to override it in a useful manner */ + public abstract String toString(); +} + diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java new file mode 100644 index 0000000..b199a23 --- /dev/null +++ b/src/edu/berkeley/sbp/Element.java @@ -0,0 +1,24 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +/** the root superclass for all components of the grammar (terminals, nonterminals, literals, etc) */ +public abstract class Element { + + /** add all positions reachable from the start of this Element to @rp */ + abstract void reachable(HashSet rp); + + Forest epsilonForm() { throw new Error("no epsilon form: " + this); } + final boolean possiblyEpsilon(Walk.Cache cache) { + Boolean ret = cache==null ? null : cache.possiblyEpsilon.get(this); + if (ret != null) return ret.booleanValue(); + ret = new Walk.PossiblyEpsilon().walk(this) ? Boolean.TRUE : Boolean.FALSE; + if (cache != null) cache.possiblyEpsilon.put(this, ret); + return ret; + } +} diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java new file mode 100644 index 0000000..13ac199 --- /dev/null +++ b/src/edu/berkeley/sbp/Forest.java @@ -0,0 +1,217 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +/** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */ +public abstract class Forest { + + /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */ + public final Tree expand1() throws Parser.Ambiguous, Parser.Failed { + Iterator> it = expand(true).iterator(); + if (!it.hasNext()) throw new Parser.Failed(); + return it.next(); + } + + /** expand this forest into a set of trees */ + public abstract HashSet> expand(boolean toss); + + abstract boolean valid(); + + static Forest singleton(Token.Location loc, Sequence creator) { return create(loc, null, new Forest[] { }, creator, false, true); } + static Forest singleton(Token.Location loc, Forest body, Sequence creator) { return create(loc, null, new Forest[] { body }, creator, false, true); } + static Forest leaf(Token.Location loc, T tag, Sequence creator) { return create(loc, tag, null, creator, false, false); } + static Forest create(Token.Location loc, T tag, Forest[] tokens, Sequence creator, boolean unwrap, boolean singleton) { + return new MultiForest(loc, tag, tokens, creator, unwrap, singleton); + } + + // Body ////////////////////////////////////////////////////////////////////////////// + + protected static class Body { + + private final Token.Location location; + private final T tag; + private final Forest[] tokens; + private final Sequence creator; + private final boolean unwrap; + private final boolean singleton; + + private Body(Token.Location loc, T tag, Forest[] tokens, Sequence creator, boolean unwrap, boolean singleton) { + this.location = loc; + this.tag = tag; + this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length]; + if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length); + this.creator = creator; + this.unwrap = unwrap; + this.singleton = singleton; + } + + private HashSet> expand(boolean toss, ArrayList> toks, int i, HashSet> h) { + if (singleton) { + for(Body b : (IterableForest)tokens[0]) b.expand(toss, toks, i, h); + + } else if (i==tokens.length) { + h.add(new Tree(null, tag, toks.toArray(tree_hint))); + + } else if (unwrap && i==tokens.length-1) { + if (tokens[i] != null) + for(Body b : (IterableForest)tokens[i]) + b.expand(toss, toks, 0, h); + + } else { + if (tokens[i]!=null) { + HashSet> exp = tokens[i].expand(toss); + if (exp != null) + for(Tree r : exp) { + int old = toks.size(); + toks.add(r); + expand(toss, toks, i+1, h); + while(toks.size() > old) toks.remove(toks.size()-1); + } + } + } + return h; + } + void addTo(HashSet h) { + if (!singleton) h.add(this); + else for(Body b : (IterableForest)tokens[0]) b.addTo(h); + } + void addTo(FastSet h) { + if (!singleton) h.add(this, true); + else for(Body b : (IterableForest)tokens[0]) b.addTo(h); + } + + private boolean kcache = false; + private boolean keep = false; + public boolean keep() { + if (kcache) return keep; + kcache = true; + for(Forest token : tokens) if (!token.valid()) return keep = false; + return keep = creator==null || (creator.needs.size()==0 && creator.hates.size()==0); + } + public boolean keep(Iterable> h) { + if (keep()) return true; + for(Forest token : tokens) if (!token.valid()) return false; + int needs = 0; + for(Body b : h) { + if (creator.hates.contains(b.creator) && b.keep(h)) return false; + if (creator.needs.contains(b.creator) && b.keep(h)) needs--; + } + return needs <= -1 * creator.needs.size(); + } + + + public String toString() { + StringBuffer ret = new StringBuffer(); + for(int i=0; i 0) { + ret.append(q); + ret.append(" "); + } + } + String tail = ret.toString().trim(); + String head = (tag!=null && !tag.toString().equals("")) ? (tail.length() > 0 ? tag+":" : tag+"") : ""; + if (tail.length() > 0) tail = "{" + tail + "}"; + return head + tail; + } + } + + + // Ref ////////////////////////////////////////////////////////////////////////////// + + static abstract class IterableForest extends Forest implements Iterable> { + public abstract Iterator> iterator(); + } + + /** + * This class represents a partially complete collection of + * forests to be viewed as a forest at some later date; once + * viewed, it becomes immutable + */ + static class Ref extends IterableForest { + private FastSet hp = new FastSet(); + private Forest res = null; + public boolean valid = false; + public Ref() { } + public void merge(Forest p) { + if (res != null) throw new Error("already resolved!"); + if (p==null) throw new Error(); + if (p!=this) hp.add(p); + } + public Iterator> iterator() { return ((IterableForest)resolve()).iterator(); } + public HashSet> expand(boolean toss) { return resolve().expand(toss); } + public boolean valid() { resolve(); return valid; } + public String toString() { return resolve().toString(); } + public Forest resolve() { + if (hp==null) return res; + HashSet results = null; + FastSet nh = new FastSet(); + for(Forest p : hp) + for(Body b : (IterableForest)p) { + if (b.keep() && (b.creator==null || !b.creator.lame)) { valid = true; b.addTo(nh); } + else results = new HashSet(); + } + if (results != null) { + for(Forest p : hp) for(Body b : (IterableForest)p) results.add(b); + for(Body b : results) { + if (b.keep() && (b.creator==null || !b.creator.lame)) continue; + if (!b.keep(results)) continue; + if (b.creator!=null && b.creator.lame) continue; + valid = true; + b.addTo(nh); + } + } + hp = null; + return res = new MultiForest(nh, valid); + } + } + + // Implementations ////////////////////////////////////////////////////////////////////////////// + + private static class MultiForest extends IterableForest { + private final FastSet> results; + private boolean valid; + public boolean valid() { return valid; } + private MultiForest(FastSet> results, boolean valid) { this.results = results; this.valid = valid; } + public MultiForest(Token.Location loc, T tag, Forest[] tokens, Sequence creator, boolean unwrap, boolean singleton) { + this.results = new FastSet>(new Body(loc, tag, tokens, creator, unwrap, singleton)); + this.valid = true; + } + public Iterator> iterator() { return results.iterator(); } + + public HashSet> expand(boolean toss) { + HashSet> ret = new HashSet>(); + for(Body b : results) + ret.addAll(b.expand(toss, new ArrayList>(), 0, new HashSet>())); + if (toss && ret.size() > 1) throw new Parser.Ambiguous(this); + return ret; + } + + // Display ////////////////////////////////////////////////////////////////////////////// + + private String toString = null; + public String toString() { + if (toString != null) return toString; + StringBuffer ret = new StringBuffer(); + ret.append(" r : results) { + if (!first) ret.append(' '); + first = false; + ret.append(r); + } + ret.append("?>"); + return toString = ret.toString(); + } + } + + // Statics ////////////////////////////////////////////////////////////////////////////// + + private static Tree[] tree_hint = new Tree[0]; + private static Body[] body_hint = new Body[0]; + private static final Forest[] emptyForestArray = new Forest[0]; +} diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java new file mode 100644 index 0000000..d8c0fd4 --- /dev/null +++ b/src/edu/berkeley/sbp/GSS.java @@ -0,0 +1,328 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +////////////////////////////////////////////////////////////////////////////// +// TODO: +// +// - fix public/package/private status +// + +////////////////////////////////////////////////////////////////////////////// +// Optimizations to add +// +// ** NOTE: not all of these are appropriate for this class -- it is +// simply a list of optimizations not implemented. This +// class is meant to remain simple and easy to understand; +// optimizations which obscure that do not belong here (they +// should go into the compiled version instead) +// +// - most of our time is now spent creating and storing Reduct instances +// - we should be able to perform Reduct's immediately after creating them... +// + +/** implements Tomita's Graph Structured Stack */ +class GSS { + + public GSS() { } + + /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ + public class Phase { + + /** the token immediately after this phase */ + public final Token token; + + /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */ + private final int pos; + + /** FIXME */ + public Forest.Ref finalResult = null; + + /** all reductions (pending and completed) */ + private HashSet reductions = new HashSet(); /* ALLOC */ + + /** all nodes, keyed by the value returned by code() */ + private HashMap hash = new HashMap(); /* ALLOC */ + + /** the number of pending reductions */ + private int pendingReductions = 0; + private int totalReductions = 0; + private HashSet pendingReduct = new HashSet(); + + /** the number of nodes in this phase */ + private int numNodes = 0; + + boolean closed = false; + + public Phase(Phase previous, Token token) { + this.pos = previous==null ? 0 : previous.pos+1; + this.token = token; + } + + public boolean isDone() { return token == null; } + + private String error = "generic syntax error"; + public void checkFailure() throws Parser.Failed { + if (numNodes <= 0) + throw new Parser.Failed(error, getLocation()); + } + + public Token.Location getLocation() { return token==null ? null : token.getLocation(); } + + /** add a new node (merging with existing nodes if possible) + * @param parent the parent of the new node + * @param result the SPPF result corresponding to the new node + * @param state the state that the new node is in + * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper) + * @param start the earliest part of the input contributing to this node (used to make merging decisions) + */ + public void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + Node p = hash.get(code(state, start)); + if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction, start); + else newNode3(parent, pending, state, fromEmptyReduction, start); + } + private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + p.holder.merge(pending); + if (p.parents.contains(parent)) return; + p.parents.add(parent, true); + if (p!=parent && !fromEmptyReduction) p.queueReductions(parent); + } + private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + do { + if (token != null && state.canShift(token)) break; + if (state.isAccepting()) break; + if (token==null) break; + int count = 0; + Parser.Table.Reduction r = null; + for(Parser.Table.Reduction red : token==null ? state.getEofReductions() : state.getReductions(token)) { r = red; count++; } + //if (count==0) return; -- BEWARE! this optimization is suspected to cause really nasty heisenbugs + if (count > 1) break; + //if (r.numPop == 0) break; + //r.reduce(pending, parent, null, Phase.this, null); + //return; + } while(false); + + Node n = new Node(parent, pending, state, start); // ALLOC + n.queueEmptyReductions(); + if (!fromEmptyReduction) n.queueReductions(); + } + + /** perform all reduction operations */ + public void reduce() { + for(Phase.Node n : hash.values()) { + n.queueEmptyReductions(); + n.queueReductions(); + } + while(pendingReduct.size()>0) + pendingReduct.iterator().next().go(); + } + + /** perform all shift operations, adding promoted nodes to next */ + public void shift(Phase next) { + closed = true; + Forest res = null; + boolean ok = false; + for(Phase.Node n : hash.values()) { + n.holder.resolve(); + if (token == null && n.state.isAccepting()) { + ok = true; + if (finalResult==null) finalResult = new Forest.Ref(); + finalResult.merge(n.holder); + } + if (!n.holder.valid()) continue; + if (token == null) continue; + for(Parser.Table.State st : n.state.getShifts(token)) { + if (res == null) res = Forest.create(token.getLocation(), token.result(), null, null, false, false); + next.newNode(n, res, st, true, this); + ok = true; + } + } + + if (!ok && token != null) { + StringBuffer error = new StringBuffer(); + error.append("error: unable to shift token \"" + token + "\"\n"); + error.append(" before: " +pendingReductions+ "\n"); + error.append(" before: " +totalReductions+ "\n"); + for(Phase.Node n : hash.values()) { + n.queueReductions(); + n.queueEmptyReductions(); + } + error.append(" after: " +pendingReductions+ "\n"); + error.append(" candidate states:\n"); + for(Phase.Node n : hash.values()) { + //for(Sequence.Position p : n.state) error.append(" " + p + "\n"); + //error.append(" --\n"); + for(Parser.Table.Reduction r : n.state.getReductions(token)) error.append(" " + r + "\n"); + //error.append(" ==\n"); + } + next.error = error.toString(); + } + + // this massively improves GC performance + reductions = null; + hash = null; + } + + + // GSS Nodes ////////////////////////////////////////////////////////////////////////////// + + private HashMap pcache = new HashMap(); + /** a node in the GSS */ + public class Node { + + private Forest.Ref holder = null; + private HashMap cache = null; + + public HashMap cache() { return cache==null ? (cache = new HashMap()) : cache; } + public Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; } + public Forest pending() { return Phase.this.closed ? holder().resolve() : holder; } + public FastSet parents() { return parents; } + + /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ + public final Phase phase = Phase.this; + + /** what state this node is in */ + public final Parser.Table.State state; + + /** the set of nodes to which there is an edge starting at this node */ + public final FastSet parents = new FastSet(); /* ALLOC */ + + /** FIXME */ + public void queueReductions() { + for(Node n2 : parents) + queueReductions(n2); + } + + /** FIXME */ + public void queueReductions(Node n2) { + new Reduct(this, n2, null); + for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) { + + // currently we have this weird problem where we + // have to do an individual reduct for each child + // when the reduction length is one (ie the + // children wind up being children of the newly + // created node rather than part of the popped + // sequence + + if (r.numPop == 1) new Reduct(this, n2, r); + } + } + + + /** FIXME */ + public void queueEmptyReductions() { + for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) { + if (r.numPop==0) + new Reduct(this, null, r); /* ALLOC */ + } + } + + private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) { + this.state = state; + if (pending != null) this.holder().merge(pending); + if (parent != null) parents.add(parent, true); + if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!"); + Phase.this.hash.put(code(state, start), this); + Phase.this.numNodes++; + if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid + } + } + + + // Forest / Completed Reductions ////////////////////////////////////////////////////////////////////////////// + + /** a pending or completed reduction */ + class Reduct { + + /** the node from which the reduction should begin */ + public Node n = null; + + /** the node on the other end of the edge to be reduced along (either: null, the second node of the reduction, + * or the parent of the result of a length-one reduction) + */ + public Node n2 = null; + + /** true iff the reduction has already been performed */ + private boolean done = false; + + /** the reduction to be applied */ + public Parser.Table.Reduction r; + + public Tree result = null; + + public Reduct(Node n, Node n2, Parser.Table.Reduction r) { + this.n = n; + this.n2 = n2; + this.r = r; + if (reductions.contains(this)) { done = true; return; } + reductions.add(this); + pendingReduct.add(this); + pendingReductions++; + } + + /** perform the reduction */ + public void go() { + if (done) return; + done = true; + pendingReduct.remove(this); + pendingReductions--; + + // FIXME: explain this + if (r==null) { + for(Parser.Table.Reduction r : token==null ? n.state.getEofReductions() : n.state.getReductions(token)) { + if (r.numPop <= 1) continue; + r.reduce(n, n2, Phase.this, null); + } + } else if (r.numPop<=1) { + // UGLY HACK + // The problem here is that a "reduction of length 0/1" + // performed twice with different values of n2 needs + // to only create a *single* new result, but must add + // multiple parents to the node holding that result. + // The current reducer doesn't differentiate between + // the next node of an n-pop reduction and the + // ultimate parent of the last pop, so we need to + // cache instances here as a way of avoiding + // recreating them. + + Forest ret = (r.numPop==0 ? pcache : n.cache()).get(r); + if (ret != null) r.reduce(n, n2, n.phase, ret); + else (r.numPop==0 ? pcache : n.cache()).put(r, r.reduce(n, n2, n.phase, null)); + + } else { + r.reduce(n, n2, Phase.this, null); + } + } + + // FIXME: this is a PITA + public int hashCode() { return n.hashCode() ^ (r==null ? 0 : r.hashCode()) ^ (n2==null ? 0 : n2.hashCode()); } + public boolean equals(Object o) { + if (o==null) return false; + if (o==this) return true; + if (!(o instanceof Reduct)) return false; + Reduct other = (Reduct)o; + return equal(r, other.r) && equal(n, other.n) && equal(n2, other.n2); + } + } + + } + + /** helper method */ + private static boolean equal(Object a, Object b) { + if (a==null && b==null) return true; + if (a==null || b==null) return false; + return a.equals(b); + } + + /** this is something of a hack right now */ + private static long code(Parser.Table.State state, Phase start) { + return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); + } + +} diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java new file mode 100644 index 0000000..046e725 --- /dev/null +++ b/src/edu/berkeley/sbp/Parser.java @@ -0,0 +1,337 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +/** a parser which translates streams of Tokens of type T into a Forest */ +public class Parser { + + private final Table pt; + + //public Parser( Topology top) { this(new Table( top)); } + //public Parser(String s, Topology top) { this(new Table(s, top)); } + + /** + * create a parser to parse the grammar with start symbol u + * @param top a "sample" Topology that can be cloned (FIXME, demanding this is lame) + */ + public Parser(Union u, Topology top) { this(new Table(u, top)); } + + Parser(Table pt) { this.pt = pt; } + + /** parse input for a exactly one unique result, throwing Ambiguous if not unique or Failed if none */ + public Tree parse1(Token.Stream input) throws IOException, Failed, Ambiguous { return parse(input).expand1(); } + + /** parse input, using the table pt to drive the parser */ + public Forest parse(Token.Stream input) throws IOException, Failed { + GSS gss = new GSS(); + GSS.Phase current = gss.new Phase(null, input.next()); + current.newNode(null, null, pt.start, true, null); + for(;;) { + GSS.Phase next = gss.new Phase(current, input.next()); + current.reduce(); + current.shift(next); + if (current.isDone()) return (Forest)current.finalResult; + current.checkFailure(); + current = next; + } + } + + + // Exceptions ////////////////////////////////////////////////////////////////////////////// + + public static class Failed extends Exception { + private final Token.Location location; + private final String message; + public Failed() { this("", null); } + public Failed(String message, Token.Location loc) { this.location = loc; this.message = message; } + public Token.Location getLocation() { return location; } + public String toString() { return message + (location==null ? "" : (" at " + location + "\n" + location.getContext())); } + } + + public static class Ambiguous extends RuntimeException { + public final Forest ambiguity; + public Ambiguous(Forest ambiguity) { this.ambiguity = ambiguity; } + public String toString() { + StringBuffer sb = new StringBuffer(); + sb.append("unresolved ambiguity "/*"at " + ambiguity.getLocation() + ":"*/); + for(Object result : ambiguity.expand(false)) + sb.append("\n " + result); + return sb.toString(); + } + } + + + // Table ////////////////////////////////////////////////////////////////////////////// + + /** an SLR(1) parse table which may contain conflicts */ + static class Table { + + private final Union start0 = new Top(); + private final Sequence start0seq; + static class Top extends Union { public Top() { super("0"); } } + + public final Walk.Cache cache = new Walk.Cache(); + + public HashSet closure() { + HashSet hp = new HashSet(); + start0.reachable(hp); + return hp; + } + public Position firstPosition() { return start0seq.firstp(); } + public Position lastPosition() { Position ret = start0seq.firstp(); while(!ret.isLast()) ret = ret.next(); return ret; } + + private void walk(Element e, HashSet hs) { + if (e==null) return; + if (hs.contains(e)) return; + hs.add(e); + if (e instanceof Atom) return; + for(Sequence s : (Union)e) { + hs.add(s); + for(Position p = s.firstp(); p != null; p = p.next()) + walk(p.element(), hs); + } + } + public HashSet walk() { + HashSet ret = new HashSet(); + walk(start0, ret); + return ret; + } + + /* + public String toString() { + StringBuffer sb = new StringBuffer(); + for(Element e : walk()) + if (e instanceof Union) + ((Union)e).toString(sb); + return sb.toString(); + } + */ + + /** the start state */ + public final State start; + + /** used to generate unique values for State.idx */ + private int master_state_idx = 0; + + /** construct a parse table for the given grammar */ + public Table(Topology top) { this("s", top); } + public Table(String startSymbol, Topology top) { this(new Union(startSymbol), top); } + public Table(Union u, Topology top) { + start0seq = new Sequence.Singleton(u, null, null); + start0.add(start0seq); + + // construct the set of states + HashMap,State> all_states = new HashMap,State>(); + HashSet all_elements = walk(); + for(Element e : all_elements) + cache.ys.put(e, new Walk.YieldSet(e, cache).walk()); + this.start = new State(closure(), all_states, all_elements); + + // for each state, fill in the corresponding "row" of the parse table + for(State state : all_states.values()) + for(Position p : state.hs) { + + // the Grammar's designated "last position" is the only accepting state + if (p==lastPosition()) + state.accept = true; + + // FIXME: how does right-nullability interact with follow restrictions? + // all right-nullable rules get a reduction [Johnstone 2000] + if (p.isRightNullable(cache)) { + Walk.Follow wf = new Walk.Follow(top.fresh(), p.owner(), all_elements, cache); + Reduction red = new Reduction(p); + state.reductions.put(wf.walk(p.owner()), red); + if (wf.includesEof()) state.eofReductions.add(red, true); + } + + // if the element following this position is an atom, copy the corresponding + // set of rows out of the "master" goto table and into this state's shift table + if (p.element() != null && p.element() instanceof Atom) + state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).top())); + } + } + + /** a single state in the LR table and the transitions possible from it */ + public class State implements Comparable, Iterable { + + public final int idx = master_state_idx++; + private final HashSet hs; + + private transient HashMap gotoSetNonTerminals = new HashMap(); + private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); + + private TopologicalBag reductions = new TopologicalBag(); + private FastSet eofReductions = new FastSet(); + private TopologicalBag shifts = new TopologicalBag(); + private boolean accept = false; + + // Interface Methods ////////////////////////////////////////////////////////////////////////////// + + public boolean canShift(Token t) { return shifts.contains(t); } + public Iterable getShifts(Token t) { return shifts.get(t); } + public boolean isAccepting() { return accept; } + public Iterable getReductions(Token t) { return reductions.get(t); } + public Iterable getEofReductions() { return eofReductions; } + public Iterator iterator() { return hs.iterator(); } + + // Constructor ////////////////////////////////////////////////////////////////////////////// + + /** + * create a new state consisting of all the Positions in hs + * @param hs the set of Positions comprising this State + * @param all_states the set of states already constructed (to avoid recreating states) + * @param all_elements the set of all elements (Atom instances need not be included) + * + * In principle these two steps could be merged, but they + * are written separately to highlight these two facts: + *
    + *
  • Non-atom elements either match all-or-nothing, and do not overlap + * with each other (at least not in the sense of which element corresponds + * to the last reduction performed). Therefore, in order to make sure we + * wind up with the smallest number of states and shifts, we wait until + * we've figured out all the token-to-position multimappings before creating + * any new states + * + *
  • In order to be able to run the state-construction algorithm in a single + * shot (rather than repeating until no new items appear in any state set), + * we need to use the "yields" semantics rather than the "produces" semantics + * for non-Atom Elements. + *
+ */ + public State(HashSet hs, + HashMap,State> all_states, + HashSet all_elements) { + this.hs = hs; + + // register ourselves in the all_states hash so that no + // two states are ever created with an identical position set + all_states.put(hs, this); + + // Step 1a: examine all Position's in this state and compute the mappings from + // sets of follow tokens (tokens which could follow this position) to sets + // of _new_ positions (positions after shifting). These mappings are + // collectively known as the _closure_ + + TopologicalBag bag0 = new TopologicalBag(); + for(Position position : hs) { + if (position.isLast() || !(position.element() instanceof Atom)) continue; + Atom a = (Atom)position.element(); + HashSet hp = new HashSet(); + position.next().reachable(hp); + bag0.addAll(a.top(), /*clo.walk()*/hp); + } + + // Step 1b: for each _minimal, contiguous_ set of characters having an identical next-position + // set, add that character set to the goto table (with the State corresponding to the + // computed next-position set). + + for(Topology r : bag0) { + HashSet h = new HashSet(); + for(Position p : bag0.getAll(r)) h.add(p); + gotoSetTerminals.put(r, all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h)); + } + + // Step 2: for every non-Atom element (ie every Element which has a corresponding reduction), + // compute the closure over every position in this set which is followed by a symbol + // which could yield the Element in question. + // + // "yields" [in one or more step] is used instead of "produces" [in exactly one step] + // to avoid having to iteratively construct our set of States as shown in most + // expositions of the algorithm (ie "keep doing XYZ until things stop changing"). + /* + for(Element e : all_elements) { + if (e instanceof Atom) continue; + HashSet h = new Walk.Closure(null, g.cache).closure(e, hs); + State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); + if (gotoSetNonTerminals.get(e) != null) + throw new Error("this should not happen"); + gotoSetNonTerminals.put(e, s); + } + */ + HashMapBag move = new HashMapBag(); + for(Position p : hs) { + Element e = p.element(); + if (e==null) continue; + HashSet ys = cache.ys.get(e); + if (ys != null) { + for(Element y : ys) { + HashSet hp = new HashSet(); + p.next().reachable(hp); + move.addAll(y, hp); + } + } + } + for(Element y : move) { + HashSet h = move.getAll(y); + State s = all_states.get(h) == null ? new State(h, all_states, all_elements) : all_states.get(h); + gotoSetNonTerminals.put(y, s); + } + } + + public String toString() { return "state["+idx+"]"; } + + public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } + } + + /** + * the information needed to perform a reduction; copied here to + * avoid keeping references to Element objects in a Table + */ + public class Reduction { + // FIXME: cleanup; almost everything in here could go in either Sequence.Position.getRewrite() or else in GSS.Reduct + public final int numPop; + private final Position position; + private final Forest[] holder; // to avoid constant reallocation + public int hashCode() { return position.hashCode(); } + public boolean equals(Object o) { + if (o==null) return false; + if (o==this) return true; + if (!(o instanceof Reduction)) return false; + Reduction r = (Reduction)o; + return r.position == position; + } + public Reduction(Position p) { + this.position = p; + this.numPop = p.pos; + this.holder = new Forest[numPop]; + } + public String toString() { return "[reduce " + position + "]"; } + public Forest reduce(Forest f, GSS.Phase.Node parent, GSS.Phase.Node onlychild, GSS.Phase target, Forest rex) { + holder[numPop-1] = f; + return reduce(parent, numPop-2, rex, onlychild, target); + } + public Forest reduce(GSS.Phase.Node parent, GSS.Phase.Node onlychild, GSS.Phase target, Forest rex) { + return reduce(parent, numPop-1, rex, onlychild, target); + } + + // FIXME: this could be more elegant and/or cleaner and/or somewhere else + private Forest reduce(GSS.Phase.Node parent, int pos, Forest rex, GSS.Phase.Node onlychild, GSS.Phase target) { + if (pos>=0) holder[pos] = parent.pending(); + if (pos<=0 && rex==null) { + System.arraycopy(holder, 0, position.holder, 0, holder.length); + rex = position.rewrite(target.getLocation()); + } + if (pos >=0) { + if (onlychild != null) + reduce(onlychild, pos-1, rex, null, target); + else + for(GSS.Phase.Node child : parent.parents()) + reduce(child, pos-1, rex, null, target); + } else { + State state = parent.state.gotoSetNonTerminals.get(position.owner()); + if (state!=null) + target.newNode(parent, rex, state, numPop<=0, parent.phase); + } + return rex; + } + } + } + + private static final Forest[] emptyForestArray = new Forest[0]; +} diff --git a/src/edu/berkeley/sbp/Repeat.java b/src/edu/berkeley/sbp/Repeat.java new file mode 100644 index 0000000..2365cbd --- /dev/null +++ b/src/edu/berkeley/sbp/Repeat.java @@ -0,0 +1,63 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +/** currently this class exports only static methods to create repetitions; there are no public instance methods or constructors */ +public class Repeat extends Union { + + /** repeat zero or one times */ + public static Repeat maybe(Element e) { return new Repeat(e, true, false); } + /** repeat zero or more times */ + public static Repeat many0(Element e) { return new Repeat(e, true, true); } + /** repeat zero or more times, separated by sep */ + public static Repeat many0(Element e, Element sep) { return new Repeat(e, true, true, sep); } + /** repeat one or more times */ + public static Repeat many1(Element e) { return new Repeat(e, false, true); } + /** repeat one or more times, separated by sep */ + public static Repeat many1(Element e, Element sep) { return new Repeat(e, false, true, sep); } + public static Maximal maximal(Element e) { return new Maximal(e); } + + // Instance ////////////////////////////////////////////////////////////////////////////// + + final boolean zeroOkay, manyOkay; + final Element e; + final Element separator; + + Repeat(final Element e, boolean zeroOkay, boolean manyOkay) { this(e, zeroOkay, manyOkay, null); } + Repeat(final Element e, boolean zeroOkay, boolean manyOkay, Element separator) { + super(e+(!manyOkay ? "?" : (zeroOkay ? "*" : "+")), true); + this.e = e; + this.zeroOkay = zeroOkay; + this.manyOkay = manyOkay; + this.separator = separator; + if (zeroOkay) { + add(new Sequence.Constant.Empty()); + if (manyOkay) add(new Sequence.Singleton(many1(e, separator), null, null)); + else add(new Sequence.Singleton(e, null, null)); + } else { + add(new Sequence.RewritingSequence(null, new Element[] { e }, null, null)); + if (this.separator==null) { + add(new Sequence.Unwrap(new Element[] { e, Repeat.this }, null, null)); + } else { + add(new Sequence.Unwrap(new Element[] { e, this.separator, Repeat.this }, new boolean[] { false, true, false }, null, null)); + } + } + } + + static class MaximalSequence extends Sequence.Singleton { + private final Element e; + public String toString() { return e+"@";} + public MaximalSequence(Element e) { super(e, null, null); this.e = e; } + } + static class Maximal extends Union { + public Maximal(final Element e) { + super(e+"+", true); + add(new MaximalSequence(e)); + } + } +} diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java new file mode 100644 index 0000000..fcff530 --- /dev/null +++ b/src/edu/berkeley/sbp/Sequence.java @@ -0,0 +1,207 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +/** juxtaposition; zero or more adjacent Elements; can specify a rewriting */ +public abstract class Sequence extends Element implements Iterable { + + // Static Constructors ////////////////////////////////////////////////////////////////////////////// + + /** the empty sequence (matches the empty string) */ + public static final Sequence empty = new Sequence.Constant.Empty(); + + /** after matching the sequence, do not add anything to the output tree */ + public static Sequence drop(Element[] e, HashSet and, HashSet not, boolean lame) { return new Constant.Drop(e, and, not, lame); } + + /** after matching the sequence, insert a constant into the output tree */ + public static Sequence constant(Element[] e, Object o, HashSet and, HashSet not) { return new Constant(e, o, and, not); } + + /** after matching the sequence, place the result of the idxth match in the output tree */ + public static Sequence singleton(Element[] e, int idx, HashSet and, HashSet not) { return new Singleton(e, idx, and, not); } + + /** + * after matching the sequence, create the specified output tree + * @param tag the tag for the output tree + * @param e the elements to match + * @param drops only elements of e whose corresponding boolean in drops is false will be included in the output tree + **/ + public static Sequence rewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet and, HashSet not) { + return new RewritingSequence(tag, e, drops, and, not); } + + //////////////////////////////////////////////////////////////////////////////// + + protected final Element[] elements; + + final HashSet needs; + final HashSet hates; + boolean lame = false; + + final Position firstp; + Position firstp() { return firstp; } + + public Iterator iterator() { return new ArrayIterator(elements); } + protected Sequence(Element[] elements, HashSet and, HashSet not) { + this.needs = and==null ? new HashSet() : and; + this.hates = not==null ? new HashSet() : not; + //for(Sequence s : needs) s.lame = true; + //for(Sequence s : hates) s.lame = true; + this.elements = elements; + this.firstp = new Position(0); + } + + void reachable(HashSet h) { firstp().reachable(h); } + + Forest epsilonForm() { return firstp().rewrite(null); } + + protected abstract Forest postReduce(Token.Location loc, Forest[] args); + + + // Position ////////////////////////////////////////////////////////////////////////////// + + /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */ + public class Position { + + void reachable(HashSet h) { + if (h.contains(this)) return; + h.add(this); + if (element() != null) element().reachable(h); + } + + final int pos; + private final Position next; + final Forest[] holder; + + private Position(int pos) { + this.pos = pos; + this.next = pos==elements.length ? null : new Position(pos+1); + this.holder = new Forest[elements.length]; + } + + boolean isFirst() { return pos==0; } + boolean isRightNullable(Walk.Cache cache) { + if (isLast()) return true; + if (!element().possiblyEpsilon(cache)) return false; + return next().isRightNullable(cache); + } + + /** the element immediately after this Position, or null if this is the last Position */ + public Element element() { return pos>=elements.length ? null : elements[pos]; } + + /** the element which produces the sequence to which this Position belongs */ + public Sequence owner() { return Sequence.this; } + + /** the next Position (the Position after this.element()) */ + public Position next() { return next; } + + /** true iff this Position is the last one in the sequence */ + public boolean isLast() { return next()==null; } + + // Reduction ///////////////////////////////////////////////////////////////////////////////// + + Forest rewrite(Token.Location loc) { + for(int i=pos; i ret = Sequence.this.postReduce(loc, holder); + for(int k=0; k"); + return ret.toString(); + } + } + + + // toString ////////////////////////////////////////////////////////////////////////////// + + public String toString() { return toString(new StringBuffer(), false).toString(); } + StringBuffer toString(StringBuffer sb) { return toString(sb, true); } + StringBuffer toString(StringBuffer sb, boolean spacing) { + for(int i=0; i and, HashSet not) { super(e, and, not); this.result = result; } + public Forest postReduce(Token.Location loc, Forest[] args) { + return (Forest)Forest.leaf(loc, result, this); + } + static class Drop extends Constant { + public Drop(Element[] e, HashSet and, HashSet not, boolean lame) { + super(e, null, and, not); + this.lame = lame; + } + } + static class Empty extends Sequence.Constant.Drop { public Empty() { super(new Element[] { }, null, null, false); } } + } + + static class Singleton extends Sequence { + private final int idx; + public Singleton(Element e, HashSet and, HashSet not) { this(new Element[] { e }, 0, and, not); } + public Singleton(Element[] e, int idx, HashSet and, HashSet not) { super(e, and, not); this.idx = idx; } + public Forest postReduce(Token.Location loc, Forest[] args) { return (Forest)Forest.singleton(loc, args[idx], this); } + } + + static class Unwrap extends Sequence { + private boolean[] drops; + public Unwrap(Element[] e, HashSet and, HashSet not) { super(e, and, not); this.drops = null; } + public Unwrap(Element[] e, boolean[] drops, HashSet and, HashSet not) { super(e, and, not); this.drops = drops; } + public Forest postReduce(Token.Location loc, Forest[] args) { + if (drops==null) return Forest.create(loc, null, args, this, true, false); + int count = 0; + for(int i=0; i[] args2 = new Forest[count]; + int j = 0; + for(int i=0; i and, HashSet not) { this(tag, e, null, and, not); } + public RewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet and, HashSet not) { + super(e, and, not); + this.tag = tag; + this.drops = drops == null ? new boolean[e.length] : drops; + for(int i=0; i Forest postReduce(Token.Location loc, Forest[] args) { + Forest[] args2 = new Forest[count]; + int j = 0; + for(int i=0; i "); + sb.append(tag); + return sb; + } + } +} diff --git a/src/edu/berkeley/sbp/Token.java b/src/edu/berkeley/sbp/Token.java new file mode 100644 index 0000000..196f5ca --- /dev/null +++ b/src/edu/berkeley/sbp/Token.java @@ -0,0 +1,34 @@ +package edu.berkeley.sbp; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; + +/** a token of input -- note that this represents an actual input token rather than an Element which matches a token */ +public interface Token { + + // FIXME!!! remove this + /** converts this Token into a standalone result (ie for a non-rewriting pattern) */ + public String result(); + + /** this is declared abstract as a way of forcing subclasses to provide a thoughtful implementation */ + public abstract String toString(); + + public abstract Location getLocation(); + + /** a sequence of input tokens; returns null when EOF is reached */ + public static interface Stream { + public T next() throws IOException; + } + + /** a location within the input stream */ + public static interface Location { + public String toString(); + public String getContext(); + } + +} + diff --git a/src/edu/berkeley/sbp/Tree.java b/src/edu/berkeley/sbp/Tree.java new file mode 100644 index 0000000..989224c --- /dev/null +++ b/src/edu/berkeley/sbp/Tree.java @@ -0,0 +1,57 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +/** a tree (or node in a tree); see jargon.txt for details */ +public class Tree { + + final T head; + Tree[] children; + final Token.Location location; + + public T head() { return head; } + public int numChildren() { return children.length; } + public Iterable> children() { return new ArrayIterator(children); } + + public Token.Location getLocation() { return location; } + + public Tree(Token.Location loc, T head) { this(loc, head, null); } + public Tree(Token.Location loc, T head, Tree[] children) { + this.location = loc; + this.head = head; + Tree[] children2 = children==null ? new Tree[0] : new Tree[children.length]; + if (children != null) System.arraycopy(children, 0, children2, 0, children.length); + this.children = children2; + } + + /** append Java code to sb which evaluates to this instance */ + public void toJava(StringBuffer sb) { + sb.append("new Tree(null, "); + sb.append(head==null ? "null" : "\"" + StringUtil.toJavaString(head+"") + "\""); + sb.append(", new Tree[] { "); + for(int i=0; i 0) { ret.append(q); ret.append(" "); } + } + String tail = ret.toString().trim(); + String h = (head!=null && !head.toString().equals("")) ? (tail.length() > 0 ? head+":" : head+"") : ""; + if (tail.length() > 0) tail = "{" + tail + "}"; + return h + tail; + } + + +} diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java new file mode 100644 index 0000000..df6c374 --- /dev/null +++ b/src/edu/berkeley/sbp/Union.java @@ -0,0 +1,90 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +/** an element which can produce one of several alternatives */ +public class Union extends Element implements Iterable { + + final String shortForm; + final boolean synthetic; + private final List alternatives = new ArrayList(); + + public Iterator iterator() { return alternatives.iterator(); } + + void reachable(HashSet h) { for(Sequence s : alternatives) s.reachable(h); } + + /** adds an alternative */ + public void add(Sequence s) { alternatives.add(s); } + + /** + * Since every cycle in a non-degenerate grammar contains at + * least one Union, every instance of this class must be able to + * display itself in both "long form" (list of the long forms of + * its alternatives) and "short form" (some abbreviation). + * + * @param shortForm the "short form" display; usually + * @param synthetic if true, this Union's "long form" is "obvious" and should not be displayed when printing the grammar + */ + public Union(String shortForm) { this(shortForm, false); } + public Union(String shortForm, boolean synthetic) { + this.shortForm = shortForm; + this.synthetic = synthetic; + } + + private Forest.Ref epsilonForm = null; + Forest epsilonForm() { + if (epsilonForm != null) return epsilonForm; + epsilonForm = new Forest.Ref(); + for(Sequence s : this) + if (s.possiblyEpsilon(null)) + epsilonForm.merge(s.epsilonForm()); + return epsilonForm; + } + + // Display ////////////////////////////////////////////////////////////////////////////// + + public String toString() { return shortForm; } + private static String pad(int i,String s) { return s.length() >= i ? s : pad(i-1,s)+" "; } + void toString(StringBuffer sb) { + if (synthetic) return; + boolean first = true; + if (alternatives.size()==0) { + sb.append(pad(15, shortForm) + "::= "); + } else for(Sequence s : this) { + sb.append(pad(15, first ? shortForm : "") + (first ? "::= " : " | ")); + first = false; + sb.append(s.toString()); + sb.append('\n'); + } + sb.append('\n'); + } + + // SubUnion ////////////////////////////////////////////////////////////////////////////// + + /** FIXME this is kind of a hack */ + public class Subset extends Union { + private final Set exclude; + public Subset(String shortForm, Set exclude) { super(shortForm, true); this.exclude = exclude; } + public Iterator iterator() { + final Iterator it = Union.this.iterator(); + return new Iterator() { + private Sequence next = it.hasNext() ? it.next() : null; + public boolean hasNext() { return next != null; } + public Sequence next() { + Sequence ret = next; + do { + next = it.hasNext() ? it.next() : null; + } while (next != null && (next instanceof Sequence) && exclude.contains((Sequence)next)); + return ret; + } + public void remove() { throw new Error(); } + }; + } + } + +} diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java new file mode 100644 index 0000000..5754726 --- /dev/null +++ b/src/edu/berkeley/sbp/Walk.java @@ -0,0 +1,191 @@ +package edu.berkeley.sbp; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.Sequence.Position; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +/** a traversal of the grammar performed by mapping from Elements to a lattice and computing the resulting LUB */ +abstract class Walk { + protected HashSet acc = new HashSet(); + protected abstract T bottom(Element e); + + protected final Cache c; + public Walk() { this(null); } + public Walk(Cache c) { this.c = c; } + + public T sequence(Sequence s) { + T ret = bottom(s); + for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next()) + ret = sequence(s, ret, walk(p.element())); + return ret; + } + + public T walkAtom(Atom r) { return walk(r); } + public T union(Union u, T a, T b) { return bottom(u); } + public T sequence(Sequence s, T a, T b) { return bottom(s); } + protected T walk(Element e) { + if (acc.contains(e)) return bottom(e); + acc.add(e); + return walk2(e); + } + + protected T walk2(Element e) { + if (e instanceof Atom) return walkAtom((Atom)e); + else if (e instanceof Sequence) return sequence((Sequence)e); + else if (e instanceof Union) { + T ret = bottom(e); + for(Sequence s : (Union)e) ret = union((Union)e, ret, walk(s)); + return ret; + } else { + throw new Error("unknown element of class " + e.getClass().getName() + ": " + e); + } + } + + static class YieldSet extends Walk> { + private final Element e; + public final HashSet walk() { return walk(e); } + public YieldSet(Element e, Cache c) { super(c); this.e = e; } + public HashSet bottom(Element e) { return acc; } + public HashSet sequence(Sequence seq) { return bottom(seq); } + public HashSet walkAtom(Atom r) { + c.atoms.put(e, c.atoms.get(e)==null ? r.top() : c.atoms.get(e).union(r.top())); + return super.walkAtom(r); + } + } + + + // Boolean ////////////////////////////////////////////////////////////////////////////// + + static class PossiblyEpsilon extends Walk { + public Boolean walkAtom(Atom r) { return false; } + public Boolean sequence(Sequence s, Boolean a, Boolean b) { return new Boolean(a && b); } + public Boolean union(Union u, Boolean a, Boolean b) { return new Boolean(a || b); } + public Boolean bottom(Element e) { return (e instanceof Union) ? false : true; } + private HashMap hm = new HashMap(); + protected Boolean walk(Element e) { + if (hm.get(e) != null) return hm.get(e); + hm.put(e, false); + Boolean ret = walk2(e); + hm.put(e, ret); + return ret; + } + } + + + // Token-Set ////////////////////////////////////////////////////////////////////////////// + + static abstract class WalkTokenSet extends Walk> { + public Topology cs; + public WalkTokenSet(Topology cs) { this.cs = cs; } + public WalkTokenSet(Topology cs, Cache c) { super(c); this.cs = cs; } + public Topology bottom(Element e) { return cs; } + public Topology walkAtom(Atom r) { cs.add(r.top()); return cs; } + } + + class First extends WalkTokenSet { + public First(Topology cs, Walk.Cache cache) { super(cs, cache); } + public Topology sequence(Sequence seq) { + for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) { + walk(p.element()); + if (!p.element().possiblyEpsilon(c)) break; + } + return cs; + } + } + + class Last extends WalkTokenSet { + public Last(Topology cs, Walk.Cache cache) { super(cs, cache); } + public Topology sequence(Sequence seq) { sequence(seq.firstp()); return cs; } + private Topology sequence(Position p) { + if (p==null) return null; + Topology ret = sequence(p.next()); + if (ret!=null) return ret; + if (p.isLast()) return null; + if (p.element().possiblyEpsilon(c)) return null; + if (p.element()==null) return null; + return walk(p.element()); + } + } + + static class Follow extends WalkTokenSet { + private final Element me; + private final HashSet all; + private boolean eof = false; + public boolean includesEof() { return eof; } + public Follow(Topology cs, Element me, HashSet all, Cache c) { super(cs, c); this.me = me; this.all = all; } + public Topology bottom(Element e) { return cs; } + public Topology sequence(Sequence seq) { return cs; } + public Topology walkAtom(Atom r) { return walk((Element)r); } + public Topology walk(Element e) { + if (acc.contains(e)) return bottom(e); + acc.add(e); + + if (c != null) { + Topology cached = (Topology)c.follow.get(e); + if (cached != null) { + cs.add(cached); + eof |= c.eof.get(e); + return cs; + } + } + + Topology cso = cs; + boolean eofo = eof; + eof = false; + cs = cso.fresh(); + + if (e instanceof Parser.Table.Top) eof = true; + for(Element x : all) { + boolean matched = false; + if (x instanceof Parser.Table.Top) walk(x); // because this symbol might not appear in any other Sequence + if (!(x instanceof Sequence)) continue; + Sequence a = (Sequence)x; + Position mp = null; + for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) { + if (matched) cs.add(new First(cs.fresh(), c).walk(pos.element())); + if (pos.isLast()) { matched = (matched && pos.element().possiblyEpsilon(c)); continue; } + boolean good = false; + if (e instanceof Atom) { + Topology top = c.atoms.get(pos.element()); + if (top==null) continue; + if (!(top.containsAll(((Atom)e).top()))) continue; + } else { + if (c.ys.get(pos.element()).contains(e)) good = true; + } + if (good) { + mp = pos; + matched = true; + } + } + if (matched) walk(a); + } + + if (e instanceof Repeat.MaximalSequence || e instanceof Repeat.Maximal) + cs.remove(new Last(cs.fresh(), c).walk(e)); + + if (c != null && e==me) { + c.follow.put(e, cs.dup()); + c.eof.put(e, eof); + } + + cso.add(cs); + cs = cso; + eofo |= eof; + eof = eofo; + + return cs; + } + } + + static class Cache { + public final HashMap possiblyEpsilon = new HashMap(); + public HashMap eof = new HashMap(); + public HashMap follow = new HashMap(); + public HashMap> ys = new HashMap>(); + public HashMap atoms = new HashMap(); + } +} diff --git a/src/edu/berkeley/sbp/misc/CharToken.java b/src/edu/berkeley/sbp/misc/CharToken.java new file mode 100644 index 0000000..bad4372 --- /dev/null +++ b/src/edu/berkeley/sbp/misc/CharToken.java @@ -0,0 +1,169 @@ +package edu.berkeley.sbp.misc; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; + +/** an implementation of Token for streams of Java char values */ +public class CharToken implements Token, IntegerTopology.IntegerMappable { + + // Public ////////////////////////////////////////////////////////////////////////////// + + public static class CharRange extends Atom { + private String esc(char c) { return StringUtil.escapify(c+"", "[]-~\\\"\'"); } + public CharRange(Topology t) { super(t); } + public String toString() { + StringBuffer sb = new StringBuffer(); + sb.append('['); + Range.Set ranges = ((IntegerTopology)top()).getRanges(); + if (ranges.size() == -1 || ranges.size() > Character.MAX_VALUE/2) { + sb.append('~'); + ranges = ranges.complement(); + } + ranges = ranges.intersect(all); + for(Range r : ranges) { + if (r.isMinNegInf() || r.isMaxPosInf()) throw new Error("should not happen"); + if (r.getMin()==r.getMax()) { + sb.append(esc((char)r.getMin())); + } else{ + sb.append(esc((char)r.getMin())); + sb.append('-'); + sb.append(esc((char)r.getMax())); + } + } + sb.append(']'); + return sb.toString(); + } + } + + /** returns an element matching all characters between start and end, inclusive */ + public static Atom positiveRange(char start, char end) { + return new CharRange(new IntegerTopology(new Range.Set(new Range((int)start, (int)end)))); + } + + /** returns an element matching all characters not between start and end, inclusive */ + public static Atom negativeRange(char start, char end) { + return new CharRange(new IntegerTopology(new Range.Set(new Range((int)start, (int)end)).complement().intersect(all))); + } + + private static final Range.Set all = new Range.Set(new Range(0, Character.MAX_VALUE)); + public static final Atom any = new CharRange(new IntegerTopology(all)); + public static final Atom none = new CharRange(new IntegerTopology()); + public static IntegerTopology range(Range r) { return new IntegerTopology(r); } + public static Atom set(Range.Set r) { return new CharRange(new IntegerTopology(r)); } + + /** returns an element which exactly matches the string given */ + public static Element string(String s) { + if (s.length() == 0) return MetaGrammar.epsilon; + final String escapified = "\""+StringUtil.escapify(s, "\"\r\n\\")+"\""; + Element ret; + if (s.length() == 1) { + ret = + new CharRange(new IntegerTopology((int)s.charAt(0))) { + public String toString() { return escapified; } }; + } else { + Union ret2 = new Union("\""+s+"\"_str", true) { + public String toString() { return escapified; } }; + Element[] refs = new Element[s.length()]; + for(int i=0; i((int)s.charAt(i))); + ret2.add(Sequence.constant(refs, s, null, null)); + ret = ret2; + } + return ret; + } + + /** FIXME */ + public static Topology top() { return new IntegerTopology(); } + public static Topology top(String s) throws java.text.ParseException { + return new IntegerTopology(Range.Set.parse(s)); + } + + // Private ////////////////////////////////////////////////////////////////////////////// + + public final char c; + public final Location location; + private CharToken(char c, int line, int col) { this(c, new CartesianLocation(line, col)); } + private CharToken(char c, Location loc) { this.c = c; this.location = loc; } + public String result() { return c+""; } + public Location getLocation() { return location; } + public String toString() { return "\'"+StringUtil.escapify(c+"")+"\'"; } + + ////////////////////////////////////////////////////////////////////////////////////////// + + public int toInt() { return (int)c; } + + // Statics ////////////////////////////////////////////////////////////////////////////// + + static class CartesianLocation implements Location { + public final int line; + public final int col; + public String toString() { return line + ":" + col; } + public CartesianLocation(int line, int col) { this.line = line; this.col = col; } + public String getContext() { return ""; } + } + + /** an implementation of Token.Stream for sequences of characters */ + public static class Stream implements Token.Stream { + private final String message; + private final Reader r; + private int line = 1; + private int col = 1; + + public Stream(String s) { this(new StringReader(s)); } + + public Stream(Reader r) { this(r, null); } + public Stream(Reader r, String s) { this.r = r; this.message = s; } + + public Stream(InputStream i) { this(i, null); } + public Stream(InputStream i, String s) { this(new InputStreamReader(i), s); } + + private Line currentLine = new Line(); + private class Line { + public StringBuffer line = new StringBuffer(); + } + + private class LocWrap implements Location { + Line myline = Stream.this.currentLine; + public final int line; + public final int col; + public String toString() { return line + ":" + col; } + public LocWrap(int line, int col) { this.line = line; this.col = col; } + public String getContext() { + StringBuffer spaces = new StringBuffer(); + for(int i=0; i 10) { + then = now; + System.out.print(" "+(message==null?"":message)+" " + s + " \r"); + } + if (c=='\n') { + currentLine = new Line(); + line++; + col = 1; + } else { + currentLine.line.append(c); + col++; + } + return ret; + } + } + +} diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java new file mode 100644 index 0000000..9244f05 --- /dev/null +++ b/src/edu/berkeley/sbp/misc/MetaGrammar.java @@ -0,0 +1,758 @@ +package edu.berkeley.sbp.misc; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import java.util.*; +import java.io.*; + +public class MetaGrammar extends ReflectiveWalker { + + public static Union make() throws Exception { + return ((MetaGrammar)new MetaGrammar().walk(meta)).done(); + } + + + // FIXME + private static HashSet dropAll = new HashSet(); + + // Statics ////////////////////////////////////////////////////////////////////////////// + + private static final Union SELF = new Union("()"); + + public static Union epsilon = new Union("()"); + static { epsilon.add(Sequence.empty); } + + // MetaGrammar ////////////////////////////////////////////////////////////////////////////// + + public Object walk(String tag, Object[] argo) { + if ("dork".equals(tag)) return Reflection.lub(argo); + return super.walk(tag, argo); + } + public PreSequence[] dork(PreSequence[] p) { return p; } + public Object _star_(Element r) { return new Rep(r, null, false, true); } + public Element _leftbracket_(Object o, Object[] args) { return rangex(o==null || !(o instanceof Character) ? null : o, args); } + public Union _colon__colon__equals_(String s, PreSequence[][] p) { return nonTerminalZ(s, p); } + public Union _bang__colon__colon__equals_(String s, PreSequence[][] p) { + return nonTerminalZ(s, p, true); } + public Union _colon__colon__equals_(boolean q, String s, PreSequence[][] p) { + return nonTerminalZ(s, p, q); + } + public Element _leftparen__rightparen_() { return epsilon; } + public Element epsilon(Object o, Object b) { return epsilon; } + public Element _rightparen_(Object e) { return SELF; } + + public PreSequence _amp_(PreSequence p, Object[] o) { + p.needs.add(new PreSequence(o, null, true)); + return p; + } + public PreSequence _amp__tilde_(PreSequence p, Object[] o) { + p.hates.add(new PreSequence(o, null, true)); + return p; + } + + public Element _bang_(Element r) { return r; } + public Object care(String s) { return new MyLift(s); } + //public Element _backtick_(Element r) { return new Unwrap(r); } + //public Element _hash_(Element e) { return e; } + //public Element _hash_(Element e) { return _plus__plus_(e); } + + public PreSequence[] alternatives(PreSequence[] s) { return s; } + + public Range _minus_(Character a, Character b) { return b==null ? new Range(a.charValue(), true) : new Range(a.charValue(), b.charValue()); } + public Union nonTerminalY(String s) { return nonTerminalX(s, false, false); } + public Union nonTerminalX(String s, boolean synthetic, boolean dropAll) { + Union n = s.equals(startSymbol) ? g : nt.get(s); + if (n == null) nt.put(s, n = new Union(s, synthetic)); + if (dropAll) this.dropAll.add(n); + return n; + } + public Object _leftparen_(PreSequence[][] p) { return nonTerminalZ(p); } + public Union nonTerminalZ(PreSequence[][] p) { return nonTerminalX("anon"+(anon++), p, false, false); } + public Union nonTerminalZ(String s, PreSequence[][] p) { return nonTerminalX(s, p, false, false); } + public Union nonTerminalZ(String s, PreSequence[][] p, boolean q) { return nonTerminalX(s, p, false, q); } + public Object _backslash__leftbrace_(String s) { return SELF; } + public Object _leftbrace_(String s) { return SELF; } + public Object _plus_(final Element r) { return new Rep(r, null, false, false); } + //public Element _tilde__slash__tilde_(final Element r) { return Repeat.maximal(r); } + public Object _plus__slash_(final Element r, Element s) { /*return Repeat.many1(r, s);*/ return new Rep(r, s, false, false); } + //public Element _star__slash_(final Element r, Element s) { return Repeat.many0(r, s); } + //public Element _star__star_(final Element r, Element s) { return Repeat.maximal(Repeat.many0(r, s)); } + public Object _plus__plus_(final Element r) { return new Rep(r, null, true, false); } + public Element _question_(final Element r) { return Repeat.maybe(r); } + public MetaGrammar gram(Object o, MetaGrammar g, Object o2) { return g; } + public MetaGrammar grammar(Object[] o) { return this; } + public MetaGrammar grammar(Object o, Union[] u, Object x) { return this; } + public char _backslash_n() { return '\n'; } + public char _backslash_r() { return '\r'; } + public String literal(String s) { return s; } + //public Element literal(String s) { return CharToken.string(s); } + + public Range range0(char a) { return new Range(a, a); } + public Range range0(char a, char b) { return new Range(a, b); } + public Element range(Object o, Range[] rr) { + Range.Set ret = !"~".equals(o+"") ? new Range.Set() : new Range.Set(new Range(true, true)); + if (rr != null) + for(Range r : rr) + if (!"~".equals(o+"")) ret.add(r); + else ret.remove(r); + return CharToken.set(ret); + } + public Element rangex(Object o, Object[] r) { + Range.Set ret = o==null ? new Range.Set() : new Range.Set(new Range(true, true)); + if (r != null) + for(Object aa : r) { + Range range = + aa instanceof Range + ? (Range)aa + : aa instanceof Character + ? new Range(((Character)aa).charValue()) + : new Range(((String)aa).charAt(0)); + if (o==null) ret.add(range); + else ret.remove(range); + } + return CharToken.set(ret); + } + + public String sify(Object arg) { + if (arg==null) return ""; + if (arg instanceof String) return (String)arg; + Object[] args = (Object[])arg; + while(true) { + args = Reflection.lub(args); + if (args instanceof String[]) { + StringBuffer ret = new StringBuffer(); + for(String s : ((String[])args)) ret.append(s); + return ret.toString(); + } + if (args instanceof Character[]) break; + if (!(args instanceof Object[])) break; + args = (Object[])args[0]; + } + if (args instanceof Character[]) { + char[] c = new char[args.length]; + for(int i=0; i nt; + private int anon = 0; + private Element dws; + private String startSymbol; + + public MetaGrammar() { this("s"); } + public MetaGrammar(String s) { done(s); } + public Union done() { return done("s"); } + public Union done(String str) { + Union ret = g; + g = new Union(str); + startSymbol = str; + nt = new HashMap(); + nt.put(str, g); + this.dws = Repeat.maximal(Repeat.many0(nonTerminalY("w"))); + return ret; + } + + public Union nonTerminalX(String str, PreSequence[][] s, boolean synthetic, boolean dropAll) { + Union n = nonTerminalX(str, synthetic, dropAll); + if (s == null || s.length==0) { n.add(Sequence.empty); return n; } + HashSet seqs = new HashSet(); + for(int i=0; i temp = new HashSet(); + for(PreSequence pre : s[i]) { + pre.hatess.addAll(seqs); + Sequence seq = pre.buildSequence(Character.isUpperCase(str.charAt(0)) ? dws : null, n, false, dropAll); + temp.add(seq); + //for(Sequence dom : seqs) seq.hates.add(dom); + n.add(seq); + } + seqs.addAll(temp); + } + return n; + } + + public String stringify(String s) { return StringUtil.unescapify(s); } + public char unescape(char x, char c) { return unescape(c); } + public char unescape(char c) { return StringUtil.unescapify("\\"+c).charAt(0); } + public PreSequence sequence(Object[] o) { return new PreSequence(o, null); } + + public static class PreBrace { + public final Object[] o; + public PreBrace(Object[] o) { this.o = o; } + } + + public PreSequence _equals__greater_(Object[] o, String s) { return new PreSequence(o, s); } + public PreSequence wrap(Object[] o) { return new PreSequence(o, ""); } + public PreSequence mwrap(Object[] o) { return new PreSequence(o, ""); } + public PreSequence rewrite(Object[] o) { return new PreSequence(o, null); } + public PreSequence rewrite(Object[] o, Object o2) { + Object[] o3 = new Object[o.length + 1]; + System.arraycopy(o, 0, o3, 0, o.length); + o3[o3.length-1] = o2; + return rewrite(o3); + } + + public static class Rep { + private final Element e; + private final Element s; + private final boolean maximal; + private final boolean zero; + public Rep(Element e, Element s, boolean maximal, boolean zero) { this.e = e; this.s = s; this.zero = zero; this.maximal = maximal;} + public Element build(Element ws) { + Element sep = null; + if (ws==null) sep = s; + else if (s==null) sep = ws; + else { + Union ws2 = new Union(e + "/" + s + "/" + ws, true); + ws2.add(Sequence.singleton(new Element[] { ws, s, ws }, 0, null, null)); + sep = ws2; + } + Element ret = zero ? Repeat.many0(e, sep) : Repeat.many1(e, sep); + return maximal ? Repeat.maximal(ret) : ret; + } + } + + public static class PreSequence { + public final HashSet needs = new HashSet(); + public final HashSet hates = new HashSet(); + public final HashSet hatess = new HashSet(); + public /*final*/ String tag; + public final Object[] o; + public final boolean keeper; + + public PreSequence(Object[] o, String tag) { this(o, tag, false); } + public PreSequence(Object[] o, String tag, boolean keeper) { this.o = o; this.tag = tag; this.keeper = keeper; } + boolean[] drops = null; + public Element[] expand(Element ws, Union u, HashSet set) { + if (o==null) return new Element[0]; + Element[] o2 = new Element[o.length]; + drops = new boolean[o.length]; + int j = 0; + for(int i=0; i0) { ret[i*2-1] = ws; drops2[i*2-1] = true; } + ret[i*2] = o2[i]; + drops2[i*2] = drops[i]; + } + drops = drops2; + return ret; + } + public Union buildUnion(Element ws) { + Union u = new Union("???"); + u.add(buildSequence(ws, u)); + return u; + } + public Sequence buildSequence(Element ws, Union u) { return buildSequence(ws, u, false, false); } + public Sequence buildSequence(Element ws, Union u, boolean lame, boolean dropAll) { + + HashSet and = new HashSet(); + HashSet not = new HashSet(); + for(PreSequence p : needs) { + Sequence ps = p.buildSequence(ws, u, true, dropAll); + u.add(ps); + and.add(ps); + } + for(Sequence p : hatess) not.add(p); + for(PreSequence p : hates) { + Sequence ps = p.buildSequence(ws, u, true, dropAll); + u.add(ps); + not.add(ps); + } + + HashSet set = new HashSet(); + Element[] expansion = expand(ws, u, set); + boolean keeper = this.keeper; + Sequence ret = dropAll || lame || keeper ? Sequence.drop(expansion, and, not, lame) : null; + if (ret==null && tag!=null) { + for(int i=0; i", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "*", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { })})})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "G", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})})}), + new Tree(null, "*", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { })})})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "m", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "G", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { })})})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, ":", new Tree[] { }), + new Tree(null, ":", new Tree[] { }), + new Tree(null, "=", new Tree[] { })})})}), + new Tree(null, "+/", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "C", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "t", new Tree[] { })})})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "!", new Tree[] { }), + new Tree(null, ":", new Tree[] { }), + new Tree(null, ":", new Tree[] { }), + new Tree(null, "=", new Tree[] { })})})}), + new Tree(null, "+/", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "C", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "t", new Tree[] { })})})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "c", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, "~", new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "]", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "\\", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "-", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "~", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "c", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "p", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "C", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+/", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "b", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "a", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "v", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "x", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "x", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "&", new Tree[] { })})})}), + new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "x", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "&", new Tree[] { }), + new Tree(null, "~", new Tree[] { })})})}), + new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "R", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "x", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=", new Tree[] { }), + new Tree(null, ">", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=", new Tree[] { }), + new Tree(null, ">", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "q", new Tree[] { }), + new Tree(null, "u", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=", new Tree[] { }), + new Tree(null, ">", new Tree[] { })})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "(", new Tree[] { }), + new Tree(null, ")", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "p", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "g", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "c", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "g", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "0", new Tree[] { })})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "c", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "-", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "c", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "g", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "0", new Tree[] { })})})})})})})}), + new Tree(null, "!::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "t", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, ">", new Tree[] { })})})})})})})})})}), + new Tree(null, "!::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "b", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "|", new Tree[] { })})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "n", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "T", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "m", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "Y", new Tree[] { })})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, null, new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "(", new Tree[] { })})})}), + new Tree(null, "range", new Tree[] { new Tree(null, null, new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, ")", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "p", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "n", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "{", new Tree[] { })})})}), + new Tree(null, "+/", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "C", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "t", new Tree[] { })})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "}", new Tree[] { })})})})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "[", new Tree[] { })})})}), + new Tree(null, "?", new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, null, new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "~", new Tree[] { })})})})}), + new Tree(null, "*", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "g", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "]", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { }), + new Tree(null, "g", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "*", new Tree[] { }), + new Tree(null, "/", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { }), + new Tree(null, "/", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "?", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "~", new Tree[] { }), + new Tree(null, "/", new Tree[] { }), + new Tree(null, "~", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "-", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "!", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "^", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "q", new Tree[] { }), + new Tree(null, "u", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "c", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "e", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "`", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "#", new Tree[] { })})})})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "q", new Tree[] { }), + new Tree(null, "u", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "l", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "l", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "(", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "*", new Tree[] { }), + new Tree(null, "*", new Tree[] { })})})})})})})}), + new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "*", new Tree[] { })})})})})})})})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "(", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { }), + new Tree(null, "+", new Tree[] { })})})})})})})}), + new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "E", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "+", new Tree[] { })})})})})})})})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "(", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})}), + new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, ")", new Tree[] { })})})})})})})}), + new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "care", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "(", new Tree[] { })})})}), + new Tree(null, "+/", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "C", new Tree[] { }), + new Tree(null, "l", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "s", new Tree[] { })})})}), + new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "g", new Tree[] { }), + new Tree(null, "t", new Tree[] { })})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, ")", new Tree[] { })})})})})})})})})}), + new Tree(null, "!::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, " ", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "/", new Tree[] { }), + new Tree(null, "/", new Tree[] { })})})}), + new Tree(null, "*", new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, "~", new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "\n", new Tree[] { })})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\n", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\n", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\r", new Tree[] { })})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, null, new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "-", new Tree[] { new Tree(null, "a", new Tree[] { }), + new Tree(null, "z", new Tree[] { })}), + new Tree(null, "-", new Tree[] { new Tree(null, "A", new Tree[] { }), + new Tree(null, "Z", new Tree[] { })}), + new Tree(null, "-", new Tree[] { new Tree(null, "0", new Tree[] { }), + new Tree(null, "9", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "_", new Tree[] { })})})})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "w", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "r", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "++", new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "a", new Tree[] { }), + new Tree(null, "n", new Tree[] { })})})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "s", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "f", new Tree[] { }), + new Tree(null, "y", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "q", new Tree[] { }), + new Tree(null, "u", new Tree[] { }), + new Tree(null, "o", new Tree[] { }), + new Tree(null, "t", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\"", new Tree[] { })})})}), + new Tree(null, "*", new Tree[] { new Tree(null, "(", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "range", new Tree[] { new Tree(null, "~", new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "\"", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "\\", new Tree[] { })})})})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "nonTerminalY", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "c", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "p", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})})})})})})})})})}), + new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\"", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "s", new Tree[] { }), + new Tree(null, "i", new Tree[] { }), + new Tree(null, "f", new Tree[] { }), + new Tree(null, "y", new Tree[] { })})})})})})})}), + new Tree(null, "::=", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "e", new Tree[] { }), + new Tree(null, "s", new Tree[] { }), + new Tree(null, "c", new Tree[] { }), + new Tree(null, "a", new Tree[] { }), + new Tree(null, "p", new Tree[] { }), + new Tree(null, "e", new Tree[] { }), + new Tree(null, "d", new Tree[] { })})}), + new Tree(null, null, new Tree[] { new Tree(null, "alternatives", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\\", new Tree[] { }), + new Tree(null, "n", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\n", new Tree[] { })})})}), + new Tree(null, "=>", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\\", new Tree[] { }), + new Tree(null, "r", new Tree[] { })})})})}), + new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\r", new Tree[] { })})})}), + new Tree(null, "rewrite", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "literal", new Tree[] { new Tree(null, "sify", new Tree[] { new Tree(null, null, new Tree[] { new Tree(null, "\\", new Tree[] { })})})}), + new Tree(null, "range", new Tree[] { new Tree(null, "~", new Tree[] { }), + new Tree(null, null, new Tree[] { new Tree(null, "range0", new Tree[] { new Tree(null, "n", new Tree[] { })}), + new Tree(null, "range0", new Tree[] { new Tree(null, "r", new Tree[] { })})})})})})})})})})})}), + new Tree(null, null, new Tree[] { new Tree(null, null, new Tree[] { })})}) + // DO NOT EDIT STUFF ABOVE: IT IS AUTOMATICALLY GENERATED + ; +} + + + + + + diff --git a/src/edu/berkeley/sbp/misc/ReflectiveWalker.java b/src/edu/berkeley/sbp/misc/ReflectiveWalker.java new file mode 100644 index 0000000..2334d62 --- /dev/null +++ b/src/edu/berkeley/sbp/misc/ReflectiveWalker.java @@ -0,0 +1,100 @@ +package edu.berkeley.sbp.misc; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +public class ReflectiveWalker extends StringWalker { + public ReflectiveWalker() { this.target = this; } + public ReflectiveWalker(Object target) { this.target = target; } + private final Object target; + private String normalize(String s) { + StringBuffer ret = new StringBuffer(); + for(int i=0; i= '0' && c <= '9') { ret.append('_'); ret.append(c); continue; } + switch(c) { + case ' ': ret.append("_space_"); break; + case '~': ret.append("_tilde_"); break; + case ';': ret.append("_semicolon_"); break; + case '=': ret.append("_equals_"); break; + case '-': ret.append("_minus_"); break; + case ')': ret.append("_rightparen_"); break; + case '(': ret.append("_leftparen_"); break; + case '!': ret.append("_bang_"); break; + case '`': ret.append("_backtick_"); break; + case '\"': ret.append("_quotes_"); break; + case '\'': ret.append("_quote_"); break; + case ',': ret.append("_comma_"); break; + case '.': ret.append("_dot_"); break; + case '>': ret.append("_greater_"); break; + case '<': ret.append("_less_"); break; + case '&': ret.append("_amp_"); break; + case '@': ret.append("_at_"); break; + case '#': ret.append("_hash_"); break; + case '|': ret.append("_pipe_"); break; + case '^': ret.append("_caret_"); break; + case '%': ret.append("_percent_"); break; + case '$': ret.append("_dollar_"); break; + case ':': ret.append("_colon_"); break; + case '?': ret.append("_question_"); break; + case '/': ret.append("_slash_"); break; + case '\\': ret.append("_backslash_"); break; + case '*': ret.append("_star_"); break; + case '+': ret.append("_plus_"); break; + case '_': ret.append("_underscore_"); break; + case '[': ret.append("_leftbracket_"); break; + case ']': ret.append("_rightbracket_"); break; + case '{': ret.append("_leftbrace_"); break; + case '}': ret.append("_rightbrace_"); break; + default: ret.append(c); break; + } + } + return ret.toString(); + } + 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; + Member m = member(normalize(tag), argo.length); + //System.out.println("preparing to invoke method " + (m==null ? "null" : (m.toString())) + " for sequence " + (owner()+"."+tag)); + if (m != null) return Reflection.fuzzyInvoke(target, m, argo); + if (argo.length==0) return null; + if (argo.length==1) return argo[0]; + Class c = argo[0].getClass(); + for(Object o : argo) c = Reflection.lub(c, o.getClass()); + Object[] ret = Reflection.newArray(c, argo.length); + System.arraycopy(argo, 0, ret, 0, argo.length); + return ret; + } + + public Member member(String methodName, int nonVoid) { + Class target = this.target.getClass(); + if (methodName == null || methodName.equals("")) return null; + Member ret = null; + for (Method m : target.getMethods()) { + if (!m.getName().equals(methodName)) continue; + if (m.getParameterTypes().length != nonVoid) continue; + if (ret != null) throw new Error("two methods with " + nonVoid + " parameters: " + target.getName() + "." + methodName); + ret = m; + } + if (ret != null) return ret; + Class t = target; + while(t != null) { + Class c = Reflection.forNameOrNull(t.getName() + "$" + methodName); + if (c != null) { + for (Constructor m : c.getConstructors()) { + if (m.getParameterTypes().length != nonVoid) continue; + if (ret != null) throw new Error("two constructors with " + nonVoid + " parameters: " + c.getName() + ".()"); + ret = m; + } + if (ret != null) return ret; + } + t = t.getSuperclass(); + } + if (ret != null) return ret; + throw new Error("while computing return type of " +methodName+ " could not find method with name " + methodName + + " and " + nonVoid + " arguments"); + } +} diff --git a/src/edu/berkeley/sbp/misc/RegressionTests.java b/src/edu/berkeley/sbp/misc/RegressionTests.java new file mode 100644 index 0000000..85a526b --- /dev/null +++ b/src/edu/berkeley/sbp/misc/RegressionTests.java @@ -0,0 +1,164 @@ +package edu.berkeley.sbp.misc; +import java.io.*; +import java.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.misc.*; +import edu.berkeley.sbp.*; + +// priorities are all messy and dont get serialized +// 1. Error messages +// 2. Java MetaGrammar (proof of concept) +// 3. Ivan's MetaGrammar +// 4. Documentation format +// - TIB + +// TODO: better API for interfacing with Java +// TODO: error messages +// TODO: integrate with TIB + +// Element +// Walk +// ParseTable / GSS +// MetaGrammar (necessary/relevant?) +// Tree (cleanup?) +// Union.SubUnion +// Repeat + +// FEATURE: serialization of ParseTable's, generation of Java code +// FEATURE: infer reject elements for literals +// FEATURE: prefer whitespace higher up +// FEATURE: full conjunctive and boolean grammars +// FEATURE: "ambiguity modulo dropped fragments"? can this be checked for statically? eliminated statically? +// - drop stuff during the parsing process (drop nodes) + +// LATER: Element -- parameterize over the input token type? Makes a huge mess... +// LATER: Go back to where Sequence is not an Element? +// - The original motivation for making Sequence "first class" was the fact that +// in order to do associativity right you need to have per-Sequence follow sets + +public class RegressionTests { + + public static boolean yes = false; + public static class MyWalker extends ReflectiveWalker { + public String top(Object[] o) { return "top("+join(o)+")"; } + public String str(String[] s) { String ret = ""; for(String st : s) ret += st; return ret; } + public String join(Object[] o) { String ret = ""; for(Object st : o) ret += st; return ret; } + public String whilex(Object s, Object y) { return "while("+s+") " + y; } + public String seq(Object[] statements) { + String ret = ""; + for(Object s : statements) ret += s + ";\n"; + return ret; + } + /* + public String bl(String s) { return "{" + s + "}"; } + */ + }; + + public static void main(String[] s) throws Exception { + try { + boolean profile = false; + if (s[0].equals("-profile")) { + profile = true; + String[] s2 = new String[s.length-1]; + System.arraycopy(s, 1, s2, 0, s2.length); + s = s2; + } + + Tree res = new Parser(MetaGrammar.make(), CharToken.top()).parse1(new CharToken.Stream(new InputStreamReader(new FileInputStream(s[0])))); + Union meta = ((MetaGrammar)new MetaGrammar().walk(res)).done(); + SequenceInputStream sis = new SequenceInputStream(new FileInputStream(s[0]), new FileInputStream(s[1])); + res = new Parser(meta, CharToken.top()).parse1(new CharToken.Stream(new InputStreamReader(sis), "parsing " + s[1] + " using " + s[0])); + Union testcasegrammar = ((MetaGrammar)new MetaGrammar("ts").walk(res)).done("ts"); + if (testcasegrammar==null) return; + CharToken.Stream cs = new CharToken.Stream(new InputStreamReader(new FileInputStream(s[2])), "parsing " + s[2] + " using " + s[1]); + Parser parser = new Parser(testcasegrammar, CharToken.top()); + + if (profile) { + System.out.println("\nready..."); + System.in.read(); + } + Forest r2 = parser.parse(cs); + if (profile) { + System.out.println("\ndone"); + System.in.read(); + System.exit(0); + } + for(TestCase tc : (TestCase[])new TestCaseBuilder().walk(r2.expand1())) tc.execute(); + + } catch (Throwable t) { + System.err.println("\n\nexception thrown, class == " + t.getClass().getName()); + System.err.println(t); + System.err.println(); + t.printStackTrace(); + System.err.println(); + } + } + + public static class TestCase { + public final String input; + public final String[] output; + public final Union grammar; + public TestCase(String input, String[] output, Union grammar) { + this.input = input; + this.output = output; + this.grammar = grammar; + } + public String toString() { + String ret = "testcase {\n" + " input \""+input+"\";\n"; + for(String s : output) ret += " output \""+s+"\";\n"; + ret += grammar +"\n}\n"; + return ret; + } + public boolean execute() throws Exception { + Forest res = new Parser(grammar, + CharToken.top()).parse(new CharToken.Stream(new StringReader(input), input.indexOf('\n')==-1?"\""+input+"\": ":"")); + Collection> results = res==null ? new HashSet>() : res.expand(false); + System.out.print("\r"); + if (results.size() == 0 && output.length > 0) { + System.out.print("\033[31m"); + System.out.println("PARSE FAILED"); + System.out.print("\033[0m"); + } else { + System.out.println("\r \r"); + } + HashSet outs = new HashSet(); + for(String s : output) outs.add(s.trim()); + boolean bad = false; + for (Tree r : results) { + String s = r.toString().trim(); + if (outs.contains(s)) { outs.remove(s); continue; } + System.out.print("\033[33m"); + System.out.println(" GOT: " + s); + bad = true; + } + for(String s : outs) { + System.out.print("\033[31m"); + System.out.println("EXPECTED: " + s); + bad = true; + } + if (bad) { + System.out.print("\033[0m"); + return true; + } + System.out.println("\033[32mPASS\033[0m"); + return false; + } + } + + public static class TestCaseBuilder extends MetaGrammar { + public TestCase[] ts(Object o1, TestCase[] ts, Object o2) { return ts; } + public TestCase testcase(String input, String[] output, Union grammar) { return new TestCase(input, output, grammar); } + public MetaGrammar grammar(Object[] o) { return this; } + public Object walk(String tag, Object[] args) { + if ("testcase".equals(tag)) { + if (args.length==2) return testcase((String)args[0], new String[0], (Union)args[1]); + return testcase((String)args[0], (String[])args[1], (Union)args[2]); } + else if ("grammar".equals(tag)) return done("s"); + else return super.walk(tag, args); + } + } + + private static String pad(int i,String s) { return s.length() >= i ? s : pad(i-1,s)+" "; } +} + diff --git a/src/edu/berkeley/sbp/misc/StringWalker.java b/src/edu/berkeley/sbp/misc/StringWalker.java new file mode 100644 index 0000000..923c639 --- /dev/null +++ b/src/edu/berkeley/sbp/misc/StringWalker.java @@ -0,0 +1,15 @@ +package edu.berkeley.sbp.misc; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; + +public abstract class StringWalker extends TreeWalker { + public Object walk(Tree tree) { return super.walk(tree); } + public Object walk(String tag, Object[] tokens) { + if (tokens.length==0) return tag; + if (tag==null) return null; + throw new Error("walker error: couldn't walk tag " + tag + " with " + tokens.length + " children"); + } +} diff --git a/src/edu/berkeley/sbp/misc/TreeWalker.java b/src/edu/berkeley/sbp/misc/TreeWalker.java new file mode 100644 index 0000000..38cbb81 --- /dev/null +++ b/src/edu/berkeley/sbp/misc/TreeWalker.java @@ -0,0 +1,20 @@ +package edu.berkeley.sbp.misc; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; + +public abstract class TreeWalker { + public abstract Object walk(T head, Object[] args); + public Object walk(Tree tree) { + Object[] args = new Object[tree.numChildren()]; + int i = 0; + for(Tree child : tree.children()) args[i++] = walk(child); + args = Reflection.lub(args); + return walk(tree.head(), args); + } +} diff --git a/src/edu/berkeley/sbp/package.html b/src/edu/berkeley/sbp/package.html new file mode 100644 index 0000000..b712dd9 --- /dev/null +++ b/src/edu/berkeley/sbp/package.html @@ -0,0 +1,3 @@ + +IMPORTANT: BE SURE TO READ THE FILE doc/jargon.txt FIRST! + diff --git a/src/edu/berkeley/sbp/tib/Braces.java b/src/edu/berkeley/sbp/tib/Braces.java new file mode 100644 index 0000000..74a3dab --- /dev/null +++ b/src/edu/berkeley/sbp/tib/Braces.java @@ -0,0 +1,41 @@ +package edu.berkeley.sbp.tib; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.*; +import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +public class Braces {}/*extends Union { + + private static final Element left = CharToken.string("{"); + private static final Element right = CharToken.string("}"); + + public static String join(Object[] e) { + StringBuffer ret = new StringBuffer(); + for(int i=0; i0) ret.append(" "); + ret.append(e[i]); + } + return ret.toString(); + } + + public Braces(Element[] e, Element sep) { + super("{"+join(e)+"}"); + Element[] e2 = new Element[sep == null ? e.length+2 : e.length + 4]; + e2[0] = left; + e2[e2.length-1] = right; + if (sep != null) { + e2[1] = sep; + e2[e2.length-2] = sep; + } + for(int i=0; i*/ { + /* + + private String str; + + public Tib(InputStream is) { this(new BufferedReader(new InputStreamReader(is))); } + public Tib(BufferedReader br) { + Block b = parse(br); + } + + public Token next() throws IOException { + if (pos >= str.length()) return Atom.EOF; + return Atom.fromChar(str.charAt(pos++)); + } + + public static Block parse(BufferedReader br) throws Invalid { + int row=0, col=0; + try { + boolean blankLine = false; + Block top = new Block.Root(); + for(String s = br.readLine(); s != null; s = br.readLine()) { + col = 0; + while (s.length() > 0 && + s.charAt(0) == ' ' && + (!(top instanceof Block.Literal) || col < top.col)) { col++; s = s.substring(1); } + if ((top instanceof Block.Literal) && col >= top.col) { top.add(s); continue; } + if (s.length()==0) { blankLine = true; continue; } + while (col < top.col) { + if (s.startsWith("{}") && top instanceof Block.Literal && ((Block.Literal)top).braceCol == col) break; + blankLine = false; + top = top.closeIndent(); + } + if (s.startsWith("{}")) { + int bc = col; + boolean append = top instanceof Block.Literal && ((Block.Literal)top).braceCol == bc; + s = s.substring(2); + col += 2; + while (s.length() > 0 && s.charAt(0) == ' ' && !(append && col >= top.col) ) { col++; s = s.substring(1); } + if (append) top.add(s); else (top = new Block.Literal(top, row, col, bc)).add(s); + continue; + } + while (s.length() > 0 && s.charAt(s.length()-1)==' ') { s = s.substring(0, s.length()-1); } + if (col > top.col) top = new Block.Indent(top, row, col); + else if (blankLine) { top = top.closeIndent(); top = new Block.Indent(top, row, col); } + blankLine = false; + for(int i=0; i result() { + // FIXME + } + + public Location getLocation() { return new Location.Cartesian(row, col); } + public boolean isEOF() { return false; } + + public int size() { return children.size(); } + public Object child(int i) { return children.elementAt(i); } + public boolean isLiteral() { return false; } + + protected Block(int row, int col) { this.row=row; this.col=col; parent = null; } + public Block(Block parent, int row, int col) { this.row=row; this.col=col; (this.parent = parent).add(this); } + + public void add(String s) { children.addElement(s); } + public void add(char c) { + if (c == '{' || c == '}') { finishWord(); return; } + if (c != ' ') { pending += c; return; } + if (pending.length() > 0) { finishWord(); add(" "); return; } + if (size()==0) return; + if (child(size()-1).equals(" ")) return; + add(" "); + return; + } + + public void add(Block b) { children.addElement(b); } + public Block promote() { parent.parent.replaceLast(this); return close(); } + public Object lastChild() { return children.lastElement(); } + public Block lastChildAsBlock() { return (Block)lastChild(); } + public void replaceLast(Block b) { children.setElementAt(b, children.size()-1); b.parent = this; } + + public void finishWord() { if (pending.length() > 0) { add(pending); pending = ""; } } + + public Block closeBrace() { throw new InternalException("attempt to closeBrace() a "+getClass().getName()); } + public Block closeIndent() { throw new InternalException("attempt to closeIndent() a "+getClass().getName()); } + public Block close() { + while(size() > 0 && child(size()-1).equals(" ")) children.setSize(children.size()-1); + if (size()==0) throw new InternalException("PARSER BUG: attempt to close an empty block (should never happen)"); + if (size() > 1 || !(lastChild() instanceof Block)) return parent; + return lastChildAsBlock().promote(); + } + public String toString() { return toString(80); } + public String toString(int justificationLimit) { return toString(0, 80); } + protected String toString(int indent, int justificationLimit) { + StringBuffer ret = new StringBuffer(); + StringBuffer line = new StringBuffer(); + for(int i=0; i0 && children.elementAt(i-1) instanceof Block && justificationLimit!=-1) ret.append("\n"); + if (o instanceof Block) { + ret.append(justify(line.toString(), indent, justificationLimit)); + line.setLength(0); + if (justificationLimit==-1) { + ret.append("{"); + ret.append(((Block)o).toString(indent+2, justificationLimit)); + ret.append("}"); + } else { + ret.append(((Block)o).toString(indent+2, justificationLimit)); + } + } else { + line.append(o.toString()); + } + } + ret.append(justify(line.toString(), indent, justificationLimit)); + return ret.toString(); + } + + private static class Root extends Block { + public Root() { super(0, Integer.MIN_VALUE); } + public Block close() { throw new InternalException("attempted to close top block"); } + public String toString(int justificationLimit) { return toString(-2, justificationLimit); } + } + + private static class Brace extends Block { + public Brace(Block parent, int row, int col) { super(parent, row, col); } + public Block closeBrace() { return super.close(); } + } + + private static class Indent extends Block { + public Indent(Block parent, int row, int col) { super(parent, row, col); } + public Block closeIndent() { return super.close(); } + } + + private static class Literal extends Block { + private StringBuffer content = new StringBuffer(); + public final int braceCol; + public Literal(Block parent, int row, int col, int braceCol) { super(parent,row,col); this.braceCol = braceCol; } + public boolean isLiteral() { return true; } + public int size() { return 1; } + public Object child(int i) { return i==0 ? content.toString() : null; } + public Block close() { return parent; } + public Block closeIndent() { return close(); } + public void add(String s) { if (content.length()>0) content.append('\n'); content.append(s); } + protected String toString(int indent, int justificationLimit) { + StringBuffer ret = new StringBuffer(); + String s = content.toString(); + while(s.length() > 0) { + int nl = s.indexOf('\n'); + if (nl==-1) nl = s.length(); + ret.append(spaces(indent)); + ret.append("{} "); + ret.append(s.substring(0, nl)); + s = s.substring(Math.min(s.length(),nl+1)); + ret.append('\n'); + } + return ret.toString(); + } + } + } + + + // Exceptions ////////////////////////////////////////////////////////////////////////////// + + private static class InternalException extends RuntimeException { public InternalException(String s) { super(s); } } + public static class Invalid extends IOException { + public Invalid(InternalException ie, int row, int col) { + super(ie.getMessage() + " at " + row + ":" + col); + } + } + + // Testing ////////////////////////////////////////////////////////////////////////////// + + public static void main(String[] s) throws Exception { System.out.println(parse(new Stream(System.in)).toString(-1)); } + + // Utilities ////////////////////////////////////////////////////////////////////////////// + + public static String spaces(int i) { if (i<=0) return ""; return " " + spaces(i-1); } + + private static String justify(String s, int indent, int justificationLimit) { + if (s.length() == 0) return ""; + if (justificationLimit==-1) return s; + StringBuffer ret = new StringBuffer(); + while(s.length() > 0) { + if (s.charAt(0) == ' ') { s = s.substring(1); continue; } + ret.append(spaces(indent)); + int i = s.indexOf(' '); + if (i==-1) i = s.length(); + while(s.indexOf(' ', i+1) != -1 && s.indexOf(' ', i+1) < justificationLimit-indent) i = s.indexOf(' ', i+1); + if (s.length() + indent < justificationLimit) i = s.length(); + ret.append(s.substring(0, i)); + s = s.substring(i); + ret.append('\n'); + } + return ret.toString(); + } + */ +} + diff --git a/src/edu/berkeley/sbp/tib/TibDoc.java b/src/edu/berkeley/sbp/tib/TibDoc.java new file mode 100644 index 0000000..504e3a4 --- /dev/null +++ b/src/edu/berkeley/sbp/tib/TibDoc.java @@ -0,0 +1,110 @@ +// Copyright 2005 the Contributors, as shown in the revision logs. +// Licensed under the Apache Public Source License 2.0 ("the License"). +// You may not use this file except in compliance with the License. + +package edu.berkeley.sbp.tib; +//import org.ibex.util.*; +//import org.ibex.io.*; +import java.util.*; +import java.io.*; + +public class TibDoc { + /* + public static enum Style { H, UL, TT, SO, IT, Q, B, PRE, LIST, EMDASH; } + + public static AST h(AST a) { return new Gather(a, Style.H); } + public static AST ul(AST a) { return new Gather(a, Style.UL); } + public static AST tt(AST a) { return new Gather(a, Style.TT); } + public static AST so(AST a) { return new Gather(a, Style.SO); } + public static AST it(AST a) { return new Gather(a, Style.IT); } + public static AST q(AST a) { return new Gather(a, Style.Q); } + public static AST b(AST a) { return new Gather(a, Style.B); } + public static AST pre(AST a) { return new Gather(a, Style.PRE); } + public static AST list(AST a) { return new Gather(a, Style.LIST); } + public static AST emdash() { return new Gather(Style.EMDASH); } + + public static AST seq(AST a) { return new Gather(a); } + + public static class Latex { + public static void emit(PrintWriter p, AST a) { + prefix(p); + emit(p, a, ""); + suffix(p); + } + public static void emit2(PrintWriter p, AST ast, String head) { + for(AST a = ast.getFirstChild(); a != null; a = a.getNextSibling()) emit(p, a, head); + } + public static void emit(PrintWriter p, AST ast, String head) { + if (!(ast instanceof Gather)) { + if (ast.getNumberOfChildren()==0) { + p.print(ast.getText()); + } else { + emit2(p, ast, head); + } + return; + } + Gather a = (Gather)ast; + if (a.style==null) { + emit2(p, a, head); + return; + } + switch(a.style) { + case H: p.println(); p.println(); p.print("\\"+head+"section{"); emit2(p, a, "sub"+head); p.println("}"); break; + case B: p.print("{\\bf{"); emit2(p, a, head); p.print("}}"); break; + case UL: p.print("{\\ul{"); emit2(p, a, head); p.print("}}"); break; + case IT: p.print("{\\it{"); emit2(p, a, head); p.print("}}"); break; + case TT: p.print("{\\tt{"); emit2(p, a, head); p.print("}}"); break; + case SO: p.print("{\\overstrike{"); emit2(p, a, head); p.print("}}"); break; + case Q: p.print("``"); emit2(p, a, head); p.print("''"); break; + case EMDASH: p.print(" \\emdash "); break; + case LIST: p.println(); p.println("\\startitemize[symbol]"); emit2(p, a, head); p.println("\\stopitemize"); break; + case PRE: + if (a.getFirstChild() != null) { + p.println(); + p.println("\\begin{verbatim}"); + p.println(a.getFirstChild().getText()); + p.println("\\end{verbatim}"); + } + } + } + public static void prefix(PrintWriter p) { + p.println("% generated by TIBDOC"); + for(int i=0; i implements Iterator, Iterable { + + private final T[] array; + private int i = 0; + + public ArrayIterator(T[] array) { this.array = array; } + + public void remove() { throw new Error(); } + public boolean hasNext() { return i iterator() { return this; } +} diff --git a/src/edu/berkeley/sbp/util/EmptyIterator.java b/src/edu/berkeley/sbp/util/EmptyIterator.java new file mode 100644 index 0000000..3c6d197 --- /dev/null +++ b/src/edu/berkeley/sbp/util/EmptyIterator.java @@ -0,0 +1,9 @@ +package edu.berkeley.sbp.util; +import java.util.*; + +public final class EmptyIterator implements Iterable, Iterator { + public void remove() { throw new Error(); } + public boolean hasNext() { return false; } + public T next() { throw new Error(); } + public Iterator iterator() { return this; } +} diff --git a/src/edu/berkeley/sbp/util/FastSet.java b/src/edu/berkeley/sbp/util/FastSet.java new file mode 100644 index 0000000..a433b7c --- /dev/null +++ b/src/edu/berkeley/sbp/util/FastSet.java @@ -0,0 +1,56 @@ +package edu.berkeley.sbp.util; +import java.util.*; + +public final class FastSet implements Iterator, Iterable { + + public static final int INITIAL_SIZE = 128; + + private Object[] array; + private T only = null; + private int i = 0; + private int size = 0; + + public Iterator iterator() { i=0; return this; } + public void remove() { throw new Error(); } + public boolean hasNext() { return only==null ? i s) { + if (s.size()==1) { only = s.iterator().next(); return; } + array = new Object[s.size()]; + for(T t : s) array[size++] = t; + } + + public int size() { return only==null ? size : 1; } + private void grow() { + Object[] array2 = array==null ? new Object[INITIAL_SIZE] : new Object[array.length * 2]; + if (array != null) System.arraycopy(array, 0, array2, 0, array.length); + array = array2; + if (only!=null) { + array[size++] = only; + only = null; + } + } + public void add(T t, boolean check) { + if (check) for(Object o : this) if (o.equals(t)) return; + add(t); + } + public void add(T t) { + if (array==null) { + if (only!=null) { only = t; return; } + grow(); + } else if (size>=array.length-1) { + grow(); + } + array[size++] = t; + } + + public boolean contains(T t) { + if (t==only) return true; + if (array==null) return false; + for(Object o : array) if (o==t) return true; + return false; + } +} diff --git a/src/edu/berkeley/sbp/util/HashMapBag.java b/src/edu/berkeley/sbp/util/HashMapBag.java new file mode 100644 index 0000000..5430a8f --- /dev/null +++ b/src/edu/berkeley/sbp/util/HashMapBag.java @@ -0,0 +1,26 @@ +package edu.berkeley.sbp.util; +import java.util.*; + +/** a mapping from keys of type K to sets of values of type T */ +public final class HashMapBag implements MapBag { + + private final HashMap> hm = new HashMap>(); + + public void add(K k, V v) { + HashSet hs = hm.get(k); + if (hs==null) hm.put(k, hs = new HashSet()); + hs.add(v); + } + + public void addAll(K k, Iterable iv) { + for(V v : iv) add(k, v); + } + + public HashSet getAll(K k) { + HashSet ret = hm.get(k); + if (ret==null) return new HashSet(); + return ret; + } + + public Iterator iterator() { return hm.keySet().iterator(); } +} diff --git a/src/edu/berkeley/sbp/util/IntegerTopology.java b/src/edu/berkeley/sbp/util/IntegerTopology.java new file mode 100644 index 0000000..e9f01df --- /dev/null +++ b/src/edu/berkeley/sbp/util/IntegerTopology.java @@ -0,0 +1,76 @@ +package edu.berkeley.sbp.util; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; + +/** implementation of Topology for any class for which there is a mapping to the ints */ +public class IntegerTopology implements Topology { + private final Range.Set rs; + + public Range.Set getRanges() { return rs; /*FIXME: copy?*/ } + + public IntegerTopology() { this(new Range.Set()); } + public IntegerTopology(V v) { this(v.toInt()); } + public IntegerTopology(V a, V b) { this(a.toInt(), b.toInt()); } + public IntegerTopology(int a) { this(a, a); } + public IntegerTopology(int a, int b) { this(new Range(a, b)); } + public IntegerTopology(Range r) { this(new Range.Set(r)); } + public IntegerTopology(Range.Set rs) { this.rs = rs; } + + public Topology fresh() { return new IntegerTopology(); } + public Topology dup() { return new IntegerTopology(this.rs); } + public Topology dup(Range.Set rs) { return new IntegerTopology(rs); } + + public void add(Topology t) { rs.add(((IntegerTopology)t).rs); } + public void remove(Topology t) { rs.remove(((IntegerTopology)t).rs); } + public void add(V v) { rs.add(v.toInt()); } + public void remove(V v) { rs.remove(v.toInt()); } + public boolean contains(V v) { return rs.contains(v.toInt()); } + + public Topology complement() { return dup(rs.complement()); } + public Topology intersect(Topology t) { return dup(rs.intersect(((IntegerTopology)t).rs)); } + public Topology minus(Topology t) { return dup(rs.intersect(((IntegerTopology)t).rs.complement())); } + public Topology union(Topology t) { return dup(rs.union(((IntegerTopology)t).rs)); } + public boolean disjoint(Topology t) { return rs.intersect(((IntegerTopology)t).rs).size()==0; } + public boolean containsAll(Topology t) { return rs.intersect(((IntegerTopology)t).rs).equals(((IntegerTopology)t).rs); } + + public int hashCode() { return rs.hashCode(); } + public boolean equals(Object o) { return o!=null && o instanceof IntegerTopology && ((IntegerTopology)o).rs.equals(rs); } + + // FIXME: this is currently char-range specific + /* + public String toString() { + String classname = this.getClass().getName().replace('$', '.'); + if (rs==null) return "new " + classname + "()"; + StringBuffer sb = new StringBuffer(); + sb.append("new "); + sb.append(classname); + sb.append("(new Range.Set(new Range[] { "); + for(Range r : rs) { + sb.append("new Range("); + if (r.isMinNegInf() && r.isMaxPosInf()) { + sb.append("true, true"); + } else if (r.isMinNegInf()) { + sb.append("true, "); + sb.append(r.getMax()); + } else if (r.isMaxPosInf()) { + sb.append(r.getMin()); + sb.append(", true"); + } else { + sb.append(r.getMin()); + sb.append(", "); + sb.append(r.getMax()); + } + sb.append(")"); + } + sb.append("new Range() }))"); + return sb.toString(); + } + */ + public static interface IntegerMappable { + public int toInt(); + } +} diff --git a/src/edu/berkeley/sbp/util/MapBag.java b/src/edu/berkeley/sbp/util/MapBag.java new file mode 100644 index 0000000..f1da08c --- /dev/null +++ b/src/edu/berkeley/sbp/util/MapBag.java @@ -0,0 +1,10 @@ +package edu.berkeley.sbp.util; +import java.util.*; + +/** a mapping from keys of type K to sets of values of type V */ +public interface MapBag extends Iterable { + public void add(K k, V v); + public void addAll(K k, Iterable iv); + public Iterable getAll(K k); + public Iterator iterator(); +} diff --git a/src/edu/berkeley/sbp/util/Range.java b/src/edu/berkeley/sbp/util/Range.java new file mode 100644 index 0000000..399d2bb --- /dev/null +++ b/src/edu/berkeley/sbp/util/Range.java @@ -0,0 +1,737 @@ +// Taken from com.onionnetworks.util (BSD license) +// Many thanks, Justin and Ry4an! + +/* + * Common Java Utilities + * + * Copyright (C) 2000-2001 Justin Chapweske (justin@chapweske.com) + * Copyright (C) 2000-2001 Ry4an Brase (ry4an@ry4an.org) + * Copyright (C) 2001 Onion Networks + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, + * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, + * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR + * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY + * OF SUCH DAMAGE. + */ +package edu.berkeley.sbp.util; +import java.util.*; +import java.text.*; + +/** + * This class represents a range of integers (incuding positive and negative + * infinity). + */ +public class Range { + + private boolean negInf, posInf; + private long min,max; + + /** + * Creates a new Range that is only one number, both min and max will + * equal that number. + * @param num The number that this range will encompass. + */ + public Range(long num) { + this(num,num,false,false); + } + + /** + * Creates a new Range from min and max (inclusive) + * @param min The min value of the range. + * @param max The max value of the range. + */ + public Range(long min, long max) { + this(min,max,false,false); + } + + /** + * Creates a new Range from min to postive infinity + * @param min The min value of the range. + * @param posInf Must be true to specify max == positive infinity + */ + public Range(long min, boolean posInf) { + this(min,Long.MAX_VALUE,false,posInf); + if (!posInf) { + throw new IllegalArgumentException("posInf must be true"); + } + } + + /** + * Creates a new Range from negative infinity to max. + * @param negInf Must be true to specify min == negative infinity + * @param max The max value of the range. + */ + public Range(boolean negInf, long max) { + this(Long.MIN_VALUE,max,negInf,false); + if (!negInf) { + throw new IllegalArgumentException("negInf must be true"); + } + } + + /** + * Creates a new Range from negative infinity to positive infinity. + * @param negInf must be true. + * @param posInf must be true. + */ + public Range(boolean negInf, boolean posInf) { + this(Long.MIN_VALUE,Long.MAX_VALUE,negInf,posInf); + if (!negInf || !posInf) { + throw new IllegalArgumentException + ("negInf && posInf must be true"); + } + } + + private Range(long min, long max, boolean negInf, boolean posInf) { + if (min > max) { + throw new IllegalArgumentException + ("min cannot be greater than max"); + } + // very common bug, its worth reporting for now. + if (min == 0 && max == 0) { + System.err.println("Range.debug: 0-0 range detected. "+ + "Did you intend to this? :"); + new Exception().printStackTrace(); + } + this.min = min; + this.max = max; + this.negInf = negInf; + this.posInf = posInf; + } + + /** + * @return true if min is negative infinity. + */ + public boolean isMinNegInf() { + return negInf; + } + + /** + * @return true if max is positive infinity. + */ + public boolean isMaxPosInf() { + return posInf; + } + + /** + * @return the min value of the range. + */ + public long getMin() { + return min; + } + + /** + * @return the max value of the range. + */ + public long getMax() { + return max; + } + + /** + * @return The size of the range (min and max inclusive) or -1 if the range + * is infinitly long. + */ + public long size() { + if (negInf || posInf) { + return -1; + } + return max-min+1; + } + + /** + * @param i The integer to check to see if it is in the range. + * @return true if i is in the range (min and max inclusive) + */ + public boolean contains(long i) { + return i >= min && i <= max; + } + + /** + * @param r The range to check to see if it is in this range. + * @return true if this range contains the entirety of the passed range. + */ + public boolean contains(Range r) { + return r.min >= min && r.max <= max; + } + + + public int hashCode() { + return (int) (min + 23 * max); + } + + public boolean equals(Object obj) { + if (obj instanceof Range && + ((Range) obj).min == min && ((Range) obj).max == max && + ((Range) obj).negInf == negInf && ((Range) obj).posInf == posInf) { + return true; + } else { + return false; + } + } + + public String toString() { + if (!negInf && !posInf && min == max) { + return new Long(min).toString(); + } else { + return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max); + } + } + + /** + * This method creates a new range from a String. + * Allowable characters are all integer values, "-", ")", and "(". The + * open and closed parens indicate positive and negative infinity. + * 
+     * Example strings would be:
+     * "11" is the range that only includes 11
+     * "-6" is the range that only includes -6
+     * "10-20" is the range 10 through 20 (inclusive)
+     * "-10--5" is the range -10 through -5
+     * "(-20" is the range negative infinity through 20
+     * "30-)" is the range 30 through positive infinity.
+     *
+ * @param s The String to parse + * @return The resulting range + * @throws ParseException, + */ + + public static final Range parse(String s) throws ParseException { + try { + long min=0,max=0; + boolean negInf=false,posInf=false; + // search from the 1 pos because it may be a negative number. + int dashPos = s.indexOf("-",1); + if (dashPos == -1) { // no dash, one value. + min = max = Long.parseLong(s); + } else { + if (s.indexOf("(") != -1) { + negInf = true; + } else { + min = Long.parseLong(s.substring(0,dashPos)); + } + if (s.indexOf(")") != -1) { + posInf = true; + } else { + max = Long.parseLong(s.substring(dashPos+1,s.length())); + } + } + if (negInf) { + if (posInf) { + return new Range(true,true); + } else { + return new Range(true,max); + } + } else if (posInf) { + return new Range(min,true); + } else { + return new Range(min,max); + } + } catch (RuntimeException e) { + throw new ParseException(e.getMessage(),-1); + } + } + + + /** + * This class represents a set of integers in a compact form by using ranges. + * This is essentially equivilent to run length encoding of a bitmap-based + * set and thus works very well for sets with long runs of integers, but is + * quite poor for sets with very short runs. + * + * This class is similar in flavor to Perl's IntSpan at + * http://world.std.com/~swmcd/steven/perl/lib/Set/IntSpan/ + * + * The Ranges use negative and positive infinity so there should be no + * border issues with standard set operations and they should behave + * exactly as you'd expect from your set identities. + * + * While the data structure itself should be quite efficient for its intended + * use, the actual implementation could be heavily optimized beyond what I've + * done, feel free to improve it. + * + * @author Justin F. Chapweske + */ + public static class Set implements Iterable { + + public static final int DEFAULT_CAPACITY = 16; + + boolean posInf, negInf; + int rangeCount; + long[] ranges; + + /** + * Creates a new empty Range.Set + */ + public Set() { + ranges = new long[DEFAULT_CAPACITY * 2]; + } + + /** + * Creates a new Range.Set and adds the provided Range + * @param r The range to add. + */ + public Set(Range r) { + this(); + add(r); + } + + public Set(Range[] ranges) { + this(); + for(Range r : ranges) add(r); + } + + /** + * @param rs The set with which to union with this set. + * @return A new set that represents the union of this and the passed set. + */ + public Range.Set union(Range.Set rs) { + // This should be rewritten to interleave the additions so that there + // is fewer midlist insertions. + Range.Set result = new Range.Set(); + result.add(this); + result.add(rs); + return result; + } + + /** + * @param rs The set with which to intersect with this set. + * @return new set that represents the intersct of this and the passed set. + */ + public Range.Set intersect(Range.Set rs) { + Range.Set result = complement(); + result.add(rs.complement()); + return result.complement(); + } + + /** + * @return The complement of this set, make sure to check for positive + * and negative infinity on the returned set. + */ + public Range.Set complement() { + Range.Set rs = new Range.Set(); + if (isEmpty()) { + rs.add(new Range(true,true)); + } else { + if (!negInf) { + rs.add(new Range(true,ranges[0]-1)); + } + for (int i=0;i 0) { + return true; + } + pos = -(pos+1); + if (pos % 2 == 0) { + return false; + } else { + return true; + } + } + + /** + * //FIX unit test + * Checks to see if this set contains all of the elements of the Range. + * + * @param r The Range to see if this Range.Set contains it. + * @return true If every element of the Range is within this set. + */ + public boolean contains(Range r) { + Range.Set rs = new Range.Set(); + rs.add(r); + return intersect(rs).equals(rs); + } + + /** + * Add all of the passed set's elements to this set. + * + * @param rs The set whose elements should be added to this set. + */ + public void add(Range.Set rs) { + for (Iterator it=rs.iterator();it.hasNext();) { + add((Range) it.next()); + } + } + + + /** + * Add this range to the set. + * + * @param r The range to add + */ + public void add(Range r) { + if (r.isMinNegInf()) { + negInf = true; + } + if (r.isMaxPosInf()) { + posInf = true; + } + add(r.getMin(),r.getMax()); + } + + /** + * Add a single integer to this set. + * + * @param i The int to add. + */ + public void add(long i) { + add(i,i); + } + + /** + * Add a range to the set. + * @param min The min of the range (inclusive) + * @param max The max of the range (inclusive) + */ + public void add(long min, long max) { + + if (min > max) { + throw new IllegalArgumentException + ("min cannot be greater than max"); + } + + if (rangeCount == 0) { // first value. + insert(min,max,0); + return; + } + + // This case should be the most common (insert at the end) so we will + // specifically check for it. Its +1 so that we make sure its not + // adjacent. Do the MIN_VALUE check to make sure we don't overflow + // the long. + if (min != Long.MIN_VALUE && min-1 > ranges[(rangeCount-1)*2+1]) { + insert(min,max,rangeCount); + return; + } + + // minPos and maxPos represent inclusive brackets around the various + // ranges that this new range encompasses. Anything within these + // brackets should be folded into the new range. + int minPos = getMinPos(min); + int maxPos = getMaxPos(max); + + // minPos and maxPos will switch order if we are either completely + // within another range or completely outside of any ranges. + if (minPos > maxPos) { + if (minPos % 2 == 0) { + // outside of any ranges, insert. + insert(min,max,minPos/2); + } else { + // completely inside a range, nop + } + } else { + combine(min,max,minPos/2,maxPos/2); + } + + } + + public void remove(Range.Set r) { + for (Iterator it=r.iterator();it.hasNext();) { + remove((Range) it.next()); + } + } + + public void remove(Range r) { + //FIX absolutely horrible implementation. + Range.Set rs = new Range.Set(); + rs.add(r); + rs = intersect(rs.complement()); + ranges = rs.ranges; + rangeCount = rs.rangeCount; + posInf = rs.posInf; + negInf = rs.negInf; + } + + public void remove(long i) { + remove(new Range(i,i)); + } + + public void remove(long min, long max) { + remove(new Range(min,max)); + } + + /** + * @return An iterator of Range objects that this Range.Set contains. + */ + public Iterator iterator() { + ArrayList l = new ArrayList(rangeCount); + for (int i=0;i=0;i--) { + if (arr1[start1+i] != arr2[start2+i]) { + return false; + } + } + return true; + } + + public static boolean arraysEqual(long[] arr1, int start1, + long[] arr2, int start2, int len) { + if (arr1 == arr2 && start1 == start2) { + return true; + } + for (int i=len-1;i>=0;i--) { + if (arr1[start1+i] != arr2[start2+i]) { + return false; + } + } + return true; + } + + public static boolean arraysEqual(char[] arr1, int start1, + char[] arr2, int start2, int len) { + if (arr1 == arr2 && start1 == start2) { + return true; + } + for (int i=len-1;i>=0;i--) { + if (arr1[start1+i] != arr2[start2+i]) { + return false; + } + } + return true; + } + + public static boolean arraysEqual(byte[] arr1, int start1, + byte[] arr2, int start2, int len) { + if (arr1 == arr2 && start1 == start2) { + return true; + } + for (int i=len-1;i>=0;i--) { + if (arr1[start1+i] != arr2[start2+i]) { + return false; + } + } + return true; + } + + + /** + * Outputs the Range in a manner that can be used to directly create + * a new range with the "parse" method. + */ + public String toString() { + StringBuffer sb = new StringBuffer(); + for (Iterator it=iterator();it.hasNext();) { + sb.append(it.next().toString()); + if (it.hasNext()) { + sb.append(","); + } + } + return sb.toString(); + } + + public Object clone() { + Range.Set rs = new Range.Set(); + rs.ranges = new long[ranges.length]; + System.arraycopy(ranges,0,rs.ranges,0,ranges.length); + rs.rangeCount = rangeCount; + rs.posInf = posInf; + rs.negInf = negInf; + return rs; + } + + private void combine(long min, long max, int minRange, int maxRange) { + // Fill in the new values into the "leftmost" range. + ranges[minRange*2] = Math.min(min,ranges[minRange*2]); + ranges[minRange*2+1] = Math.max(max,ranges[maxRange*2+1]); + + // shrink if necessary. + if (minRange != maxRange && maxRange != rangeCount-1) { + System.arraycopy(ranges,(maxRange+1)*2,ranges,(minRange+1)*2, + (rangeCount-1-maxRange)*2); + } + + rangeCount -= maxRange-minRange; + } + + + /** + * @return the position of the min element within the ranges. + */ + private int getMinPos(long min) { + // Search for min-1 so that adjacent ranges are included. + int pos = binarySearch(min == Long.MIN_VALUE ? min : min-1); + return pos >= 0 ? pos : -(pos+1); + } + + /** + * @return the position of the max element within the ranges. + */ + private int getMaxPos(long max) { + // Search for max+1 so that adjacent ranges are included. + int pos = binarySearch(max == Long.MAX_VALUE ? max : max+1); + // Return pos-1 if there isn't a direct hit because the max + // pos is inclusive. + return pos >= 0 ? pos : (-(pos+1))-1; + } + + /** + * @see java.util.Arrays#binarySearch + */ + private int binarySearch(long key) { + int low = 0; + int high = (rangeCount*2)-1; + + while (low <= high) { + int mid =(low + high)/2; + long midVal = ranges[mid]; + + if (midVal < key) { + low = mid + 1; + } else if (midVal > key) { + high = mid - 1; + } else { + return mid; // key found + } + } + return -(low + 1); // key not found. + } + + private void insert(long min, long max, int rangeNum) { + + // grow the array if necessary. + if (ranges.length == rangeCount*2) { + long[] newRanges = new long[ranges.length*2]; + System.arraycopy(ranges,0,newRanges,0,ranges.length); + ranges = newRanges; + } + + if (rangeNum != rangeCount) { + System.arraycopy(ranges,rangeNum*2,ranges,(rangeNum+1)*2, + (rangeCount-rangeNum)*2); + } + ranges[rangeNum*2] = min; + ranges[rangeNum*2+1] = max; + rangeCount++; + } + + /* + public static final void main(String[] args) throws Exception { + Range.Set rs = Range.Set.parse("5-10,15-20,25-30"); + BufferedReader br = new BufferedReader(new InputStreamReader + (System.in)); + while (true) { + System.out.println(rs.toString()); + String s = br.readLine(); + if (s.charAt(0) == '~') { + rs = rs.complement(); + } else if (s.charAt(0) == 'i') { + rs = rs.intersect(Range.Set.parse(br.readLine())); + } else { + rs.add(Range.Set.parse(s)); + } + } + } + */ + } +} + diff --git a/src/edu/berkeley/sbp/util/Reflection.java b/src/edu/berkeley/sbp/util/Reflection.java new file mode 100644 index 0000000..cf683f0 --- /dev/null +++ b/src/edu/berkeley/sbp/util/Reflection.java @@ -0,0 +1,122 @@ +package edu.berkeley.sbp.util; +import java.io.*; +import java.lang.reflect.*; + +/** Random reflection-related utilities */ +public final class Reflection { + + private static Object rebuild(Object o, Class c) { + //System.out.println("rebuild " + o + " (a " + (o==null?null:o.getClass().getName()) + ") " + c); + if (o==null || c.isAssignableFrom(o.getClass())) return o; + if ((c == Character.class || c == Character.TYPE) && o instanceof String && ((String)o).length()==1) return new Character(((String)o).charAt(0)); + if (o instanceof Character && c == String.class) return o+""; + if (o instanceof Object[]) { + Object[] a = (Object[])o; + if (c.isArray()) { + Object[] ret = (Object[])Array.newInstance(c.getComponentType(), a.length); + for(int i=0; iClass.forName that returns null instead of throwing an exception */ + public static Class forNameOrNull(String s) { + try { + return Class.forName(s); + } catch (ClassNotFoundException _) { + return null; + } + } + + /** invoke method/constructor m on object o with arguments args, and perform reasonable coercions as needed */ + public static Object fuzzyInvoke(Object o, Member m, Object[] args) { + try { + Class[] argTypes = m instanceof Method ? ((Method)m).getParameterTypes() : ((Constructor)m).getParameterTypes(); + boolean ok = true; + Object[] args2 = new Object[args.length]; + System.arraycopy(args, 0, args2, 0, args.length); + args = args2; + for(int i=0; i " + zoo(args[i])); + } else { + System.out.println(" arg => " + args[i] + (args[i]==null?"":(" (a " + args[i].getClass().getName() + ")"))); + } + } + */ + // FIXME: deal with the case where it is an inner class ctor + return m instanceof Method ? ((Method)m).invoke(o, args) : ((Constructor)m).newInstance(args); + } catch (Exception e) { + throw new RuntimeException(e); + } + } + + private static String zoo(Object o) { + if (o==null) return "null"; + if (o instanceof Object[]) { + String ret = "[ "; + for(int j=0; j<((Object[])o).length; j++) + ret += zoo(((Object[])o)[j]) + " "; + return ret+"]"; + } + return o+""; + } + +} diff --git a/src/edu/berkeley/sbp/util/StringUtil.java b/src/edu/berkeley/sbp/util/StringUtil.java new file mode 100644 index 0000000..fc8f8e1 --- /dev/null +++ b/src/edu/berkeley/sbp/util/StringUtil.java @@ -0,0 +1,58 @@ +package edu.berkeley.sbp.util; + +/** miscellaneous string utilities */ +public class StringUtil { + public static String toJavaString(String s) { + StringBuffer sb = new StringBuffer(); + for(int i=0; iK to sets of values of type V */ +public class TopologicalBag implements MapBag,V> { + + // CRUCIAL INVARIANT: keys in this hashmap MUST be disjoint or the universe will implode + private final HashMap,HashSet> h = new HashMap,HashSet>(); + + public Iterator> iterator() { return h.keySet().iterator(); } + + public void addAll(TopologicalBag tb) { + for(Topology k : tb) + addAll(k, tb.getAll(k)); + } + + public void add(Topology t, V v) { put(t, v); } + public void addAll(Topology k, Iterable vi) { putAll(k, vi); } + + public void putAll(Topology k, Iterable vi) { for(V v : vi) put(k, v); } + public void put(Topology t, V v) { + for(Topology ht : h.keySet()) { + if (t.disjoint(ht)) continue; + if (t.equals(ht)) { + h.get(ht).add(v); + return; + } + if (ht.containsAll(t)) { + HashSet v0 = h.get(ht); + HashSet v1 = new HashSet(); + v1.addAll(v0); + h.remove(ht); + v1.add(v); + h.put(ht.intersect(t), v1); + h.put(ht.minus(t), v0); + return; + } + put(t.intersect(ht), v); + put(t.minus(ht), v); + return; + } + HashSet v1 = new HashSet(); + v1.add(v); + h.put(t, v1); + } + + + public TopologicalBag subset(Topology t) { + TopologicalBag ret = new TopologicalBag(); + for(Topology ht : h.keySet()) { + if (ht.disjoint(t)) continue; + ret.putAll(ht.intersect(t), h.get(ht)); + } + return ret; + } + + public Map,HashSet> gett(Topology t) { + HashMap,HashSet> ret = new HashMap,HashSet>(); + for(Topology ht : h.keySet()) { + if (ht.disjoint(t)) continue; + ret.put(ht.intersect(t), h.get(ht)); + } + return ret; + } + + public boolean empty(K k) { + for(Topology t : h.keySet()) + if (t.contains(k) && h.get(t).size() > 0) + return false; + return true; + } + + public boolean contains(K k) { return get(k).iterator().hasNext(); } + + public boolean contains(K k, V v) { + for(Topology t : h.keySet()) + if (t.contains(k)) + return h.get(t).contains(v); + return false; + } + + private HashMap> cache = new HashMap>(); + public Iterable getAll(Topology k) { return h.get(k); } + public Iterable get(K k) { + Iterable c = cache.get(k); + if (c != null) return c; + HashSet ret = null; + HashSet ret0 = null; + for(Topology t : h.keySet()) + if (t.contains(k)) { + if (ret==null) { + ret0 = ret = h.get(t); + } else { + if (ret0 != null) { + ret = new HashSet(); + ret.addAll(ret0); + ret0 = null; + } + ret.addAll(h.get(t)); + } + } + if (ret==null) { + cache.put(k, emptyIterator); + return emptyIterator; + } else { + cache.put(k, new FastSet(ret)); + return ret; + } + } + private final Iterable emptyIterator = new EmptyIterator(); +} diff --git a/src/edu/berkeley/sbp/util/Topology.java b/src/edu/berkeley/sbp/util/Topology.java new file mode 100644 index 0000000..4f36f08 --- /dev/null +++ b/src/edu/berkeley/sbp/util/Topology.java @@ -0,0 +1,29 @@ +package edu.berkeley.sbp.util; +import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.*; +import java.io.*; +import java.util.*; +import java.lang.reflect.*; +import java.lang.ref.*; + +// FIXME: this should be a value class -- add/remove/etc should return new Topology objects +/** values inhabiting a topology over V (roughly, infinite sets of V's equipped with union/intersection/complement) */ +public interface Topology { + + public void add(Topology t); + public void add(V t); + public void remove(Topology t); + public void remove(V t); + public Topology dup(); + public boolean contains(V v); + public Topology fresh(); + + public Topology intersect(Topology t); + public Topology minus(Topology t); + public Topology union(Topology t); + public boolean disjoint(Topology t); + public boolean containsAll(Topology t); + + public abstract int hashCode(); + public abstract boolean equals(Object o); +} diff --git a/tests/meta.g b/tests/meta.g new file mode 100644 index 0000000..0920a7a --- /dev/null +++ b/tests/meta.g @@ -0,0 +1,54 @@ +s ::= w* Grammar w* => "gram" +Grammar ::= R+ => "grammar" +R ::= word ^"::=" Class+/gt + | word ^"!::=" Class+/gt + +ec ::= [~\]\\\-\~] | escaped + +Class ::= Rewrite +/ bar => "alternatives" + +Rewrite ::= Rewritex + | Rewritex ^"&" E+ + | Rewritex ^"&~" E+ + +Rewritex ::= E+ => "rewrite" + | E+ ^"=>" word + | E+ ^"=>" quoted + | E+ "=>" "()" => "wrap" + +range ::= ec => "range0" | ec ^"-" ec => "range0" +gt !::= ">" +bar !::= "|" +E ::= word => "nonTerminalY" + | [(][)] => "epsilon" + | ^"{" Class+/gt "}" + | "[" [\~]? range* "]" => "range" + | E ^"*/" E + | E ^"+/" E + | E ^"?" + | E ^"~/~" + + | E ^"-" E + + | ^"!" E + | "^" quoted => "care" + | ^"`" E + | E ^"#" + | quoted => "literal" + + | (E ^"**" > E ^"*") + | (E ^"++" > E ^"+") + + | "(" word ^")" + > ^"(" Class+/gt ")" + +w !::= " " + | "//" [~\n]* "\n" + | "\n" + | "\r" +an ::= [a-zA-Z0-9_] +word ::= an++ => "sify" +quoted ::= "\"" ([~\"\\] | escaped)* "\"" => "sify" +escaped ::= "\\n" => "\n" + | "\\r" => "\r" + | "\\" [~nr] diff --git a/tests/regression.tc b/tests/regression.tc new file mode 100644 index 0000000..040bf84 --- /dev/null +++ b/tests/regression.tc @@ -0,0 +1,305 @@ +//testcase { +// input "x"; +// output "a1:{x}"; +// +// s ::= a => a1 +// a ::= s => s1 +// a ::= ^"x" +//} +// +//testcase { +// input "x"; +// output "x"; +// output "s2:{s2:{s0 s0} x}"; +// output "s2:{s0 x}"; +// +// +// s ::= s s => s2 +// s ::= ^"x" +// s ::= () => s0 +//} + +testcase { + input "ab c"; + output "1:{{a b} {c}}"; + + s ::= ids + ids ::= id (" " ids &~ id [~]*) => "1" + | id ( ids &~ id [~]*) => "2" + | id + id ::= [a-z]++ +} + +testcase { + input "ab c"; + + output "2:{{a} 1:{{b} {c}}}"; + output "1:{{a b} {c}}"; + + s ::= ids + ids ::= id " " ids => "1" + | id ids => "2" + | id + id ::= [a-z]+ +} + +testcase { + input "aaabbbccc"; + output ""; + + s ::= ab & dc + ab ::= a b + dc ::= d c + a ::= "a" a | () + b ::= "b" b "c" | () + c ::= "c" c | () + d ::= "a" d "b" | () +} + +testcase { + input "aaabbbbccc"; + + s ::= ab & dc + ab !::= a b + dc !::= d c + a ::= "a" a | () + b ::= "b" b "c" | () + c ::= "c" c | () + d ::= "a" d "b" | () +} + +testcase { + input "12111211"; + output "ac:{{2 1 2 1}}"; + //output "a:{{2 1 2 1}}"; + //output "c:{{c:{1 1} c:{1 1}}}"; + + s ::= ab => "ab" + | ac => "ac" + | bc => "bc" + //| a => "a" + //| b => "b" + //| c => "c" + ab ::= a & b + ac ::= a & c + bc ::= b & c + a ::= ("1" x)* + b ::= (x "2" => "b")* + c ::= (x "2" x "1" => "c")* + x ::= [123] +} + +testcase { + input "xbambambam"; + output "bam:{a bam:{a bam:{a x}}}"; + + s ::= a s ^"bam" + s ::= ^"x" + a ::= () => "a" +} + +testcase { + input "baaaa"; + output "s2:{b0 a:{a:{epsilon}}}"; + output "b:{a:{a:{epsilon}} epsilon}"; + s ::= b t => "s2" + | ^"b" t b + t ::= ^"a" t "a" + | () => "epsilon" + b ::= "b" => "b0" + | () => "epsilon" +} + +testcase { + input "qaq"; + output "q:{a:{s1:{epsilon}}}"; + + s ::= ^"q" x "q" + x ::= ^"a" a + x ::= () => "epsilon" + a ::= x => "s1" +} + +testcase { + input "baa"; + output "s1:{a2:{a2:{a0 b0} b0}}"; + + s ::= "b" a => "s1" + a ::= "a" a b => "a2" + | () => "a0" + b ::= () => "b0" +} + +testcase { + input "aaa"; + + output "s3:{s3:{epsilon a0 epsilon epsilon} epsilon epsilon epsilon}"; + output "s3:{s3:{epsilon epsilon epsilon epsilon} a0 epsilon epsilon}"; + output "s3:{s3:{epsilon epsilon a0 epsilon} epsilon epsilon epsilon}"; + output "s3:{s3:{epsilon epsilon epsilon a0} epsilon epsilon epsilon}"; + output "s3:{epsilon epsilon a0 a0}"; + output "s3:{s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon epsilon} epsilon epsilon epsilon}"; + output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon a0}"; + output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon a0 epsilon}"; + output "s3:{epsilon a0 epsilon a0}"; + output "s3:{epsilon a0 a0 epsilon}"; + + s ::= "a" s a a a => "s3" + | () => "epsilon" + a ::= "a" => "a0" + | () => "epsilon" +} + +testcase { + input "aa"; + output "poo:{poo:{poox poox} poox}"; + output "poo:{poox poo:{poox poox}}"; + s ::= s s "a" => "poo" + s ::= () => "poox" +} + +testcase { + input "baa"; + output "s:{aa:{aa:{a b} b}}"; + s ::= "b" a => "s" + a ::= "a" a b => "aa" + a ::= () => "a" + b ::= () => "b" +} + +testcase { + input "aaab"; + output "sx:{b aa:{aa:{b b} b}}"; + s ::= b d "a" "b" => "sx" + s ::= "a" d "a" d => "sy" + d ::= "a" a b => "aa" + a ::= "a" b b => "aa" + a ::= () => "a" + b ::= () => "b" +} + +testcase { + input "a+(b*c)"; + output "+:{{a} *:{{b} {c}}}"; + + s ::= R + R ::= id + | R ^"*" R + | R ^"+" R + | "(" R ")" + id ::= [a-z]++ +} + +testcase { + input "a+b-d*c"; + output "plus:{stringify:{{a}} minus:{stringify:{{b}} times:{stringify:{{d}} stringify:{{c}}}}}"; + output "times:{plus:{stringify:{{a}} minus:{stringify:{{b}} stringify:{{d}}}} stringify:{{c}}}"; + output "plus:{stringify:{{a}} times:{minus:{stringify:{{b}} stringify:{{d}}} stringify:{{c}}}}"; + output "times:{minus:{plus:{stringify:{{a}} stringify:{{b}}} stringify:{{d}}} stringify:{{c}}}"; + output "minus:{plus:{stringify:{{a}} stringify:{{b}}} times:{stringify:{{d}} stringify:{{c}}}}"; + s ::= S + w ::= " " + L ::= id + S ::= L "=" Q => "assign" + | Q + Q ::= id + | L "=" Q => "assign" + | Q "-" Q => "minus" + | Q "+" Q => "plus" + | Q "*" Q => "times" + | "(" Q ")" + id ::= idl++ => "stringify" + idl ::= [a-d] +} + +testcase { + input "a*b*c"; + output "times:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}"; + s ::= S + w ::= " " + L ::= id + S ::= L "=" R => "assign" + | R + R ::= L + | L "=" R => "assign" + | R "+" R => "plus" + | (R) "*" R => "times" + | "(" R ")" + | R R => "times" + id ::= idl++ => "stringify" + idl ::= [a-d] +} + +testcase { + input "a+b*c"; + output "plus:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}"; + s ::= S + w ::= " " + L ::= id + S ::= L "=" R => "assign" + | R + R ::= L + | L "=" R => "assign" + | R "+" R => "plus" + > R "*" R => "times" + | "(" R ")" + | R R => "times" + id ::= idl++ => "stringify" + idl ::= [a-d] +} + +testcase { + + input " + + + while x>0 + while y>0 + foo() + bar() + + while x>0 + while y>0 + foo() + bar() + + +"; + output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}}}"; + output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}"; + +indent !::= ww +outdent !::= " " outdent " " + | " " [~]* "\n" + +any !::= [~]* +s ::= !any "\n\n" !ww Statement !ww "\n\n" !any => smt +ww ::= sp* +sp ::= " " + +block ::= "\n" !indent BlockBody + &~ "\n" outdent [~\ ] [~]* + +BlockBody ::= Statement + > Statement BlockBody => "sbb" + +Statement ::= Call + | ^"while" Expr block + +Expr ::= ident + | Call + | Expr ^">" Expr + | num + +Call ::= Expr "()" + +num ::= [0-9]++ + +ident ::= [a-z]++ &~ keyword +keyword ::= "if" | "then" | "else" | "while" + +w ::= " " | "\n" | "\r" +ws ::= w* + + +} diff --git a/tests/testcase.g b/tests/testcase.g new file mode 100644 index 0000000..9993dce --- /dev/null +++ b/tests/testcase.g @@ -0,0 +1,7 @@ +ts ::= ws Ts ws => ts +Ts ::= Test* +ws !::= w* +Test ::= ^"testcase" "{" Input Output+ Grammar "}" + | ^"testcase" "{" Input Grammar "}" +Output ::= "output" quoted ";" +Input ::= "input" quoted ";"