finiteAutomata
Class StringVarTerm

java.lang.Object
  finiteAutomata.StringVarTerm

public class StringVarTerm
extends java.lang.Object

A non-empty string of variables and terminals such as occur in grammar derivations (supports the CNF class).

Data Fields: Each StringVarTerm has a Vector (code) of Integer codes to represent the string, a counter (vars) telling how many variables are in the string, a Vector (derivation) of String objects showing the sequence of strings used in deriving this string, and an Alphabet (alpha) of allowable terminal symbols.

Example (encoding/decoding): Suppose the Alphabet is {a,b,c}. The integers 1, 2, 3 are used to represent, respectively, the terminal symbols a, b, and c. 0 represents the start variable v0, -1 represents v1, -2 represents v2, and so on. Thus, the string "c a v1 v2 b a v2" would be encoded by the integer sequence "3, 1, -1, -2, 2, 1, -2". Note that terminals are represented by positive codes and variables are represented by non-positive codes.

Version:

Fall 2007

Author:

Barbara Wahl

Field Summary

protected Alphabet	alpha alphabet of terminal symbols
protected java.util.Vector	code sequence of Integer codes for this StringVarTerm
protected java.util.Vector	derivation sequence of Strings showing how this StringVarTerm is derived from start (v0)
protected int	vars number of variables in this StringVarTerm (vars == 0 if this represents a string of terminal symbols)

Constructor Summary

StringVarTerm(Alphabet S)
1-parameter constructor, creates the StringVarTerm representing the start string, "v0"

Method Summary

StringVarTerm	applyRule(CNFRule r) Returns the result of applying the given CNFRule to the LEFT-MOST variable in this StringVarTerm.
java.util.Vector	code() Returns a deep copy of this.code.
StringVarTerm	copy() Returns a deep copy of this StringVarTerm.
protected int	decodeVar(int i) Returns the decoded value of the given position in this.code, assuming that position is a coded variable.
java.util.Vector	derivation() Returns a deep copy of this.derivation.
boolean	equalString(StringVarTerm other) Tests whether "this" and another StringVarTerm represent the same string.
boolean	equalTermString(java.lang.String s) Tests whether a given String is a non-empty string of terminals and this StringVarTerm represents the same string of terminals.
int	leftMostVarIndex() Returns the index (position) of the left-most variable in this StringVarTerm.
static void	main(java.lang.String[] args)
boolean	matches(CNFRule r) Tests whether a given rule applies to the left-most variable in this StringVarTerm.
int	numSteps() Returns number of steps to derive this StringVarTerm.
void	printDerivation() Pretty-prints the derivation.
void	printStringVarTerm() Pretty-prints a report on this StringVarTerm.
java.lang.String	toPrettyString() Returns a "pretty" representation of the string represented by this StringVarTerm.
java.lang.String	toTermString() Decodes this StringVarTerm (which has no variables); returns a String with no spaces.
int	vars() Returns number of variables.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

code

protected java.util.Vector code

sequence of Integer codes for this StringVarTerm

vars

protected int vars

number of variables in this StringVarTerm (vars == 0 if this represents a string of terminal symbols)

alpha

protected Alphabet alpha

alphabet of terminal symbols

derivation

protected java.util.Vector derivation

sequence of Strings showing how this StringVarTerm is derived from start (v0)

Constructor Detail

StringVarTerm

public StringVarTerm(Alphabet S)

1-parameter constructor, creates the StringVarTerm representing the start string, "v0"

Parameters:

S - Alphabet of terminal symbols

Postcondition:

creates the "start" string consisting of only the start variable, "v0" (alpha = S, vars = 1, derivation is empty)

Method Detail

numSteps

public int numSteps()

Returns number of steps to derive this StringVarTerm.

Returns:

number of steps to derive this StringVarTerm from "v0" (where 0 steps are needed to derive "v0")

vars

public int vars()

Returns number of variables.

Returns:

this.vars

copy

public StringVarTerm copy()

Returns a deep copy of this StringVarTerm.

Returns:

a new StringVarTerm with all the same data fields as this

Postcondition:

the new object is completely independent of the original (the derivation and code Vectors are deep-copied)

derivation

public java.util.Vector derivation()

Returns a deep copy of this.derivation.

Returns:

a new derivation Vector filled with new String objects

code

public java.util.Vector code()

Returns a deep copy of this.code.

Returns:

a new code Vector filled with new Integer objects

printStringVarTerm

public void printStringVarTerm()

Pretty-prints a report on this StringVarTerm.

Postcondition:

reports alphabet, string of variables and terminals, number of variables in string, number of terminals in string, length of derivation for this StringVarTerm, steps in derivation for this StringVarTerm

printDerivation

public void printDerivation()

Pretty-prints the derivation.

Postcondition:

prints each string in the derivation, separated by arrows ("->"), with "this" string appended at the end

toPrettyString

public java.lang.String toPrettyString()

Returns a "pretty" representation of the string represented by this StringVarTerm.

Returns:

a "pretty" String representation of this StringVarTerm (decodes the "code" Vector, inserts 'v's and spaces)

toTermString

public java.lang.String toTermString()

Decodes this StringVarTerm (which has no variables); returns a String with no spaces.

Returns:

the decoded String version of this.code, with no spaces inserted between characters (useful for strings of terminals only)

Precondition:

vars == 0

applyRule

public StringVarTerm applyRule(CNFRule r)

Returns the result of applying the given CNFRule to the LEFT-MOST variable in this StringVarTerm.

Parameters:

r - the rule to be applied

Returns:

the StringVarTerm which results from applying rule r to the LEFT-MOST variable in this StringVarTerm, if possible (otherwise, returns a copy of this StringVarTerm and prints a warning message).

Precondition:

if r is a "type 1" rule (var -> term) then r.term() must be a symbol in this.alpha

Postcondition:

this StringVarTerm is left unchanged

decodeVar

protected int decodeVar(int i)

Returns the decoded value of the given position in this.code, assuming that position is a coded variable.

Parameters:

i - position of interest in this code

Returns:

assuming code.elementAt(i) has a non-positive value, returns the corresponding variable number

Precondition:

0 <= i < code.length()

leftMostVarIndex

public int leftMostVarIndex()

Returns the index (position) of the left-most variable in this StringVarTerm.

Returns:

the index of the left-most variable in this StringVarTerm, or -1 (if no variables are present)

matches

public boolean matches(CNFRule r)

Tests whether a given rule applies to the left-most variable in this StringVarTerm.

Parameters:

r - the rule to be tested

Returns:

true iff the left-most variable in this StringVarTerm is the same as r.var1, the LHS of rule r

Precondition:

r is not null

equalTermString

public boolean equalTermString(java.lang.String s)

Tests whether a given String is a non-empty string of terminals and this StringVarTerm represents the same string of terminals.

Parameters:

s - the String to be tested

Returns:

true iff "this" and s represent exactly the same non-empty string of terminal symbols

Precondition:

s is not null

equalString

public boolean equalString(StringVarTerm other)

Tests whether "this" and another StringVarTerm represent the same string.

Parameters:

other - the StringVarTerm with which to compare this

Returns:

true iff "this" and other represent the same string of variables and terminals (perhaps with different derivations)

Precondition:

other is not null

main

public static void main(java.lang.String[] args)