Left & Right Context Sensitivity: `ChomskyGrammar`

Introduction

Instances of ChomskyGrammar class generate sequences of tokens by beginning with a short axiom, mostly consisting of rewritable tokens, by replacing each rewriteable token with a succession of new tokens, some of which may themselves be rewriteable. The process continues recursively until only terminal tokens remain. Each terminal token is identified by a unique index value consistent with the Index/Supply design. Index values range from 0 to N-1, where N should is the length of the external array or list from which supply elements are to be drawn.

Backstory

Several developers have thought to employ Chomsky's phrase-structure grammars as a basis for composing programs intended for non-programmers to use. Sources describing these efforts include Curtis Roads's 1978 document on "Composing Grammars"¹ and Steven Holtzman's 1980 article "A generative grammar definition language for music"². Bernard Bel's Bol Processor has been in ongoing development since 1981³.

My Compose program included a "Chomsky" index generator with productions that injected integer sequences between "origin" and "goal" indices. No student actually used this feature. In preparing the present page I originally intended to recreate the Compose feature, but decided instead to provide a more general formulation — something closer to Chomsky's own.

Operation

The explanations that follow will be illustrated with a grammar that generates well-formed musical rhythms. Although this particular grammar was freshly conceived to illustrate how the ChomskyGrammar, people who know my work may recognize the categorization scheme from my "Concurrence" project⁴, and the rhythmic style grammars (distinguishing jazz, rock, and ragtime) of my Cybernetic Composer. The present grammar has three TokenCategory instances: "Detach", "Tie", and "Rest". (The "Slur" category from "Concurrence" was dropped to keep the number of tokens down.)

Tokens

The tokens for this grammar are listed in Table 1. They indicate whole-note durations, half-note durations, quarter-note durations, and eighth-note durations in the "Detach", "Tie", and "Rest" categories. The naming scheme is pseudo-graphic with an initial letter indicating the category and a succession of hyphens extending out the duration by eighth notes. Rewriteable tokens use upper-case categories; terminal tokens use lower-case.

Class	Name	Category	Description
`RewriteableToken`	D-------	Detach	Rewriteable detached whole note
`RewriteableToken`	D---	Detach	Rewriteable detached half note
`RewriteableToken`	T---	Tie	Rewriteable tied half note
`RewriteableToken`	R---	Rest	Rewriteable half-note rest
`RewriteableToken`	D-	Detach	Rewriteable detached quarter note
`RewriteableToken`	T-	Tie	Rewriteable tied quarter note
`RewriteableToken`	R-	Rest	Rewriteable quarter-note rest
`TerminalToken`	d-	Detach	Terminal detached quarter note
`TerminalToken`	t-	Tie	Terminal tied quarter note
`TerminalToken`	r-	Rest	Terminal quarter-note rest
`TerminalToken`	d	Detach	Terminal detached eighth note
`TerminalToken`	t	Tie	Terminal tied eighth note
`TerminalToken`	r	Rest	Terminal eighth-note rest

Table 1: List of tokens

Token	Rule	Elaboration	Weight
D-------	Free	[D---][D---]	1.0
		[D---][T---]	1.0
	RightDR	[D---][R---]	1.0
D---	Free	[D-][D-]	1.0
		[d][d-][d]	1.0
	RightDR	[D-][R-]	1.0
T---	Free	[T-][D-]	1.0
		[T-][T-]	1.0
		[t][d-][d]	1.0
	RightDR	[T-][R-]	1.0
		[T-][d][r]	1.0
R---	Free	[R-][D-]	1.0
		[r][d-][d]	1.0
	RightDR	[R-][d][r]	1.0
D-	Free	[d][d]	1.0
	RightDR	[d][r]	1.0
T-	Free	[t][d]	1.0
		[t-]	1.0
R-	Free	[r][d]	1.0
	RightDR	[r-]	1.0

Table 2: Productions operating on the tokens listed in Table 1

Productions

The productions for this grammar are listed in Table 2. They divide whole notes into halves, half notes mostly into quarters, and quarters into eighths.

Productions designated "Free" can be applied to a rewriteable token regardless of what leads or follows the token.

Productions designated "RightDR" can be applied if what follows has category "Detach" or "Rest" but not if what follows has category "Tie". Notice that all "RightDR" elaborations end with rests; it makes no sense to tie over in this circumstance.

Notice also that tied options are offered only in the second half of a whole note and the second quarter of a half note. Treating a top-level whole note as a measure of 4-4 time, ties can never happen into beat 1. They can happen into beats 2, 3, and 4, but not elsewhere.

Generation

Table 3 (a) and Table 3 (b) illustrate how the productions from Table 2 can elaborate the axiom [D-------][D-------][D-------][D-------][d-] into two different statements, with the only difference between production runs being the random seed. The top row in each table presents the axiom, which is the same for both tables. Beneath each table is a rhythmic transcription of its sequence of terminal tokens.

D-------

D---

T---

D---

R---

D---

T---

D---

T---

D-

T-

R-

D-

T-

Table 3 (a): One statement generated by the productions listed in Table 2
from the axiom [D-------][D-------][D-------][D-------][d-].

D-------

D---

T---

D---

R---

D---

R---

D-

R-

D-

R-

D-

Table 3 (b): A second statement generated by the productions listed in Table 2
from the axiom [D-------][D-------][D-------][D-------][d-].

The second row in each table presents the first level of elaboration, which divides whole-note durations (all rewriteable) into half-note durations. Each operation begins with a rewriteable detached whole note followed in 3 of 4 instances (per table) by another rewriteable detached whole note (category "Detach") or followed in 1 of 4 instances by a terminal detached quarter note (also category "Detach"). All of these situations satisfy both the "Free" condition (offering [D---][D---] and [D---][T---]) and the "RightD" condition (offering [D---][R---]). The production is therefore chosen randomly from among these three offerings, with weight 1.0 accorded to each offering.

In Table 3 (a), as it happens, elaboration [D---][T---] was selected 3 times, [D---][R---] was selected once, and [D---][D---] wasn't selected at all.
In Table 3 (b), [D---][R---] was selected twice, [D---][T---] once, and [D---][D---] also once.

The third row in each table presents the second level of elaboration, which divides half-note (all rewriteable) durations into a mix of quarter-note and eighth-note durations. Narrowing in on [D---] instances for Table 3 (a), the follow-on token has category "Tie" in three instances (satisfying both the "Free" condition but not the "RightDR" condition) and "Rest" in once instance (satisfying both "Free" and "RightDR" conditions).

The [D---] instances followed on by "Tie" offer elaborations [D-][D-] and [d][d-][d] but not [D-][R-]. Both offered elaborations were actually selected for Table 3 (a).
The [D---] instance followed on by "Rest" offers [D-][D-], [d][d-][d], and also [D-][R-]. There being only one instance in Table 3 (a), only one of these offerings ([d][d-][d]) actually appears.

The fourth and bottom row in each table presents the third level of elaboration, which divides rewriteable quarter-note durations into a mix of terminal quarter-note and terminal eighth-note durations. Third-row terminal tokens are not subject to elaboration.

Features

My implementation of generative grammars strays from the letter (but not the spirit) of linguistic and meta-mathematical formulations I've seen:

One feature is that my implementations allow multiple rewriteable tokens. Although the linguistic formulations I've seen explicitly include only one rewritable token, there's usually words like "of the form of". Most concrete examples given applying generative grammars parts of language to could only have been generated using multiple rewriteable tokens. Having many rewriteable tokens means that the tokens themselves provide context influencing which productions may be applied. When Chomsky distinguished context-free productions from context-sensitive productions, he abstracted away this additional influence.
A second feature is that context evaluation is based on categories of token rather than specific token values. Thus "RightDR" productions evaluate positive for 9 different follow-on tokens, 5 of which have the "Detach" category and 4 of which have the "Rest" category. Categories provide efficiency.
The third feature is the introduction of weighted random selection to identify which among all compliant productions will actually be applied. When Chomsky was contemplating these grammars, he was developing a model for language compentence. To say that a statement is grammatically competent, it is enough to identify a tree of productions which elaborates an accepted axiom into the target statement.
Supporting this third feature is the separating out of the RuleProduction class from the RewriteRule class. In grammar jargon, "rewrite rules" and "productions" are the same thing. However, it proved uneconomical to implement things as "under this condition do that" rather than "under this condition do that or that or that or …".

Evaluating Statements

Weighted random selection creates branches in the production tree. With K branches and M_k alternatives introduced in the kth branch, the total number of statements obtainable from one axiom can be calculated as

N =

Π^K_k=1

M_k

This formula assumes that higher-level branching exerts no influence over lower-level production options, which is not exactly what happens in practice. Table 2 offers 3 ways to divide a whole note into half notes. The first half note is always detached, and there are 3 ways of breaking it up though only two lead to further branches. The second half note can be a detached note (3 productions), a tie (5 productions) or a rest (2 productions) giving an average just over 3. Dividing quarters into eighths gives 2 productions per quarter-note category but remember that this branch happens 4 times per whole note. The resulting product gives approximately

3 × 3×3 × 2×2×2×2 = 3×9×8 = 216

different ways of competently elaborating a whole note, and 216⁴ = 2,176,782,336 ways of elaborating four measures of 4-4 time.

Are any

Coding

First, a disclaimer: The classes presented here where adapted from the MarkovMatrix classes, which were designed to support a graphical user interface. A lot of that GUI-supporting code was carried over; however, the present ChomskyGrammar have not themselves been excercised within a GUI framework. In fact, the testing of these new classes did not extend much farther than the production runs documented in Table 3 (a) and Table 3 (b) above. So while I can confidently assert that these classes do work, I do not pretend that they will never break.

There are several classes which together implement a composite design pattern where a single parent ChomskyGrammar instance (Listing 1) stands for the whole.

Each ChomskyGrammar instance contains many child ChomskyToken instances (Listing 2) A ChomskyToken can be either a RewriteableToken (Listing 3) or a TerminalToken (Listing 4). A ChomskyGrammar also maintains a list of TokenCategory instances (Listing 5). Every ChomskyToken references a TokenCategory. The ChomskyToken, RewriteableToken, TerminalToken, and TokenCategory classes are described below under Tokens.

A RewriteableToken itself contains a set of RewriteRule instances. Each RewriteRule contains a set of 'before' categories, a set of 'after' categories, and a set of RuleProduction instances. A RuleProduction is a list of ChomskyToken references with an associated weight. The ChomskyToken and RuleProduction classes are described below under Productions.

Every ChomskyGrammar manages the set of ChomskyStatement instances associated with that particular grammar. Each ChomskyStatement is a list of ChomskyToken references. ChomskyStatement instances can be assembled by the user from both RewriteableToken and TerminalToken elements; such statements typically provide the axiom for a generation cycle. ChomskyStatement instances generated by such cycles contain only TerminalToken elements. (In grammar jargon, the word "axiom" is reserved for the process input while the word "statement" is reserved for the process output. Sorry.)

