initial import
authoradam <adam@megacz.com>
Mon, 12 Dec 2005 07:23:16 +0000 (02:23 -0500)
committeradam <adam@megacz.com>
Mon, 12 Dec 2005 07:23:16 +0000 (02:23 -0500)
darcs-hash:20051212072316-5007d-b2da724d7a4090bc581c289fdec49c2a295abbdc.gz

44 files changed:
LICENSE [new file with mode: 0644]
Makefile [new file with mode: 0644]
README [new file with mode: 0644]
TODO [new file with mode: 0644]
doc/jargon.txt [new file with mode: 0644]
doc/osq.lunch.talk.pdf [new file with mode: 0644]
doc/preprint.pdf [new file with mode: 0644]
doc/sbp.html [new file with mode: 0644]
index.html [new file with mode: 0644]
src/edu/berkeley/sbp/Atom.java [new file with mode: 0644]
src/edu/berkeley/sbp/Element.java [new file with mode: 0644]
src/edu/berkeley/sbp/Forest.java [new file with mode: 0644]
src/edu/berkeley/sbp/GSS.java [new file with mode: 0644]
src/edu/berkeley/sbp/Parser.java [new file with mode: 0644]
src/edu/berkeley/sbp/Repeat.java [new file with mode: 0644]
src/edu/berkeley/sbp/Sequence.java [new file with mode: 0644]
src/edu/berkeley/sbp/Token.java [new file with mode: 0644]
src/edu/berkeley/sbp/Tree.java [new file with mode: 0644]
src/edu/berkeley/sbp/Union.java [new file with mode: 0644]
src/edu/berkeley/sbp/Walk.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/CharToken.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/MetaGrammar.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/ReflectiveWalker.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/RegressionTests.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/StringWalker.java [new file with mode: 0644]
src/edu/berkeley/sbp/misc/TreeWalker.java [new file with mode: 0644]
src/edu/berkeley/sbp/package.html [new file with mode: 0644]
src/edu/berkeley/sbp/tib/Braces.java [new file with mode: 0644]
src/edu/berkeley/sbp/tib/Tib.java [new file with mode: 0644]
src/edu/berkeley/sbp/tib/TibDoc.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/ArrayIterator.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/EmptyIterator.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/FastSet.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/HashMapBag.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/IntegerTopology.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/MapBag.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/Range.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/Reflection.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/StringUtil.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/TopologicalBag.java [new file with mode: 0644]
src/edu/berkeley/sbp/util/Topology.java [new file with mode: 0644]
tests/meta.g [new file with mode: 0644]
tests/regression.tc [new file with mode: 0644]
tests/testcase.g [new file with mode: 0644]

