sjm.parse
Class Parser

java.lang.Object
  |
  +--sjm.parse.Parser

Direct Known Subclasses:

CollectionParser, Empty, Repetition, Terminal

public abstract class Parser

extends java.lang.Object

A Parser is an object that recognizes the elements of a language.

Each Parser object is either a Terminal or a composition of other parsers. The Terminal class is a subclass of Parser, and is itself a hierarchy of parsers that recognize specific patterns of text. For example, a Word recognizes any word, and a Literal matches a specific string.

In addition to Terminal, other subclasses of Parser provide composite parsers, describing sequences, alternations, and repetitions of other parsers. For example, the following Parser objects culminate in a good parser that recognizes a description of good coffee.

     Alternation adjective = new Alternation();
     adjective.add(new Literal("steaming"));
     adjective.add(new Literal("hot"));
     Sequence good = new Sequence();
     good.add(new Repetition(adjective));
     good.add(new Literal("coffee"));
     String s = "hot hot steaming hot coffee";
     Assembly a = new TokenAssembly(s);
     System.out.println(good.bestMatch(a));
 

This prints out:

     [hot, hot, steaming, hot, coffee]
     hot/hot/steaming/hot/coffee^
 

The parser does not match directly against a string, it matches against an Assembly. The resulting assembly shows its stack, with four words on it, along with its sequence of tokens, and the index at the end of these. In practice, parsers will do some work on an assembly, based on the text they recognize.

Version:

1.0

Author:

Steven J. Metsker

Field Summary

protected Assembler	assembler
protected java.lang.String	name

Constructor Summary

Parser()
Constructs a nameless parser.

Parser(java.lang.String name)
Constructs a parser with the given name.

Method Summary

void	accept(ParserVisitor pv) Accepts a "visitor" which will perform some operation on a parser structure.
abstract void	accept(ParserVisitor pv, java.util.Vector visited) Accepts a "visitor" along with a collection of previously visited parsers.
static void	add(java.util.Vector v1, java.util.Vector v2) Adds the elements of one vector to another.
Assembly	best(java.util.Vector v) Returns the most-matched assembly in a collection.
Assembly	bestMatch(Assembly a) Returns an assembly with the greatest possible number of elements consumed by matches of this parser.
Assembly	completeMatch(Assembly a) Returns either null, or a completely matched version of the supplied assembly.
static java.util.Vector	elementClone(java.util.Vector v) Create a copy of a vector, cloning each element of the vector.
java.lang.String	getName() Returns the name of this parser.
abstract java.util.Vector	match(java.util.Vector in) Given a set (well, a Vector, really) of assemblies, this method matches this parser against all of them, and returns a new set (also really a Vector) of the assemblies that result from the matches.
java.util.Vector	matchAndAssemble(java.util.Vector in) Match this parser against an input state, and then apply this parser's assembler against the resulting state.
protected abstract java.util.Vector	randomExpansion(int maxDepth, int depth)
java.lang.String	randomInput(int maxDepth, java.lang.String separator) Return a random element of this parser's language.
Parser	setAssembler(Assembler assembler) Sets the object that will work on an assembly whenever this parser successfully matches against the assembly.
java.lang.String	toString() Returns a textual description of this parser.
protected java.lang.String	toString(java.util.Vector visited) Returns a textual description of this parser.
protected abstract java.lang.String	unvisitedString(java.util.Vector visited)

Methods inherited from class java.lang.Object

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

Field Detail

name

protected java.lang.String name

assembler

protected Assembler assembler

Constructor Detail

Parser

public Parser()

Constructs a nameless parser.

Parser

public Parser(java.lang.String name)

Constructs a parser with the given name.

Parameters:

String - A name to be known by. For parsers that are deep composites, a simple name identifying its purpose is useful.

Method Detail

accept

public void accept(ParserVisitor pv)

Accepts a "visitor" which will perform some operation on a parser structure. The book, "Design Patterns", explains the visitor pattern.

Parameters:

ParserVisitor - the visitor to accept

accept

public abstract void accept(ParserVisitor pv,
                            java.util.Vector visited)

Accepts a "visitor" along with a collection of previously visited parsers.

Parameters:

ParserVisitor - the visitor to accept

Vector - a collection of previously visited parsers.

add

public static void add(java.util.Vector v1,
                       java.util.Vector v2)

Adds the elements of one vector to another.

Parameters:

v1 - the vector to add to

v2 - the vector with elements to add

best

public Assembly best(java.util.Vector v)

Returns the most-matched assembly in a collection.

Parameters:

Vector - the collection to look through

Returns:

the most-matched assembly in a collection.

bestMatch

public Assembly bestMatch(Assembly a)

Returns an assembly with the greatest possible number of elements consumed by matches of this parser.

Parameters:

Assembly - an assembly to match against

Returns:

an assembly with the greatest possible number of elements consumed by this parser

completeMatch

public Assembly completeMatch(Assembly a)

Returns either null, or a completely matched version of the supplied assembly.

Parameters:

Assembly - an assembly to match against

Returns:

either null, or a completely matched version of the supplied assembly

elementClone

public static java.util.Vector elementClone(java.util.Vector v)

Create a copy of a vector, cloning each element of the vector.

Parameters:

in - the vector to copy

Returns:

a copy of the input vector, cloning each element of the vector

getName

public java.lang.String getName()

Returns the name of this parser.

Returns:

the name of this parser

match

public abstract java.util.Vector match(java.util.Vector in)

Given a set (well, a Vector, really) of assemblies, this method matches this parser against all of them, and returns a new set (also really a Vector) of the assemblies that result from the matches.

For example, consider matching the regular expression a* against the string "aaab". The initial set of states is {^aaab}, where the ^ indicates how far along the assembly is. When a* matches against this initial state, it creates a new set {^aaab, a^aab, aa^ab, aaa^b}.

Parameters:

Vector - a vector of assemblies to match against

Returns:

a Vector of assemblies that result from matching against a beginning set of assemblies

matchAndAssemble

public java.util.Vector matchAndAssemble(java.util.Vector in)

Match this parser against an input state, and then apply this parser's assembler against the resulting state.

Parameters:

Vector - a vector of assemblies to match against

Returns:

a Vector of assemblies that result from matching against a beginning set of assemblies

randomExpansion

protected abstract java.util.Vector randomExpansion(int maxDepth,
                                                    int depth)

randomInput

public java.lang.String randomInput(int maxDepth,
                                    java.lang.String separator)

Return a random element of this parser's language.

Returns:

a random element of this parser's language

setAssembler

public Parser setAssembler(Assembler assembler)

Sets the object that will work on an assembly whenever this parser successfully matches against the assembly.

Parameters:

Assembler - the assembler to apply

Returns:

Parser this

toString

public java.lang.String toString()

Returns a textual description of this parser.

Overrides:

toString in class java.lang.Object

Returns:

String a textual description of this parser, taking care to avoid infinite recursion

toString

protected java.lang.String toString(java.util.Vector visited)

Returns a textual description of this parser. Parsers can be recursive, so when building a descriptive string, it is important to avoid infinite recursion by keeping track of the objects already described. This method keeps an object from printing twice, and uses unvisitedString which subclasses must implement.

Parameters:

Vector - a list of objects already printed

Returns:

a textual version of this parser, avoiding recursion

unvisitedString

protected abstract java.lang.String unvisitedString(java.util.Vector visited)