Each time an axiom is elaborated into a statement, there is an option of also generating a ProductionTree instance. A ProductionTree is a hierarchy of ProductionNode.Branch and ProductionNode.Leaf instances. A Branch references the RuleProduction which was selected to rewrite a RewriteableToken into a mix of RewriteableToken and/or TerminalToken instances. The same Branch maintains a list of child nodes, which will be either Branch instances (if the RuleProduction generated a RewriteableToken) or Leaf instances (if the RuleProduction generated a TerminalToken). I introduced the ProductionTree class into the ChomskyGrammar zoo with the specific intent of generating production hierarchies such as those displayed in Table 3 (a) and Table 3 (b) above.

The ChomskyStatement and ProductionTree classes are described below under Data.

/**
 * The {@link ChomskyGrammar} class implements an alphabet of tokens along with
 * productions.
 * @author Charles Ames
 */
public class ChomskyGrammar
extends WriteableEntity implements Indexer {
   private static final String PRODUCT_STATEMENT_NAME = "Product";
   /**
    * Master collection of {@link TerminalToken} instances,
    * indexed by id.
    */
   private SortedMap<Integer, TerminalToken> terminalsByID;
   /**
    * Master collection of {@link ChomskyToken} instances,
    * indexed by name.  Contains mix of {@link TerminalToken}
    * and {@link RewriteableToken} instances.
    */
   private SortedMap<String, ChomskyToken> tokensByName;
   /**
    * Master collection of {@link TokenCategory} instances,
    * indexed by name.
    */
   private SortedMap<String, TokenCategory> categoriesByName;
   /**
    * Master collection of {@link ChomskyStatement} instances,
    * indexed by name.
    */
   private SortedMap<String, ChomskyStatement> statementsByName;
   /**
    * The original statement, which should contain mostly
    * {@link RewriteableToken} instances.
    */
   private ChomskyStatement axiom;
   /**
    * The working statement, which starts out as a copy of the
    * axiom but which during the generation cycle has all of
    * its {@link RewriteableToken} instances rewritten into
    * {@link TerminalToken} instances.
    */
   private ChomskyStatement product;
   /**
    * Flag controlling whether or not
    * {@link #hasNextToken()}/{@link #nextToken()}
    * cycle should generate {@link ProductionTree}.
    */
   private boolean documentProduction;
   /**
    * Position of next token in {@link #product} statement.
    */
   private int incident;
   private List<ProductionNode> productionNodes;
   private List<Integer> productionLevels;
   private int indexDigits = 1;
   private DecimalFormat indexFormat;
   /**
    * The null category matches the beginning or end of a statement.
    */
   private TokenCategory nullCategory;
   /**
    * Output file format.
    */
   private OutputFormat outputFormat;
   /**
    * Constructor for {@link ChomskyGrammar} instances.
    * @param container The grammar container (may be null).
    */
   protected ChomskyGrammar(WriteableEntity container) {
      super(container);
      this.setIDQuality(Entity.AttributeQuality.MODIFIABLE);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      this.terminalsByID = new TreeMap<Integer, TerminalToken>();
      this.tokensByName = new TreeMap<String, ChomskyToken>();
      this.categoriesByName = new TreeMap<String, TokenCategory>();
      this.statementsByName = new TreeMap<String, ChomskyStatement>();
      this.outputFormat = null;
      this.indexDigits = 1;
      this.indexFormat = new DecimalFormat("0");
      this.nullCategory = createCategory("Z");
      this.axiom = null;
      this.product = null;
      this.documentProduction = false;
   }
   @Override
   public boolean setName(String name) {
      boolean result = false;
      String oldName = getOldName();
      if (name.equals(oldName)) return result;
      result = super.setName(name);
      return result;
   }
   /**
    * Getter for {@link #outputFormat}.
    * @return The assigned {@link #outputFormat} value.
    */
   public final OutputFormat getOutputFormat() {
      return outputFormat;
   }
   /**
    * Setter for {@link #outputFormat}.
    * @param outputFormat The intended {@link #outputFormat} value.
    * @return true if the value differs from the old value; false otherwise.
    */
   public boolean setOutputFormat(OutputFormat outputFormat) {
      boolean changed = false;
      if (this.outputFormat != outputFormat) {
         this.outputFormat = outputFormat;
         makeDirty();
         changed = true;
      }
      return changed;
   }
   /**
    * Getter for {@link #axiom}.
    * @return The assigned {@link #axiom} statement.
    * @throws UninitializedException when the {@link #axiom} field
    * has not been initialized.
    */
   public ChomskyStatement getAxiom() {
      if (null == axiom)
         throw new UninitializedException("Axiom not initialized");
      return axiom;
   }
   /**
    * Setter for {@link #axiom}.
    * @param axiom The intended {@link #axiom} statement.
    */
   public void setAxiom(ChomskyStatement axiom) {
      if (this != axiom.getContainer())
         throw new IllegalArgumentException("Inconsistent grammar");
      this.axiom = axiom;
   }
   /**
    * Getter for {@link #product}.
    * @return The assigned {@link #product} statement.
    * @throws UninitializedException when the {@link #product} field
    * has not been initialized.
    */
   public ChomskyStatement getProduct() {
      if (null == product)
         throw new UninitializedException("Product not initialized");
      return product;
   }
   /**
    * Getter for {@link #documentProduction}.
    * @return The assigned {@link #documentProduction} value.
    */
   public boolean isDocumentProduction() {
      return documentProduction;
   }
   /**
    * Setter for {@link #documentProduction}.
    * @param documentProduction The intended {@link
    * #documentProduction} value.
    */
   public void setDocumentProduction(boolean documentProduction) {
      this.documentProduction = documentProduction;
   }
   /**
    * Get all terminal tokens by id.
    * @return A collection of {@link TerminalToken} instances,
    * indexed by id.
    */
   public SortedMap<Integer, TerminalToken> getTerminalsByID() {
      return terminalsByID;
   }
   /**
    * Get terminal & rewriteable tokens by name.
    * @return A collection of {@link ChomskyToken} instances,
    * indexed by name.
    */
   public SortedMap<String, ChomskyToken> getTokensByName() {
      return tokensByName;
   }
   /**
    * Get all token categories by name.
    * @return A collection of {@link ChomskyToken} instances,
    * indexed by name.
    */
   public SortedMap<String, TokenCategory> getCategoriesByName() {
      return categoriesByName;
   }
   /**
    * Get all statements by name.
    * @return A collection of {@link ChomskyStatement} instances,
    * indexed by name.
    */
   public SortedMap<String, ChomskyStatement> getStatementsByName() {
      return statementsByName;
   }
   /**
    * Getter for {@link #nullCategory}.
    * @return The assigned null {@link TokenCategory} instance.
    */
   public TokenCategory getNullCategory() {
      return nullCategory;
   }
   /**
    * Get the {@link TerminalToken} with the indicated id.
    * @param id The indicated id.
    * @return The terminal token with the indicated id.
    * @throws NoSuchObjectException when there is no {@link TerminalToken}
    * with the indicated id.
    */
   public TerminalToken getTerminalToken(int id) {
      TerminalToken token = terminalsByID.get(id);
      if (null == token) {
         throw new NoSuchObjectException(
            "There is no terminal token with id [" + id + "]");
      }
      if (token.getID() != id)
         throw new RuntimeException("Programmer error");
      return token;
   }
   /**
    * Get the {@link ChomskyToken} with the indicated name.
    * @param name The indicated name.
    * @return The token with the indicated name.
    * @throws NoSuchObjectException when there is no {@link ChomskyToken} with the indicated name.
    */
   public ChomskyToken getToken(String name) {
      ChomskyToken token = tokensByName.get(name);
      if (null == token) {
         throw new NoSuchObjectException(
            "There is no token with name [" + name + "]");
      }
      if (!token.getName().equals(name))
         throw new RuntimeException("Programmer error");
      return token;
   }
   /**
    * Get the rewriteable token with the indicated name.
    * @param name The indicated name.
    * @return The rewriteable token with the indicated name.
    * @throws NoSuchObjectException when there is no rewriteable
    * token with the indicated name.
    */
   public RewriteableToken getRewriteableToken(String name) {
      ChomskyToken token = tokensByName.get(name);
      if (null == token || !token.isRewriteable())
         throw new NoSuchObjectException(
            "There is no rewriteable token with name [" + name + "]");
      if (!token.getName().equals(name))
         throw new RuntimeException("Programmer error");
      return (RewriteableToken) token;
   }
   /**
    * Test if the grammar contains a {@link TerminalToken} with the
    * indicated id.
    * @param id The indicated id.
    * @return True if the grammar contains a {@link TerminalToken} with
    * the indicated id; false otherwise.
    */
   public boolean hasTerminalToken(int id) {
      return getTerminalsByID().containsKey(id);
   }
   /**
    * Test if the grammar contains a {@link ChomskyToken} with the
    * indicated name.
    * @param name The indicated name.
    * @return True if the grammar contains a {@link ChomskyToken}
    * with the indicated name; false otherwise.
    */
   public boolean hasToken(String name) {
      return getTokensByName().containsKey(name);
   }
   /**
    * Create a new {@link TerminalToken} with the indicated id and name.
    * @param id The intended token id.
    * @param name The intended token name.
    * @return The newly created {@link TerminalToken} instance.
    * @throws IllegalArgumentException when there is already
    * a {@link TerminalToken} with the indicated id or there is already
    * a token with the indicated name.
    */
   public TerminalToken createTerminalToken(int id, String name) {
      if (hasTerminalToken(id)) {
         throw new IllegalArgumentException(
            "There is already a token with id [" + id + "]");
      }
      if (hasToken(name)) {
         throw new IllegalArgumentException(
            "There is already a token with name [" + name + "]");
      }
      TerminalToken result = new TerminalToken(this, id, name);
      refreshIndexFormat();
      makeDirty();
      return result;
   }
   /**
    * Create a new {@link TerminalToken} with the indicated id, name,
    * and category.
    * @param id The intended token id.
    * @param name The intended token name.
    * @param category The intended token category.
    * @return The newly created {@link TerminalToken} instance.
    * @throws IllegalArgumentException when there is already a token
    * with the indicated id or there is already a token with the
    * indicated name.
    */
   public TerminalToken createTerminalToken(int id, String name,
         TokenCategory category) {
      TerminalToken result = createTerminalToken(id, name);
      result.setCategory(category);
      return result;
   }
   /**
    * Remove the indicated {@link TerminalToken} instance.
    * @param token The indicated token.
    */
   public void removeTerminalToken(TerminalToken token) {
      if (this != token.getContainer())
         throw new IllegalArgumentException(
            "Token does not belong to this grammar");
      // TODO: delete all productions that reference the token.
      terminalsByID.remove(token.getID());
      tokensByName.remove(token.getName());
      token.dispose();
      refreshIndexFormat();
      makeDirty();
   }
   /**
    * Remove the {@link TerminalToken} with the indicated id.
    * @param id The indicated id.
    */
   public void removeTerminalToken(int id) {
      TerminalToken token = getTerminalToken(id);
      removeTerminalToken(token);
   }
   /**
    * Create a new {@link RewriteableToken} with the indicated id
    * and name.
    * @param name The intended token name.
    * @return The newly created {@link RewriteableToken} instance.
    * @throws IllegalArgumentException when there is already a
    * {@link ChomskyToken} with the indicated name.
    */
   public RewriteableToken createRewriteableToken(String name) {
      if (hasToken(name)) {
         throw new IllegalArgumentException(
            "There is already a token with name [" + name + "]");
      }
      RewriteableToken result = new RewriteableToken(this, name);
      makeDirty();
      return result;
   }
   /**
    * Create a new {@link RewriteableToken} with the indicated
    * name and category.
    * @param name The intended token name.
    * @param category The intended token category.
    * @return The newly created {@link RewriteableToken} instance.
    * @throws IllegalArgumentException when there is already a
    * {@link ChomskyToken} with the indicated name.
    */
   public RewriteableToken createRewriteableToken(String name,
         TokenCategory category) {
      RewriteableToken result = createRewriteableToken(name);
      result.setCategory(category);
      return result;
   }
   /**
    * Remove the indicated {@link RewriteableToken} instance.
    * @param token The indicated token.
    */
   public void removeRewriteableToken(RewriteableToken token) {
      if (this != token.getContainer())
         throw new IllegalArgumentException(
            "Token does not belong to this grammar");
      // TODO: delete all productions that reference the token.
      tokensByName.remove(token.getName());
      token.dispose();
      makeDirty();
   }
   /**
    * Remove the {@link RewriteableToken} with the indicated name.
    * @param name The indicated name.
    */
   public void removeRewriteableToken(String name) {
      RewriteableToken token = getRewriteableToken(name);
      removeRewriteableToken(token);
   }
   /**
    * Get the token category with the indicated name.
    * @param name The indicated name.
    * @return The token category with the indicated name.
    * @throws NoSuchObjectException when there is no category with
    * the indicated name.
    */
   public TokenCategory getCategory(String name) {
      TokenCategory token = categoriesByName.get(name);
      if (null == token) {
         throw new NoSuchObjectException(
            "There is no category with name [" + name + "]");
      }
      if (!token.getName().equals(name))
         throw new RuntimeException("Programmer error");
      return token;
   }
   /**
    * Test if the grammar contains a token category with the indicated name.
    * @param name The indicated name.
    * @return True if the grammar contains a token category with the
    * indicated name; false otherwise.
    */
   public boolean hasCategory(String name) {
      return getCategoriesByName().containsKey(name);
   }
   /**
    * Create a new token category with the indicated id and name.
    * @param name The intended category name.
    * @return The newly created category.
    * @throws IllegalArgumentException when there is already a category
    * with the indicated id or there is already a category with
    * the indicated name.
    */
   public TokenCategory createCategory(String name) {
      if (hasCategory(name)) {
         throw new IllegalArgumentException(
            "There is already a category with name [" + name + "]");
      }
      TokenCategory result = new TokenCategory(this, name);
      makeDirty();
      return result;
   }
   /**
    * Remove the indicated category.
    * @param category The indicated category.
    */
   public void removeCategory(TokenCategory category) {
      if (this != category.getContainer())
         throw new IllegalArgumentException(
            "Category does not belong to this grammar");
      if (category == nullCategory)
         throw new UnsupportedOperationException(
            "Tried to remove null category");
      for (ChomskyToken token : tokensByName.values()) {
         if (category == token.getCategory()) {
            throw new UnsupportedOperationException(
               "One or more tokens exist under category ["
               + category.getName() + "]");
         }
      }
      categoriesByName.remove(category.getName());
      category.dispose();
      refreshIndexFormat();
      makeDirty();
   }
   /**
    * Get the {@link ChomskyStatement} with the indicated name.
    * @param name The indicated name.
    * @return The {@link ChomskyStatement} with the indicated name.
    * @throws NoSuchObjectException when there is no statement with
    * the indicated name.
    */
   public ChomskyStatement getStatement(String name) {
      ChomskyStatement token = statementsByName.get(name);
      if (null == token) {
         throw new NoSuchObjectException(
            "There is no statement with name [" + name + "]");
      }
      if (!token.getName().equals(name))
         throw new RuntimeException("Programmer error");
      return token;
   }
   /**
    * Test if the grammar contains a {@link ChomskyStatement} with the
    * indicated name.
    * @param name The indicated name.
    * @return True if the grammar contains a {@link ChomskyStatement} with
    * the indicated name; false otherwise.
    */
   public boolean hasStatement(String name) {
      return getCategoriesByName().containsKey(name);
   }
   /**
    * Create a new {@link ChomskyStatement} with the indicated id
    * and name.
    * @param name The intended statement name.
    * @return The newly created statement.
    * @throws IllegalArgumentException when there is already a
    * statement with the indicated id or there is already a statement
    * with the indicated name.
    */
   public ChomskyStatement createStatement(String name) {
      if (hasStatement(name)) {
         throw new IllegalArgumentException(
            "There is already a statement with name [" + name + "]");
      }
      ChomskyStatement result = new ChomskyStatement(this, name);
      makeDirty();
      return result;
   }
   /**
    * Remove the indicated statement.
    * @param statement The indicated statement.
    */
   public void removeStatement(ChomskyStatement statement) {
      if (this != statement.getContainer())
         throw new IllegalArgumentException(
            "Statement does not belong to this grammar");
      statementsByName.remove(statement.getName());
      statement.dispose();
      makeDirty();
   }
   /**
    * Test if the number of digits in the number of tokens has changed
    * and, if so, rebuild the format to reflect this.
    */
   private void refreshIndexFormat() {
      int magnitude = terminalsByID.size();
      int digits;
      if (0 == magnitude)
         digits = 1;
      else
         digits = 1 + (int) Math.floor(Math.log10(magnitude));
      if (indexDigits != digits) {
         indexDigits = digits;
         String pattern = StringUtils.repeat("0",digits);
         indexFormat = new DecimalFormat(pattern);
      }
   }
   /**
    * Getter for {@link #indexFormat}.
    * @return A {@link DecimalFormat} with enough 0-padded digits to
    * accommodate all token indices.
    */
   public DecimalFormat getIndexFormat() {
      return indexFormat;
   }
   @Override
   public int getLimit() {
      if (0 == terminalsByID.size()) return 0;
      return terminalsByID.lastKey()+1;
   }
   @Override
   public boolean hasReset() {
      return true;
   }
   @Override
   public void reset() {
      if (hasStatement(PRODUCT_STATEMENT_NAME)) {
         removeStatement(getStatement(PRODUCT_STATEMENT_NAME));
      }
      product = getAxiom().copy(PRODUCT_STATEMENT_NAME);
      incident = 0;
      if (documentProduction) {
         ProductionTree productionTree = product.createProductionTree();
         productionNodes = new ArrayList<ProductionNode>();
         productionNodes.add(0, productionTree);
         productionLevels = new ArrayList<Integer>();
         for (int i = 0; i < product.getTokens().size(); i++) {
            productionLevels.add(0);
         }
      }
   }
   /**
    * Advance to the next element in the cycle.
    * @return The next {@link TerminalToken} in the cycle.
    */
   public TerminalToken nextToken() {
      ChomskyStatement product = getProduct();
      List<ChomskyToken> productTokens = product.getTokens();
      if (incident >= productTokens.size())
         throw new NoSuchElementException();
      RewriteableToken rewriteable = null;
      ProductionTree productionTree = documentProduction
            ? product.getProductionTree() : null;
      for (;;) {
         ChomskyToken token = productTokens.get(incident);
         if (null == token)
            throw new RuntimeException("Programmer error");
         if (rewriteable == token)
            throw new RuntimeException(
               "Rewrite loop for token [" + rewriteable.getName() + "]");
         if (!token.isRewriteable()) {
            TerminalToken terminal = (TerminalToken) token;
            if (null != productionTree) {
               int productionLevel = productionLevels.get(incident);
               ProductionNode productionNode
                  = productionNodes.get(productionLevel);
               productionLevel++;
               productionNode.addChildNode(terminal, incident);
               productionNodes.add(productionLevel, productionNode);
            }
            incident++;
            return (TerminalToken) token;
         }
         rewriteable = (RewriteableToken) token;
         RuleProduction production
            = rewriteable.chooseProduction(product, incident);
         ProductionNode productionNode = null;
         int productionLevel = 0;
         if (null != productionTree) {
            productionLevel = productionLevels.get(incident);
            productionNode = productionNodes.get(productionLevel);
            productionLevel++;
            productionNode = productionNode.addChildNode(production, incident);
            productionNodes.add(productionLevel, productionNode);
         }
         List<ChomskyToken> productionTokens = production.getTokens();
         productTokens.remove(incident);
         if (null != productionTree) {
            productionLevels.remove(incident);
         }
         int tokenPosition = incident;
         for (ChomskyToken productionToken : productionTokens){
            productTokens.add(tokenPosition, productionToken);
            if (null != productionTree) {
               productionLevels.add(tokenPosition, productionLevel);
            }
            tokenPosition++;
         }
      }
   }
   @Override
   public Integer next() {
      return nextToken().getID();
   }
   /**
    * Test if there are still elements remaining in the cycle.
    * @return True if the cycle has more elements; false otherwise.
    */
   public boolean hasNextToken() {
      return incident < getProduct().size();
   }
   @Override
   public boolean hasNext() {
      return hasNextToken();
   }
   @Override
   public double minGraphValue() {
      throw new UnsupportedOperationException("Method not supported");
   }
   @Override
   public double maxGraphValue() {
      throw new UnsupportedOperationException("Method not supported");
   }
   /**
    * Copy content from the source grammar into the current grammar.
    * @param source The source grammar.
    * @param option Indicates how to handle overlaps between corresponding
    * objects.
    */
   public final void copyFrom(ChomskyGrammar source, CopyOption option) {
      outputFormat = source.getOutputFormat();
      copyCategories(source, option);
      copyTokens(source, option);
   }
   /**
    * Copy {@link TokenCategory} instances from the source grammar into the
    * current grammar.
    * @param source The source grammar.
    * @param option Indicates how to handle overlaps between corresponding
    * categories.
    */
   public void copyCategories(ChomskyGrammar source, CopyOption option) {
      if (CopyOption.CLEAR == option)
      {
         categoriesByName.clear();
      }
      for (TokenCategory sourceCategory : source.categoriesByName.values()) {
         String sourceName = sourceCategory.getName();
         if (hasCategory(sourceName)) {
            if (CopyOption.OVERWRITE != option) continue;
            TokenCategory targetCategory = categoriesByName.get(sourceName);
            if (null == targetCategory)
               throw new RuntimeException("Programmer error");
         }
         else {
            createCategory(sourceName);
         }
      }
   }
   /**
    * Copy tokens from the source grammar into the current grammar.
    * @param source The source grammar.
    * @param option Indicates how to handle overlaps between corresponding tokens.
    */
   public void copyTokens(ChomskyGrammar source, CopyOption option) {
      if (CopyOption.CLEAR == option)
      {
         terminalsByID.clear();
         tokensByName.clear();
      }
      for (ChomskyToken sourceToken : source.tokensByName.values()) {
         String sourceName = sourceToken.getName();
         if (hasToken(sourceName)) {
            if (CopyOption.OVERWRITE != option) continue;
            ChomskyToken targetToken = tokensByName.get(sourceName);
            targetToken.copyFrom(sourceToken, option);
         }
         else {
            copyToken(sourceToken);
         }
      }
      for (ChomskyToken sourceToken : source.tokensByName.values()) {
         if (!sourceToken.isRewriteable()) continue;
         String sourceName = sourceToken.getName();
         RewriteableToken targetToken = (RewriteableToken) tokensByName.get(sourceName);
         if (targetToken.getRulesByName().size() > 0 && CopyOption.OVERWRITE != option) continue;
         targetToken.copyRules(sourceToken, option);
      }
   }
   private ChomskyToken copyToken(ChomskyToken sourceToken) {
      ChomskyToken result;
      if (sourceToken.isRewriteable()) {
         result = createRewriteableToken(sourceToken.getName());
      }
      else {
         result = createTerminalToken(sourceToken.getID(), sourceToken.getName());
      }
      result.copyFrom(sourceToken, CopyOption.CLEAR);
      return result;
   }
}

