Package nltk :: Package parse :: Module rd :: Class RecursiveDescentParser

Class RecursiveDescentParser

 object --+    
          |    
api.ParserI --+
              |
             RecursiveDescentParser

Known Subclasses:

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

RecursiveDescentParser 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

Instance Methods

[hide private]

__init__(self, grammar, trace=0)
Create a new RecursiveDescentParser, that uses grammar to parse texts. source code

grammar(self)
Returns: The grammar used by this parser.

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

list of Tree

_parse(self, remaining_text, tree, frontier)
Recursively expand and match each elements of tree specified by frontier, to cover remaining_text. source code

list of Tree

_match(self, rtext, tree, frontier)
Returns: a list of all parses that can be generated by matching the first element of frontier against the first token in rtext. source code

list of Tree

_expand(self, remaining_text, tree, frontier, production=None)
Returns: A list of all parses that can be generated by expanding the first element of frontier with production. source code

Tree

_production_to_tree(self, production)
Returns: The Tree that is licensed by production. source code

None

trace(self, trace=2)
Set the level of tracing output that should be generated when parsing a text.

source code

None

_trace_fringe(self, tree, treeloc=None)
Print trace output displaying the fringe of tree. source code

None

_trace_tree(self, tree, frontier, operation)
Print trace output displaying the parser's current state.

source code

_trace_start(self, tree, frontier, text)

source code

_trace_expand(self, tree, frontier, production)

source code

_trace_match(self, tree, frontier, tok)

source code

_trace_succeed(self, tree, frontier)

source code

_trace_backtrack(self, tree, frontier, toks=None)

source code

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

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 (Grammar) - The grammar used to parse texts.
trace (int) - 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: object.__init__

grammar(self)

source code

Returns:: The grammar used by this parser.
Overrides: api.ParserI.grammar: (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: api.ParserI.nbest_parse

(inherited documentation)

_parse(self, remaining_text, tree, frontier)

source code

Recursively expand and match each elements of tree specified by frontier, to cover remaining_text. Return a list of all parses found.

Parameters:

tree (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 (list of Strings) - The portion of the text that is not yet covered by tree.
frontier (list of tuple of int) - 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 Tree

A list of all parses that can be generated by matching and expanding the elements of tree specified by frontier.

_match(self, rtext, tree, frontier)

source code

Parameters:

tree (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.
rtext (list of Strings) - The portion of the text that is not yet covered by tree.
frontier (list of tuple of int) - 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.

Returns: list of Tree

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.

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

source code

Parameters:

tree (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 (list of Strings) - The portion of the text that is not yet covered by tree.
frontier (list of tuple of int) - 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.

Returns: list of Tree

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.

_production_to_tree(self, production)

source code

Parameters:

production (Production) - The CFG production that licenses the tree token that should be returned.

Returns: Tree

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

trace(self, trace=2)

source code

Set the level of tracing output that should be generated when parsing a text.

Parameters:

trace (int) - The trace level. A trace level of 0 will generate no tracing output; and higher trace levels will produce more verbose tracing output.

Returns: None

_trace_fringe(self, tree, treeloc=None)

source code

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)

source code

Print trace output displaying the parser's current state.

Parameters:

operation - A character identifying the operation that generated the current state.

Returns: None

Class RecursiveDescentParser

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

grammar(self)

nbest_parse(self, tokens, n=None)

_parse(self, remaining_text, tree, frontier)

_match(self, rtext, tree, frontier)

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

_production_to_tree(self, production)

trace(self, trace=2)

_trace_fringe(self, tree, treeloc=None)

_trace_tree(self, tree, frontier, operation)

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