Class BottomUpChartParser

java.lang.Object
  extended byBottomUpChartParser
Direct Known Subclasses:
AugmentedChartParser

public class BottomUpChartParser
extends java.lang.Object

This is the simple bottom-up parser described in NLU Chapter 3. It uses just syntactic catgeories (no features).


Field Summary
(package private)  Agenda agenda
          The Agenda used by this BottomUpChartParser.
(package private)  java.util.HashMap categoryCounters
          Set of counters to support more intuitive use of gensym().
(package private)  Chart chart
          The Chart used by this BottomUpChartParser.
(package private)  Grammar grammar
          The Grammar used by this BottomUpChartParser.
(package private)  int inputLength
          Length of the sentence being parsed.
(package private)  Lexicon lexicon
          The Lexicon used by this BottomUpChartParser.
(package private)  int nParsesFound
          Number of parses found so far.
(package private)  int nParsesWanted
          Number of parses after which we should stop (0 means find all parses).
(package private)  Symbol SYMBOL_S
          The Symbol ``S'', used for the syntactic category representing complete parses.
(package private)  Tokenizer tokenizer
          The Tokenizer used by this BottomUpChartParser.
(package private)  java.util.List tokens
          The input tokens being parsed (for debugging).
 
Constructor Summary
BottomUpChartParser()
          Create a new BottomUpChartParser.
 
Method Summary
(package private)  void addArcToChart(Arc arc)
          Step 4 of the bottom-up parsing algorithm (step 4, substep 3 in second edition).
(package private)  void addEntryToChart(Entry entry)
          Adds the given Entry (completed constituent) to the chart and tries to add or extend arcs (possibly adding new entries to the agenda for completed arcs).
(package private)  Entry createEntryForCompletedArc(Arc arc)
          Create the new Entry to be added to the agenda for given (completed) Arc.
(package private)  Symbol createEntryId(Symbol category)
          Creates a Symbol id for a new entry of the given category.
(package private)  boolean entryIsCompleteParse(Entry entry)
          Returns true if the given Entry represents a complete parse of the input.
(package private)  void extendArcsForEntry(Entry entry)
          Step 3 of the bottom-up parsing algorithm (step 4, substep 2 in second edition).
(package private)  Arc extendArcWithEntry(Arc arc, Entry entry)
          If the constituent of the given Entry matches the next Constituent of the given Arc, then create and return a new Arc extending the given one, otherwise return null.
(package private)  void fireRulesForEntry(Entry entry)
          Step 2 of the bottom-up parsing algorithm (step 3 in second edition).
(package private)  void initializeAgenda(java.util.List tokenList)
          Adds initial entries to the agenda for the given (tokenized) input sentence.
(package private)  void initializeAgendaForWord(Symbol word, int pos)
          Finds the entry in the lexicon for a specific word and creates chart entries on the agenda for each interpretation.
static void main(java.lang.String[] argv)
          Test the basic bottom-up chart BottomUpChartParser.
static void main(java.lang.String[] argv, java.lang.Class lexiconClass, java.lang.Class grammarClass, java.lang.Class parserClass)
          For use by subclasses that need to specify different types of lexicon, grammar, and parser.
 int parse(java.lang.String input)
          Parse the given input string.
(package private)  boolean parseDone()
          Returns true if we should stop parsing, either because the agenda is empty, or because we have found the requested number of parses.
(package private)  void setGrammar(Grammar grammar)
          Set the Grammar used by this BottomUpChartParser.
(package private)  void setLexicon(Lexicon lexicon)
          Set the Lexicon used by this BottomUpChartParser.
(package private)  void setNParsesWanted(int n)
          Set the number of parses after which to stop (0 means find all parses).
(package private)  void setTokenizer(Tokenizer tokenizer)
          Set the Tokenizer used by this BottomUpChartParser.
(package private)  java.lang.String tokensAsString(int start, int end)
          Return a string consisting of the input tokens of the sentence being parsed within the given start-end range.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

lexicon

Lexicon lexicon
The Lexicon used by this BottomUpChartParser.


grammar

Grammar grammar
The Grammar used by this BottomUpChartParser.


tokenizer

Tokenizer tokenizer
The Tokenizer used by this BottomUpChartParser.


nParsesWanted

int nParsesWanted
Number of parses after which we should stop (0 means find all parses).


chart

Chart chart
The Chart used by this BottomUpChartParser.


agenda

Agenda agenda
The Agenda used by this BottomUpChartParser.


tokens

java.util.List tokens
The input tokens being parsed (for debugging).


inputLength

int inputLength
Length of the sentence being parsed.