Listing 1: The ChomskyGrammar implementation class.

The type hierarchy for ChomskyGrammar is:

ChomskyGrammar extends WriteableEntity implements Indexer

The life cycle of a ChomskyGrammar instance has two phases: Construction and Generation.

Construction begins by allocating the instance using new ChomskyGrammar(). Construction also includes the creation of TokenCategory, RewriteableToken, TerminalToken, RewriteRule, and RuleProduction instances.

To fully construct a ChomskyGrammar, it's good practice first to set up the TokenCategory collection, since each token must have a category. Then the tokens must be established. I like to work from the general to the specific, which means starting with the top-level RewriteableToken instances and saving the TerminalToken instances for last. A RewriteableToken is said to be "top-level" when it appears in the axiom, which is a ChomskyStatement that includes RewriteableToken references. At this point one can begin to flesh out the RewriteRule instances under each RewriteableToken.

The SortedMap<String, TokenCategory> named categoriesByName manages the collection of TokenCategory instances (Listing 5) under a ChomskyGrammar.

Method hasCategory(String name) tests if an existing TokenCategory is registered with categoriesByName under indicated name.
Method getCategory(String name) retrieves an existing TokenCategory which auto-registers itself with categoriesByName.
Method getNullCategory() retrieves the automatically-created "null" category (described shortly).
Method createCategory(String name) creates a new TokenCategory from categoriesByName.
Method removeCategory(TokenCategory category) removes the indicated TokenCategory from categoriesByName, so long as no ChomskyToken references the category.

