nltk.grammar module¶

Basic data classes for representing context free grammars. A “grammar” specifies which trees can represent the structure of a given text. Each of these trees is called a “parse tree” for the text (or simply a “parse”). In a “context free” grammar, the set of parse trees for any piece of a text can depend only on that piece, and not on the rest of the text (i.e., the piece’s context). Context free grammars are often used to find possible syntactic structures for sentences. In this context, the leaves of a parse tree are word tokens; and the node values are phrasal categories, such as NP and VP.

The CFG class is used to encode context free grammars. Each CFG consists of a start symbol and a set of productions. The “start symbol” specifies the root node value for parse trees. For example, the start symbol for syntactic parsing is usually S. Start symbols are encoded using the Nonterminal class, which is discussed below.

A Grammar’s “productions” specify what parent-child relationships a parse tree can contain. Each production specifies that a particular node can be the parent of a particular set of children. For example, the production <S> -> <NP> <VP> specifies that an S node can be the parent of an NP node and a VP node.

Grammar productions are implemented by the Production class. Each Production consists of a left hand side and a right hand side. The “left hand side” is a Nonterminal that specifies the node type for a potential parent; and the “right hand side” is a list that specifies allowable children for that parent. This lists consists of Nonterminals and text types: each Nonterminal indicates that the corresponding child may be a TreeToken with the specified node type; and each text type indicates that the corresponding child may be a Token with the with that type.

The Nonterminal class is used to distinguish node values from leaf values. This prevents the grammar from accidentally using a leaf value (such as the English word “A”) as the node of a subtree. Within a CFG, all node values are wrapped in the Nonterminal class. Note, however, that the trees that are specified by the grammar do not include these Nonterminal wrappers.

Grammars can also be given a more procedural interpretation. According to this interpretation, a Grammar specifies any tree structure tree that can be produced by the following procedure:

Set tree to the start symbol

Repeat until tree contains no more nonterminal leaves:

Choose a production prod with whose left hand side

lhs is a nonterminal leaf of tree.

Replace the nonterminal leaf with a subtree, whose node

value is the value wrapped by the nonterminal lhs, and

whose children are the right hand side of prod.

The operation of replacing the left hand side (lhs) of a production with the right hand side (rhs) in a tree (tree) is known as “expanding” lhs to rhs in tree.

class nltk.grammar.CFG[source]¶

Bases: object

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.

__init__(start, productions, calculate_leftcorners=True)[source]¶

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

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.

