Home       Trees       Indices       Help   
nltk 0.9.5
Package nltk :: Package parse :: Module rd :: Class SteppingRecursiveDescentParser
[hide private]
[frames] | no frames]

Class SteppingRecursiveDescentParser

source code

        object --+        
                 |        
       api.ParserI --+    
                     |    
RecursiveDescentParser --+
                         |
                        SteppingRecursiveDescentParser
Known Subclasses:

A RecursiveDescentParser that allows you to step through the parsing process, performing a single operation at a time.

The initialize method is used to start parsing a text. expand expands the first element on the frontier using a single CFG production, and match matches the first element on the frontier against the next text token. backtrack undoes the most recent expand or match operation. step performs a single expand, match, or backtrack operation. parses returns the set of parses that have been found by the parser.

See Also: nltk.cfg

Instance Methods [hide private]
 
__init__(self, grammar, trace=0)
Create a new RecursiveDescentParser, that uses grammar to parse texts.		 source code
 
_freeze(self, tree) source code
list of Tree
nbest_parse(self, tokens, n=None)
Returns: A list of parse trees that represent possible structures for the given sentence.		 source code
 
initialize(self, tokens)
Start parsing a given text.		 source code
list of String
remaining_text(self)
Returns: The portion of the text that is not yet covered by the tree.		 source code
list of tuple of int
frontier(self)
Returns: A list of the tree locations of all subtrees that have not yet been expanded, and all leaves that have not yet been matched.		 source code
Tree
tree(self)
Returns: A partial structure for the text that is currently being parsed.		 source code
Production or String or boolean
step(self)
Perform a single parsing operation.		 source code
Production or None
expand(self, production=None)
Expand the first element of the frontier.		 source code
String or None
match(self)
Match the first element of the frontier.		 source code
boolean
backtrack(self)
Return the parser to its state before the most recent match or expand operation.		 source code
list of Production
expandable_productions(self)
Returns: A list of all the productions for which expansions are available for the current parser state.		 source code
list of Production
untried_expandable_productions(self)
Returns: A list of all the untried productions for which expansions are available for the current parser state.		 source code
boolean
untried_match(self)
Returns: Whether the first element of the frontier is a token that has not yet been matched.		 source code
boolean
currently_complete(self)
Returns: Whether the parser's current state represents a complete parse.		 source code
list of int
_parse(self, remaining_text, tree, frontier)
A stub version of _parse that sets the parsers current state to the given arguments.		 source code
list of Tree
parses(self)
Returns: A list of the parses that have been found by this parser so far.		 source code
 
set_grammar(self, grammar)
Change the grammar used to parse texts.		 source code

Inherited from RecursiveDescentParser: grammar, trace

Inherited from RecursiveDescentParser (private): _expand, _match, _production_to_tree, _trace_backtrack, _trace_expand, _trace_fringe, _trace_match, _trace_start, _trace_succeed, _trace_tree

Inherited from api.ParserI: batch_iter_parse, batch_nbest_parse, batch_parse, batch_prob_parse, iter_parse, parse, prob_parse

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __str__

    Deprecated

Inherited from api.ParserI: batch_test, get_parse, get_parse_dict, get_parse_list, get_parse_prob

Instance Variables [hide private]
  _history
A list of (rtext, tree, frontier) tripples, containing the previous states of the parser.
  _tried_e
A record of all productions that have been tried for a given tree.
  _tried_m
A record of what tokens have been matched for a given tree.
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, grammar, trace=0)
(Constructor)

source code 

Create a new RecursiveDescentParser, that uses grammar to parse texts.

Parameters:
  • grammar - The grammar used to parse texts.
  • trace - The level of tracing that should be used when parsing a text. 0 will generate no tracing output; and higher numbers will produce more verbose tracing output.
Overrides: RecursiveDescentParser.__init__
(inherited documentation)

nbest_parse(self, tokens, n=None)

source code 
Parameters:
  • sent - The sentence to be parsed
  • n - The maximum number of trees to return.