One TokenCategory is created automatically, and it can't be removed. This is what I call the "null" category. When the null category appears in RewriteRule.beforeCategories, it indicates that the rule's parent RewriteableToken is positioned at the beginning of a statement. When the null category appears in RewriteRule.afterCategories, it indicates that the rule's parent RewriteableToken is positioned at the end of a statement.

The SortedMap<Integer, TerminalToken> named terminalsByID manages the collection of TerminalToken instances (Listing 4) under a ChomskyGrammar. The SortedMap<String, ChomskyToken> named tokensByName manages the broader collection of Integer instances (Listing 2) under the same grammer. tokensByName combines all TerminalToken instances with all RewriteableToken instances, enforcing name-uniqueness across this combined set.

Method hasToken(String name) tests if an existing ChomskyToken is registered with tokensByName under the indicated name.
Method hasTerminalToken(int id) tests if an existing ChomskyToken is registered with terminalsByID under the indicated id.
Method getToken(String name) retrieves an existing ChomskyToken from tokensByName.
Method getTerminalToken(String name) retrieves an existing ChomskyToken from tokensByName, returning the token if it is terminal, but throwing a NoSuchObjectException otherwise.
Method getRewriteableToken(String name) retrieves an existing ChomskyToken from tokensByName, returning the token if it is rewriteable, but throwing a NoSuchObjectException otherwise.
Method createTerminalToken(int id, String name TokenCategory category) creates a new TerminalToken which auto-registers itself with both terminalsByID and tokensByName.
Method createRewriteableToken(String name TokenCategory category) creates a new RewriteableToken which auto-registers itself with tokensByName.
Method removeTerminalToken(TerminalToken token) removes the indicated TerminalToken from both terminalsByID and tokensByName.
Method removeRewriteableToken(RewriteableToken token) removes the indicated RewriteableToken from tokensByName. Any child RewriteRule and RuleProduction instances are cleared away by the call to RewriteableToken.dispose().

Generation happens in cycles. Each cycle begins with a preparation stage which consists of a call to setAxiom(ChomskyStatement axiom) (optional after the first cycle) and a call to reset(). Then follows an iteration stage. Following the Index/Supply design, iteration begins with the first pair of calls to hasNext(), and — if hasNext() returns true — to next(). Iteration continues until hasNext() returns false.

Notice that the hasNext() method wraps hasNextToken(), while the next() method wraps nextToken(). If you wish to encapsulate "supply" options directly into the terminal tokens, you can employ an alternative iteration cycle using calls to hasNextToken(), and — if hasNextToken() returns true — to nextToken().

The reset() call copies the list of token references from the internally held ChomskyStatement named axiom to a second internally held ChomskyStatement named product. The guts of the generation phase are implemented in method nextToken(), which iterates through product, returning TerminalToken instances as it encounters them. If instead the iteration encounters a RewriteableToken, things get more complicated. Each RewriteableToken is replaced by a succession of "lower-level" tokens; the tokens rightward of the current position being pushed aside to make room. The iteration stalls until the upcoming token finally resolves to a TerminalToken, at which point the iteration can finally advance.

/**
 * The {@link ChomskyToken} class defines a potential stage in the progress of a statement.
 * Each {@link ChomskyToken} is identifiable by unique name.  Each {@link ChomskyToken}
 * instance references a {@link TokenCategory}; categories may be shared.
 * @author Charles Ames
 */
public abstract class ChomskyToken extends WriteableEntity {
   private TokenCategory category;
   private String description;
   private String displayText = null;

   /**
    * Constructor for {@link ChomskyToken} instances.
    * @param grammar The {@link ChomskyGrammar} which contains this instance.
    * @param name The intended token name.
    */
   protected ChomskyToken(ChomskyGrammar grammar, String name) {
      super(grammar);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      setName(name);
      this.category = null;
      this.description = null;
   }
   @Override
   public String toString() {
      if (null == displayText) {
         displayText = "#" + (getID() + 1) + " " + getName();
      }
      return displayText;
   }
   /**
    * Getter for {@link #displayText}.
    * @return The assigned {@link #displayText} content.
    */
   public String getDisplayText() {
      return displayText;
   }
   protected void setDisplayText(String displayText) {
      this.displayText = displayText;
   }
   /**
    * Getter for {@link #description}.
    * @return The assigned {@link #description} text.
    * @throws UninitializedException when the {@link #description} field is null.
    */
   public String getDescription() {
      if (null == description) throw new IllegalArgumentException("Description text not initialized");
      return description;
   }
   /**
    * Setter for {@link #description}.
    * @param description The intended {@link #description} text.
    * @throws IllegalArgumentException when the argument is null or blank.
    */
   public void setDescription(String description) {
      if (StringUtils.isEmpty(description)) throw new IllegalArgumentException("Empty description text");
      this.description = description;
   }
   /**
    * Get the grammar to which this {@link ChomskyToken} belongs.
    * @return The assigned container.
    */
   public ChomskyGrammar getContainer() {
      return (ChomskyGrammar) super.getContainer();
   }
   @Override
   public boolean setName(String name) {
      if (StringUtils.isBlank(name))
         throw new IllegalArgumentException("Blank name");
      SortedMap<String, ChomskyToken> map = getContainer().getTokensByName();
      String oldName = getOldName();
      if (StringUtils.equals(name, oldName)) return false;
      if (!StringUtils.isEmpty(oldName))
         map.remove(oldName);
      super.setName(name);
      map.put(name, this);
      displayText = null;
      return true;
   }
   /**
    * Getter for {@link #category}.
    * @return The assigned {@link #category} value.
    */
   public TokenCategory getCategory() {
      if (null == category) throw new UninitializedException("Category not initialized");
      return category;
   }
   /**
    * Setter for {@link #category}.
    * @param category The intended {@link #category} value.
    */
   public void setCategory(TokenCategory category) {
      if (null == category) throw new IllegalArgumentException("Null argument");
      if (getContainer().getNullCategory() == category) throw new IllegalArgumentException("No token may be attributed the null category");
      this.category = category;
   }
   protected void copyCategory(ChomskyToken source) {
      TokenCategory sourceCategory = source.getCategory();
      TokenCategory targetCategory = null;
      if (null != sourceCategory) {
         targetCategory = getContainer().getCategory(sourceCategory.getName());
         if (null != targetCategory) setCategory(targetCategory);
      }
   }
   protected void copyFrom(ChomskyToken source, CopyOption option) {
      setName(source.getName());
      copyCategory(source);
   }
   /**
    * Is this a rewriteable token?
    * @return True if rewriteable; false otherwise.
    */
   public abstract boolean isRewriteable();
}

Listing 2: The ChomskyToken base class.

Tokens

The type hierarchy for ChomskyToken is:

ChomskyToken extends WriteableEntity

The name associated with each ChomskyToken instance is superclass-maintained property. The setName() method override takes responsibility for registering each ChomskyToken instance name with the parent ChomskyGrammar, and for updating this registration whenever the instance name changes.

Aside from the name, the properties shared between the RewriteableToken and TerminalToken subclasses are category and description. Each of these fields has a getter and a setter.

/**
 * The {@link RewriteableToken} class implements a {@link ChomskyToken}
 * which is replaceable by rewrite rules.
 * @author Charles Ames
 */