classmethod binarize(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

check_coverage(tokens)[source]¶

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

chomsky_normal_form(new_token_padding='@$@', flexible=False)[source]¶

Returns a new Grammar that is in chomsky normal

Param: new_token_padding Customise new rule formation during binarisation

classmethod eliminate_start(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 fromstring(input, encoding=None)[source]¶

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.

is_binarised()[source]¶: Return True if all productions are at most binary. Note that there can still be empty and unary productions.

is_chomsky_normal_form()[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”.

is_flexible_chomsky_normal_form()[source]¶: Return True if all productions are of the forms A -> B C, A -> B, or A -> “s”.

is_leftcorner(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

Return type

bool

is_lexical()[source]¶: Return True if all productions are lexicalised.

is_nonempty()[source]¶: Return True if there are no empty productions.

is_nonlexical()[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.

leftcorner_parents(cat)[source]¶

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: the set of all parents to the leftcorner
Return type: set(Nonterminal)

leftcorners(cat)[source]¶

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: the set of all leftcorners
Return type: set(Nonterminal)

max_len()[source]¶: Return the right-hand side length of the longest grammar production.

min_len()[source]¶: Return the right-hand side length of the shortest grammar production.

productions(lhs=None, rhs=None, empty=False)[source]¶

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

A list of productions matching the given constraints.

Return type

list(Production)

classmethod remove_unitary_rules(grammar)[source]¶: Remove nonlexical unitary rules and convert them to lexical

start()[source]¶

Return the start symbol of the grammar

Return type: Nonterminal

class nltk.grammar.DependencyGrammar[source]¶

Bases: object

A dependency grammar. A DependencyGrammar consists of a set of productions. Each production specifies a head/modifier relationship between a pair of words.

__init__(productions)[source]¶

Create a new dependency grammar, from the set of Productions.

Parameters: productions (list(Production)) – The list of productions that defines the grammar

contains(head, mod)[source]¶

Parameters

head (str) – A head word.
mod (str) – A mod word, to test as a modifier of ‘head’.

Returns

true if this DependencyGrammar contains a DependencyProduction mapping ‘head’ to ‘mod’.

Return type

bool

classmethod fromstring(input)[source]¶

class nltk.grammar.DependencyProduction[source]¶

Bases: Production

A dependency grammar production. Each production maps a single head word to an unordered list of one or more modifier words.

class nltk.grammar.Nonterminal[source]¶

Bases: object

A non-terminal symbol for a context free grammar. Nonterminal is a wrapper class for node values; it is used by Production objects to distinguish node values from leaf values. The node value that is wrapped by a Nonterminal is known as its “symbol”. Symbols are typically strings representing phrasal categories (such as "NP" or "VP"). However, more complex symbol types are sometimes used (e.g., for lexicalized grammars). Since symbols are node values, they must be immutable and hashable. Two Nonterminals are considered equal if their symbols are equal.

See: CFG, Production
Variables: _symbol – The node value corresponding to this Nonterminal. This value must be immutable and hashable.

__init__(symbol)[source]¶

Construct a new non-terminal from the given symbol.

Parameters: symbol (any) – The node value corresponding to this Nonterminal. This value must be immutable and hashable.

symbol()[source]¶

Return the node value corresponding to this Nonterminal.

Return type: (any)

class nltk.grammar.PCFG[source]¶

Bases: CFG

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

PCFG productions use the ProbabilisticProduction class. PCFGs impose the constraint that the set of productions with any given left-hand-side must have probabilities that sum to 1 (allowing for a small margin of error).

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

Variables: EPSILON – The acceptable margin of error for checking that productions with a given left-hand side have probabilities that sum to 1.

EPSILON = 0.01¶

__init__(start, productions, calculate_leftcorners=True)[source]¶

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

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.

Raises

ValueError – if the set of productions with any left-hand-side do not have probabilities that sum to a value within EPSILON of 1.

classmethod fromstring(input, encoding=None)[source]¶

Return a probabilistic context-free grammar corresponding to the input string(s).

Parameters: input – a grammar, either in the form of a string or else as a list of strings.

class nltk.grammar.ProbabilisticDependencyGrammar[source]¶

Bases: object

__init__(productions, events, tags)[source]¶

contains(head, mod)[source]¶

Return True if this DependencyGrammar contains a DependencyProduction mapping ‘head’ to ‘mod’.

Parameters

head (str) – A head word.
mod (str) – A mod word, to test as a modifier of ‘head’.

Return type

bool

class nltk.grammar.ProbabilisticProduction[source]¶

Bases: Production, ImmutableProbabilisticMixIn

A probabilistic context free grammar production. A PCFG ProbabilisticProduction is essentially just a Production that has an associated probability, which represents how likely it is that this production will be used. In particular, the probability of a ProbabilisticProduction records the likelihood that its right-hand side is the correct instantiation for any given occurrence of its left-hand side.

See: Production

__init__(lhs, rhs, **prob)[source]¶

Construct a new ProbabilisticProduction.

Parameters

lhs (Nonterminal) – The left-hand side of the new ProbabilisticProduction.
rhs (sequence(Nonterminal and terminal)) – The right-hand side of the new ProbabilisticProduction.
prob – Probability parameters of the new ProbabilisticProduction.

class nltk.grammar.Production[source]¶

Bases: object

A grammar production. Each production maps a single symbol on the “left-hand side” to a sequence of symbols on the “right-hand side”. (In the case of context-free productions, the left-hand side must be a Nonterminal, and the right-hand side is a sequence of terminals and Nonterminals.) “terminals” can be any immutable hashable object that is not a Nonterminal. Typically, terminals are strings representing words, such as "dog" or "under".

See

CFG

See

DependencyGrammar

See

Nonterminal

Variables

_lhs – The left-hand side of the production.
_rhs – The right-hand side of the production.

__init__(lhs, rhs)[source]¶

Construct a new Production.

Parameters

lhs (Nonterminal) – The left-hand side of the new Production.
rhs (sequence(Nonterminal and terminal)) – The right-hand side of the new Production.

is_lexical()[source]¶

Return True if the right-hand contain at least one terminal token.

Return type: bool

is_nonlexical()[source]¶

Return True if the right-hand side only contains Nonterminals

Return type: bool

lhs()[source]¶

Return the left-hand side of this Production.

Return type: Nonterminal

rhs()[source]¶

Return the right-hand side of this Production.

Return type: sequence(Nonterminal and terminal)

nltk.grammar.induce_pcfg(start, productions)[source]¶

Induce a PCFG grammar from a list of productions.

The probability of a production A -> B C in a PCFG is:

count(A -> B C)

P(B, C | A) = ————— where * is any right hand side

count(A -> *)

Parameters

start (Nonterminal) – The start symbol
productions (list(Production)) – The list of productions that defines the grammar

nltk.grammar.nonterminals(symbols)[source]¶

Given a string containing a list of symbol names, return a list of Nonterminals constructed from those symbols.

Parameters: symbols (str) – The symbol name string. This string can be delimited by either spaces or commas.
Returns: A list of Nonterminals constructed from the symbol names given in symbols. The Nonterminals are sorted in the same order as the symbols names.
Return type: list(Nonterminal)

nltk.grammar.read_grammar(input, nonterm_parser, probabilistic=False, encoding=None)[source]¶

Return a pair consisting of a starting category and a list of Productions.

Parameters

input – a grammar, either in the form of a string or else as a list of strings.
nonterm_parser – a function for parsing nonterminals. It should take a (string, position) as argument and return a (nonterminal, position) as result.
probabilistic (bool) – are the grammar rules probabilistic?
encoding (str) – the encoding of the grammar, if it is a binary string

NLTK

Documentation

nltk.grammar module¶