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: Any, left: Any, right: Any)

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

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)

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

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)

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

static is_end_rule() → bool

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: pyformlang.indexed_grammar.rules.Rules, start_variable: Any = 'S')

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]

Get the generating symbols

Returns

generating – The generating symbols from the start state

Return type

set of any

get_reachable_non_terminals() → AbstractSet[Any]

Get the reachable symbols

Returns

reachables – The reachable symbols from the start state

Return type

set of any

intersection(other: Any) → pyformlang.indexed_grammar.indexed_grammar.IndexedGrammar

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

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() → pyformlang.indexed_grammar.indexed_grammar.IndexedGrammar

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)

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

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[pyformlang.indexed_grammar.reduced_rule.ReducedRule], optim: int = 7)

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)

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[pyformlang.indexed_grammar.consumption_rule.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)

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[pyformlang.indexed_grammar.reduced_rule.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