public class RewriteableToken extends ChomskyToken {
   private SortedMap<String, RewriteRule> rulesByName;
   /**
    * Constructor for {@link ChomskyToken} instances.
    * @param grammar The {@link ChomskyGrammar} which contains this instance.
    * @param name The intended token name.
    */
   protected RewriteableToken(ChomskyGrammar grammar, String name) {
      super(grammar, name);
      this.setIDQuality(Entity.AttributeQuality.UNUSED);
      this.rulesByName = new TreeMap<String, RewriteRule>();
   }
   @Override
   public boolean isRewriteable() {
      return true;
   }
   /**
    * Get all rewrite rules by name.
    * @return A collection of {@link RewriteRule} instances, indexed by name.
    */
   public SortedMap<String, RewriteRule> getRulesByName() {
      return rulesByName;
   }
   /**
    * Get the {@link RewriteRule} with the indicated name.
    * @param name The indicated name.
    * @return The {@link RewriteRule} with the indicated name.
    * @throws NoSuchObjectException when there is no {@link RewriteRule}
    * with the indicated name.
    */
   public RewriteRule getRule(String name) {
      RewriteRule token = rulesByName.get(name);
      if (null == token) {
         throw new NoSuchObjectException(
            "There is no rewrite rule with name [" + name + "]");
      }
      if (!token.getName().equals(name))
         throw new RuntimeException("Programmer error");
      return token;
   }
   /**
    * Test if the grammar contains a {@link RewriteRule} with the indicated
    * name.
    * @param name The indicated name.
    * @return True if the grammar contains a {@link RewriteRule} with the
    * indicated name; false otherwise.
    */
   public boolean hasRule(String name) {
      return rulesByName.containsKey(name);
   }
   /**
    * Create a new {@link RewriteRule} with the indicated id and name.
    * @param name The intended rule name.
    * @return The newly created {@link RewriteRule} instance.
    * @throws IllegalArgumentException when there is already a
    * {@link RewriteRule} instance with the indicated name.
    */
   public RewriteRule createRule(String name) {
      if (hasRule(name)) {
         throw new IllegalArgumentException(
            "There is already a rewrite rule with name [" + name + "]");
      }
      RewriteRule result = new RewriteRule(this, name);
      makeDirty();
      return result;
   }
   @Override
   protected void copyFrom(ChomskyToken source, CopyOption option) {
      RewriteableToken token = (RewriteableToken) source;
      setName(token.getName());
      copyCategory(source);
   }
   protected void copyRules(ChomskyToken source, CopyOption option) {
      RewriteableToken token = (RewriteableToken) source;
      for (RewriteRule sourceRule : token.getRulesByName().values()) {
         String sourceName = sourceRule.getName();
         if (hasRule(sourceName)) {
            if (CopyOption.OVERWRITE != option) continue;
            RewriteRule targetRule = rulesByName.get(sourceName);
            targetRule.copyFrom(sourceRule, option);
         }
         else {
            copyRule(sourceRule);
         }
      }
   }
   private RewriteRule copyRule(RewriteRule source) {
      RewriteRule result = createRule(source.getName());
      result.copyFrom(source, CopyOption.CLEAR);
      return result;
   }

   /**
    * Find an existing production which covers the indicated array of tokens.
    * @param array The indicated.
    * @return The corresponding {@link RuleProduction} instance if found;
    * null otherwise.
    */
   public RuleProduction findProduction(ChomskyToken[] array) {
      int length = array.length;
      for (RewriteRule rule : rulesByName.values()) {
         for (RuleProduction production : rule.getProductions()) {
            List<ChomskyToken> tokens = production.getTokens();
            if (tokens.size() != length) continue;
            boolean success = true;
            for (int position = 0; position < length; position++) {
               if (tokens.get(position) != array[position]) {
                  success = false;
                  break;
               }
            }
            if (success) return production;
         }
      }
      return null;
   }
   /**
    * Choose a production by weighted randomness.
    * @param statement The {@link ChomskyStatement} holding the token
    * being evaluated.
    * @param position The position of the token in the
    * {@link ChomskyStatement}.
    * @return The selected production.
    * @throws UnsupportedOperationException when no production weights
    * are positive.
    */
   public RuleProduction chooseProduction(ChomskyStatement statement,
         int position) {
      if (this != statement.getToken(position))
         throw new RuntimeException("Programmer error");
      Double sumOfWeights = 0.;
      List<RuleProduction> productions = new ArrayList<RuleProduction>();
      for (RewriteRule rule : rulesByName.values()) {
         if (rule.applies(statement, position)) {
            for (RuleProduction production : rule.getProductions()) {
               double weight = production.getWeight();
               if (MathMethods.TINY > weight) {
                  continue;
               }
               productions.add(production);
               sumOfWeights += weight;
            }
         }
      }
      if (0 == productions.size()) {
         throw new UnsupportedOperationException(
            "No rewrite rules apply for [" + getName() + "]");
      }
      if (MathMethods.TINY > sumOfWeights)
         throw new UnsupportedOperationException(
            "No positive-weight productions for [" + getName() + "]");
      double chooser
         = SharedRandomGenerator.getSingleton().getRandom().nextDouble() * sumOfWeights;
      for (RuleProduction production : productions) {
         double weight = production.getWeight();
         if (chooser <= weight) return production;
         chooser -= weight;
      }
      throw new RuntimeException("Programmer error");
   }
   /**
    * Remove the indicated {@link RewriteRule} instance.
    * @param rule The indicated {@link RewriteRule} instance.
    */
   public void removeRule(RewriteRule rule) {
      if (this != rule.getContainer())
         throw new IllegalArgumentException("Rewrite rule does not belong to this grammar");
      rulesByName.remove(rule.getName());
      rule.dispose();
      makeDirty();
   }
}

Listing 3: The RewriteableToken implementation class.

The type hierarchy for RewriteableToken is:

ChomskyToken extends WriteableEntity
RewriteableToken extends ChomskyToken

The RewriteableToken feature not shared with TerminalToken is its collection of RewriteRule instances. This collection is managed by the SortedMap<String, RewriteRule> named rulesByName.

Method hasRule(String name) tests if an existing RewriteRule is registered with rulesByName under the indicated name.
Method getRule(String name) retrieves an existing RewriteRule from rulesByName.
Method createRule(String name) creates a new RewriteRule which auto-registers itself with rulesByName.
Method removeRule(RewriteRule token) removes the indicated RewriteRule from rulesByName and disposes of its productions.

/**
 * The {@link TerminalToken} class implements a {@link ChomskyToken} which is left
 * in place by rewrite rules.  {@link TerminalToken} instances are distinguished from
 * other {@link TerminalToken} instances by a unique integer identifier ranging
 * from 0 upwards.  The {@link TerminalToken} instances may optionally reference
 * an {@link Object} which tells what to do when the token is selected.
 * @author Charles Ames
 */
public class TerminalToken extends ChomskyToken {
   private Object object;

   /**
    * Constructor for {@link TerminalToken} instances.
    * @param grammar The {@link ChomskyGrammar} which contains this instance.
    * @param id The intended token id.
    * @param name The intended token name.
    */
   protected TerminalToken(ChomskyGrammar grammar, int id, String name) {
      super(grammar, name);
      this.setIDQuality(Entity.AttributeQuality.MODIFIABLE);
      this.setID(id);
      this.object = null;
   }
   @Override
   public boolean isRewriteable() {
      return false;
   }
   @Override
   public void wipe() {
      object = null;
      super.wipe();
   }
   @Override
   public String toString() {
      String displayText = getDisplayText();
      if (null == displayText) {
         Object o = getObject();
         if (null == o)
            displayText = "#" + (getID() + 1);
         else
            displayText = "#" + (getID() + 1) + " " + o.toString();
         setDisplayText(displayText);
      }
      return displayText;
   }
   @Override
   public boolean setID(int id) {
      if (0 > id)
         throw new IllegalArgumentException("Negative id");
      SortedMap<Integer, TerminalToken> map = getContainer().getTerminalsByID();
      int oldID = getOldID();
      if (oldID == id) return false;
      if (0 <= oldID)
         map.remove(oldID);
      super.setID(id);
      map.put(id, this);
      setDisplayText(null);
      return true;
   }
   /**
    * Get the object.
    * @return The assigned object.
    */
   public Object getObject() {
      return object;
   }
   /**
    * Set the object.
    * @param object The intended object.
    * @return True if the object changed; false otherwise.
    */
   public boolean setObject(Object object) {
      if (null == object)
         throw new IllegalArgumentException("Null object");
      boolean changed = false;
      if (null == this.object || !this.object.equals(object)) {
         this.object = object;
         changed = true;
         makeDirty();
         setDisplayText(null);
      }
      return changed;
   }
   /**
    * Clear the object.
    */
   public void clearObject() {
      this.object = null;
   }
   /**
    * Copy the object from the indicated reference token.
    * @param source The indicated reference token.
    */
   public void copyObject(TerminalToken source) {
      object = source.object;
   }
   /**
    * Returns a representation of the token's object not including
    * the token id.
    * @return The object value description.
    */
   public String objectString() {
      return getObject().toString();
   }
   @Override
   protected void copyFrom(ChomskyToken source, CopyOption option) {
      super.copyFrom(source, option);
      TerminalToken token = (TerminalToken) source;
      setID(source.getID());
      copyObject(token);
   }
   /**
    * Get the {@link TerminalToken} with the next lower id.
    * @return The {@link TerminalToken} with the next lower id.  Null if not found.
    */
   public TerminalToken predecessor() {
      SortedMap<Integer, TerminalToken> tokens = getContainer().getTerminalsByID();
      int firstKey = tokens.firstKey();
      TerminalToken result = null;
      int id = getID();
      for (int predecessorID = id; --predecessorID >= firstKey;) {
         result = tokens.get(predecessorID);
         if (null != result) break;
      }
      return result;
   }
   /**
    * Get the {@link TerminalToken} with the next higher id.
    * @return The {@link TerminalToken} with the next higher id.  Null if not found.
    */
   public TerminalToken successor() {
      SortedMap<Integer, TerminalToken> tokens = getContainer().getTerminalsByID();
      int lastKey = tokens.lastKey();
      TerminalToken result = null;
      int id = getID();
      for (int successorID = id; ++successorID <= lastKey;) {
         result = tokens.get(successorID);
         if (null != result) break;
      }
      return result;
   }
}

Listing 4: The TerminalToken implementation class.

The type hierarchy for TerminalToken is:

ChomskyToken extends WriteableEntity
TerminalToken extends ChomskyToken

The integer id associated with each TerminalToken instance is superclass-maintained property. The setID() method override takes responsibility for registering each TerminalToken instance id with the parent ChomskyGrammar, and for updating this registration whenever the instance id changes.

Aside from the id, the TerminalToken feature not shared with RewriteableToken is the object field. Users who consider the Index/Supply design too detached can use this field to embed a "supply" element directly into the present TerminalToken instance.

/**
 * The {@link TokenCategory} class implement categories for
 * {@link ChomskyToken} instances.
 * @author Charles Ames
 */
public class TokenCategory extends WriteableEntity {
   /**
    * Constructor for {@link TokenCategory} instances.
    * @param grammar The {@link ChomskyGrammar} which contains this instance.
    * @param name The intended text identifier.
    */
   protected TokenCategory(ChomskyGrammar grammar, String name) {
      super(grammar);
      this.setIDQuality(Entity.AttributeQuality.UNUSED);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      setName(name);
   }
   @Override
   public String toString() {
      return getName();
   }
   /**
    * Get the grammar to which this category belongs.
    * @return The grammar to which this category belongs.
    */
   public ChomskyGrammar getContainer() {
      return (ChomskyGrammar) super.getContainer();
   }
   @Override
   public boolean setName(String name) {
      if (StringUtils.isBlank(name))
         throw new IllegalArgumentException("Blank name");
      SortedMap<String, TokenCategory> map = getContainer().getCategoriesByName();
      String oldName = getOldName();
      if (StringUtils.equals(name, oldName)) return false;
      if (!StringUtils.isEmpty(oldName))
         map.remove(oldName);
      super.setName(name);
      map.put(name, this);
      return true;
   }
}

Listing 5: The TokenCategory implementation class.

The type hierarchy for TokenCategory is:

TokenCategory extends WriteableEntity

The name associated with each ChomskyToken instance is superclass-maintained property, as was the case with ChomskyToken. The setName() method override takes responsibility for registering each instance ChomskyToken with its parent ChomskyGrammar, and for updating this registration whenever the instance name changes.

/**
 * The {@link RewriteRule} class defines conditions under which productions can be applied.
 * @author Charles Ames
 */
public class RewriteRule extends WriteableEntity {
   private SortedMap<String, TokenCategory> beforeCategories;
   private SortedMap<String, TokenCategory> afterCategories;
   private List<RuleProduction> productions;
   /**
    * Constructor for {@link RewriteRule} instances.
    * @param token The {@link RewriteableToken} which contains this instance.
    * @param name The intended text identifier.
    */
   protected RewriteRule(RewriteableToken token, String name) {
      super(token);
      this.setIDQuality(Entity.AttributeQuality.UNUSED);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      setName(name);
      beforeCategories = new TreeMap<String, TokenCategory>();
      afterCategories = new TreeMap<String, TokenCategory>();
      productions = new ArrayList<RuleProduction>();
   }
   /**
    * Get the {@link RewriteableToken} to which this {@link RewriteRule} belongs.
    * @return This object's container.
    */
   public RewriteableToken getContainer() {
      return (RewriteableToken) super.getContainer();
   }
   @Override
   public boolean setName(String name) {
      if (StringUtils.isBlank(name))
         throw new IllegalArgumentException("Blank name");
      SortedMap<String, RewriteRule> map = getContainer().getRulesByName();
      String oldName = getOldName();
      if (StringUtils.equals(name, oldName)) return false;
      if (!StringUtils.isEmpty(oldName))
         map.remove(oldName);
      super.setName(name);
      map.put(name, this);
      return true;
   }
   /**
    * Include a {@link TokenCategory} among the acceptable before conditions.
    * @param category The intended new before {@link TokenCategory}.
    * @throws IllegalArgumentException when the containers differ.
    * @throws IllegalArgumentException when the {@link TokenCategory} is already present.
    */
   public void addBeforeCategory(TokenCategory category) {
      if (category.getContainer() != getContainer().getContainer())
         throw new UnsupportedOperationException("Not same grammar");
      String name = category.getName();
      if (beforeCategories.containsKey(name))
         throw new IllegalArgumentException("Before categories already includes [" + name + "]");
      beforeCategories.put(name, category);
   }
   /**
    * Remove the indicated {@link TokenCategory} from the acceptable before conditions.
    * @param category The {@link TokenCategory} to be removed.
    * @throws IllegalArgumentException when the {@link TokenCategory} is not present.
    */
   public void removeBeforeCategory(TokenCategory category) {
      String name = category.getName();
      if (!beforeCategories.containsKey(name))
         throw new UnsupportedOperationException("Before categories does not include [" + name + "]");
      beforeCategories.remove(name);
   }
   /**
    * Include a {@link TokenCategory} among the acceptable after conditions.
    * @param category The intended new after {@link TokenCategory}.
    * @throws IllegalArgumentException when the containers differ.
    * @throws IllegalArgumentException when the {@link TokenCategory} is already present.
    */
   public void addAfterCategory(TokenCategory category) {
      if (category.getContainer() != getContainer().getContainer())
         throw new UnsupportedOperationException("Not same grammar");
      String name = category.getName();
      if (afterCategories.containsKey(name))
         throw new IllegalArgumentException("After categories already includes [" + name + "]");
      afterCategories.put(name, category);
   }
   /**
    * Remove the indicated {@link TokenCategory} from the acceptable after conditions.
    * @param category The {@link TokenCategory} to be removed.
    * @throws IllegalArgumentException when the {@link TokenCategory} is not present.
    */
   public void removeAfterCategory(TokenCategory category) {
      String name = category.getName();
      if (!afterCategories.containsKey(name))
         throw new UnsupportedOperationException("After categories does not include [" + name + "]");
      afterCategories.remove(name);
   }
   /**
    * Create a new {@link RuleProduction} instance.
    * @param array The content of the production.
    * @return The new {@link RuleProduction} instance.
    */
   public RuleProduction createProduction(ChomskyToken[] array) {
      RuleProduction oldProduction = getContainer().findProduction(array);
      if (null != oldProduction) {
         RewriteRule oldRule = oldProduction.getContainer();
         throw new IllegalArgumentException(
            "Redundant production in rule [" + oldRule.getName() + "]");
      }
      RuleProduction newProduction = new RuleProduction(this);
      List<ChomskyToken> tokens = newProduction.getTokens();
      for (ChomskyToken token : array) {
         tokens.add(token);
      }
      productions.add(newProduction);
      return newProduction;
   }
   /**
    * Remove the production at the indicated position from the list.
    * @param position
    */
   public void removeProduction(int position) {
      RuleProduction production = productions.get(position);
      productions.remove(position);
      production.dispose();
   }
   protected void copyFrom(RewriteRule source, CopyOption option) {
      setName(source.getName());
      RewriteableToken rewriteable = getContainer();
      ChomskyGrammar grammar = rewriteable.getContainer();
      for (TokenCategory sourceCategory : source.beforeCategories.values()) {
         TokenCategory targetCategory = grammar.getCategoriesByName().get(sourceCategory.getName());
         this.addBeforeCategory(targetCategory);
      }
      for (TokenCategory sourceCategory : source.afterCategories.values()) {
         TokenCategory targetCategory = grammar.getCategoriesByName().get(sourceCategory.getName());
         this.addAfterCategory(targetCategory);
      }
      for (RuleProduction sourceProduction : source.getProductions()) {
         List<ChomskyToken> sourceTokens = sourceProduction.getTokens();
         ChomskyToken[] content = new ChomskyToken[sourceTokens.size()];
         int position = 0;
         for (ChomskyToken sourceToken : sourceTokens) {
            ChomskyToken targetToken = grammar.getToken(sourceToken.getName());
            content[position++] = targetToken;
         }
         RuleProduction targetProduction = rewriteable.findProduction(content);
         if (null != targetProduction) {
            if (CopyOption.OVERWRITE != option) continue;
            targetProduction.setWeight(sourceProduction.getWeight());
         }
         else {
            targetProduction = createProduction(content);
            targetProduction.setWeight(sourceProduction.getWeight());
         }
      }
   }
   protected List<RuleProduction> getProductions() {
      return productions;
   }
   /**
    * Test if this {@link RewriteRule} applies to the token
    * in the indicated position of the given {@link ChomskyStatement}.
    * @param statement The {@link ChomskyStatement} holding the token being evaluated.
    * @param position The position of the token in the {@link ChomskyStatement}.
    * @return True if the rule is satisfied; false otherwise.
    */
   public boolean applies(ChomskyStatement statement, int position) {
      ChomskyToken token = statement.getToken(position);
      if (token != getContainer()) return false;
      if (!matchFound(statement, position, beforeCategories, -1)) return false;
      if (!matchFound(statement, position, afterCategories, 1)) return false;
      return true;
   }
   private boolean matchFound(ChomskyStatement statement, int position,
         SortedMap<String, TokenCategory> categories, int offset) {
      if (0 == categories.size()) {
         return true;
      }
      int i = position + offset;
      ChomskyToken token = statement.getToken(i);
      if (null == token) {
         TokenCategory nullCategory = getContainer().getContainer().getNullCategory();
         if (categories.keySet().contains(nullCategory.getName())) {
            return true;
         }
         else {
            return false;
         }
      }
      TokenCategory tokenCategory = token.getCategory();
      for (TokenCategory ruleCategory : categories.values()) {
         if (ruleCategory == tokenCategory) {
            return true;
         }
      }
      return false;
   }
   @Override
   public void wipe() {
      beforeCategories.clear();
      afterCategories.clear();
      for (RuleProduction production : productions) production.dispose();
      productions.clear();
      super.wipe();
   }
   @Override
   public boolean equals(Entity other) {
      if (!super.equals(other)) {
         return false;
      }
      RewriteRule otherRule = (RewriteRule) other;
      {
         if (beforeCategories.size() != otherRule.beforeCategories.size()) {
            Entity.printDebugMessage(this, "Different before category counts");
            return false;
         }
         Iterator<TokenCategory> thisIterator = beforeCategories.values().iterator();
         Iterator<TokenCategory> otherIterator = otherRule.beforeCategories.values().iterator();
         while (thisIterator.hasNext()) {
            TokenCategory thisCategory = thisIterator.next();
            TokenCategory otherCategory = otherIterator.next();
            if (!thisCategory.equals(otherCategory)) {
               Entity.printDebugMessage(this, "Before categories differ");
               return false;
            }
         }
      }
      {
         if (afterCategories.size() != otherRule.afterCategories.size()) {
            Entity.printDebugMessage(this, "Different after category counts");
            return false;
         }
         Iterator<TokenCategory> thisIterator = afterCategories.values().iterator();
         Iterator<TokenCategory> otherIterator = otherRule.afterCategories.values().iterator();
         while (thisIterator.hasNext()) {
            TokenCategory thisCategory = thisIterator.next();
            TokenCategory otherCategory = otherIterator.next();
            if (!thisCategory.equals(otherCategory)) {
               Entity.printDebugMessage(this, "After categories differ");
               return false;
            }
         }
      }
      {
         if (productions.size() != otherRule.productions.size()) {
            Entity.printDebugMessage(this, "Different production counts");
            return false;
         }
         Iterator<RuleProduction> thisAfterIterator = productions.iterator();
         Iterator<RuleProduction> otherAfterIterator = otherRule.productions.iterator();
         while (thisAfterIterator.hasNext()) {
            RuleProduction thisProduction = thisAfterIterator.next();
            RuleProduction otherProduction = otherAfterIterator.next();
            if (!thisProduction.equals(otherProduction)) {
               Entity.printDebugMessage(this, "Productions differ");
               return false;
            }
         }
      }
      return true;
   }
}

Listing 6: The RewriteRule implementation class.

Productions

The type hierarchy for RewriteRule is:

RewriteRule extends WriteableEntity

The name associated with each RewriteRule instance is superclass-maintained property. The setName() method override takes responsibility for registering each RewriteRule instance name with the parent RewriteableToken, and for updating this registration whenever the instance name changes.

Aside from the name, the RewriteRule class maintains three collections. Two of the collections help define the conditions under which the present RewriteRule is determined to be applicable. These collections are the SortedMap<String, TokenCategory> named beforeCategories and the SortedMap<String, TokenCategory> named afterCategories.

The significance of these two collections becomes clarified with an understanding of the boolean method applies(ChomskyStatement statement, int position) This method is consulted when the production process has elaborated the elements of statement up through position-1, is now elaborating the token at position, and has already determined that the token under scrutiny is the RewriteableToken which contains the present RewriteRule.

