Indexed Grammar

`pyformlang.indexed_grammar`

This module deals with indexed grammars.

Available Classes

IndexedGrammar: An indexed grammar
Rules: A representation of a set of indexed grammar rules
EndRule: An end rule, turning a variable into a terminal
ConsumptionRule: A consumption rule, consuming something from the stack
ProductionRule: A production rule, pushing something on the stack
DuplicationRule: A duplication rule, duplicating the stack

class pyformlang.indexed_grammar.ConsumptionRule(f_param: Any, left: Any, right: Any)[source]

Contains a representation of a consumption rule, i.e. a rule of the form:: C[ r sigma] -> B[sigma]

Parameters:

f_paramany: The consumed symbol
leftany: The non terminal on the left (here C)
rightany: The non terminal on the right (here B)

property f_parameter: Any

Gets the symbol which is consumed

Returns:

fany: The symbol being consumed by the rule

is_consumption() → bool[source]

Whether the rule is a consumption rule or not

Returns:

is_consumptionbool: Whether the rule is a consumption rule or not

property left_term: Any

Gets the symbol on the left of the rule

leftany: The left symbol of the rule

property non_terminals: Iterable[Any]

Gets the non-terminals used in the rule

non_terminalsiterable of any: The non_terminals used in the rule

property production

The production

Returns:

right_termsany: The production

property right: Any

Gets the symbole on the right of the rule

rightany: The right symbol

property right_term

The unique right term

Returns:

right_termiterable of any: The unique right term of the rule

property right_terms

The right terms

Returns:

right_termsiterable of any: The right terms of the rule

property terminals: AbstractSet[Any]

Gets the terminals used in the rule

terminalsset of any: The terminals used in the rule

class pyformlang.indexed_grammar.DuplicationRule(left_term, right_term0, right_term1)[source]

Represents a duplication rule, i.e. a rule of the form:: A[sigma] -> B[sigma] C[sigma]

Parameters:

left_termany: The non-terminal on the left of the rule (A here)
right_term0any: The first non-terminal on the right of the rule (B here)
right_term1any: The second non-terminal on the right of the rule (C here)

property f_parameter

The f parameter

Returns:

fany: The f parameter

is_duplication() → bool[source]

Whether the rule is a duplication rule or not

Returns:

is_duplicationbool: Whether the rule is a duplication rule or not

property left_term: Any

Gives the non-terminal on the left of the rule

Returns:

left_termany: The left term of the rule

property non_terminals: Iterable[Any]

Gives the set of non-terminals used in this rule

Returns:

non_terminalsiterable of any: The non terminals used in this rule

property production

The production

Returns:

right_termsany: The production

property right_term

The unique right term

Returns:

right_termiterable of any: The unique right term of the rule

property right_terms: Tuple[Any, Any]

Gives the non-terminals on the right of the rule

Returns:

right_termsiterable of any: The right terms of the rule

property terminals: AbstractSet[Any]

Gets the terminals used in the rule

Returns:

terminalsset of any: The terminals used in this rule

class pyformlang.indexed_grammar.EndRule(left, right)[source]

Represents an end rule, i.e. a rule of the form:: A[sigma] -> a

Parameters:

leftany: The non-terminal on the left, “A” here
rightany: The terminal on the right, “a” here

property f_parameter

The f parameter

Returns:

fany: The f parameter

is_end_rule() → bool[source]

Whether the rule is an end rule or not

Returns:

is_endbool: Whether the rule is an end rule or not

property left_term: Any

Gets the non-terminal on the left of the rule

Returns:

left_termany: The left non-terminal of the rule

property non_terminals: Iterable[Any]

Gets the non-terminals used

Returns:

non_terminalsiterable of any: The non terminals used in this rule

property production

The production

Returns:

right_termsany: The production

property right_term: Any

Gets the terminal on the right of the rule

Returns:

right_termany: The right terminal of the rule

property right_terms

The right terms

Returns:

right_termsiterable of any: The right terms of the rule

property terminals: AbstractSet[Any]

Gets the terminals used

Returns:

terminalsset of any: The terminals used in this rule

class pyformlang.indexed_grammar.IndexedGrammar(rules: Rules, start_variable: Any = 'S')[source]

Describes an indexed grammar.

Parameters:

rulesRules: The rules of the grammar, in reduced form put into a Rule
start_variableAny, optional: The start symbol of the indexed grammar

