diva.sketch.parser2d
Class NorvigParser

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

public class NorvigParser
extends java.lang.Object

A simple CFG parser for strings, based on Norvig's parsing algorithm. This parser maybe extended to parsing 2D structures for high-level recognition purposes. For now it's simply for experimentation.

Version:
$Revision: 1.1 $

Inner Class Summary
static class NorvigParser.Parse
          Parse tree and remainder.
static class NorvigParser.Tree
          Grammar rules of the form: LHS => (RHS) sem For example S => '(var EQ expr) assign Alternatively can represent derivations based on grammar rules.
 
Constructor Summary
NorvigParser(NorvigParser.Tree[] grammar, java.lang.String[] openCategories)
          Construct a parser that uses the given grammar.
 
Method Summary
 boolean checkSemantics(NorvigParser.Tree t)
          Return true if the semantics of the parse tree check out?
 void clearMemoization()
          Clear memoization by clearing the hashtable of 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.
 java.util.List extendParse(java.lang.String lhs, java.lang.String sem, java.util.List rhs, java.util.List rem, java.util.List needed)
          Parse the given list of tokens using the installed grammar.
protected  java.util.List getMemoized(java.util.List in)
          FIXME
 java.util.Iterator lexicalRules(java.lang.String tok)
          Rules starting with the given terminal in their RHS.
 java.util.List parse(java.util.List in)
          Parse the given list of tokens using the installed grammar.
 java.util.Iterator rulesStartingWith(java.lang.String tok)
          Rules whose RHS start with the given non-terminal.
protected  void setMemoized(java.util.List in, java.util.List out)
          FIXME
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

NorvigParser

public NorvigParser(NorvigParser.Tree[] grammar,
                    java.lang.String[] openCategories)
Construct a parser that uses the given grammar.
Method Detail

parse

public java.util.List parse(java.util.List in)
Parse the given list of tokens using the installed grammar. Return a list of the possible parses, including incomplete parses with remainders.

getMemoized

protected java.util.List getMemoized(java.util.List in)
FIXME

setMemoized

protected void setMemoized(java.util.List in,
                           java.util.List out)
FIXME

clearMemoization

public void clearMemoization()
Clear memoization by clearing the hashtable of memoized results.

extendParse

public java.util.List extendParse(java.lang.String lhs,
                                  java.lang.String sem,
                                  java.util.List rhs,
                                  java.util.List rem,
                                  java.util.List needed)
Parse the given list of tokens using the installed grammar.

lexicalRules

public java.util.Iterator lexicalRules(java.lang.String tok)
Rules starting with the given terminal in their RHS.

rulesStartingWith

public java.util.Iterator rulesStartingWith(java.lang.String tok)
Rules whose RHS start with the given non-terminal.

checkSemantics

public boolean checkSemantics(NorvigParser.Tree t)
Return true if the semantics of the parse tree check out?

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).