diva.sketch.parser2d
Class Parser2D

java.lang.Object
  |
  +--diva.sketch.parser2d.Parser2D

public class Parser2D
extends java.lang.Object

A simple CFG parser for graph grammars. This is currently the most trivial and inefficient strictly bottom-up implementation, just to see how much we inefficiency can get away with in parsing graph grammars.

The parser successively applies a set of rules ot the input constituent set, and if the rules match a subset of the constituents, it substitutes the left side of the rule for the matching constituents in the right side. This forms a new constuent set which is then passed to the parser again along with the remaining constituents. This chain continues until there are no rule matches. If the constituent at the end of the chain is a successful parse (definition of which is probably application-dependent) this is returned as part of the results.

Version:
$Revision: 1.1 $

Constructor Summary
Parser2D(Rule[] grammar)
          Construct a new parser with the specified grammar rules.
Parser2D(java.lang.String grammarURL)
          Construct a new parser with the grammar rules specified in the file at the given URL (can be a relative file too).
 
Method Summary
 void clearMemoization()
          Clear the cached (memoized) results.
static java.util.List completeParses(java.util.List parses)
          Return the subset of this list of parses that are complete parses (i.e.
static void debug(java.lang.String s)
          Debugging output.
static boolean isComplete(ConstituentSet cs)
          Return whether or not this parse is complete (has no loose ends).
 java.util.List parse(ConstituentSet in)
          Parse the given constituent set (initially terminals) into a coherent parse tree.
protected  java.util.List parseNoMemoize(ConstituentSet in)
          Parse the given constituent set (initially terminals) into a coherent parse tree.
static java.util.List removeDuplicates(java.util.List in)
          Return the given list without duplicates.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Parser2D

public Parser2D(Rule[] grammar)
Construct a new parser with the specified grammar rules.

Parser2D

public Parser2D(java.lang.String grammarURL)
         throws java.lang.Exception
Construct a new parser with the grammar rules specified in the file at the given URL (can be a relative file too). Throws an exception if there is problems opening, reading, or parsing the given URL.
Method Detail

debug

public static void debug(java.lang.String s)
Debugging output.

parse

public java.util.List parse(ConstituentSet in)
Parse the given constituent set (initially terminals) into a coherent parse tree. Return a list of the possible parses, including incomplete parses with remainders.

parseNoMemoize

protected java.util.List parseNoMemoize(ConstituentSet in)
Parse the given constituent set (initially terminals) into a coherent parse tree. Return a list of the possible parses, including incomplete parses with remainders.

clearMemoization

public void clearMemoization()
Clear the cached (memoized) results.

removeDuplicates

public static java.util.List removeDuplicates(java.util.List in)
Return the given list without duplicates.

completeParses

public static java.util.List completeParses(java.util.List parses)
Return the subset of this list of parses that are complete parses (i.e. that have no remainder).

isComplete

public static boolean isComplete(ConstituentSet cs)
Return whether or not this parse is complete (has no loose ends).