Package nltk_lite :: Package parse :: Module rd :: Class RecursiveDescent
[show private | hide private]
[frames | no frames]

Type RecursiveDescent

object --+        
         |        
    ParseI --+    
             |    
 AbstractParse --+
                 |
                RecursiveDescent

Known Subclasses:
SteppingRecursiveDescent

A simple top-down CFG parser that parses texts by recursively expanding the fringe of a Tree, and matching it against a text.

RecursiveDescent uses a list of tree locations called a frontier to remember which subtrees have not yet been expanded and which leaves have not yet been matched against the text. Each tree location consists of a list of child indices specifying the path from the root of the tree to a subtree or a leaf; see the reference documentation for Tree for more information about tree locations.

When the parser begins parsing a text, it constructs a tree containing only the start symbol, and a frontier containing the location of the tree's root node. It then extends the tree to cover the text, using the following recursive procedure:

See Also: nltk.cfg

Method Summary
  __init__(self, grammar, trace)
Create a new RecursiveDescent, that uses grammar to parse texts.
  get_parse_list(self, tokens)
None trace(self, trace)
Set the level of tracing output that should be generated when parsing a text.
list of Tree _expand(self, remaining_text, tree, frontier, production)
Return a list of all parses that can be generated by expanding the first element of frontier with production.
list of Tree _match(self, rtext, tree, frontier)
Return a list of all parses that can be generated by matching the first element of frontier against the first token in rtext.
list of Tree _parse(self, remaining_text, tree, frontier)
Recursively expand and match each elements of tree specified by frontier, to cover remaining_text.
Tree _production_to_tree(self, production)
Return the Tree that is licensed by production.
  _trace_backtrack(self, tree, frontier, toks)
  _trace_expand(self, tree, frontier, production)
None _trace_fringe(self, tree, treeloc)
Print trace output displaying the fringe of tree.
  _trace_match(self, tree, frontier, tok)
  _trace_start(self, tree, frontier, text)
  _trace_succeed(self, tree, frontier)
None _trace_tree(self, tree, frontier, operation)
Print trace output displaying the parser's current state.
Inherited from AbstractParse: get_parse, grammar, parse
Inherited from ParseI: get_parse_probs
Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __str__

Method Details

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

Create a new RecursiveDescent, that uses grammar to parse texts.
Parameters:
grammar - The grammar used to parse texts.
           (type=Grammar)
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.
           (type=int)
Overrides:
nltk_lite.parse.AbstractParse.__init__

trace(self, trace=2)

Set the level of tracing output that should be generated when parsing a text.
Parameters:
trace - The trace level. A trace level of 0 will generate no tracing output; and higher trace levels will produce more verbose tracing output.
           (type=int)
Returns:
None

_expand(self, remaining_text, tree, frontier, production=None)

Parameters:
remaining_text - The portion of the text that is not yet covered by tree.
           (type=list of Strings)
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.
           (type=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.
           (type=list of tuple of int)
Returns:
A list of all parses that can be generated by expanding the first element of frontier with production. In particular, if the first element of 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; and return all parses that can be generated by matching and expanding the remaining elements of frontier. If the first element of frontier is not a subtree whose node type is equal to production's left hand side, then return an empty list. If production is not specified, then return a list of all parses that can be generated by expanding the first element of frontier with any CFG production.
           (type=list of Tree)

_match(self, rtext, tree, frontier)

Parameters:
rtext - The portion of the text that is not yet covered by tree.
           (type=list of Strings)
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.
           (type=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.
           (type=list of tuple of int)
Returns:
a list of all parses that can be generated by matching the first element of frontier against the first token in rtext. In particular, if the first element of frontier has the same type as the first token in rtext, then substitute the token into tree; and return all parses that can be generated by matching and expanding the remaining elements of frontier. If the first element of frontier does not have the same type as the first token in rtext, then return empty list.
           (type=list of Tree)

_parse(self, remaining_text, tree, frontier)

Recursively expand and match each elements of tree specified by frontier, to cover remaining_text. Return a list of all parses found.
Parameters:
remaining_text - The portion of the text that is not yet covered by tree.
           (type=list of Strings)
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.
           (type=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.
           (type=list of tuple of int)
Returns:
A list of all parses that can be generated by matching and expanding the elements of tree specified by frontier.
           (type=list of Tree)

_production_to_tree(self, production)

Parameters:
production - The CFG production that licenses the tree token that should be returned.
           (type=Production)
Returns:
The Tree that is licensed by production. In particular, given the production:
   C{[M{lhs} -> M{elt[1]} ... M{elt[n]}]}
Return a tree token that has a node lhs.symbol, and n children. For each nonterminal element elt[i] in the production, the tree token has a childless subtree with node value elt[i].symbol; and for each terminal element elt[j], the tree token has a leaf token with type elt[j].
           (type=Tree)

_trace_fringe(self, tree, treeloc=None)

Print trace output displaying the fringe of tree. The fringe of tree consists of all of its leaves and all of its childless subtrees.
Returns:
None

_trace_tree(self, tree, frontier, operation)

Print trace output displaying the parser's current state.
Parameters:
operation - A character identifying the operation that generated the current state.
Returns:
None

Generated by Epydoc 2.1 on Tue Sep 5 09:37:22 2006 http://epydoc.sf.net