nltk.grammar.CFG

class documentation

class CFG(object): (source)

Known subclasses: nltk.grammar.FeatureGrammar, nltk.grammar.PCFG

Constructor: CFG(start, productions, calculate_leftcorners)

A context-free grammar. A grammar consists of a start state and a set of productions. The set of terminals and nonterminals is implicitly specified by the productions.

If you need efficient key-based access to productions, you can use a subclass to implement it.

Class Method	`binarize`	Convert all non-binary rules into binary by introducing new tokens. Example:: Original:
Class Method	`eliminate_start`	Eliminate start rule in case it appears on RHS Example: S -> S0 S1 and S0 -> S1 S Then another rule S0_Sigma -> S is added
Class Method	`fromstring`	Return the grammar instance corresponding to the input string(s).
Class Method	`remove_unitary_rules`	Remove nonlexical unitary rules and convert them to lexical
Method	`__init__`	Create a new context-free grammar, from the given start state and set of ``Production``s.
Method	`__repr__`	Undocumented
Method	`__str__`	Undocumented
Method	`check_coverage`	Check whether the grammar rules cover the given list of tokens. If not, then raise an exception.
Method	`chomsky_normal_form`	Returns a new Grammer that is in chomsky normal :param: new_token_padding
Method	`is_binarised`	Return True if all productions are at most binary. Note that there can still be empty and unary productions.
Method	`is_chomsky_normal_form`	Return True if the grammar is of Chomsky Normal Form, i.e. all productions are of the form A -> B C, or A -> "s".
Method	`is_flexible_chomsky_normal_form`	Return True if all productions are of the forms A -> B C, A -> B, or A -> "s".
Method	`is_leftcorner`	True if left is a leftcorner of cat, where left can be a terminal or a nonterminal.
Method	`is_lexical`	Return True if all productions are lexicalised.
Method	`is_nonempty`	Return True if there are no empty productions.
Method	`is_nonlexical`	Return True if all lexical rules are "preterminals", that is, unary rules which can be separated in a preprocessing step.
Method	`leftcorner_parents`	Return the set of all nonterminals for which the given category is a left corner. This is the inverse of the leftcorner relation.
Method	`leftcorners`	Return the set of all nonterminals that the given nonterminal can start with, including itself.
Method	`max_len`	Return the right-hand side length of the longest grammar production.
Method	`min_len`	Return the right-hand side length of the shortest grammar production.
Method	`productions`	Return the grammar productions, filtered by the left-hand side or the first item in the right-hand side.
Method	`start`	Return the start symbol of the grammar
Method	`_calculate_grammar_forms`	Pre-calculate of which form(s) the grammar is.
Method	`_calculate_indexes`	Undocumented
Method	`_calculate_leftcorners`	Undocumented
Instance Variable	`_all_unary_are_lexical`	Undocumented
Instance Variable	`_categories`	Undocumented
Instance Variable	`_empty_index`	Undocumented
Instance Variable	`_immediate_leftcorner_categories`	Undocumented
Instance Variable	`_immediate_leftcorner_words`	Undocumented
Instance Variable	`_is_lexical`	Undocumented
Instance Variable	`_is_nonlexical`	Undocumented
Instance Variable	`_leftcorner_parents`	Undocumented
Instance Variable	`_leftcorner_words`	Undocumented
Instance Variable	`_leftcorners`	Undocumented
Instance Variable	`_lexical_index`	Undocumented
Instance Variable	`_lhs_index`	Undocumented
Instance Variable	`_max_len`	Undocumented
Instance Variable	`_min_len`	Undocumented
Instance Variable	`_productions`	Undocumented
Instance Variable	`_rhs_index`	Undocumented
Instance Variable	`_start`	Undocumented

@classmethod
def binarize(cls, grammar, padding='@$@'): (source) ¶

Convert all non-binary rules into binary by introducing new tokens. Example:: Original:

A => B C D

After Conversion:: A => B A@$@B A@$@B => C D

@classmethod
def eliminate_start(cls, grammar): (source) ¶