What RewriteRule.applies() does is first determine the category of the token at position-1. If beforeCategories excludes this category, and if beforeCategories is not empty, then applies() returns false (the rule doesn't apply). If position is situated at the beginning of the statement, then there's no previous token; under this circumstance applies() returns false unless beforeCategories contains the "null" category described previously.
What RewriteRule.applies() does next is determine the category of the token at position+1. If afterCategories excludes this category, and if afterCategories is not empty, then applies() returns false (the rule doesn't apply). If position is situated at the end of the statement, then there's no following token; under this circumstance applies() returns false unless afterCategories contains the "null" category described previously.
If the rule survives the preceding two steps, then applies() returns true (the rule applies).

The following methods are available for managing RewriteRule before categories and after categories:

Method addBeforeCategory(TokenCategory category) appends a new TokenCategory reference to beforeCategories.
Method removeBeforeCategory(TokenCategory category) removes the reference to the indicated TokenCategory from beforeCategories.
Method addAfterCategory(TokenCategory category) appends a new TokenCategory reference to afterCategories.
Method removeAfterCategory(TokenCategory category) removes the reference to the indicated TokenCategory from afterCategories.

The third collection managed by RewriteRule is the List<RuleProduction> named productions. Each element of this List offers a different way of rewriting the parent RewriteableToken. The sequential order of RuleProduction instances in this list doesn't really matter since only one element will be selected at random. (It could have been a Set rather than a List.) The following methods are available for managing RuleProduction references:

Method createProduction(ChomskyToken[] array) appends a new RuleProduction reference to the end of the productions List. It throws an IllegalArgumentException if two productions under the same RewriteableToken will list the same sequence of child tokens.
Method removeProduction(int position) deletes the RuleProduction from productions at the indicated position.

/**
 * The {@link RuleProduction} class maintains a sequence of tokens.
 * @author Charles Ames
 */
public class RuleProduction extends WriteableEntity {
   private List<ChomskyToken> tokens;
   private double weight;

   protected RuleProduction(RewriteRule rule) {
      super(rule);
      this.setIDQuality(Entity.AttributeQuality.UNUSED);
      this.setNameQuality(Entity.AttributeQuality.UNUSED);
      this.tokens = new ArrayList<ChomskyToken>();
      this.weight = 0.;
   }
   /**
    * Get the {@link RewriteRule} to which this {@link RuleProduction} belongs.
    * @return The assigned container.
    */
   public RewriteRule getContainer() {
      return (RewriteRule) super.getContainer();
   }
   /**
    * Getter for {@link #weight}.
    * @return The assigned {@link #weight} value.
    */
   public double getWeight() {
      return weight;
   }
   /**
    * Setter for {@link #weight}.
    * @param weight The intended {@link #weight} value.
    * @throws IllegalArgumentException when the argument is negative.
    */
   public void setWeight(double weight) {
      if (weight < 0.) throw new IllegalArgumentException("Negative weight");
      this.weight = weight;
   }
   protected List<ChomskyToken> getTokens() {
      return tokens;
   }
   /**
    * Get the succession of tokens.
    * @return An {@link Iterator} which presents each token
    * in sequence until the list is exhausted.
    */
   public Iterator<ChomskyToken> iterateTokens() {
      return tokens.iterator();
   }
   /**
    * Returns a text representation of the sequence of tokens
    * to be inserted in place of the {@link RewriteableToken} for
    * which this production is selected.
    * @return A text string.
    */
   public String contentString() {
      StringBuilder builder = new StringBuilder();
      for (ChomskyToken token : tokens) {
         builder.append("[");
         builder.append(token.getName());
         builder.append("]");
      }
      return builder.toString();
   }
   @Override
   public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("[");
      builder.append(getContainer().getContainer().getName());
      builder.append("] [");
      builder.append(getContainer().getName());
      builder.append("]");
      builder.append(" -> ");
      builder.append(contentString());
      builder.append(" (");
      builder.append(MathMethods.df3.format(weight));
      builder.append(") ");
      return builder.toString();
   }
}

Listing 7: The RuleProduction implementation class.

The type hierarchy for RuleProduction is:

RuleProduction extends WriteableEntity

RuleProduction instances have no identifying id or name. Each RuleProduction instance contains a List<ChomskyToken> named tokens and a double named weight.

The tokens list is populated from an array of ChomskyToken references upon construction. For the present, one cannot edit this content; one must simply remove and recreate the RuleProduction. No two RuleProduction instances under the same RewriteableEntity may share the same succession of ChomskyToken references.

The weight field influences the likelihood that this particular RuleProduction will be selected. The weight is relative to the total count of applicable productions. Suppose a certain RewriteableToken has three RewriteRule instances, each listing two RuleProduction instances, and that all six RuleProduction instances have equal weight. Then if RewriteRule.applies() returns true for two out of three rules, then the likelihood of selecting any one of the four applicable RuleProduction instances is 1 in 4.

/**
 * The {@link ChomskyStatement} class maintains a sequence of tokens.
 * @author Charles Ames
 */
public class ChomskyStatement extends WriteableEntity
      implements Iterable<ChomskyToken> {
   private List<ChomskyToken> tokens;
   private ProductionTree productionTree;
   /**
    * Constructor for {@link ChomskyStatement} instances.
    * @param grammar The {@link ChomskyGrammar} which contains this instance.
    * @param name The intended text identifier.
    */
   protected ChomskyStatement(ChomskyGrammar grammar, String name) {
      super(grammar);
      this.setIDQuality(Entity.AttributeQuality.UNUSED);
      this.setNameQuality(Entity.AttributeQuality.MODIFIABLE);
      setName(name);
      this.tokens = new ArrayList<ChomskyToken>();
      this.productionTree = null;
   }
   /**
    * Get the grammar to which this {@link ChomskyStatement} belongs.
    * @return The assigned container.
    */
   public ChomskyGrammar getContainer() {
      return (ChomskyGrammar) super.getContainer();
   }
   @Override
   public boolean setName(String name) {
      if (StringUtils.isBlank(name))
         throw new IllegalArgumentException("Blank name");
      SortedMap<String, ChomskyStatement> map = getContainer().getStatementsByName();
      String oldName = getOldName();
      if (StringUtils.equals(name, oldName)) return false;
      if (!StringUtils.isEmpty(oldName))
         map.remove(oldName);
      super.setName(name);
      map.put(name, this);
      return true;
   }
   /**
    * Allocate {@link #productionTree}.
    * @return The newly created {@link ProductionTree} instance.
    * @throws UnsupportedOperationException when {@link #productionTree} was previously allocated.
    */
   public ProductionTree createProductionTree() {
      if (null != productionTree) throw new UnsupportedOperationException("Production tree previously initialized");
      productionTree = new ProductionTree(this);
      return productionTree;
   }
   /**
    *
    * @throws NoSuchObjectException when no {@link #productionTree} has been allocated.
    */
   public void clearProductionTree() {
      productionTree = null;
   }
   /**
    * Getter for {@link #productionTree}.
    * @return The assigned {@link #productionTree} value.
    * @throws NoSuchObjectException when no {@link #productionTree} has been allocated.
    */
   public ProductionTree getProductionTree() {
      if (null == productionTree) throw new NoSuchObjectException("Production tree not allocated");
      return productionTree;
   }
   /**
    * Getter for {@link #tokens}.
    * @return A list of {@link ChomskyToken} instances.
    */
   protected List<ChomskyToken> getTokens() {
      return tokens;
   }
   /**
    * Append a {@link ChomskyToken} instance to this statement.
    * @param token The intended new statement element.
    */
   public void addToken(ChomskyToken token) {
      if (null == token) throw new IllegalArgumentException("Null argument");
      if (token.getContainer() != getContainer()) throw new IllegalArgumentException("Inconsistent grammar");
      tokens.add(token);
   }
   public Iterator<ChomskyToken> iterator() {
      return tokens.iterator();
   }
   /**
    * Get the number of tokens in this statement.
    * @return The size of the {@link #tokens} list.
    */
   public int size() {
      return tokens.size();
   }
   /**
    * Get the token in the indicated position.
    * @param position The indicated position.
    * @return The token in the indicated position.
    * Null if position out of range.
    */
   public ChomskyToken getToken(int position) {
      if (position < 0) return null;
      if (position >= tokens.size()) return null;
      return tokens.get(position);
   }
   /**
    * Copy this statement to a new {@link ChomskyStatement} instance
    * in the same container.
    * @param name The name distinguishing the new instance.
    * @return The duplicated {@link ChomskyStatement} instance.
    */
   public ChomskyStatement copy(String name) {
      ChomskyStatement result = getContainer().createStatement(name);
      for (ChomskyToken token : tokens) {
         result.addToken(token);
      }
      return result;
   }
   public String toString() {
      StringBuilder builder = new StringBuilder();
      for (ChomskyToken token : tokens) {
         builder.append("[");
         builder.append(token.getName());
         builder.append("]");
      }
      return builder.toString();
   }
   @Override
   public boolean equals(Entity other) {
      if (!super.equals(other)) {
         return false;
      }
      ChomskyStatement otherStatement = (ChomskyStatement) other;
      if (tokens.size() != otherStatement.tokens.size()) {
         Entity.printDebugMessage(this, "Different token counts");
         return false;
      }
      for (int position = 0; position < tokens.size(); position++) {
         ChomskyToken thisToken = this.tokens.get(position);
         ChomskyToken otherToken = otherStatement.tokens.get(position);
         if (!thisToken.equals(otherToken)) {
            Entity.printDebugMessage(this, "Tokens in position " + position + "] are different");
            return false;
         }
      }
      return true;
   }
}

Listing 8: The ChomskyStatement implementation class.

Data

The type hierarchy for ChomskyStatement is:

ChomskyStatement extends WriteableEntity implements Iterable<ChomskyToken>

The name associated with each ChomskyStatement instance is superclass-maintained property. The setName() method override takes responsibility for registering each ChomskyStatement instance name with the parent ChomskyGrammar, and for updating this registration whenever the instance name changes.

Aside from the name, the ChomskyStatement contains just a List<ChomskyToken> named tokens.

Method addToken(ChomskyToken token) appends new token references to the end of tokens, while method iterator() gives access to the succession of tokens while protecting the contents from external manipulation.

/**
 * The {@link ProductionNode} implements functionality shared between
 * {@link ProductionTree}, {@link ProductionNode.Branch}, and
 * {@link ProductionNode.Leaf}
 * @author Charles Ames
 */
public abstract class ProductionNode extends Entity {
   /**
    * Encapsulated functionality for managing child nodes.
    * Null for {@link ProductionNode.Leaf}.
    */
   ChildNodeManager manager;
   /**
    * Where in the product {@link ChomskyStatement}
    * this current production node happened.
    */
   int incident;
   /**
    * Constructor for {@link ProductionNode} instances.
    * @param container Who this object belongs to.  The
    * topmost node (always a {@link ProductionTree} belongs to a
    * {@link ChomskyGrammar}.  All other nodes belong to
    * other {@link ProductionNode} instances.
    * @param incident Where in the product {@link ChomskyStatement}
    * this current production node happened.
    */
   protected ProductionNode(EntityContainer container, int incident) {
      super(container);
      this.manager = null;
      this.incident = incident;
   }
   /**
    * Calculate the number of leaves terminating this portion of the
    * production tree.
    * @return The calculated number of leaves.
    */
   public final int leafCount() {
      if (null == manager) return 1;
      int result = 0;
      for (ProductionNode childNode : manager.childNodes)
         result += childNode.leafCount();
      return result;
   }
   /**
    * Calculate the depth of this node in the production hierarchy.  The
    * topmost node (always a {@link ProductionTree}) has depth -1.  All other
    * nodes have one more than their container's depth.
    * @return The calculated depth of this node in the production hierarchy.
    */
   public int depth() {
      ProductionNode container = (ProductionNode) getContainer();
      return container.depth() + 1;
   }
   /**
    * Getter for {@link #incident}.
    * @return The assigned {@link #incident} value.
    */
   public final int getIncident() {
      return incident;
   }
   /**
    * Calculate how many nodes exist under the present node.
    * @return The calculate depth beneath the present node.
    */
   public int maxDepth() {
      if (null == manager) return 1;
      int result = 0;
      for (ProductionNode childNode : manager.childNodes)
         result = Math.max(result, childNode.maxDepth());
      return result + 1;
   }
   /**
    * Get the {@link ChomskyStatement} which owns this production tree.
    * @return The {@link ChomskyStatement} which owns this production tree.
    */
   public ChomskyStatement getStatement()
   {
      ProductionNode container = (ProductionNode) getContainer();
      return container.getStatement();
   }
   /**
    * Get the {@link ChomskyGrammar} which owns this production tree.
    * @return The {@link ChomskyGrammar} which owns this production tree.
    */
   public ChomskyGrammar getGrammar()
   {
      ProductionNode container = (ProductionNode) getContainer();
      return container.getGrammar();
   }
   /**
    * Get the {@link ChomskyToken} that was encountered in the
    * product {@link ChomskyStatement} at the current incident
    * position.
    * @return The {@link ChomskyToken} that was encountered in the
    * product {@link ChomskyStatement} at the current incident
    * position.
    */
   public abstract ChomskyToken getToken();
   /**
    * Reset the {@link #hasNextNode()}/{@link #nextNode()} cycle.
    */
   public void reset() {
      setPosition(-1);
      resetChildren();
   }
   protected void resetChildren() {
      if (null != manager)
         for (ProductionNode childNode : manager.childNodes)
            childNode.reset();
   }
   protected void setPosition(int i) {
      if (null != manager) {
         manager.position = i;
      }
   }
   /**
    * Test if nodes remain to iterate.
    * @return True if nodes remain to iterate; false otherwise.
    */
   public boolean hasNextNode() {
      if (null == manager)
         throw new UnsupportedOperationException(
            "Cannot iterate child nodes from a leaf");
      int size = manager.childNodes.size();
      if (manager.position >= size) return false;
      if (manager.position < size - 1) return true;
      ProductionNode child = manager.childNodes.get(manager.position);
      if (!child.getToken().isRewriteable()) return true;
      return child.hasNextNode();
   }
   /**
    * Iterate recursively through this node and its children.
    * @return The next {@link ProductionNode} in the iteration.
    * @throws UnsupportedOperationException when this node is a leaf.
    */
   public ProductionNode nextNode() {
      if (null == manager)
         throw new UnsupportedOperationException(
            "Cannot iterate child nodes from a leaf");
      if (-1 == manager.position) {
         manager.position++;
         return this;
      }
      ProductionNode child = manager.childNodes.get(manager.position);
      for (;;) {
         if (child instanceof Leaf) {
            manager.position++;
            return child;
         }
         Branch branch = (Branch) child;
         if (branch.hasNextNode()) {
            ProductionNode node = branch.nextNode();
            return node;
         }
         else {
            if (++manager.position >= manager.childNodes.size())
               throw new NoSuchElementException("Programmer error");
            child = manager.childNodes.get(manager.position);
         }
      }
   }
   /**
    * Add a child {@link ProductionNode.Branch} to this {@link ProductionNode}.
    * @param production The {@link RuleProduction} invoked at this moment of
    * production.
    * @param incident The position in the product {@link ChomskyStatement}.
    * @return The newly created {@link ProductionNode.Branch} instance.
    */
   public ProductionNode addChildNode(RuleProduction production, int incident) {
      if (null == manager)
         throw new UnsupportedOperationException(
            "Cannot add nodes to leaves " + getClass().getSimpleName());
      Branch result = new Branch(this, production, incident);
      manager.childNodes.add(result);
      return result;
   }
   /**
    * Add a child {@link ProductionNode.Branch} to this {@link ProductionNode}.
    * @param token The {@link TerminalToken} inserted at this moment of
    * production.
    * @param incident The position in the product {@link ChomskyStatement}.
    * @return The newly created {@link ProductionNode.Branch} instance.
    */
   public ProductionNode addChildNode(TerminalToken token,  int incident) {
      if (null == manager)
         throw new UnsupportedOperationException(
            "Cannot add nodes to leaves");
      Leaf result = new Leaf(this, token, incident);
      manager.childNodes.add(result);
      return result;
   }
   /**
    * Embedded data structure to manage child nodes.
    * @author Charles Ames
    */
   public class ChildNodeManager {
      protected List<ProductionNode> childNodes;
      protected int position;
      protected ChildNodeManager() {
         this.childNodes = new ArrayList<ProductionNode>();
      }
   }
   /**
    * {@link ProductionNode} which contains child nodes, but which is
    * not a {@link ProductionTree}.
    * @author Charles Ames
    */
   public class Branch extends ProductionNode {
      /**
       * The {@link RuleProduction} whose content will be inserted
       * into the product {@link ChomskyStatement} at the current
       * incident position.       */
      private RuleProduction production;
      /**
       * Constructor for {@link ProductionNode.Branch} instances.
       * @param container The {@link ProductionNode} which owns this leaf.
       * @param production The {@link RuleProduction} whose content will be
       * inserted into the product {@link ChomskyStatement} at the current
       * incident position.
       * @param incident The position in the product {@link ChomskyStatement}.
       */
      protected Branch(ProductionNode container, RuleProduction production, int incident) {
         super(container, incident);
         if (getGrammar() != production.getContainer().getContainer().getContainer())
            throw new IllegalArgumentException("Inconsistent grammar");
         this.manager = new ChildNodeManager();
         this.production = production;
      }
      @Override
      public ProductionNode getContainer() {
         return (ProductionNode) super.getContainer();
      }
      /**
       * Getter for {@link #production}.
       * @return The assigned {@link #production} value.
       */
      public RuleProduction getProduction() {
         return production;
      }
      @Override
      public String toString() {
         return production.toString();
      }
      @Override
      public RewriteableToken getToken() {
         return getProduction().getContainer().getContainer();
      }
   }
   /**
    * {@link ProductionNode} which contains no child nodes.
    * @author Charles Ames
    */
   public class Leaf extends ProductionNode {
      TerminalToken token;
      /**
       * Constructor for {@link ProductionNode.Leaf} instances.
       * @param container The {@link ProductionNode} which owns this leaf.
       * @param token The {@link TerminalToken} selected for the product
       * {@link ChomskyStatement} at the current incident position.
       * @param incident The position in the product {@link ChomskyStatement}.
       */
      protected Leaf(ProductionNode container, TerminalToken token, int incident) {
         super(container, incident);
         if (getGrammar() != token.getContainer())
            throw new IllegalArgumentException("Inconsistent grammar");
         this.token = token;
      }
      @Override
      public ProductionNode getContainer() {
         return (ProductionNode) super.getContainer();
      }
      /**
       * Getter for {@link #token}.
       * @return The assigned {@link #token} value.
       */
      @Override
      public TerminalToken getToken() {
         return token;
      }
      @Override
      public String toString() {
         return token.getName();
      }
      @Override
      public int maxDepth() {
         return 0;
      }
      @Override
      public ChomskyGrammar getGrammar() {
         return getContainer().getGrammar();
      }
   }
}

Listing 9: The ProductionNode base class.


package net.charlesames.seqgen.index.chomsky;

/**
 * The {@link ProductionTree} class documents the productions applied
 * to an axiom, by which the referenced {@link ChomskyStatement} was
 * generated.
 * @author Charles Ames
 */
public class ProductionTree extends ProductionNode {
   /**
    * Constructor for {@link ProductionTree} instances.
    * @param container The {@link ChomskyStatement} whose generation
    * history this {@link ProductionTree} documents.
    */
   public ProductionTree(ChomskyStatement container) {
      super(container, -1);
      this.manager = new ChildNodeManager();
   }
   @Override
   public ChomskyStatement getContainer() {
      return (ChomskyStatement) super.getContainer();
   }
   @Override
   public int depth() {
      return -1;
   }
   public void reset() {
      super.setPosition(0);
      resetChildren();
   }
   @Override
   public ChomskyStatement getStatement() {
      return getContainer();
   }
   @Override
   public ChomskyGrammar getGrammar() {
      return getContainer().getContainer();
   }
   @Override
   public ChomskyToken getToken() {
      return null;
   }
}

Listing 10: The ProductionTree implementation class.

The type hierarchy for the ProductionTree apex class and its component Branch and Leaf classes is:

ProductionNode extends Entity
ProductionTree extends ProductionNode
ProductionNode.Branch extends ProductionNode
ProductionNode.Leaf extends ProductionNode

The tree, branch, and leaf classes together implement a composite design pattern, actually a hierarchy entirely made up of classes extending ProductionNode. These classes were implemented specifically for populating Table 3 (a) and Table 3 (b) above.

A single ProductionTree instance sits at the apex; The container holding this ProductionTree is the ChomskyStatement whose production the tree documents. Each ProductionTree maintains a collection of child nodes which can be either ProductionNode.Branch or ProductionNode.Leaf instances.

The container holding a ProductionNode.Branch is either the ProductionTree itself or a higher-level ProductionNode.Branch. Each ProductionNode.Branch references a RuleProduction which elaborated a higher-level RewriteableToken into a lower-level succession of ChomskyToken instances. Each ProductionNode.Branch maintains a collection of child nodes which can be either ProductionNode.Branch or ProductionNode.Leaf instances.

The container holding a ProductionNode.Leaf is either the ProductionTree itself or a higher-level ProductionNode.Branch. Each ProductionNode.Leaf references a single bottom-level TerminalToken instance.

Method ProductionNode.nextNode() implements a recursive algorithm that enumerates the entire tree of ProductionNode instances without repeating any. In this circumstance the word "recursive" refers to the fact that nextNode() includes within its code a call to nextNode(). Successive instances are offered primarily in incident order and secondarily in depth order.

Comments

Curtis Roads, "Composing Grammars" (Proceedings of the 1977 International Computer Music Conference).
Steven Holtzman, "A generative grammar definition language for music", Interface: Journal of New Music Research Vol. 9, No. 1 (1980) pp. 1-48.
For details see the Bol Processor home page.
Charles Ames, "Concurrence" Interface: Journal of New Music Research, Vol. 17, No. 1 (1988) pp. 3-24.

Left & Right Context Sensitivity: ChomskyGrammar

Left & Right Context Sensitivity: `ChomskyGrammar`