--- /dev/null
+* 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.
--- /dev/null
+
+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 '<html><head><meta HTTP-EQUIV="Refresh" CONTENT="0;URL=doc/sbp.html"></head></html>' > index.html
+ rsync -are ssh --progress --verbose --delete ./ argus.cs.berkeley.edu:public_html/sbp/
--- /dev/null
+==============================================================================
+Scannerless Boolean Parser
+
+Adam Megacz <megacz@cs.berkeley.edu>
+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.
--- /dev/null
+
+______________________________________________________________________________
+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.
--- /dev/null
+______________________________________________________________________________
+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<String> (Trees of Strings); it
+can be generalized to Tree<X> where X maps onto Strings (ie
+Tree<Number>, 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
+
+
--- /dev/null
+<html>
+<head><title>The Scannerless Boolean Parser (SBP)</title>
+<style>
+
+ H1 {
+ margin-left: -20px;
+ margin-top: 30px;
+ font-family: helvetica, verdana, arial, sans-serif;
+ font-size: 14pt;
+ font-weight: bold;
+ text-align: left;
+ width : 100%;
+ border-top-width: 2pt;
+ border-top-style: solid;
+ }
+
+ H2 {
+ font-family: helvetica, verdana, arial, sans-serif;
+ font-size: 12pt;
+ font-weight: bold;
+ }
+
+ H3 {
+ margin-left: -10px;
+ font-family: helvetica, verdana, arial, sans-serif;
+ font-size: 12pt;
+ font-weight: bold;
+ }
+
+ TH, TD, P, LI {
+ font-family: helvetica, verdana, arial, sans-serif;
+ font-size: 13px;
+ text-decoration:none;
+ }
+
+ LI { margin-top: 5px; }
+
+</style>
+</head>
+<body>
+<center><table><tr><td width=600>
+
+<center>
+<font style='font-size:24pt; font-family:helvetica, verdana, arial, sans-serif'>
+<b>SBP: the Scannerless Boolean Parser</b></font>
+</center>
+
+<h1>What is it?</h1>
+
+The Scannerless Boolean Parser (SBP) is a scannerless parser for <a
+href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
+grammars</a> (a superset of context-free grammars). It is written in
+Java and emits Java source code.
+
+<h1>What is interesting about it?</h1>
+
+SBP deliberately sacrifices performance in favor of ease of extensibility.
+<p>
+
+Since it is an implementation of the (modified) <a
+href=http://www.program-transformation.org/Sdf/GeneralizedLR>Lang-Tomita
+GLR algorithm</a>, SBP supports all context-free languages.
+<p>
+
+It is <a
+href=http://en.wikipedia.org/wiki/Lexerless_parsing>scannerless</a>
+(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.
+<p>
+
+In addition to the juxtaposition and union operators provided in
+context-free languages, JTP supports grammars which use the
+intersection operator (<a
+href=http://www.cs.queensu.ca/home/okhotin/conjunctive/>conjunctive
+grammars</a>) and the complement operator (<a
+href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
+grammars</a>).
+
+<h1>What features does it have?</h1>
+
+Features fully implemented are in <font color=green>green</font>;
+those partially implemented are in <font color=orange>orange</font>;
+those unimplemented (but planned) are in <font color=red>red</font>.
+
+<ul> <li> <b>An implementation of the Lang-Tomita GLR parsing algorithm</b>
+ <ul>
+ <li> Including <font color=green>Johnstone & Scott's RNGLR algorithm</font> for epsilon-productions</a>
+
+ <li> <a href=http://citeseer.ist.psu.edu/vandenbrand02disambiguation.html><font color=green>Visser's</font> extensions</a>
+ for <font color=green>scannerless parsing</font>
+ <ul> <li> <font color=green>Follow</font>, <font color=green>Avoid, Prefer</font>, <font color=green>Reject</font> constraints
+ <li> <font color=green>Character ranges</font>
+ <li> Automatic insertion of <font color=green>whitespace/comments</font>
+ </ul>
+
+ <li> <font color=green>Any topological space</font> can be
+ used as an alphabet (need not be discrete)
+ <ul> <li> <font color=green>Unicode</font>
+ <li> <font color=orange>Trees</font>
+ </ul>
+
+ <li> <font color=green>Associativity constraints</font> on <font color=green><i>n</i>-ary operators</font>
+
+ </ul>
+
+ <li> <b>Ability to parse a wide variety of grammars in
+ </b> O(n<sup>3</sup>) time:
+
+ <ul>
+ <li> <font color=green>all context-free grammars</font>
+
+ <li> <font color=green>epsilon productions</font>, <font
+ color=green>included in the parse forest</font>
+
+ <li> <font color=green>circularities</font>, <font
+ color=red>included in the parse forest</font>.
+
+ <li> Regular expression operators (
+ <tt><font color=green>*</font></tt>,
+ <tt><font color=green>?</font></tt>,
+ <tt><font color=green>+</font></tt>
+ )
+
+ <li> <font color=green>conjunctive grammars</font>
+ (<font color=green>intersection</font> operator)
+
+ <li> <font color=orange>boolean grammars</font> (<font
+ color=green>intersection</font>, <font
+ color=green>intersect-with-complement</font>, and
+ <font color=orange>generalized-complement</font>)
+ </ul>
+
+
+ <li> <b>Facilitates experimenting with grammars</b>
+
+ <ul>
+ <li> <font color=green>Interpreted mode</font>, in which the
+ parse table is interpreted directly, eliminating the
+ need for a compiler and making it easier for grammars
+ to operate on grammars.
+
+ <li> <font color=green>Simple
+ <a href=api/edu/berkeley/sbp/package-summary.html>API</a></font>
+ makes it easy to generate, analyze, and modify grammars
+ programmatically.
+
+ <ul>
+ <li> Components of a grammar (nonterminals,
+ productions, etc) <font
+ color=green>represented as objects</font>
+ <li> composite elements implement <font color=green><tt>Iterable<T></tt></font>
+ </ul>
+
+ <li> <font color=red>Compiled mode</font>, in which Java
+ source code is emitted; compiling this code yields a
+ parser. The resulting parser is <i>much</i> faster.
+ </ul>
+
+
+</ul>
+
+<h1>What is it deliberately missing?</h1>
+
+<ul> <li> Semantic actions; the only option is to return a parse forest.
+ <ul>
+ <li> This keeps the grammar specification language-neutral.
+ <li> A grammar can, however, indicate that certain parts of the parse tree should be dropped.
+ </ul>
+</ul>
+
+<h1>What features would be nice to have?</h1>
+
+<ul>
+ <li> <strike>Drop Farshi's algorithm and use <a
+ href=http://doi.ieeecomputersociety.org/10.1109/HICSS.2002.994495>GRMLR</a></strike>.
+ <font color=green>Done!</font>
+
+ <li> An implementation of the <a
+ href=http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elkhound/algorithm.html>McPeak-Necula
+ optimization</a> for bounded-depth determinism.
+
+ <li> Lazy parse trees, to decrease the space requirements from
+ o(n) to o(1) [but still O(n)].
+
+ <li> Consider implementing <a
+ href=http://www.cs.uvic.ca/~nigelh/Publications/cc99-paper.pdf>
+ Aycock-Horspool</a> unrolling. Improves performance with
+ only highly localized increase in algorithmic complexity.
+ Subsumes many other optimizations.
+
+</ul>
+
+<h1>What are the long term goals?</h1>
+
+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 (<a
+href=http://www.cs.berkeley.edu/~smcpeak/elkhound/>Elkhound</a>, <a
+href=http://www.delorie.com/gnu/docs/bison/bison_90.html>bison-glr</a>).
+
+<h1>Where can I read more about it?</h1>
+
+<ul> <li> The <a href=../README>README</a> file is the best place to start
+ <li> After that, be sure to read <a href=jargon.txt>jargon.txt</a>
+ <li> The <a
+ href=api/edu/berkeley/sbp/package-summary.html>javadoc</a>
+ is the best description of the API
+ <li> There's a <a href=../tests/meta.g>tentative metagrammar</a>,
+ written in itself.
+ <li> You can also get <a href=osq.lunch.talk.pdf>slides</a>
+ 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.
+ <li> A <a href=preprint.pdf>preprint</a> of one of my conference
+ submissions.
+</ul>
+
+<h1>Where can I get it?</h1>
+
+The color coding above accurately reflects the state of the
+implementation (<font color=green>11-Dec-2005</font>). 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.
+<p>
+
+SBP is available under the BSD license.
+<p>
+
+You can download a snapshot (<font color=green>11-Dec-2005</font>) <a
+href=../../sbp/edu.berkeley.sbp.tar.gz>here</a>. The parser-generator
+requires Java 1.5 or later; the Java code it emits <font
+color=orange>should run on any Java 1.1+ JVM</font>. After unpacking
+the archive, simply type <tt>make</tt> to compile SBP and run the
+regression tests.
+
+</td></tr></table></center>
+</body>
+</html>
\ No newline at end of file
--- /dev/null
+<html><head><meta HTTP-EQUIV="Refresh" CONTENT="0;URL=doc/sbp.html"></head></html>
--- /dev/null
+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<T extends Token> extends Element {
+
+ private final Topology<T> rt;
+
+ public Atom(Topology<T> rt) { this.rt = rt; }
+
+ Topology<T> top() { return rt; }
+
+ void reachable(HashSet<Sequence.Position> h) { /* do-nothing */ }
+
+ /** equality is based on the underlying <tt>Topology</tt> */
+ public int hashCode() { return rt.hashCode(); }
+
+ /** equality is based on the underlying <tt>Topology</tt> */
+ 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();
+}
+
--- /dev/null
+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<Sequence.Position> 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;
+ }
+}
--- /dev/null
+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<T> {
+
+ /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
+ public final Tree<T> expand1() throws Parser.Ambiguous, Parser.Failed {
+ Iterator<Tree<T>> 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<Tree<T>> expand(boolean toss);
+
+ abstract boolean valid();
+
+ static <T> Forest<T> singleton(Token.Location loc, Sequence creator) { return create(loc, null, new Forest[] { }, creator, false, true); }
+ static <T> Forest<T> singleton(Token.Location loc, Forest<T> body, Sequence creator) { return create(loc, null, new Forest[] { body }, creator, false, true); }
+ static <T> Forest<T> leaf(Token.Location loc, T tag, Sequence creator) { return create(loc, tag, null, creator, false, false); }
+ static <T> Forest<T> create(Token.Location loc, T tag, Forest<T>[] tokens, Sequence creator, boolean unwrap, boolean singleton) {
+ return new MultiForest<T>(loc, tag, tokens, creator, unwrap, singleton);
+ }
+
+ // Body //////////////////////////////////////////////////////////////////////////////
+
+ protected static class Body<T> {
+
+ private final Token.Location location;
+ private final T tag;
+ private final Forest<T>[] tokens;
+ private final Sequence creator;
+ private final boolean unwrap;
+ private final boolean singleton;
+
+ private Body(Token.Location loc, T tag, Forest<T>[] 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<Tree<T>> expand(boolean toss, ArrayList<Tree<T>> toks, int i, HashSet<Tree<T>> h) {
+ if (singleton) {
+ for(Body<T> b : (IterableForest<T>)tokens[0]) b.expand(toss, toks, i, h);
+
+ } else if (i==tokens.length) {
+ h.add(new Tree<T>(null, tag, toks.toArray(tree_hint)));
+
+ } else if (unwrap && i==tokens.length-1) {
+ if (tokens[i] != null)
+ for(Body b : (IterableForest<T>)tokens[i])
+ b.expand(toss, toks, 0, h);
+
+ } else {
+ if (tokens[i]!=null) {
+ HashSet<Tree<T>> exp = tokens[i].expand(toss);
+ if (exp != null)
+ for(Tree<T> 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<Body> h) {
+ if (!singleton) h.add(this);
+ else for(Body b : (IterableForest<T>)tokens[0]) b.addTo(h);
+ }
+ void addTo(FastSet<Body> h) {
+ if (!singleton) h.add(this, true);
+ else for(Body b : (IterableForest<T>)tokens[0]) b.addTo(h);
+ }
+
+ private boolean kcache = false;
+ private boolean keep = false;
+ public boolean keep() {
+ if (kcache) return keep;
+ kcache = true;
+ for(Forest<T> token : tokens) if (!token.valid()) return keep = false;
+ return keep = creator==null || (creator.needs.size()==0 && creator.hates.size()==0);
+ }
+ public boolean keep(Iterable<Body<T>> h) {
+ if (keep()) return true;
+ for(Forest<T> token : tokens) if (!token.valid()) return false;
+ int needs = 0;
+ for(Body<T> 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<tokens.length; i++) {
+ String q = tokens[i]==null ? "null" : tokens[i].toString();
+ if (q.length() > 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<T> extends Forest<T> implements Iterable<Forest.Body<T>> {
+ public abstract Iterator<Forest.Body<T>> 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<T> extends IterableForest<T> {
+ private FastSet<Forest> hp = new FastSet<Forest>();
+ 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<Body<T>> iterator() { return ((IterableForest<T>)resolve()).iterator(); }
+ public HashSet<Tree<T>> 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<Body> results = null;
+ FastSet<Body> nh = new FastSet<Body>();
+ 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<Body>();
+ }
+ 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<T> extends IterableForest<T> {
+ private final FastSet<Body<T>> results;
+ private boolean valid;
+ public boolean valid() { return valid; }
+ private MultiForest(FastSet<Body<T>> results, boolean valid) { this.results = results; this.valid = valid; }
+ public MultiForest(Token.Location loc, T tag, Forest<T>[] tokens, Sequence creator, boolean unwrap, boolean singleton) {
+ this.results = new FastSet<Body<T>>(new Body(loc, tag, tokens, creator, unwrap, singleton));
+ this.valid = true;
+ }
+ public Iterator<Body<T>> iterator() { return results.iterator(); }
+
+ public HashSet<Tree<T>> expand(boolean toss) {
+ HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
+ for(Body<T> b : results)
+ ret.addAll(b.expand(toss, new ArrayList<Tree<T>>(), 0, new HashSet<Tree<T>>()));
+ 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("<?");
+ boolean first = true;
+ for(Forest.Body<T> 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];
+}
--- /dev/null
+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 <i>between tokens</i> 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<Phase.Reduct> reductions = new HashSet<Phase.Reduct>(); /* ALLOC */
+
+ /** all nodes, keyed by the value returned by code() */
+ private HashMap<Long,Phase.Node> hash = new HashMap<Long,Phase.Node>(); /* ALLOC */
+
+ /** the number of pending reductions */
+ private int pendingReductions = 0;
+ private int totalReductions = 0;
+ private HashSet<Reduct> pendingReduct = new HashSet<Reduct>();
+
+ /** 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 <tt>next</tt> */
+ 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<Parser.Table.Reduction,Forest> pcache = new HashMap<Parser.Table.Reduction,Forest>();
+ /** a node in the GSS */
+ public class Node {
+
+ private Forest.Ref holder = null;
+ private HashMap<Parser.Table.Reduction,Forest> cache = null;
+
+ public HashMap<Parser.Table.Reduction,Forest> cache() { return cache==null ? (cache = new HashMap<Parser.Table.Reduction,Forest>()) : 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<Node> 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<Node> parents = new FastSet<Node>(); /* 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<String> 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);
+ }
+
+}
--- /dev/null
+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<R> */
+public class Parser<T extends Token, R> {
+
+ 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 <tt>u</tt>
+ * @param top a "sample" Topology<T> that can be cloned (FIXME, demanding this is lame)
+ */
+ public Parser(Union u, Topology<T> top) { this(new Table(u, top)); }
+
+ Parser(Table pt) { this.pt = pt; }
+
+ /** parse <tt>input</tt> for a exactly one unique result, throwing <tt>Ambiguous</tt> if not unique or <tt>Failed</tt> if none */
+ public Tree<R> parse1(Token.Stream<T> input) throws IOException, Failed, Ambiguous { return parse(input).expand1(); }
+
+ /** parse <tt>input</tt>, using the table <tt>pt</tt> to drive the parser */
+ public Forest<R> parse(Token.Stream<T> 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<R>)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<Position> closure() {
+ HashSet<Position> hp = new HashSet<Position>();
+ 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<Element> 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<Element> walk() {
+ HashSet<Element> ret = new HashSet<Element>();
+ 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<HashSet<Position>,State> all_states = new HashMap<HashSet<Position>,State>();
+ HashSet<Element> 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<Table.State>, Iterable<Position> {
+
+ public final int idx = master_state_idx++;
+ private final HashSet<Position> hs;
+
+ private transient HashMap<Element,State> gotoSetNonTerminals = new HashMap<Element,State>();
+ private transient TopologicalBag<Token,State> gotoSetTerminals = new TopologicalBag<Token,State>();
+
+ private TopologicalBag<Token,Reduction> reductions = new TopologicalBag<Token,Reduction>();
+ private FastSet<Reduction> eofReductions = new FastSet<Reduction>();
+ private TopologicalBag<Token,State> shifts = new TopologicalBag<Token,State>();
+ private boolean accept = false;
+
+ // Interface Methods //////////////////////////////////////////////////////////////////////////////
+
+ public boolean canShift(Token t) { return shifts.contains(t); }
+ public Iterable<State> getShifts(Token t) { return shifts.get(t); }
+ public boolean isAccepting() { return accept; }
+ public Iterable<Reduction> getReductions(Token t) { return reductions.get(t); }
+ public Iterable<Reduction> getEofReductions() { return eofReductions; }
+ public Iterator<Position> iterator() { return hs.iterator(); }
+
+ // Constructor //////////////////////////////////////////////////////////////////////////////
+
+ /**
+ * create a new state consisting of all the <tt>Position</tt>s in <tt>hs</tt>
+ * @param hs the set of <tt>Position</tt>s comprising this <tt>State</tt>
+ * @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:
+ * <ul>
+ * <li> 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
+ *
+ * <li> 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.
+ * </ul>
+ */
+ public State(HashSet<Position> hs,
+ HashMap<HashSet<Position>,State> all_states,
+ HashSet<Element> 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<Token,Position> bag0 = new TopologicalBag<Token,Position>();
+ for(Position position : hs) {
+ if (position.isLast() || !(position.element() instanceof Atom)) continue;
+ Atom a = (Atom)position.element();
+ HashSet<Position> hp = new HashSet<Position>();
+ 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<Token> r : bag0) {
+ HashSet<Position> h = new HashSet<Position>();
+ 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<Position> 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<Element,Position> move = new HashMapBag<Element,Position>();
+ for(Position p : hs) {
+ Element e = p.element();
+ if (e==null) continue;
+ HashSet<Element> ys = cache.ys.get(e);
+ if (ys != null) {
+ for(Element y : ys) {
+ HashSet<Position> hp = new HashSet<Position>();
+ p.next().reachable(hp);
+ move.addAll(y, hp);
+ }
+ }
+ }
+ for(Element y : move) {
+ HashSet<Position> 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 <tt>Element</tt> 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];
+}
--- /dev/null
+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 <tt>sep</tt> */
+ 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 <tt>sep</tt> */
+ 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));
+ }
+ }
+}
--- /dev/null
+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<Element> {
+
+ // 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<Sequence> and, HashSet<Sequence> 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<Sequence> and, HashSet<Sequence> not) { return new Constant(e, o, and, not); }
+
+ /** after matching the sequence, place the result of the <tt>idx</tt>th match in the output tree */
+ public static Sequence singleton(Element[] e, int idx, HashSet<Sequence> and, HashSet<Sequence> 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 <tt>e</tt> whose corresponding <tt>boolean</tt> in <tt>drops</tt> is <i>false</i> will be included in the output tree
+ **/
+ public static Sequence rewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet<Sequence> and, HashSet<Sequence> not) {
+ return new RewritingSequence(tag, e, drops, and, not); }
+
+ ////////////////////////////////////////////////////////////////////////////////
+
+ protected final Element[] elements;
+
+ final HashSet<Sequence> needs;
+ final HashSet<Sequence> hates;
+ boolean lame = false;
+
+ final Position firstp;
+ Position firstp() { return firstp; }
+
+ public Iterator<Element> iterator() { return new ArrayIterator<Element>(elements); }
+ protected Sequence(Element[] elements, HashSet<Sequence> and, HashSet<Sequence> not) {
+ this.needs = and==null ? new HashSet<Sequence>() : and;
+ this.hates = not==null ? new HashSet<Sequence>() : 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<Position> h) { firstp().reachable(h); }
+
+ Forest epsilonForm() { return firstp().rewrite(null); }
+
+ protected abstract <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args);
+
+
+ // Position //////////////////////////////////////////////////////////////////////////////
+
+ /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
+ public class Position {
+
+ void reachable(HashSet<Position> 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 <tt>this.element()</tt>) */
+ public Position next() { return next; }
+
+ /** true iff this Position is the last one in the sequence */
+ public boolean isLast() { return next()==null; }
+
+ // Reduction /////////////////////////////////////////////////////////////////////////////////
+
+ <T> Forest<T> rewrite(Token.Location loc) {
+ for(int i=pos; i<elements.length; i++) if (holder[i]==null) holder[i] = elements[i].epsilonForm();
+ Forest<T> ret = Sequence.this.postReduce(loc, holder);
+ for(int k=0; k<pos; k++) holder[k] = null; // to help GC
+ return ret;
+ }
+
+ public String toString() {
+ StringBuffer ret = new StringBuffer();
+ ret.append("<{");
+ for(Position p = Sequence.this.firstp(); p != null; p = p.next()) {
+ ret.append(' ');
+ if (p==this) ret.append(" | ");
+ if (p.element()!=null) ret.append(p.element().possiblyEpsilon(null) ? "["+p.element()+"]" : p.element());
+ else ret.append(' ');
+ }
+ ret.append("}>");
+ 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<elements.length; i++) {
+ sb.append(elements[i].toString());
+ sb.append(' ');
+ }
+ return sb;
+ }
+
+
+ // Specialized Subclasses //////////////////////////////////////////////////////////////////////////////
+
+ static class Constant extends Sequence {
+ private final Object result;
+ public Constant(Element[] e, Object result, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.result = result; }
+ public <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args) {
+ return (Forest<T>)Forest.leaf(loc, result, this);
+ }
+ static class Drop extends Constant {
+ public Drop(Element[] e, HashSet<Sequence> and, HashSet<Sequence> 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<Sequence> and, HashSet<Sequence> not) { this(new Element[] { e }, 0, and, not); }
+ public Singleton(Element[] e, int idx, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.idx = idx; }
+ public <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args) { return (Forest<T>)Forest.singleton(loc, args[idx], this); }
+ }
+
+ static class Unwrap extends Sequence {
+ private boolean[] drops;
+ public Unwrap(Element[] e, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.drops = null; }
+ public Unwrap(Element[] e, boolean[] drops, HashSet<Sequence> and, HashSet<Sequence> not) { super(e, and, not); this.drops = drops; }
+ public <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args) {
+ if (drops==null) return Forest.create(loc, null, args, this, true, false);
+ int count = 0;
+ for(int i=0; i<drops.length; i++) if (!drops[i]) count++;
+ Forest<T>[] args2 = new Forest[count];
+ int j = 0;
+ for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
+ return Forest.create(loc, null, args2, this, true, false);
+ }
+ }
+
+ static class RewritingSequence extends Sequence {
+ private final Object tag;
+ private final boolean[] drops;
+ private int count = 0;
+ public RewritingSequence(Object tag, Element[] e, HashSet<Sequence> and, HashSet<Sequence> not) { this(tag, e, null, and, not); }
+ public RewritingSequence(Object tag, Element[] e, boolean[] drops, HashSet<Sequence> and, HashSet<Sequence> not) {
+ super(e, and, not);
+ this.tag = tag;
+ this.drops = drops == null ? new boolean[e.length] : drops;
+ for(int i=0; i<this.drops.length; i++) if (!this.drops[i]) count++;
+ }
+ public <T> Forest<T> postReduce(Token.Location loc, Forest<T>[] args) {
+ Forest<T>[] args2 = new Forest[count];
+ int j = 0;
+ for(int i=0; i<args.length; i++) if (!drops[i]) args2[j++] = args[i];
+ return Forest.create(loc, (T)tag, args2, this, false, false);
+ }
+ public StringBuffer toString(StringBuffer sb, boolean spacing) {
+ int len = sb.length();
+ super.toString(sb, spacing);
+ len = sb.length()-len;
+ if (spacing) for(int i=0; i<50-len; i++) sb.append(' ');
+ sb.append(" => ");
+ sb.append(tag);
+ return sb;
+ }
+ }
+}
--- /dev/null
+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 <i>actual input token</i> rather than an <tt>Element</tt> which <i>matches</i> a token */
+public interface Token {
+
+ // FIXME!!! remove this
+ /** converts this <tt>Token</tt> 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<T extends Token> {
+ public T next() throws IOException;
+ }
+
+ /** a location within the input stream */
+ public static interface Location {
+ public String toString();
+ public String getContext();
+ }
+
+}
+
--- /dev/null
+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<T> {
+
+ final T head;
+ Tree<T>[] children;
+ final Token.Location location;
+
+ public T head() { return head; }
+ public int numChildren() { return children.length; }
+ public Iterable<Tree<T>> 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<T>[] children) {
+ this.location = loc;
+ this.head = head;
+ Tree<T>[] 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 <tt>sb</tt> 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<children.length; i++) {
+ if (children[i]==null) sb.append("null");
+ else children[i].toJava(sb);
+ if (i<children.length-1) sb.append(",\n ");
+ }
+ sb.append("})");
+ }
+
+ public String toString() {
+ StringBuffer ret = new StringBuffer();
+ for(int i=0; i<children.length; i++) {
+ String q = children[i]==null ? "null" : children[i].toString();
+ if (q.length() > 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;
+ }
+
+
+}
--- /dev/null
+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<Sequence> {
+
+ final String shortForm;
+ final boolean synthetic;
+ private final List<Sequence> alternatives = new ArrayList<Sequence>();
+
+ public Iterator<Sequence> iterator() { return alternatives.iterator(); }
+
+ void reachable(HashSet<Sequence.Position> 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<Sequence> exclude;
+ public Subset(String shortForm, Set<Sequence> exclude) { super(shortForm, true); this.exclude = exclude; }
+ public Iterator<Sequence> iterator() {
+ final Iterator<Sequence> it = Union.this.iterator();
+ return new Iterator<Sequence>() {
+ 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(); }
+ };
+ }
+ }
+
+}
--- /dev/null
+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<T> {
+ protected HashSet<Element> acc = new HashSet<Element>();
+ 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<HashSet<Element>> {
+ private final Element e;
+ public final HashSet<Element> walk() { return walk(e); }
+ public YieldSet(Element e, Cache c) { super(c); this.e = e; }
+ public HashSet<Element> bottom(Element e) { return acc; }
+ public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
+ public HashSet<Element> 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<Boolean> {
+ 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<Element,Boolean> hm = new HashMap<Element,Boolean>();
+ 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<Tok extends Token> extends Walk<Topology<Tok>> {
+ public Topology<Tok> cs;
+ public WalkTokenSet(Topology<Tok> cs) { this.cs = cs; }
+ public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
+ public Topology<Tok> bottom(Element e) { return cs; }
+ public Topology<Tok> walkAtom(Atom r) { cs.add(r.top()); return cs; }
+ }
+
+ class First<Tok extends Token> extends WalkTokenSet<Tok> {
+ public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
+ public Topology<Tok> 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<Tok extends Token> extends WalkTokenSet<Tok> {
+ public Last(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
+ public Topology<Tok> sequence(Sequence seq) { sequence(seq.firstp()); return cs; }
+ private Topology<Tok> sequence(Position p) {
+ if (p==null) return null;
+ Topology<Tok> 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<Tok extends Token> extends WalkTokenSet<Tok> {
+ private final Element me;
+ private final HashSet<Element> all;
+ private boolean eof = false;
+ public boolean includesEof() { return eof; }
+ public Follow(Topology<Tok> cs, Element me, HashSet<Element> all, Cache c) { super(cs, c); this.me = me; this.all = all; }
+ public Topology<Tok> bottom(Element e) { return cs; }
+ public Topology<Tok> sequence(Sequence seq) { return cs; }
+ public Topology<Tok> walkAtom(Atom r) { return walk((Element)r); }
+ public Topology<Tok> walk(Element e) {
+ if (acc.contains(e)) return bottom(e);
+ acc.add(e);
+
+ if (c != null) {
+ Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
+ if (cached != null) {
+ cs.add(cached);
+ eof |= c.eof.get(e);
+ return cs;
+ }
+ }
+
+ Topology<Tok> 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<Tok>(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<Tok>(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<Element,Boolean> possiblyEpsilon = new HashMap<Element,Boolean>();
+ public HashMap<Element,Boolean> eof = new HashMap<Element,Boolean>();
+ public HashMap<Element,Topology> follow = new HashMap<Element,Topology>();
+ public HashMap<Element,HashSet<Element>> ys = new HashMap<Element,HashSet<Element>>();
+ public HashMap<Element,Topology> atoms = new HashMap<Element,Topology>();
+ }
+}
--- /dev/null
+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 <tt>char</tt> values */
+public class CharToken implements Token, IntegerTopology.IntegerMappable {
+
+ // Public //////////////////////////////////////////////////////////////////////////////
+
+ public static class CharRange extends Atom<CharToken> {
+ private String esc(char c) { return StringUtil.escapify(c+"", "[]-~\\\"\'"); }
+ public CharRange(Topology<CharToken> 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 <tt>start</tt> and <tt>end</tt>, inclusive */
+ public static Atom positiveRange(char start, char end) {
+ return new CharRange(new IntegerTopology<CharToken>(new Range.Set(new Range((int)start, (int)end))));
+ }
+
+ /** returns an element matching all characters <b>not</b> between <tt>start</tt> and <tt>end</tt>, inclusive */
+ public static Atom negativeRange(char start, char end) {
+ return new CharRange(new IntegerTopology<CharToken>(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<CharToken>(all));
+ public static final Atom none = new CharRange(new IntegerTopology<CharToken>());
+ public static IntegerTopology<CharToken> range(Range r) { return new IntegerTopology<CharToken>(r); }
+ public static Atom set(Range.Set r) { return new CharRange(new IntegerTopology<CharToken>(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<CharToken>((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<refs.length; i++) refs[i] = new CharRange(new IntegerTopology<CharToken>((int)s.charAt(i)));
+ ret2.add(Sequence.constant(refs, s, null, null));
+ ret = ret2;
+ }
+ return ret;
+ }
+
+ /** FIXME */
+ public static Topology<CharToken> top() { return new IntegerTopology<CharToken>(); }
+ public static Topology<CharToken> top(String s) throws java.text.ParseException {
+ return new IntegerTopology<CharToken>(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<col-1; i++) spaces.append(' ');
+ spaces.append('^');
+ return " " + myline.line.toString() + "\n " + spaces.toString();
+ }
+ }
+
+ long then = 0;
+ public Token next() throws IOException {
+ int i = r.read();
+ if (i==-1) return null;
+ char c = (char)i;
+ Token ret = new CharToken(c, new LocWrap(line, col));
+ String s = line + "";
+ while(s.length() < 4) s = " " + s;
+ s = "line "+s+", col " + col;
+ long now = System.currentTimeMillis();
+ if (now-then > 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;
+ }
+ }
+
+}
--- /dev/null
+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<Union> dropAll = new HashSet<Union>();
+
+ // 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<c.length; i++) c[i] = ((Character)args[i]).charValue();
+ String s = new String(c, 0, c.length);
+ return s;
+ }
+ return (String)args[0];
+ }
+
+
+ ////////////////////////////////////////////////////////////////////////////////
+
+ private Union g;
+ private HashMap<String,Union> 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<String,Union>();
+ 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<Sequence> seqs = new HashSet<Sequence>();
+ for(int i=0; i<s.length; i++) {
+ if (s[i]==null) continue;
+ HashSet<Sequence> temp = new HashSet<Sequence>();
+ 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<PreSequence> needs = new HashSet<PreSequence>();
+ public final HashSet<PreSequence> hates = new HashSet<PreSequence>();
+ public final HashSet<Sequence> hatess = new HashSet<Sequence>();
+ 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<Sequence> 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; i<o.length; i++) {
+ if (o[i] instanceof PreSequence) o2[j] = ((PreSequence)o[i]).buildUnion(ws);
+ else if (o[i]==SELF) o2[j] = u.new Subset("(("+u+"))", set);
+ else if (o[i] instanceof MyLift) { o2[j] = CharToken.string(tag = ((MyLift)o[i]).s); drops[j] = true; }
+ else if (o[i] instanceof String) { o2[j] = CharToken.string( ((String)o[i]) ); drops[j] = true; }
+ else if (o[i] instanceof Rep) o2[j] = ((Rep)o[i]).build(ws);
+ else o2[j] = (Element)o[i];
+
+ if (dropAll.contains(o2[j])) drops[j] = true;
+
+ o2[j] = o2[j];
+ j++;
+ }
+ if (ws == null || o2.length <= 1) return o2;
+ Element[] ret = new Element[o2.length*2-1];
+ boolean[] drops2 = new boolean[ret.length];
+ for(int i=0; i<o2.length; i++) {
+ if (i>0) { 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<Sequence> and = new HashSet<Sequence>();
+ HashSet<Sequence> not = new HashSet<Sequence>();
+ 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<Sequence> set = new HashSet<Sequence>();
+ 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<expansion.length; i++) expansion[i] = expansion[i];
+ ret = Sequence.rewritingSequence(tag, expansion, drops, and, not);
+ }
+ if (ret==null) {
+ int idx = -1;
+ for(int i=0; i<expansion.length; i++) {
+ if (!drops[i]) idx = i;
+ else expansion[i] = expansion[i];
+ }
+ ret = idx==-1 ? Sequence.drop(expansion, and, not, false) : Sequence.singleton(expansion, idx, and, not);
+ }
+ set.add(ret);
+ return ret;
+ }
+ }
+
+ public static void main(String[] args) throws Exception {
+ if (args.length != 2) {
+ System.err.println("usage: java " + MetaGrammar.class.getName() + " grammarfile.g com.yourdomain.package.ClassName");
+ System.exit(-1);
+ }
+
+ String className = args[1].substring(args[1].lastIndexOf('.')+1);
+ String packageName = args[1].substring(0, args[1].lastIndexOf('.'));
+ String fileName = packageName.replace('.', '/') + "/" + className + ".java";
+
+ BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(fileName)));
+ StringBuffer out = new StringBuffer();
+
+ boolean skip = false;
+ for(String s = br.readLine(); s != null; s = br.readLine()) {
+ if (s.indexOf("DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED") != -1 && s.indexOf("\"")==-1) skip = true;
+ if (s.indexOf("DO NOT EDIT STUFF ABOVE: IT IS AUTOMATICALLY GENERATED") != -1 && s.indexOf("\"")==-1) break;
+ if (!skip) out.append(s+"\n");
+ }
+
+ out.append("\n // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED\n");
+ new Parser(MetaGrammar.make(), CharToken.top()).parse1(new CharToken.Stream(new InputStreamReader(new FileInputStream(args[0])))).toJava(out);
+ out.append("\n // DO NOT EDIT STUFF ABOVE: IT IS AUTOMATICALLY GENERATED\n");
+
+ for(String s = br.readLine(); s != null; s = br.readLine()) out.append(s+"\n");
+ br.close();
+
+ OutputStream os = new FileOutputStream(fileName);
+ PrintWriter p = new PrintWriter(new OutputStreamWriter(os));
+ p.println(out.toString());
+ p.flush();
+ os.close();
+ }
+
+ public static class MyLift {
+ public final String s;
+ public MyLift(String s) { this.s = s; }
+ }
+
+ private static final Tree meta =
+
+
+
+
+ // DO NOT EDIT STUFF BELOW: IT IS AUTOMATICALLY GENERATED
+new Tree(null, "gram", new Tree[] { new Tree(null, null, new Tree[] { }),
+ new Tree(null, "grammar", 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, 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, "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
+ ;
+}
+
+
+
+
+
+
--- /dev/null
+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<s.length(); i++) {
+ char c = s.charAt(i);
+ if (i==0 && c >= '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() + ".<init>()");
+ 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");
+ }
+}
--- /dev/null
+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<String> (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<A> -- 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<String> 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<String> 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<String> res = new Parser(grammar,
+ CharToken.top()).parse(new CharToken.Stream(new StringReader(input), input.indexOf('\n')==-1?"\""+input+"\": ":""));
+ Collection<Tree<String>> results = res==null ? new HashSet<Tree<String>>() : 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<String> outs = new HashSet<String>();
+ for(String s : output) outs.add(s.trim());
+ boolean bad = false;
+ for (Tree<String> 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)+" "; }
+}
+
--- /dev/null
+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<String> {
+ public Object walk(Tree<String> 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");
+ }
+}
--- /dev/null
+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<T> {
+ public abstract Object walk(T head, Object[] args);
+ public Object walk(Tree<T> tree) {
+ Object[] args = new Object[tree.numChildren()];
+ int i = 0;
+ for(Tree<T> child : tree.children()) args[i++] = walk(child);
+ args = Reflection.lub(args);
+ return walk(tree.head(), args);
+ }
+}
--- /dev/null
+<body>
+<b><font color=red>IMPORTANT:</font> BE SURE TO READ THE FILE <tt><font size=big><a href=../../../../jargon.txt>doc/jargon.txt</a></big></tt> FIRST!</b>
+</body>
--- /dev/null
+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; i<e.length; i++) {
+ if (i>0) 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<e.length; i++) e2[i+(sep==null ? 1 : 2)] = e[i];
+ addAlternative(new Sequence.Singleton(e2));
+ addAlternative(new Sequence.Singleton(sep==null ? new Element[] { left, this, right} : new Element[] { left, sep, this, sep, right }));
+ }
+}
+ */
--- /dev/null
+// 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.*;
+
+// TODO: multiple {{ }} for superquotation
+// TODO: strings
+// TODO: comments
+
+/**
+ * A slow, ugly, inefficient, inelegant, ad-hoc parser for TIB files.
+ *
+ * Despite being inelegant, this parser keeps all internal state on
+ * the stack (the only heap objects created are those which are
+ * returned).
+ *
+ * This was written as an ad-hoc parser to facilitate
+ * experimentation with the TIB spec. Once the spec is finalized it
+ * should probably be rewritten using a parser-generator, if
+ * possible (it is unclear whether or not the associated grammar is
+ * context-free).
+ */
+public class Tib /*implements Token.Stream<TibToken>*/ {
+ /*
+
+ 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<s.length(); i++) {
+ top.add(s.charAt(i));
+ switch(s.charAt(i)) {
+ case '{': top = new Block.Brace(top, row, col); break;
+ case '}': top = top.closeBrace(); break;
+ }
+ }
+ top.add(' ');
+ top.finishWord();
+ }
+ // FIXME
+ Block ret = top;
+ while (ret.parent != null) ret = ret.parent;
+ return ret;
+ } catch (InternalException ie) {
+ throw new Invalid(ie, row, col);
+ }
+ }
+
+ public static class Block implements Token {
+ Block parent;
+ public final int row;
+ public final int col;
+ private final Vec children = new Vec();
+ private String pending = "";
+
+ public Tree<String> 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; i<children.size(); i++) {
+ Object o = children.elementAt(i);
+ if (i>0 && 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();
+ }
+ */
+}
+
--- /dev/null
+// 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<packages.length; i++) p.println("\\usemodule["+packages[i]+"]");
+ p.println("\\setuppapersize[letter]");
+ p.println("\\setuppagenumbering[location=]");
+ p.println("\\setupcolors[state=start]");
+ //"\\setupinteraction[title={Title},author={Me},"++
+ //"subtitle={Deez Nutz},keywords={blargh},color=blue]\n" ++
+ //"\\setuppublications[database={me},numbering=yes,sort=author]\n" ++
+ p.println("\\setuphead[section][style={\\ss\\bfa},number=no,before=\\blank\\hairline\\nowhitespace]");
+ p.println("\\definelayout[mypage][backspace=1.75in,cutspace=1.75in,width=5in]");
+ p.println("\\setuplayout[mypage]");
+ p.println("\\definetypeface[myface][rm][Xserif][Warnock Pro]");
+ p.println("\\definetypeface[myface][tt][Xmono][CMU Typewriter Text Regular][default]");
+ p.println("\\definetypeface[myface][ss][Xsans][Myriad Pro][default]");
+ p.println("\\usesymbols[uni]");
+ p.println("\\definesymbol[1][{\\USymbCharZapf{39}{164}}]");
+ p.println("\\setupbodyfont[myface, 11pt]");
+ p.println("\\setupwhitespace[7pt]");
+ p.println("\\def\\MyDroppedCaps%");
+ p.println(" {\\DroppedCaps");
+ p.println(" {} {Serif} {2\\baselineskip} {2pt} {1\\baselineskip} {2}}");
+ p.println("\\starttext");
+ p.println("\\switchtobodyfont[16pt]\\midaligned{\\ss\\bfa{Title}}\\switchtobodyfont[10pt]");
+ p.println("\\midaligned{Adam Megacz}\n\n\\nowhitespace\\midaligned{\\tt{adam@megacz.com}}");
+ p.println("\\blank[1cm,force]");
+ //p.println("\\defineparagraphs[mypar][n=2,before={\\blank},after={\\blank}");
+ //p.println("\\setupparagraphs[mypar][1][width=.45\\textwidth");
+ //p.println("\\setupparagraphs[mypar][2][width=.55\\textwidth");
+ //p.println("\\startmypa");
+ //p.println("\\switchtobodyfont[sma");
+ }
+
+ public static void suffix(PrintWriter p) {
+ p.println("\\stoptext");
+ }
+ static String[] packages = new String[] { "supp-fun", "bib", "href" };
+ }
+ */
+}
+
--- /dev/null
+package edu.berkeley.sbp.util;
+import java.util.*;
+
+public final class ArrayIterator<T> implements Iterator<T>, Iterable<T> {
+
+ 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<array.length; }
+ public T next() { return array[i++]; }
+ public Iterator<T> iterator() { return this; }
+}
--- /dev/null
+package edu.berkeley.sbp.util;
+import java.util.*;
+
+public final class EmptyIterator<T> implements Iterable<T>, Iterator<T> {
+ public void remove() { throw new Error(); }
+ public boolean hasNext() { return false; }
+ public T next() { throw new Error(); }
+ public Iterator<T> iterator() { return this; }
+}
--- /dev/null
+package edu.berkeley.sbp.util;
+import java.util.*;
+
+public final class FastSet<T> implements Iterator<T>, Iterable<T> {
+
+ public static final int INITIAL_SIZE = 128;
+
+ private Object[] array;
+ private T only = null;
+ private int i = 0;
+ private int size = 0;
+
+ public Iterator<T> iterator() { i=0; return this; }
+ public void remove() { throw new Error(); }
+ public boolean hasNext() { return only==null ? i<size : i<1; }
+ public T next() { return only==null ? (T)array[i++] : (i++)==0 ? only : null; }
+
+ public FastSet() { }
+ public FastSet(T t) { only = t; }
+ public FastSet(Set<T> 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;
+ }
+}
--- /dev/null
+package edu.berkeley.sbp.util;
+import java.util.*;
+
+/** a mapping from keys of type <tt>K</tt> to <i>sets</i> of values of type <tt>T</tt> */
+public final class HashMapBag<K,V> implements MapBag<K,V> {
+
+ private final HashMap<K,HashSet<V>> hm = new HashMap<K,HashSet<V>>();
+
+ public void add(K k, V v) {
+ HashSet<V> hs = hm.get(k);
+ if (hs==null) hm.put(k, hs = new HashSet<V>());
+ hs.add(v);
+ }
+
+ public void addAll(K k, Iterable<V> iv) {
+ for(V v : iv) add(k, v);
+ }
+
+ public HashSet<V> getAll(K k) {
+ HashSet<V> ret = hm.get(k);
+ if (ret==null) return new HashSet<V>();
+ return ret;
+ }
+
+ public Iterator<K> iterator() { return hm.keySet().iterator(); }
+}
--- /dev/null
+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 <tt>Topology</tt> for any class for which there is a mapping to the <tt>int</tt>s */
+public class IntegerTopology<V extends IntegerTopology.IntegerMappable> implements Topology<V> {
+ 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<V> fresh() { return new IntegerTopology<V>(); }
+ public Topology<V> dup() { return new IntegerTopology<V>(this.rs); }
+ public Topology<V> dup(Range.Set rs) { return new IntegerTopology<V>(rs); }
+
+ public void add(Topology<V> t) { rs.add(((IntegerTopology<V>)t).rs); }
+ public void remove(Topology<V> t) { rs.remove(((IntegerTopology<V>)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<V> complement() { return dup(rs.complement()); }
+ public Topology<V> intersect(Topology<V> t) { return dup(rs.intersect(((IntegerTopology<V>)t).rs)); }
+ public Topology<V> minus(Topology<V> t) { return dup(rs.intersect(((IntegerTopology<V>)t).rs.complement())); }
+ public Topology<V> union(Topology<V> t) { return dup(rs.union(((IntegerTopology<V>)t).rs)); }
+ public boolean disjoint(Topology<V> t) { return rs.intersect(((IntegerTopology<V>)t).rs).size()==0; }
+ public boolean containsAll(Topology<V> t) { return rs.intersect(((IntegerTopology<V>)t).rs).equals(((IntegerTopology<V>)t).rs); }
+
+ public int hashCode() { return rs.hashCode(); }
+ public boolean equals(Object o) { return o!=null && o instanceof IntegerTopology && ((IntegerTopology<V>)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();
+ }
+}
--- /dev/null
+package edu.berkeley.sbp.util;
+import java.util.*;
+
+/** a mapping from keys of type <tt>K</tt> to <i>sets</i> of values of type <tt>V</tt> */
+public interface MapBag<K,V> extends Iterable<K> {
+ public void add(K k, V v);
+ public void addAll(K k, Iterable<V> iv);
+ public Iterable<V> getAll(K k);
+ public Iterator<K> iterator();
+}
--- /dev/null
+// 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.
+ * <pre>
+ * 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.
+ * </pre>
+ * @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<Range> {
+
+ 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<rangeCount-1;i++) {
+ rs.add(ranges[i*2+1]+1,ranges[i*2+2]-1);
+ }
+ if (!posInf) {
+ rs.add(new Range(ranges[(rangeCount-1)*2+1]+1,true));
+ }
+ }
+ return rs;
+ }
+
+ /**
+ * @param i The integer to check to see if it is in this set..
+ * @return true if i is in the set.
+ */
+ public boolean contains(long i) {
+ int pos = binarySearch(i);
+ if (pos > 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<Range> iterator() {
+ ArrayList l = new ArrayList(rangeCount);
+ for (int i=0;i<rangeCount;i++) {
+ if (rangeCount == 1 && negInf && posInf) {
+ l.add(new Range(true,true));
+ } else if (i == 0 && negInf) {
+ l.add(new Range(true,ranges[i*2+1]));
+ } else if (i == rangeCount-1 && posInf) {
+ l.add(new Range(ranges[i*2],true));
+ } else {
+ l.add(new Range(ranges[i*2],ranges[i*2+1]));
+ }
+ }
+ return l.iterator();
+ }
+
+ /**
+ * @return The number of integers in this set, -1 if infinate.
+ */
+ public long size() {
+ if (negInf || posInf) {
+ return -1;
+ }
+ long result = 0;
+ for (Iterator it=iterator();it.hasNext();) {
+ result+=((Range) it.next()).size();
+ }
+ return result;
+ }
+
+ /**
+ * @return true If the set doesn't contain any integers or ranges.
+ */
+ public boolean isEmpty() {
+ return rangeCount == 0;
+ }
+
+ /**
+ * Parse a set of ranges seperated by commas.
+ *
+ * @see Range
+ *
+ * @param s The String to parse
+ * @return The resulting range
+ * @throws ParseException
+ */
+
+ public static Range.Set parse(String s) throws ParseException {
+ Range.Set rs = new Range.Set();
+ for (StringTokenizer st = new StringTokenizer(s,",");
+ st.hasMoreTokens();) {
+ rs.add(Range.parse(st.nextToken()));
+ }
+ return rs;
+ }
+
+ public int hashCode() {
+ int result = 0;
+ for (int i = 0; i < rangeCount*2; i++) {
+ result = (int) (91*result + ranges[i]);
+ }
+ return result;
+ }
+
+ public boolean equals(Object obj) {
+ if (obj instanceof Range.Set) {
+ Range.Set rs = (Range.Set) obj;
+ if (negInf == rs.negInf &&
+ posInf == rs.posInf &&
+ rangeCount == rs.rangeCount &&
+ arraysEqual(ranges,0,rs.ranges,0,rangeCount*2)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public static boolean arraysEqual(int[] arr1, int start1,
+ int[] 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(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));
+ }
+ }
+ }
+ */
+ }
+}
+
--- /dev/null
+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; i<ret.length; i++) {
+ Object o2 = rebuild(a[i], c.getComponentType());
+ //if (o2 != null) System.out.println("storing " + o2.getClass().getName() + " to " + c.getComponentType());
+ ret[i] = o2;
+ }
+ return ret;
+ }
+ if (c == String.class) {
+ boolean ok = true;
+ for(int i=0; i<a.length; i++) if (a[i]==null || !(a[i] instanceof Character)) ok = false;
+ if (ok) {
+ StringBuffer s = new StringBuffer();
+ for(int i=0; i<a.length; i++) s.append((((Character)a[i])).charValue());
+ return s.toString();
+ }
+ }
+ } else if (c.isArray()) {
+ Object[] ret = (Object[])Array.newInstance(c.getComponentType(), 1);
+ ret[0] = o;
+ return ret;
+ } else {
+ throw new Error("unable to cast " + o + " from " + o.getClass().getName() + " to " + c.getName());
+ }
+ return o;
+ }
+
+ public static Object[] newArray(Class c, int i) {
+ return (Object[])Array.newInstance(c, i);
+ }
+
+ public static Object[] lub(Object[] argo) {
+ if (argo==null) return null;
+ Class c = null;
+ for(Object o : argo) if (o != null) c = Reflection.lub(c, o.getClass());
+ if (c==null) c = Object.class;
+ Object[] ret = Reflection.newArray(c, argo.length);
+ System.arraycopy(argo, 0, ret, 0, argo.length);
+ return ret;
+ }
+
+ public static Class lub(Class a, Class b) {
+ if (a==null) return b;
+ if (b==null) return a;
+ if (a==b) return a;
+ if (a.isAssignableFrom(b)) return a;
+ if (b.isAssignableFrom(a)) return b;
+ return lub(b, a.getSuperclass());
+ }
+
+ /** a version of <tt>Class.forName</tt> that returns <tt>null</tt> 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<args.length; i++) {
+ Class goal = argTypes[i];
+ Class actual = args[i] == null ? null : args[i].getClass();
+ if (args[i] == null || goal.isAssignableFrom(actual)) continue;
+ try {
+ args[i] = rebuild(args[i], goal);
+ } catch (Error e) {
+ throw new Error(e.getMessage() + "\n while trying to fuzzyInvoke("+m.getName()+")");
+ }
+ }
+ // for debugging
+ /*
+ System.out.println("\ninvoking " + o + "." + m);
+ for(int i=0; i<args.length; i++) {
+ if (args[i] instanceof Object[]) {
+ System.out.print(" arg => " + 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+"";
+ }
+
+}
--- /dev/null
+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; i<s.length(); i++) {
+ char c = s.charAt(i);
+ switch(c) {
+ case '\\': sb.append("\\\\"); break;
+ case '\"': sb.append("\\\""); break;
+ case '\'': sb.append("\\\'"); break;
+ case '\n': sb.append("\\n"); break;
+ case '\r': sb.append("\\r"); break;
+ default: sb.append(c); break;
+ }
+ }
+ return sb.toString();
+ }
+
+ public static String unescapify(String s) {
+ StringBuffer sb = new StringBuffer();
+ for(int i=0; i<s.length(); i++) {
+ char c = s.charAt(i);
+ if (c=='\\') {
+ c = s.charAt(++i);
+ switch(c) {
+ case 'r': c = '\r'; break;
+ case 'n': c = '\n'; break;
+ default: break;
+ }
+ }
+ sb.append(c);
+ }
+ return sb.toString();
+ }
+ /*
+ case ' ': sb.append("\\ "); break;
+ case '{': sb.append("\\{"); break;
+ case '}': sb.append("\\}"); break;
+ case ':': sb.append("\\:"); break;
+ */
+ public static String escapify(String s) { return escapify(s, "\\\n\r"); }
+ public static String escapify(String s, String illegal) {
+ StringBuffer sb = new StringBuffer();
+ for(int i=0; i<s.length(); i++) {
+ char c = s.charAt(i);
+ if (illegal.indexOf(c) != -1)
+ switch(c) {
+ case '\n': sb.append("\\n"); continue;
+ case '\r': sb.append("\\r"); continue;
+ default: sb.append('\\'); break;
+ }
+ sb.append(c);
+ }
+ return sb.toString();
+ }
+}
--- /dev/null
+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.*;
+
+//
+// This is a fairly crude implementation; if things need to be fast,
+// you should implement a special-purpose class
+//
+
+/** a mapping from topologies over <tt>K</tt> to <i>sets of</i> values of type <tt>V</tt> */
+public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
+
+ // CRUCIAL INVARIANT: keys in this hashmap MUST be disjoint or the universe will implode
+ private final HashMap<Topology<K>,HashSet<V>> h = new HashMap<Topology<K>,HashSet<V>>();
+
+ public Iterator<Topology<K>> iterator() { return h.keySet().iterator(); }
+
+ public void addAll(TopologicalBag<K,V> tb) {
+ for(Topology<K> k : tb)
+ addAll(k, tb.getAll(k));
+ }
+
+ public void add(Topology<K> t, V v) { put(t, v); }
+ public void addAll(Topology<K> k, Iterable<V> vi) { putAll(k, vi); }
+
+ public void putAll(Topology<K> k, Iterable<V> vi) { for(V v : vi) put(k, v); }
+ public void put(Topology<K> t, V v) {
+ for(Topology<K> ht : h.keySet()) {
+ if (t.disjoint(ht)) continue;
+ if (t.equals(ht)) {
+ h.get(ht).add(v);
+ return;
+ }
+ if (ht.containsAll(t)) {
+ HashSet<V> v0 = h.get(ht);
+ HashSet<V> v1 = new HashSet<V>();
+ 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<V> v1 = new HashSet<V>();
+ v1.add(v);
+ h.put(t, v1);
+ }
+
+
+ public TopologicalBag<K,V> subset(Topology<K> t) {
+ TopologicalBag<K,V> ret = new TopologicalBag<K,V>();
+ for(Topology<K> ht : h.keySet()) {
+ if (ht.disjoint(t)) continue;
+ ret.putAll(ht.intersect(t), h.get(ht));
+ }
+ return ret;
+ }
+
+ public Map<Topology<K>,HashSet<V>> gett(Topology<K> t) {
+ HashMap<Topology<K>,HashSet<V>> ret = new HashMap<Topology<K>,HashSet<V>>();
+ for(Topology<K> 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<K> 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<K> t : h.keySet())
+ if (t.contains(k))
+ return h.get(t).contains(v);
+ return false;
+ }
+
+ private HashMap<K,Iterable<V>> cache = new HashMap<K,Iterable<V>>();
+ public Iterable<V> getAll(Topology<K> k) { return h.get(k); }
+ public Iterable<V> get(K k) {
+ Iterable<V> c = cache.get(k);
+ if (c != null) return c;
+ HashSet<V> ret = null;
+ HashSet<V> ret0 = null;
+ for(Topology<K> t : h.keySet())
+ if (t.contains(k)) {
+ if (ret==null) {
+ ret0 = ret = h.get(t);
+ } else {
+ if (ret0 != null) {
+ ret = new HashSet<V>();
+ 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<V>(ret));
+ return ret;
+ }
+ }
+ private final Iterable<V> emptyIterator = new EmptyIterator<V>();
+}
--- /dev/null
+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 <tt>V</tt> (roughly, infinite sets of <tt>V</tt>'s equipped with union/intersection/complement) */
+public interface Topology<V> {
+
+ public void add(Topology<V> t);
+ public void add(V t);
+ public void remove(Topology<V> t);
+ public void remove(V t);
+ public Topology<V> dup();
+ public boolean contains(V v);
+ public Topology<V> fresh();
+
+ public Topology<V> intersect(Topology<V> t);
+ public Topology<V> minus(Topology<V> t);
+ public Topology<V> union(Topology<V> t);
+ public boolean disjoint(Topology<V> t);
+ public boolean containsAll(Topology<V> t);
+
+ public abstract int hashCode();
+ public abstract boolean equals(Object o);
+}
--- /dev/null
+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]
--- /dev/null
+//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*
+
+
+}
--- /dev/null
+ts ::= ws Ts ws => ts
+Ts ::= Test*
+ws !::= w*
+Test ::= ^"testcase" "{" Input Output+ Grammar "}"
+ | ^"testcase" "{" Input Grammar "}"
+Output ::= "output" quoted ";"
+Input ::= "input" quoted ";"