Eliminate start rule in case it appears on RHS Example: S -> S0 S1 and S0 -> S1 S Then another rule S0_Sigma -> S is added

@classmethod
def fromstring(cls, input, encoding=None): (source) ¶

overridden in nltk.grammar.FeatureGrammar, nltk.grammar.PCFG

Return the grammar instance corresponding to the input string(s).

Parameters
input	a grammar, either in the form of a string or as a list of strings.
encoding	Undocumented

@classmethod
def remove_unitary_rules(cls, grammar): (source) ¶

Remove nonlexical unitary rules and convert them to lexical

def __init__(self, start, productions, calculate_leftcorners=True): (source) ¶

overridden in nltk.grammar.FeatureGrammar, nltk.grammar.PCFG

Create a new context-free grammar, from the given start state and set of ``Production``s.

Parameters
start:Nonterminal	The start symbol
productions:list(Production)	The list of productions that defines the grammar
calculate_leftcorners:bool	False if we don't want to calculate the leftcorner relation. In that case, some optimized chart parsers won't work.

def __repr__(self): (source) ¶

Undocumented

def __str__(self): (source) ¶

Undocumented

def check_coverage(self, tokens): (source) ¶

Check whether the grammar rules cover the given list of tokens. If not, then raise an exception.

Parameters
tokens:list(str)	Undocumented

def chomsky_normal_form(self, new_token_padding='@$@', flexible=False): (source) ¶

Returns a new Grammer that is in chomsky normal :param: new_token_padding

Customise new rule formation during binarisation

def is_binarised(self): (source) ¶

Return True if all productions are at most binary. Note that there can still be empty and unary productions.

def is_chomsky_normal_form(self): (source) ¶

Return True if the grammar is of Chomsky Normal Form, i.e. all productions are of the form A -> B C, or A -> "s".

def is_flexible_chomsky_normal_form(self): (source) ¶

Return True if all productions are of the forms A -> B C, A -> B, or A -> "s".

def is_leftcorner(self, cat, left): (source) ¶

True if left is a leftcorner of cat, where left can be a terminal or a nonterminal.

Parameters
cat:Nonterminal	the parent of the leftcorner
left:Terminal or Nonterminal	the suggested leftcorner
Returns
bool	Undocumented

def is_lexical(self): (source) ¶

Return True if all productions are lexicalised.

def is_nonempty(self): (source) ¶

Return True if there are no empty productions.

def is_nonlexical(self): (source) ¶

Return True if all lexical rules are "preterminals", that is, unary rules which can be separated in a preprocessing step.

This means that all productions are of the forms A -> B1 ... Bn (n>=0), or A -> "s".

Note: is_lexical() and is_nonlexical() are not opposites. There are grammars which are neither, and grammars which are both.

def leftcorner_parents(self, cat): (source) ¶

overridden in nltk.grammar.FeatureGrammar

Return the set of all nonterminals for which the given category is a left corner. This is the inverse of the leftcorner relation.

Parameters
cat:Nonterminal	the suggested leftcorner
Returns
set(Nonterminal)	the set of all parents to the leftcorner

def leftcorners(self, cat): (source) ¶

overridden in nltk.grammar.FeatureGrammar

Return the set of all nonterminals that the given nonterminal can start with, including itself.

This is the reflexive, transitive closure of the immediate leftcorner relation: (A > B) iff (A -> B beta)

Parameters
cat:Nonterminal	the parent of the leftcorners
Returns
set(Nonterminal)	the set of all leftcorners

def max_len(self): (source) ¶

Return the right-hand side length of the longest grammar production.

def min_len(self): (source) ¶

Return the right-hand side length of the shortest grammar production.

def productions(self, lhs=None, rhs=None, empty=False): (source) ¶

overridden in nltk.grammar.FeatureGrammar

Return the grammar productions, filtered by the left-hand side or the first item in the right-hand side.

Parameters
lhs	Only return productions with the given left-hand side.
rhs	Only return productions with the given first item in the right-hand side.
empty	Only return productions with an empty right-hand side.
Returns
list(Production)	A list of productions matching the given constraints.