diff --git a/LICENSE b/LICENSE
new file mode 100644 (file)
index 0000000..acf93e9
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,24 @@
+* Copyright (c) 2005, Regents of the University of California
+* All rights reserved.
+* Redistribution and use in source and binary forms, with or without
+* modification, are permitted provided that the following conditions are met:
+*
+*     * Redistributions of source code must retain the above copyright
+*       notice, this list of conditions and the following disclaimer.
+*     * Redistributions in binary form must reproduce the above copyright
+*       notice, this list of conditions and the following disclaimer in the
+*       documentation and/or other materials provided with the distribution.
+*     * Neither the name of the University of California, Berkeley nor the
+*       names of its contributors may be used to endorse or promote products
+*       derived from this software without specific prior written permission.
+*
+* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND ANY
+* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+* DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
+* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..40ad504
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,48 @@
+
+java = java
+
+regress:
+       make boot
+       rm edu.berkeley.sbp.jar
+       make test
+
+profile: edu.berkeley.sbp.jar
+       $(java) -agentlib:yjpagent \
+               -cp $< edu.berkeley.sbp.misc.RegressionTests \
+               -profile \
+               tests/meta.g \
+               tests/testcase.g \
+               tests/regression.tc
+
+test: edu.berkeley.sbp.jar
+       $(java) -cp $< edu.berkeley.sbp.misc.RegressionTests \
+               tests/meta.g \
+               tests/testcase.g \
+               tests/regression.tc
+
+boot: edu.berkeley.sbp.jar
+       cd src; \
+       $(java) -cp ../$< \
+               edu.berkeley.sbp.misc.MetaGrammar \
+               ../tests/meta.g \
+               edu.berkeley.sbp.misc.MetaGrammar
+
+edu.berkeley.sbp.jar: $(shell find src -name \*.java)
+       mkdir -p bin
+       javac -d bin -sourcepath src $^
+       cd bin; jar cf ../$@ .
+
+javadoc:
+       rm -rf doc/api
+       mkdir -p doc/api
+       javadoc -sourcepath src -public -d doc/api `find src -name \*.java`
+
+clean:
+       rm -rf doc/api edu.berkeley.sbp.jar bin edu.berkeley.sbp.tar.gz
+
+upload:
+       make clean
+       make javadoc
+       darcs dist
+       echo '<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/
diff --git a/README b/README
new file mode 100644 (file)
index 0000000..fd7dd4c
--- /dev/null
+++ b/README
@@ -0,0 +1,78 @@
+==============================================================================
+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.
diff --git a/TODO b/TODO
new file mode 100644 (file)
index 0000000..4931457
--- /dev/null
+++ b/TODO
@@ -0,0 +1,110 @@
+
+______________________________________________________________________________
+pre-1.0
+
+  - Javadoc comments
+
+  - switch maximal to not-followed-by (~/~)
+
+  - should Union.add() be there?
+  - should Atom.top() be there?
+
+  - fix the location stuff, it's broken
+  - decent/better error messages
+
+  - finalize metagrammar
+      - Java grammar
+      - TeX (math?)
+      - URL (RFC)
+      - RFC2822 (email message/headers)
+
+  - WIKI!!!  TEX!!!
+
+______________________________________________________________________________
+Undecided
+
+  - public API for hates/needs
+
+  - clean up the whole Walk situation
+  - cleaner solution to "maximal"?
+  - "lift" cases:
+      - right now I can only lift the last child in a forest...  begs
+        the question of what the right representation for Forests is
+        if we need to be able to do lift operations on it.
+
+
+______________________________________________________________________________
+post-1.0
+
+  - Implement a k-token peek buffer (for each state, see if it "dead
+    ends" during the next k Phases based solely on state -- ignoring
+    result SPPF)
+
+  - Arrange for the SPPF corresponding to dropped subtrees to never be
+    generated (or merged, etc)
+
+  - Is there any way we can avoid creating a GSS.Node instance for
+    nodes which are transient in the sense that they have only one
+    eligible reduction?
+
+  - Implement "GLR syntactic predicates" -- the ability to do
+    arbitrary lookahead (ie "followed-by" and "not-followed-by" for
+    arbitrary patterns).  This enables generalized longest-match and
+    lets us drop the Maximal hack.
+
+  - Re-read Rekers, particularly the stuff on optimal sharing
+
+  - Isolate the Element objects from Parse.Table/GSS so we can move
+    towards compilation.
+
+  - consider allowing a Forest.Body to represent some other Tree whose
+    Body's should be [recursively] considered part of this Forest.
+
+      - perhaps not: right now we have a nice situation where
+        Forest.Ref instances become immutable once iterator()ed.  This
+        also gives us a strong place to to culling with the certainty
+        that we won't throw out a Body which would later be salvaged
+        by some yet-to-be-added dependency.
+
+  - Figure out if there is a way to:
+
+      - allow unwrapping of children other than the very last one.
+
+      - fold repetitions into an array form in Forest, before
+        conversion to Tree.  The major problem here is that multiple
+        tree-arrays are possible, all of different lengths.  Worse,
+        even if they're all the same length, not all elements belong
+        in the same "possibility vector" as all others.  You
+        essentially need a GSS to represent the array, which perhaps
+        is what the unfolded form was in the first place.
+
+  - Wikipedia grammar (needs to be both lexerless and boolean)
+
+  - Boolean Parsing
+      => Ordered Choice (";" operator)
+
+  - bring back in parse-table phase resolution of precedence (just
+    like associativity).  This can be inferred from the use of ">"
+    when the rules are in one of these special forms:
+
+       E ::=  E     _
+           >  _     E
+
+       E ::=  _     E
+           >  E  _  E
+
+       E ::=  E  _  E
+           >  E  _  E
+
+    where "_" is anything and "E" is the defining nonterminal.
+    Essentially what we're looking for is the situation where the
+    leftmost portion of one rule produces another rule, and the
+    rightmost portion of the latter produces the former.
+
+    I'm not 100% certain that this is as "strong" as the prefer/avoid
+    form (try to prove this, you probably can), but it's "what people
+    intend" most of the time.
+
+  - implement Johnstone's algorithm for "reduced, resolved LR
+    tables" to eliminate superfluous reductions on
+    epsilon-transitions.
diff --git a/doc/jargon.txt b/doc/jargon.txt
new file mode 100644 (file)
index 0000000..c622090
--- /dev/null
@@ -0,0 +1,112 @@
+______________________________________________________________________________
+Definitions
+
+  Token    -- an indivisible datum.  Most things in SBP are parameterized
+              over a token type.
+  Tree     -- a tree of Tokens; each node consists of a Token (called the
+              node's "head") and zero or more children (which are in
+              turn Trees).  To use a Haskell-like notation,
+                data Tree a = Tree a [Tree]
+              Note that (1) this is not the algebraic type most
+              commonly used for trees and (2) this model of trees is
+              not simply specific to the data structures used to
+              implement SBP -- the parser assumes that everything it
+              deals with is a Token, Tree, or Forest (see below).
+  Forest   -- a set of trees.  There is an implicit assumption here that
+              a Forest can be represented efficiently when its
+              constituent trees share supertrees and subtrees.
+              SBP does not yet commit to a specific model of Forests,
+              and the API exposes little more than the ability to expand
+              a Forest into a set of Trees.  This may change.
+              One key issue to resolve is how to efficiently represent
+              trees with a huge number of children where only a subset
+              of these children are shared (this effectively requires a
+              Tomita-style SPPF just for the child-list).  Currently
+              this issue is sidestepped by the fact that the "raw" parse
+              forest will never have a tree of arity greater than the
+              longest production rule (and therefore not unreasonably
+              long); the "unfolding" transformation used to create
+              arrays out of EBNF-repetition productions takes place
+              during the Forest-to-TreeSet expansion.  Clearly this is
+              not an ideal long-term solution.
+  Element  -- a pattern which:
+                 1. matches a sequence of zero or more Trees
+                 2. uses the matched Trees to create a sequence of output Forests
+              The restriction that the result of an Element can only be
+              zero or one Trees (rather than zero or more) is one which
+              we hope to lift soon.
+  Atom     -- an Element which matches exactly one Token.  An Atom is
+              effectively a (possibly infinite) set of Tokens; matching
+              is a membership-test.
+
+  Sequence -- an Element which matches the juxtaposition of zero or
+              more sub-Elements, and which creates its output Tree by
+              composing the output Trees of those sub-Elements.
+
+     Position -- within a specific Sequence, a Position is the
+                 imaginary space before or after one of the elements
+                 (ie at the beginning of the sequence, at the end, or
+                 between two elements).  Positions correspond exactly
+                 to the automata-theoretic notion of an LR "item", but
+                 "item" is such a horribly chosen and vague name that
+                 I just couldn't bring myself to perpetuate it.  Note
+                 that Positions and Locations have no relationship to
+                 each other.
+
+  Union    -- an Element which matches exactly one of a set of one or
+              more sub-Elements; its output forest is union
+
+  Location -- a specific location in the input tree.  This notion
+              still needs to be formalized; for example, not all
+              nodes in the output Forest have a sensible notion of
+              Location.
+
+
+______________________________________________________________________________
+Tree Notation
+
+The following notation is used for Tree<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
+
+
diff --git a/doc/osq.lunch.talk.pdf b/doc/osq.lunch.talk.pdf
new file mode 100644 (file)
index 0000000..31ca8d2
Binary files /dev/null and b/doc/osq.lunch.talk.pdf differ
diff --git a/doc/preprint.pdf b/doc/preprint.pdf
new file mode 100644 (file)
index 0000000..6600afd
Binary files /dev/null and b/doc/preprint.pdf differ
diff --git a/doc/sbp.html b/doc/sbp.html
new file mode 100644 (file)
index 0000000..fe6ac8f
--- /dev/null
@@ -0,0 +1,242 @@
+<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 &amp; 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&lt;T&gt;</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
diff --git a/index.html b/index.html
new file mode 100644 (file)
index 0000000..36be89b
--- /dev/null
@@ -0,0 +1 @@
+<html><head><meta HTTP-EQUIV="Refresh" CONTENT="0;URL=doc/sbp.html"></head></html>
diff --git a/src/edu/berkeley/sbp/Atom.java b/src/edu/berkeley/sbp/Atom.java
new file mode 100644 (file)
index 0000000..0722d0b
--- /dev/null
@@ -0,0 +1,30 @@
+package edu.berkeley.sbp;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+
+/** an element which matches exactly one input token */
+public abstract class Atom<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();
+}
+
diff --git a/src/edu/berkeley/sbp/Element.java b/src/edu/berkeley/sbp/Element.java
new file mode 100644 (file)
index 0000000..b199a23
--- /dev/null
@@ -0,0 +1,24 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+/** the root superclass for all components of the grammar (terminals, nonterminals, literals, etc) */
+public abstract class Element {
+
+    /** add all positions reachable from the start of this Element to @rp */
+    abstract void reachable(HashSet<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;
+    }
+}
diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
new file mode 100644 (file)
index 0000000..13ac199
--- /dev/null
@@ -0,0 +1,217 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+/** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */
+public abstract class Forest<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];
+}
diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
new file mode 100644 (file)
index 0000000..d8c0fd4
--- /dev/null
@@ -0,0 +1,328 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+//////////////////////////////////////////////////////////////////////////////
+// TODO:
+//
+//  - fix public/package/private status
+//
+
+//////////////////////////////////////////////////////////////////////////////
+// Optimizations to add
+//
+// ** NOTE: not all of these are appropriate for this class -- it is
+//          simply a list of optimizations not implemented.  This
+//          class is meant to remain simple and easy to understand;
+//          optimizations which obscure that do not belong here (they
+//          should go into the compiled version instead)
+//
+// - most of our time is now spent creating and storing Reduct instances
+// - we should be able to perform Reduct's immediately after creating them...
+//
+
+/** implements Tomita's Graph Structured Stack */
+class GSS {
+
+    public GSS() { }
+
+    /** corresponds to a positions <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);
+    }
+
+}
diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
new file mode 100644 (file)
index 0000000..046e725
--- /dev/null
@@ -0,0 +1,337 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+/** a parser which translates streams of Tokens of type T into a Forest<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];
+}
diff --git a/src/edu/berkeley/sbp/Repeat.java b/src/edu/berkeley/sbp/Repeat.java
new file mode 100644 (file)
index 0000000..2365cbd
--- /dev/null
@@ -0,0 +1,63 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+/** currently this class exports only static methods to create repetitions; there are no public instance methods or constructors */
+public class Repeat extends Union {
+
+    /** repeat zero or one times */
+    public  static Repeat maybe(Element e)              { return new Repeat(e, true, false); }
+    /** repeat zero or more times */
+    public  static Repeat many0(Element e)              { return new Repeat(e, true, true); }
+    /** repeat zero or more times, separated by <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));
+        }
+    }
+}
diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
new file mode 100644 (file)
index 0000000..fcff530
--- /dev/null
@@ -0,0 +1,207 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+/** juxtaposition; zero or more adjacent Elements; can specify a rewriting */
+public abstract class Sequence extends Element implements Iterable<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;
+        }
+    }
+}
diff --git a/src/edu/berkeley/sbp/Token.java b/src/edu/berkeley/sbp/Token.java
new file mode 100644 (file)
index 0000000..196f5ca
--- /dev/null
@@ -0,0 +1,34 @@
+package edu.berkeley.sbp;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+
+/** a token of input -- note that this represents an <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();
+    }
+
+}
+
diff --git a/src/edu/berkeley/sbp/Tree.java b/src/edu/berkeley/sbp/Tree.java
new file mode 100644 (file)
index 0000000..989224c
--- /dev/null
@@ -0,0 +1,57 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+/** a tree (or node in a tree); see jargon.txt for details */
+public class Tree<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;
+    }
+
+
+}
diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java
new file mode 100644 (file)
index 0000000..df6c374
--- /dev/null
@@ -0,0 +1,90 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+/** an element which can produce one of several alternatives */
+public class Union extends Element implements Iterable<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(); }
+            };
+        }
+    }
+
+}
diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java
new file mode 100644 (file)
index 0000000..5754726
--- /dev/null
@@ -0,0 +1,191 @@
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.Sequence.Position;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+/** a traversal of the grammar performed by mapping from Elements to a lattice and computing the resulting LUB */
+abstract class Walk<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>();
+    }
+}
diff --git a/src/edu/berkeley/sbp/misc/CharToken.java b/src/edu/berkeley/sbp/misc/CharToken.java
new file mode 100644 (file)
index 0000000..bad4372
--- /dev/null
@@ -0,0 +1,169 @@
+package edu.berkeley.sbp.misc;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+
+/** an implementation of Token for streams of Java <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;
+        }
+    }
+
+}
diff --git a/src/edu/berkeley/sbp/misc/MetaGrammar.java b/src/edu/berkeley/sbp/misc/MetaGrammar.java
new file mode 100644 (file)
index 0000000..9244f05
--- /dev/null
@@ -0,0 +1,758 @@
+package edu.berkeley.sbp.misc;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import java.util.*;
+import java.io.*;
+
+public class MetaGrammar extends ReflectiveWalker {
+
+    public static Union make() throws Exception {
+        return ((MetaGrammar)new MetaGrammar().walk(meta)).done();
+    }
+
+
+    // FIXME
+    private static HashSet<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
+        ;
+}
+
+
+
+
+
+
diff --git a/src/edu/berkeley/sbp/misc/ReflectiveWalker.java b/src/edu/berkeley/sbp/misc/ReflectiveWalker.java
new file mode 100644 (file)
index 0000000..2334d62
--- /dev/null
@@ -0,0 +1,100 @@
+package edu.berkeley.sbp.misc;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+public class ReflectiveWalker extends StringWalker {
+    public ReflectiveWalker()              { this.target = this; }
+    public ReflectiveWalker(Object target) { this.target = target; }
+    private final Object target;
+    private String normalize(String s) {
+        StringBuffer ret = new StringBuffer();
+        for(int i=0; i<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");
+    }
+}
diff --git a/src/edu/berkeley/sbp/misc/RegressionTests.java b/src/edu/berkeley/sbp/misc/RegressionTests.java
new file mode 100644 (file)
index 0000000..85a526b
--- /dev/null
@@ -0,0 +1,164 @@
+package edu.berkeley.sbp.misc;
+import java.io.*;
+import java.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.misc.*;
+import edu.berkeley.sbp.*;
+
+// priorities are all messy and dont get serialized
+// 1. Error messages
+// 2. Java MetaGrammar (proof of concept)
+// 3. Ivan's MetaGrammar
+// 4. Documentation format
+//       - TIB
+
+// TODO: better API for interfacing with Java
+// TODO: error messages
+// TODO: integrate with TIB
+
+// Element
+// Walk
+// ParseTable / GSS
+// MetaGrammar (necessary/relevant?)
+// Tree<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)+" "; }
+}
+
diff --git a/src/edu/berkeley/sbp/misc/StringWalker.java b/src/edu/berkeley/sbp/misc/StringWalker.java
new file mode 100644 (file)
index 0000000..923c639
--- /dev/null
@@ -0,0 +1,15 @@
+package edu.berkeley.sbp.misc;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+public abstract class StringWalker extends TreeWalker<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");
+    }
+}
diff --git a/src/edu/berkeley/sbp/misc/TreeWalker.java b/src/edu/berkeley/sbp/misc/TreeWalker.java
new file mode 100644 (file)
index 0000000..38cbb81
--- /dev/null
@@ -0,0 +1,20 @@
+package edu.berkeley.sbp.misc;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+
+public abstract class TreeWalker<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);
+    }
+}
diff --git a/src/edu/berkeley/sbp/package.html b/src/edu/berkeley/sbp/package.html
new file mode 100644 (file)
index 0000000..b712dd9
--- /dev/null
@@ -0,0 +1,3 @@
+<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>
diff --git a/src/edu/berkeley/sbp/tib/Braces.java b/src/edu/berkeley/sbp/tib/Braces.java
new file mode 100644 (file)
index 0000000..74a3dab
--- /dev/null
@@ -0,0 +1,41 @@
+package edu.berkeley.sbp.tib;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.Sequence.Position;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+public class Braces {}/*extends Union {
+
+    private static final Element left  = CharToken.string("{");
+    private static final Element right = CharToken.string("}");
+    
+    public static String join(Object[] e) {
+        StringBuffer ret = new StringBuffer();
+        for(int i=0; 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 }));
+    }
+}
+                      */
diff --git a/src/edu/berkeley/sbp/tib/Tib.java b/src/edu/berkeley/sbp/tib/Tib.java
new file mode 100644 (file)
index 0000000..df56855
--- /dev/null
@@ -0,0 +1,246 @@
+// 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();
+    }
+    */    
+}
+
diff --git a/src/edu/berkeley/sbp/tib/TibDoc.java b/src/edu/berkeley/sbp/tib/TibDoc.java
new file mode 100644 (file)
index 0000000..504e3a4
--- /dev/null
@@ -0,0 +1,110 @@
+// Copyright 2005 the Contributors, as shown in the revision logs.
+// Licensed under the Apache Public Source License 2.0 ("the License").
+// You may not use this file except in compliance with the License.
+
+package edu.berkeley.sbp.tib;
+//import org.ibex.util.*;
+//import org.ibex.io.*;
+import java.util.*;
+import java.io.*;
+
+public class TibDoc {
+    /*
+    public static enum Style { H, UL, TT, SO, IT, Q, B, PRE, LIST, EMDASH; }
+
+    public static AST h(AST a)      { return new Gather(a, Style.H); }
+    public static AST ul(AST a)     { return new Gather(a, Style.UL); }
+    public static AST tt(AST a)     { return new Gather(a, Style.TT); }
+    public static AST so(AST a)     { return new Gather(a, Style.SO); }
+    public static AST it(AST a)     { return new Gather(a, Style.IT); }
+    public static AST q(AST a)      { return new Gather(a, Style.Q); }
+    public static AST b(AST a)      { return new Gather(a, Style.B); }
+    public static AST pre(AST a)    { return new Gather(a, Style.PRE); }
+    public static AST list(AST a)   { return new Gather(a, Style.LIST); }
+    public static AST emdash()      { return new Gather(Style.EMDASH); }
+
+    public static AST seq(AST a) { return new Gather(a); }
+
+    public static class Latex {
+        public static void emit(PrintWriter p, AST a) {
+            prefix(p);
+            emit(p, a, "");
+            suffix(p);
+        }
+        public static void emit2(PrintWriter p, AST ast, String head) {
+            for(AST a = ast.getFirstChild(); a != null; a = a.getNextSibling()) emit(p, a, head);
+        }
+        public static void emit(PrintWriter p, AST ast, String head) {
+            if (!(ast instanceof Gather)) {
+                if (ast.getNumberOfChildren()==0) {
+                    p.print(ast.getText());
+                } else {
+                    emit2(p, ast, head);
+                }
+                return;
+            }
+            Gather a = (Gather)ast;
+            if (a.style==null) {
+                emit2(p, a, head);
+                return;
+            }
+            switch(a.style) {
+                case H:    p.println(); p.println(); p.print("\\"+head+"section{"); emit2(p, a, "sub"+head); p.println("}"); break;
+                case B:    p.print("{\\bf{");                          emit2(p, a, head); p.print("}}"); break;
+                case UL:   p.print("{\\ul{");                          emit2(p, a, head); p.print("}}"); break;
+                case IT:   p.print("{\\it{");                          emit2(p, a, head); p.print("}}"); break;
+                case TT:   p.print("{\\tt{");                          emit2(p, a, head); p.print("}}"); break;
+                case SO:   p.print("{\\overstrike{");                  emit2(p, a, head); p.print("}}"); break;
+                case Q:    p.print("``");                              emit2(p, a, head); p.print("''"); break;
+                case EMDASH: p.print(" \\emdash "); break;
+                case LIST: p.println(); p.println("\\startitemize[symbol]"); emit2(p, a, head); p.println("\\stopitemize"); break;
+                case PRE:
+                    if (a.getFirstChild() != null) {
+                        p.println();
+                        p.println("\\begin{verbatim}");
+                        p.println(a.getFirstChild().getText());
+                        p.println("\\end{verbatim}");
+                    }
+            }
+        }
+        public static void prefix(PrintWriter p) {
+            p.println("% generated by TIBDOC");
+            for(int i=0; i<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" };
+    }
+    */
+}
+
diff --git a/src/edu/berkeley/sbp/util/ArrayIterator.java b/src/edu/berkeley/sbp/util/ArrayIterator.java
new file mode 100644 (file)
index 0000000..61bbcfb
--- /dev/null
@@ -0,0 +1,15 @@
+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; }
+}
diff --git a/src/edu/berkeley/sbp/util/EmptyIterator.java b/src/edu/berkeley/sbp/util/EmptyIterator.java
new file mode 100644 (file)
index 0000000..3c6d197
--- /dev/null
@@ -0,0 +1,9 @@
+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; }
+}
diff --git a/src/edu/berkeley/sbp/util/FastSet.java b/src/edu/berkeley/sbp/util/FastSet.java
new file mode 100644 (file)
index 0000000..a433b7c
--- /dev/null
@@ -0,0 +1,56 @@
+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;
+    }
+}
diff --git a/src/edu/berkeley/sbp/util/HashMapBag.java b/src/edu/berkeley/sbp/util/HashMapBag.java
new file mode 100644 (file)
index 0000000..5430a8f
--- /dev/null
@@ -0,0 +1,26 @@
+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(); }
+}
diff --git a/src/edu/berkeley/sbp/util/IntegerTopology.java b/src/edu/berkeley/sbp/util/IntegerTopology.java
new file mode 100644 (file)
index 0000000..e9f01df
--- /dev/null
@@ -0,0 +1,76 @@
+package edu.berkeley.sbp.util;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+
+/** implementation of <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();
+    }
+}
diff --git a/src/edu/berkeley/sbp/util/MapBag.java b/src/edu/berkeley/sbp/util/MapBag.java
new file mode 100644 (file)
index 0000000..f1da08c
--- /dev/null
@@ -0,0 +1,10 @@
+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();
+}
diff --git a/src/edu/berkeley/sbp/util/Range.java b/src/edu/berkeley/sbp/util/Range.java
new file mode 100644 (file)
index 0000000..399d2bb
--- /dev/null
@@ -0,0 +1,737 @@
+// Taken from com.onionnetworks.util (BSD license)
+// Many thanks, Justin and Ry4an!
+
+/*
+ * Common Java Utilities
+ *
+ * Copyright (C) 2000-2001 Justin Chapweske (justin@chapweske.com)
+ * Copyright (C) 2000-2001 Ry4an Brase (ry4an@ry4an.org) 
+ * Copyright (C) 2001 Onion Networks
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
+ * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
+ * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
+ * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
+ * OF SUCH DAMAGE.
+ */
+package edu.berkeley.sbp.util;
+import java.util.*;
+import java.text.*;
+
+/**
+ * This class represents a range of integers (incuding positive and negative 
+ * infinity).
+ */
+public class Range {
+
+    private boolean negInf, posInf;
+    private long min,max;
+   
+    /**
+     * Creates a new Range that is only one number, both min and max will
+     * equal that number.
+     * @param num The number that this range will encompass.
+     */
+    public Range(long num) {
+        this(num,num,false,false);
+    }
+
+    /**
+     * Creates a new Range from min and max (inclusive)
+     * @param min The min value of the range.
+     * @param max The max value of the range.
+     */
+    public Range(long min, long max) {
+        this(min,max,false,false);
+    }
+
+    /**
+     * Creates a new Range from min to postive infinity
+     * @param min The min value of the range.
+     * @param posInf Must be true to specify max == positive infinity
+     */
+    public Range(long min, boolean posInf) {
+        this(min,Long.MAX_VALUE,false,posInf);
+        if (!posInf) {
+            throw new IllegalArgumentException("posInf must be true");
+        }
+    }
+
+    /**
+     * Creates a new Range from negative infinity to max.
+     * @param negInf Must be true to specify min == negative infinity
+     * @param max The max value of the range.
+     */
+    public Range(boolean negInf, long max) {
+        this(Long.MIN_VALUE,max,negInf,false);
+        if (!negInf) {
+            throw new IllegalArgumentException("negInf must be true");
+        }
+    }
+
+    /**
+     * Creates a new Range from negative infinity to positive infinity.
+     * @param negInf must be true.
+     * @param posInf must be true.
+     */
+    public Range(boolean negInf, boolean posInf) {
+        this(Long.MIN_VALUE,Long.MAX_VALUE,negInf,posInf);
+        if (!negInf || !posInf) {
+            throw new IllegalArgumentException
+                ("negInf && posInf must be true");
+        }
+    }
+
+    private Range(long min, long max, boolean negInf, boolean posInf) {
+       if (min > max) {
+           throw new IllegalArgumentException
+             ("min cannot be greater than max");
+       }
+       // very common bug, its worth reporting for now.
+       if (min == 0 && max == 0) {
+           System.err.println("Range.debug: 0-0 range detected. "+
+                              "Did you intend to this? :");
+           new Exception().printStackTrace();
+       }
+        this.min = min;
+        this.max = max;
+        this.negInf = negInf;
+        this.posInf = posInf;
+    }
+    
+    /**
+     * @return true if min is negative infinity.
+     */
+    public boolean isMinNegInf() {
+        return negInf;
+    }
+
+    /**
+     * @return true if max is positive infinity.
+     */
+    public boolean isMaxPosInf() {
+        return posInf;
+    }
+
+    /**
+     * @return the min value of the range.
+     */
+    public long getMin() {
+       return min;
+    }
+    
+    /**
+     * @return the max value of the range.
+     */
+    public long getMax() {
+       return max;
+    }
+    
+    /**
+     * @return The size of the range (min and max inclusive) or -1 if the range
+     * is infinitly long.
+     */
+    public long size() {
+        if (negInf || posInf) {
+            return -1;
+        }
+        return max-min+1;
+    }
+
+    /**
+     * @param i The integer to check to see if it is in the range.
+     * @return true if i is in the range (min and max inclusive)
+     */
+    public boolean contains(long i) {
+       return i >= min && i <= max;
+    }
+    
+    /**
+     * @param r The range to check to see if it is in this range.
+     * @return true if this range contains the entirety of the passed range.
+     */
+    public boolean contains(Range r) {
+       return r.min >= min && r.max <= max;
+    }
+    
+    
+    public int hashCode() {
+       return (int) (min + 23 * max);
+    }
+    
+    public boolean equals(Object obj) {
+       if (obj instanceof Range &&
+           ((Range) obj).min == min && ((Range) obj).max == max &&
+            ((Range) obj).negInf == negInf && ((Range) obj).posInf == posInf) {
+           return true;
+       } else {
+           return false;
+       }
+    }
+    
+    public String toString() {
+       if (!negInf && !posInf && min == max) {
+           return new Long(min).toString();
+       } else {
+           return (negInf ? "(" : ""+min) + "-" + (posInf ? ")" : ""+max);
+       }
+    }
+    
+    /**
+     * This method creates a new range from a String.
+     * Allowable characters are all integer values, "-", ")", and "(".  The
+     * open and closed parens indicate positive and negative infinity.
+     * <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));
+                }
+            }
+        }
+        */
+    }
+}
+
diff --git a/src/edu/berkeley/sbp/util/Reflection.java b/src/edu/berkeley/sbp/util/Reflection.java
new file mode 100644 (file)
index 0000000..cf683f0
--- /dev/null
@@ -0,0 +1,122 @@
+package edu.berkeley.sbp.util;
+import java.io.*;
+import java.lang.reflect.*;
+
+/** Random reflection-related utilities */
+public final class Reflection {
+
+    private static Object rebuild(Object o, Class c) {
+        //System.out.println("rebuild " + o + " (a " + (o==null?null:o.getClass().getName()) + ") " + c);
+        if (o==null || c.isAssignableFrom(o.getClass())) return o;
+        if ((c == Character.class || c == Character.TYPE) && o instanceof String && ((String)o).length()==1) return new Character(((String)o).charAt(0));
+        if (o instanceof Character && c == String.class) return o+"";
+        if (o instanceof Object[]) {
+            Object[] a = (Object[])o;
+            if (c.isArray()) {
+                Object[] ret = (Object[])Array.newInstance(c.getComponentType(), a.length);
+                for(int i=0; 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+"";
+    }
+
+}
diff --git a/src/edu/berkeley/sbp/util/StringUtil.java b/src/edu/berkeley/sbp/util/StringUtil.java
new file mode 100644 (file)
index 0000000..fc8f8e1
--- /dev/null
@@ -0,0 +1,58 @@
+package edu.berkeley.sbp.util;
+
+/** miscellaneous string utilities */
+public class StringUtil {
+    public static String toJavaString(String s) {
+        StringBuffer sb = new StringBuffer();
+        for(int i=0; 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();
+    }
+}
diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java
new file mode 100644 (file)
index 0000000..7812a51
--- /dev/null
@@ -0,0 +1,121 @@
+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>();
+}
diff --git a/src/edu/berkeley/sbp/util/Topology.java b/src/edu/berkeley/sbp/util/Topology.java
new file mode 100644 (file)
index 0000000..4f36f08
--- /dev/null
@@ -0,0 +1,29 @@
+package edu.berkeley.sbp.util;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.*;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+import java.lang.ref.*;
+
+// FIXME: this should be a value class -- add/remove/etc should return new Topology objects
+/** values inhabiting a topology over <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);
+}
diff --git a/tests/meta.g b/tests/meta.g
new file mode 100644 (file)
index 0000000..0920a7a
--- /dev/null
@@ -0,0 +1,54 @@
+s         ::=  w* Grammar w*                  => "gram"
+Grammar   ::=  R+ => "grammar"
+R         ::=  word  ^"::=" Class+/gt
+            |  word ^"!::=" Class+/gt
+
+ec        ::=  [~\]\\\-\~] | escaped
+
+Class     ::=  Rewrite +/ bar                 => "alternatives"
+
+Rewrite   ::=  Rewritex
+            |  Rewritex ^"&"  E+
+            |  Rewritex ^"&~" E+
+
+Rewritex  ::=  E+                             => "rewrite"
+            |  E+ ^"=>" word
+            |  E+ ^"=>" quoted
+            |  E+  "=>" "()"                  => "wrap"
+
+range    ::= ec => "range0" | ec ^"-" ec      => "range0"
+gt   !::= ">"
+bar  !::= "|"
+E        ::= word                             => "nonTerminalY"
+           |    [(][)] => "epsilon"
+           |    ^"{" Class+/gt "}"
+           |     "[" [\~]?  range* "]"        => "range"
+           |  E ^"*/" E
+           |  E ^"+/" E
+           |  E ^"?"
+           |  E ^"~/~"
+
+           |  E ^"-"  E
+
+           |    ^"!" E
+           |     "^" quoted => "care"
+           |    ^"`" E
+           |  E ^"#"
+           |  quoted                        => "literal"
+
+           |  (E ^"**" > E ^"*")
+           |  (E ^"++" > E ^"+")
+
+           |     "(" word ^")"
+           >    ^"(" Class+/gt ")"
+
+w       !::= " "
+           | "//" [~\n]* "\n"
+           | "\n"
+           | "\r"
+an       ::= [a-zA-Z0-9_]
+word     ::= an++                           => "sify"
+quoted   ::= "\"" ([~\"\\] | escaped)* "\"" => "sify"
+escaped  ::= "\\n" => "\n"
+           | "\\r" => "\r"
+           | "\\" [~nr]
diff --git a/tests/regression.tc b/tests/regression.tc
new file mode 100644 (file)
index 0000000..040bf84
--- /dev/null
@@ -0,0 +1,305 @@
+//testcase {
+//    input  "x";
+//    output "a1:{x}";
+//
+//    s ::= a        => a1
+//    a ::= s        => s1
+//    a ::= ^"x"
+//}
+//
+//testcase {
+//    input  "x";
+//    output "x";
+//    output "s2:{s2:{s0 s0} x}";
+//    output "s2:{s0 x}";
+//
+//
+//    s ::= s s      => s2
+//    s ::= ^"x"
+//    s ::= ()       => s0
+//}
+
+testcase {
+    input "ab c";
+    output "1:{{a b} {c}}";
+
+    s   ::= ids
+    ids ::= id (" " ids &~ id [~]*) => "1"
+          | id (    ids &~ id [~]*) => "2"
+          | id
+    id  ::= [a-z]++
+}
+
+testcase {
+    input "ab c";
+
+    output "2:{{a} 1:{{b} {c}}}";
+    output "1:{{a b} {c}}";
+
+    s   ::= ids
+    ids ::= id " " ids => "1"
+          | id     ids => "2"
+          | id
+    id  ::= [a-z]+
+}
+
+testcase {
+    input "aaabbbccc";
+    output "";
+
+    s   ::= ab & dc
+    ab  ::= a b
+    dc  ::= d c
+    a   ::= "a" a     | ()
+    b   ::= "b" b "c" | ()
+    c   ::= "c" c     | ()
+    d   ::= "a" d "b" | ()
+}
+
+testcase {
+    input "aaabbbbccc";
+
+    s   ::= ab & dc
+    ab !::= a b
+    dc !::= d c
+    a   ::= "a" a     | ()
+    b   ::= "b" b "c" | ()
+    c   ::= "c" c     | ()
+    d   ::= "a" d "b" | ()
+}
+
+testcase {
+    input "12111211";
+    output "ac:{{2 1 2 1}}";
+    //output "a:{{2 1 2 1}}";
+    //output "c:{{c:{1 1} c:{1 1}}}";
+
+    s ::= ab => "ab"
+        | ac => "ac"
+        | bc => "bc"
+        //| a  =>  "a"
+        //| b  =>  "b"
+        //| c  =>  "c"
+    ab ::= a & b
+    ac ::= a & c
+    bc ::= b & c
+    a ::= ("1" x)*
+    b ::= (x "2" => "b")*
+    c ::= (x "2" x "1" => "c")*
+    x ::= [123]
+}
+
+testcase {
+    input  "xbambambam";
+    output "bam:{a bam:{a bam:{a x}}}";
+
+    s ::= a s ^"bam"
+    s ::= ^"x"
+    a ::= ()       => "a"
+}
+
+testcase {
+    input  "baaaa";
+    output "s2:{b0 a:{a:{epsilon}}}";
+    output "b:{a:{a:{epsilon}} epsilon}";
+    s ::= b t        => "s2"
+        | ^"b" t b
+    t ::= ^"a" t "a"
+        | ()         => "epsilon"
+    b ::= "b"        => "b0"
+        | ()         => "epsilon"
+}
+
+testcase {
+    input  "qaq";
+    output "q:{a:{s1:{epsilon}}}";
+
+    s ::= ^"q" x "q"
+    x ::= ^"a" a
+    x ::= ()        => "epsilon"
+    a ::= x         => "s1"
+}
+
+testcase {
+    input "baa";
+    output "s1:{a2:{a2:{a0 b0} b0}}";
+
+    s ::= "b" a     => "s1"
+    a ::= "a" a b   => "a2"
+        | ()        => "a0"
+    b ::= ()        => "b0"
+}
+
+testcase {
+    input  "aaa";
+
+    output "s3:{s3:{epsilon a0 epsilon epsilon} epsilon epsilon epsilon}";
+    output "s3:{s3:{epsilon epsilon epsilon epsilon} a0 epsilon epsilon}";
+    output "s3:{s3:{epsilon epsilon a0 epsilon} epsilon epsilon epsilon}";
+    output "s3:{s3:{epsilon epsilon epsilon a0} epsilon epsilon epsilon}";
+    output "s3:{epsilon epsilon a0 a0}";
+    output "s3:{s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon epsilon} epsilon epsilon epsilon}";
+    output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon epsilon a0}";
+    output "s3:{s3:{epsilon epsilon epsilon epsilon} epsilon a0 epsilon}";
+    output "s3:{epsilon a0 epsilon a0}";
+    output "s3:{epsilon a0 a0 epsilon}";
+
+    s ::= "a" s a a a => "s3"
+        | ()          => "epsilon"
+    a ::= "a"         => "a0"
+        | ()          => "epsilon"
+}
+
+testcase {
+    input "aa";
+    output "poo:{poo:{poox poox} poox}";
+    output "poo:{poox poo:{poox poox}}";
+    s ::= s s "a"  => "poo"
+    s ::= ()       => "poox"
+}
+
+testcase {
+    input "baa";
+    output "s:{aa:{aa:{a b} b}}";
+    s ::= "b" a      => "s"
+    a ::= "a" a b    => "aa"
+    a ::= ()         => "a"
+    b ::= ()         => "b"
+}
+
+testcase {
+    input "aaab";
+    output "sx:{b aa:{aa:{b b} b}}";
+    s ::= b d "a" "b"  => "sx"
+    s ::= "a" d "a" d  => "sy"
+    d ::= "a" a b      => "aa"
+    a ::= "a" b b      => "aa"
+    a ::= ()           => "a"
+    b ::= ()           => "b"
+}
+
+testcase {
+    input "a+(b*c)";
+    output "+:{{a} *:{{b} {c}}}";
+
+    s   ::= R
+    R   ::= id
+          | R ^"*" R
+          | R ^"+" R
+          | "(" R ")"
+    id  ::= [a-z]++
+}
+
+testcase {
+    input "a+b-d*c";
+    output "plus:{stringify:{{a}} minus:{stringify:{{b}} times:{stringify:{{d}} stringify:{{c}}}}}";
+    output "times:{plus:{stringify:{{a}} minus:{stringify:{{b}} stringify:{{d}}}} stringify:{{c}}}";
+    output "plus:{stringify:{{a}} times:{minus:{stringify:{{b}} stringify:{{d}}} stringify:{{c}}}}";
+    output "times:{minus:{plus:{stringify:{{a}} stringify:{{b}}} stringify:{{d}}} stringify:{{c}}}";
+    output "minus:{plus:{stringify:{{a}} stringify:{{b}}} times:{stringify:{{d}} stringify:{{c}}}}";
+    s  ::= S
+    w  ::= " "
+    L  ::= id
+    S  ::= L "=" Q  => "assign"
+         | Q
+    Q  ::= id
+         | L "=" Q       => "assign"
+         | Q "-" Q       => "minus"
+         | Q "+" Q       => "plus"
+         | Q "*" Q       => "times"
+         | "(" Q ")"
+    id   ::= idl++       => "stringify"
+    idl  ::= [a-d]
+}
+
+testcase {
+    input "a*b*c";
+    output "times:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}";
+    s  ::= S
+    w  ::= " "
+    L  ::= id
+    S  ::= L "=" R  => "assign"
+         | R
+    R  ::= L
+         | L "=" R       => "assign"
+         | R "+" R       => "plus"
+         | (R) "*" R       => "times"
+         | "(" R ")"
+         | R R           => "times"
+    id   ::= idl++       => "stringify"
+    idl  ::= [a-d]
+}
+
+testcase {
+    input "a+b*c";
+    output "plus:{stringify:{{a}} times:{stringify:{{b}} stringify:{{c}}}}";
+    s  ::= S
+    w  ::= " "
+    L  ::= id
+    S  ::= L "=" R  => "assign"
+         | R
+    R  ::= L
+         | L "=" R       => "assign"
+         | R "+" R       => "plus"
+         > R "*" R       => "times"
+         | "(" R ")"
+         | R R           => "times"
+    id   ::= idl++       => "stringify"
+    idl  ::= [a-d]
+}
+
+testcase {
+
+    input "
+
+
+ while x>0
+   while y>0
+    foo()
+     bar()
+
+ while x>0
+   while y>0
+    foo()
+   bar()
+
+
+";
+    output "smt:{while:{>:{{x} {0}} while:{>:{{y} {0}} sbb:{{f o o} {b a r}}}}}";
+    output "smt:{while:{>:{{x} {0}} sbb:{while:{>:{{y} {0}} {f o o}} {b a r}}}}";
+
+indent  !::= ww
+outdent !::= " "  outdent " "
+           | " "  [~]*    "\n"
+
+any      !::= [~]*
+s         ::= !any "\n\n" !ww Statement !ww "\n\n" !any => smt
+ww        ::= sp*
+sp        ::= " "
+
+block     ::= "\n" !indent  BlockBody
+           &~ "\n" outdent [~\ ] [~]*
+
+BlockBody ::= Statement
+            > Statement BlockBody => "sbb"
+
+Statement ::= Call
+            | ^"while" Expr block
+
+Expr      ::= ident
+            | Call
+            | Expr ^">" Expr
+            | num
+
+Call      ::= Expr "()"
+
+num       ::= [0-9]++
+
+ident     ::= [a-z]++ &~ keyword
+keyword   ::= "if" | "then" | "else" | "while"
+
+w         ::= " " | "\n" | "\r"
+ws        ::= w*
+
+
+}
diff --git a/tests/testcase.g b/tests/testcase.g
new file mode 100644 (file)
index 0000000..9993dce
--- /dev/null
@@ -0,0 +1,7 @@
+ts       ::= ws Ts ws => ts
+Ts       ::= Test*
+ws      !::= w*
+Test     ::= ^"testcase" "{" Input Output+ Grammar "}"
+           | ^"testcase" "{" Input         Grammar "}"
+Output   ::= "output" quoted ";"
+Input    ::= "input"  quoted ";"