get_generating_non_terminals() → AbstractSet[Any][source]

Get the generating symbols

Returns:

generatingset of any: The generating symbols from the start state

get_reachable_non_terminals() → AbstractSet[Any][source]

Get the reachable symbols

Returns:

reachablesset of any: The reachable symbols from the start state

intersection(other: Any) → IndexedGrammar[source]

Computes the intersection of the current indexed grammar with the other object

Parameters:

otherany: The object to intersect with

Returns:

i_grammarIndexedGrammar: The indexed grammar which useless rules

Raises:

NotImplementedError: When trying to intersection with something else than a regular expression or a finite automaton

is_empty() → bool[source]

Checks whether the grammar generates a word or not

Returns:

is_emptybool: Whether the grammar is empty or not

remove_useless_rules() → IndexedGrammar[source]

Remove useless rules in the grammar

More precisely, we remove rules which do not contain only generating or reachable non terminals.

Returns:

i_grammarIndexedGrammar: The indexed grammar which useless rules

property terminals: Iterable[Any]

Get all the terminals in the grammar

Returns:

terminalsiterable of any: The terminals used in the rules

class pyformlang.indexed_grammar.ProductionRule(left, right, prod)[source]

Represents a production rule, i.e. a rule of the form:: A[sigma] -> B[r sigma]

Parameters:

leftany: The non-terminal on the left side of the rule, A here
rightany: The non-terminal on the right side of the rule, B here
prodany: The terminal used in the rule, “r” here

property f_parameter

The f parameter

Returns:

fany: The f parameter

is_production() → bool[source]

Whether the rule is a production rule or not

Returns:

is_productionbool: Whether the rule is a production rule or not

property left_term: Any

Gets the non-terminal on the left side of the rule

Returns:

left_termany: The left term of this rule

property non_terminals: Iterable[Any]

Gets the non-terminals used in the rule

Returns:

non_terminalsany: The non terminals used in this rules

property production: Any

Gets the terminal used in the production

Returns:

productionany: The production used in this rule

property right_term: Any

Gets the non-terminal on the right side of the rule

Returns:

right_termany: The right term used in this rule

property right_terms

The right terms

Returns:

right_termsiterable of any: The right terms of the rule

property terminals: AbstractSet[Any]

Gets the terminals used in the rule

Returns:

terminalsany: The terminals used in this rule

class pyformlang.indexed_grammar.Rules(rules: Iterable[ReducedRule], optim: int = 7)[source]

Store a set of rules and manipulate them

Parameters:

rulesiterable of ReducedRule: A list of all the rules
optimint: Optimization of the order of the rules 0 -> given order 1 -> reverse order 2 -> order by core number 3 -> reverse order of core number 4 -> reverse order by arborescence 5 -> order by arborescence 6 -> order by number of edges 7 -> reverse order by number of edges 8 -> random order

add_production(left: Any, right: Any, prod: Any)[source]

Add the production rule:: left[sigma] -> right[prod sigma]

Parameters:

leftany: The left non-terminal in the rule
rightany: The right non-terminal in the rule
prodany: The production used in the rule

property consumption_rules: Dict[Any, Iterable[ConsumptionRule]]

Gets the consumption rules

Returns:

consumption_rulesdict of any to iterable of ConsumptionRule: A dictionary contains the consumption rules gathered by consumed symbols

property length: (<class 'int'>, <class 'int'>)

Get the total number of rules

Returns:

number_rulescouple of int: A couple with first the number of non consumption rules and then the number of consumption rules

property non_terminals: List[Any]

Gets all the non-terminals used by all the rules

Returns:

non_terminalsiterable of any: The non terminals used in the rule

property optim

Gets the optimization number

Returns:

non_consumption_rulesint: The optimization number

remove_production(left: Any, right: Any, prod: Any)[source]

Remove the production rule:: left[sigma] -> right[prod sigma]

Parameters:

leftany: The left non-terminal in the rule
rightany: The right non-terminal in the rule
prodany: The production used in the rule

property rules: Iterable[ReducedRule]

Gets the non consumption rules

Returns:

non_consumption_rulesiterable of ReducedRule: The non consumption rules

property terminals: Iterable[Any]

Gets all the terminals used by all the rules

Returns:

terminalsiterable of any: The terminals used in the rules

Indexed Grammar

pyformlang.indexed_grammar

Available Classes

`pyformlang.indexed_grammar`