nltk.parse.recursivedescent module

class nltk.parse.recursivedescent.RecursiveDescentParser

Bases: ParserI

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

nltk.grammar

__init__(grammar, trace=0)

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

Parameters

• grammar (CFG) – 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.

grammar()

Returns

The grammar used by this parser.

parse(tokens)

Returns

An iterator that generates parse trees for the sentence. When possible this list is sorted from most likely to least likely.

Parameters

sent (list(str)) – The sentence to be parsed

Return type

iter(Tree)

trace(trace=2)

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.

Return type

None

class nltk.parse.recursivedescent.SteppingRecursiveDescentParser

Bases: RecursiveDescentParser

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.

Variables

• _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.

See

nltk.grammar

__init__(grammar, trace=0)

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

Parameters

• grammar (CFG) – 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.

backtrack()

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

true if an operation was successfully undone.

Return type

bool

currently_complete()

Returns

Whether the parser’s current state represents a complete parse.

Return type

bool

expand(production=None)

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

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

Return type

Production or None

expandable_productions()

Returns

A list of all the productions for which expansions are available for the current parser state.

Return type

list(Production)

frontier()

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.

Return type

list(tuple(int))

initialize(tokens)

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

match()

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

The token matched, if a match operation was performed. If no match was performed, return None

Return type

str or None

parse(tokens)

Returns

An iterator that generates parse trees for the sentence. When possible this list is sorted from most likely to least likely.

Parameters

sent (list(str)) – The sentence to be parsed

Return type

iter(Tree)

parses()

Returns

An iterator of the parses that have been found by this parser so far.

Return type

list of Tree

remaining_text()

Returns

The portion of the text that is not yet covered by the tree.

Return type

list(str)

set_grammar(grammar)

Change the grammar used to parse texts.

Parameters

grammar (CFG) – The new grammar.

step()

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 True. Otherwise, return None.

Returns

None if no operation was performed; a token if a match was performed; a production if an expansion was performed; and True if a backtrack operation was performed.

Return type

Production or String or bool

tree()

Returns

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

Return type

Tree

untried_expandable_productions()

Returns

A list of all the untried productions for which expansions are available for the current parser state.

Return type

list(Production)

untried_match()

Returns

Whether the first element of the frontier is a token that has not yet been matched.

Return type

bool

nltk.parse.recursivedescent.demo()

A demonstration of the recursive descent parser.