nParsesFound

int nParsesFound
Number of parses found so far.


categoryCounters

java.util.HashMap categoryCounters
Set of counters to support more intuitive use of gensym().


SYMBOL_S

final Symbol SYMBOL_S
The Symbol ``S'', used for the syntactic category representing complete parses.

Constructor Detail

BottomUpChartParser

public BottomUpChartParser()
Create a new BottomUpChartParser.

Method Detail

setLexicon

void setLexicon(Lexicon lexicon)
Set the Lexicon used by this BottomUpChartParser.


setGrammar

void setGrammar(Grammar grammar)
Set the Grammar used by this BottomUpChartParser.


setTokenizer

void setTokenizer(Tokenizer tokenizer)
Set the Tokenizer used by this BottomUpChartParser.


setNParsesWanted

void setNParsesWanted(int n)
Set the number of parses after which to stop (0 means find all parses).


parse

public int parse(java.lang.String input)
Parse the given input string. This is the main interface method for the BottomUpChartParser. After parsing, the chart is left unchanged until the next call to this method. Returns the number of parses found.


initializeAgenda

void initializeAgenda(java.util.List tokenList)
Adds initial entries to the agenda for the given (tokenized) input sentence.


initializeAgendaForWord

void initializeAgendaForWord(Symbol word,
                             int pos)
Finds the entry in the lexicon for a specific word and creates chart entries on the agenda for each interpretation.


createEntryId

Symbol createEntryId(Symbol category)
Creates a Symbol id for a new entry of the given category. This could just call Symbol.gensym(category), but with a bit more bookkeeping we can make the numbering come out as it does in the NLU textbook (essentially, per-category numbering).


parseDone

boolean parseDone()
Returns true if we should stop parsing, either because the agenda is empty, or because we have found the requested number of parses.


addEntryToChart

void addEntryToChart(Entry entry)
Adds the given Entry (completed constituent) to the chart and tries to add or extend arcs (possibly adding new entries to the agenda for completed arcs).


tokensAsString

java.lang.String tokensAsString(int start,
                                int end)
Return a string consisting of the input tokens of the sentence being parsed within the given start-end range. This is used only for the trace messages in addEntryToChart() (but is very informative there).


entryIsCompleteParse

boolean entryIsCompleteParse(Entry entry)
Returns true if the given Entry represents a complete parse of the input. This method may be overidden by subclasses.


fireRulesForEntry

void fireRulesForEntry(Entry entry)
Step 2 of the bottom-up parsing algorithm (step 3 in second edition).

For newly-added constituent C from p1 to p2: If C begins a rule R in the grammar, add an active arc for R from p1 to p2. That is, if R = ``X -> C X2 .. Xn'' is a rule in grammar, add an active arc ``X -> C * X2 ... XN'' from p1 to p2.


extendArcsForEntry

void extendArcsForEntry(Entry entry)
Step 3 of the bottom-up parsing algorithm (step 4, substep 2 in second edition).

For newly-added constituent C from p1 to p2: For any active arc A beginning at (some) p0 and ending at p1 (the beginning of C), if C is the next subconstituent of A, then add an active arc from p0 to p2 with the updated rule from A. That is, for any active arc of the form ``X -> X1 ... * C ... Xn'' from p0 to p1 (the beginning of C), add an active arc ``X -> X1 ... C * ... Xn'' from p0 to p2.

Note: The description in the second edition of NLU phrases this a bit differently, putting the ``completed arc'' condition test here rather than handling the arcs from steps 2 and 3 uniformly. The original description of the process works better in code.


extendArcWithEntry

Arc extendArcWithEntry(Arc arc,
                       Entry entry)
If the constituent of the given Entry matches the next Constituent of the given Arc, then create and return a new Arc extending the given one, otherwise return null. This method may be overidden by subclasses.


addArcToChart

void addArcToChart(Arc arc)
Step 4 of the bottom-up parsing algorithm (step 4, substep 3 in second edition).

If any of the active arcs added in steps 2 or 3 are completed rules, add the new constituents, which are named by the left-hand side of the rules, to the agenda.


createEntryForCompletedArc

Entry createEntryForCompletedArc(Arc arc)
Create the new Entry to be added to the agenda for given (completed) Arc. This method may be overidden by subclasses.


main

public static void main(java.lang.String[] argv)
Test the basic bottom-up chart BottomUpChartParser.


main

public static void main(java.lang.String[] argv,
                        java.lang.Class lexiconClass,
                        java.lang.Class grammarClass,
                        java.lang.Class parserClass)
For use by subclasses that need to specify different types of lexicon, grammar, and parser.