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 (any) – The consumed symbol
left (any) – The non terminal on the left (here C)
right (any) – The non terminal on the right (here B)

property f_parameter: Any¶

Gets the symbol which is consumed

Returns: f – The symbol being consumed by the rule
Return type: any

is_consumption() → bool[source]¶

Whether the rule is a consumption rule or not

Returns: is_consumption – Whether the rule is a consumption rule or not
Return type: bool

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_terms – The production
Return type: any

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_term – The unique right term of the rule
Return type: iterable of any

property right_terms¶

The right terms

Returns: right_terms – The right terms of the rule
Return type: iterable of any

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_term (any) – The non-terminal on the left of the rule (A here)
right_term0 (any) – The first non-terminal on the right of the rule (B here)
right_term1 (any) – The second non-terminal on the right of the rule (C here)

property f_parameter¶

The f parameter

Returns: f – The f parameter
Return type: any

is_duplication() → bool[source]¶

Whether the rule is a duplication rule or not

Returns: is_duplication – Whether the rule is a duplication rule or not
Return type: bool

property left_term: Any¶

Gives the non-terminal on the left of the rule

Returns: left_term – The left term of the rule
Return type: any

property non_terminals: Iterable[Any]¶

Gives the set of non-terminals used in this rule

Returns: non_terminals – The non terminals used in this rule
Return type: iterable of any

property production¶

The production

Returns: right_terms – The production
Return type: any

property right_term¶

The unique right term

Returns: right_term – The unique right term of the rule
Return type: iterable of any

property right_terms: Tuple[Any, Any]¶

Gives the non-terminals on the right of the rule

Returns: right_terms – The right terms of the rule
Return type: iterable of any

property terminals: AbstractSet[Any]¶

Gets the terminals used in the rule

Returns: terminals – The terminals used in this rule
Return type: set of any

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

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

Parameters

left (any) – The non-terminal on the left, “A” here
right (any) – The terminal on the right, “a” here

property f_parameter¶

The f parameter

Returns: f – The f parameter
Return type: any

is_end_rule() → bool[source]¶

Whether the rule is an end rule or not

Returns: is_end – Whether the rule is an end rule or not
Return type: bool

property left_term: Any¶

Gets the non-terminal on the left of the rule

Returns: left_term – The left non-terminal of the rule
Return type: any

property non_terminals: Iterable[Any]¶

Gets the non-terminals used

Returns: non_terminals – The non terminals used in this rule
Return type: iterable of any

property production¶

The production

Returns: right_terms – The production
Return type: any

property right_term: Any¶

Gets the terminal on the right of the rule

Returns: right_term – The right terminal of the rule
Return type: any

property right_terms¶

The right terms

Returns: right_terms – The right terms of the rule
Return type: iterable of any

property terminals: AbstractSet[Any]¶

Gets the terminals used

Returns: terminals – The terminals used in this rule
Return type: set of any

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

Describes an indexed grammar.

Parameters

rules (Rules) – The rules of the grammar, in reduced form put into a Rule
start_variable (Any, optional) – The start symbol of the indexed grammar

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

Get the generating symbols

Returns: generating – The generating symbols from the start state
Return type: set of any

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

Get the reachable symbols

Returns: reachables – The reachable symbols from the start state
Return type: set of any

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

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

>> indexed_grammar and regex

Parameters: other (any) – The object to intersect with
Returns: i_grammar – The indexed grammar which useless rules
Return type: IndexedGrammar
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_empty – Whether the grammar is empty or not
Return type: bool

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_grammar – The indexed grammar which useless rules
Return type: IndexedGrammar

property terminals: Iterable[Any]¶

Get all the terminals in the grammar

Returns: terminals – The terminals used in the rules
Return type: iterable of any

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

left (any) – The non-terminal on the left side of the rule, A here
right (any) – The non-terminal on the right side of the rule, B here
prod (any) – The terminal used in the rule, “r” here

property f_parameter¶

The f parameter

Returns: f – The f parameter
Return type: any

is_production() → bool[source]¶

Whether the rule is a production rule or not

Returns: is_production – Whether the rule is a production rule or not
Return type: bool

property left_term: Any¶

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

Returns: left_term – The left term of this rule
Return type: any

property non_terminals: Iterable[Any]¶

Gets the non-terminals used in the rule

Returns: non_terminals – The non terminals used in this rules
Return type: any

property production: Any¶

Gets the terminal used in the production

Returns: production – The production used in this rule
Return type: any

property right_term: Any¶

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

Returns: right_term – The right term used in this rule
Return type: any

property right_terms¶

The right terms

Returns: right_terms – The right terms of the rule
Return type: iterable of any

property terminals: AbstractSet[Any]¶

Gets the terminals used in the rule

Returns: terminals – The terminals used in this rule
Return type: any

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

Store a set of rules and manipulate them

Parameters

rules (iterable of ReducedRule) – A list of all the rules
optim (int) – 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

left (any) – The left non-terminal in the rule
right (any) – The right non-terminal in the rule
prod (any) – The production used in the rule

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

Gets the consumption rules

Returns: consumption_rules – A dictionary contains the consumption rules gathered by consumed symbols
Return type: dict of any to iterable of ConsumptionRule

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

Get the total number of rules

Returns: number_rules – A couple with first the number of non consumption rules and then the number of consumption rules
Return type: couple of int

property non_terminals: List[Any]¶

Gets all the non-terminals used by all the rules

Returns: non_terminals – The non terminals used in the rule
Return type: iterable of any

property optim¶

Gets the optimization number

Returns: non_consumption_rules – The optimization number
Return type: int

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

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

Parameters

left (any) – The left non-terminal in the rule
right (any) – The right non-terminal in the rule
prod (any) – The production used in the rule

property rules: Iterable[ReducedRule]¶

Gets the non consumption rules

Returns: non_consumption_rules – The non consumption rules
Return type: iterable of ReducedRule

property terminals: Iterable[Any]¶

Gets all the terminals used by all the rules

Returns: terminals – The terminals used in the rules
Return type: iterable of any

Indexed Grammar¶

pyformlang.indexed_grammar¶

Available Classes¶

`pyformlang.indexed_grammar`¶