Returns: list of Tree
A list of parse trees that represent possible structures for the given sentence. When possible, this list is sorted from most likely to least likely. If n is specified, then the returned list will contain at most n parse trees.
Overrides: RecursiveDescentParser.nbest_parse

initialize(self, tokens)

source code 

Start parsing a given text. This sets the parser's tree to the start symbol, its frontier to the root node, and its remaining text to token['SUBTOKENS'].

remaining_text(self)

source code 
Returns: list of String
The portion of the text that is not yet covered by the tree.

frontier(self)

source code 
Returns: list of tuple of int
A list of the tree locations of all subtrees that have not yet been expanded, and all leaves that have not yet been matched.

tree(self)

source code 
Returns: Tree
A partial structure for the text that is currently being parsed. The elements specified by the frontier have not yet been expanded or matched.

step(self)

source code 

Perform a single parsing operation. If an untried match is possible, then perform the match, and return the matched token. If an untried expansion is possible, then perform the expansion, and return the production that it is based on. If backtracking is possible, then backtrack, and return 1. Otherwise, return 0.

Returns: Production or String or boolean
0 if no operation was performed; a token if a match was performed; a production if an expansion was performed; and 1 if a backtrack operation was performed.

expand(self, production=None)

source code 

Expand the first element of the frontier. In particular, if the first element of the frontier is a subtree whose node type is equal to production's left hand side, then add a child to that subtree for each element of production's right hand side. If production is not specified, then use the first untried expandable production. If all expandable productions have been tried, do nothing.

Returns: Production or None
The production used to expand the frontier, if an expansion was performed. If no expansion was performed, return None.

match(self)

source code 

Match the first element of the frontier. In particular, if the first element of the frontier has the same type as the next text token, then substitute the text token into the tree.

Returns: String or None
The token matched, if a match operation was performed. If no match was performed, return None

backtrack(self)

source code 

Return the parser to its state before the most recent match or expand operation. Calling undo repeatedly return the parser to successively earlier states. If no match or expand operations have been performed, undo will make no changes.

Returns: boolean
true if an operation was successfully undone.

expandable_productions(self)

source code 
Returns: list of Production
A list of all the productions for which expansions are available for the current parser state.

untried_expandable_productions(self)

source code 
Returns: list of Production
A list of all the untried productions for which expansions are available for the current parser state.

untried_match(self)

source code 
Returns: boolean
Whether the first element of the frontier is a token that has not yet been matched.

currently_complete(self)

source code 
Returns: boolean
Whether the parser's current state represents a complete parse.

_parse(self, remaining_text, tree, frontier)

source code 

A stub version of _parse that sets the parsers current state to the given arguments. In RecursiveDescentParser, the _parse method is used to recursively continue parsing a text. SteppingRecursiveDescentParser overrides it to capture these recursive calls. It records the parser's old state in the history (to allow for backtracking), and updates the parser's new state using the given arguments. Finally, it returns [1], which is used by match and expand to detect whether their operations were successful.

Parameters:
  • tree - A partial structure for the text that is currently being parsed. The elements of tree that are specified by frontier have not yet been expanded or matched.
  • remaining_text - The portion of the text that is not yet covered by tree.
  • frontier - A list of the locations within tree of all subtrees that have not yet been expanded, and all leaves that have not yet been matched. This list sorted in left-to-right order of location within the tree.
Returns: list of int
[1]
Overrides: RecursiveDescentParser._parse

parses(self)

source code 
Returns: list of Tree
A list of the parses that have been found by this parser so far.

set_grammar(self, grammar)

source code 

Change the grammar used to parse texts.

Parameters:
  • grammar (CFG) - The new grammar.

Instance Variable Details [hide private]

_history

A list of (rtext, tree, frontier) tripples, containing the previous states of the parser. This history is used to implement the backtrack operation.

_tried_e

A record of all productions that have been tried for a given tree. This record is used by expand to perform the next untried production.

_tried_m

A record of what tokens have been matched for a given tree. This record is used by step to decide whether or not to match a token.

   Home       Trees       Indices       Help   
nltk 0.9.5
Generated by Epydoc 3.0beta1 on Wed Aug 27 15:08:56 2008 http://epydoc.sourceforge.net