nltk_lite.parse.rd.RecursiveDescent

Package nltk_lite :: Package parse :: Module rd :: Class RecursiveDescent

[show private | hide private]

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:

If the frontier is empty, and the text is covered by the tree, then return the tree as a possible parse.
If the frontier is empty, and the text is not covered by the tree, then return no parses.
If the first element of the frontier is a subtree, then use CFG productions to expand it. For each applicable production, add the expanded subtree's children to the frontier, and recursively find all parses that can be generated by the new tree and frontier.
If the first element of the frontier is a token, then match it against the next token from the text. Remove the token from the frontier, and recursively find all parses that can be generated by the new tree and frontier.

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