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)[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
- 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
- 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
- static 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
- 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')[source]¶
Describes an indexed grammar.
- Parameters
rules (
Rules
) – The rules of the grammar, in reduced form put into a Rulestart_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) pyformlang.indexed_grammar.indexed_grammar.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
- 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
- remove_useless_rules() pyformlang.indexed_grammar.indexed_grammar.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
- 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
- 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)[source]¶
Store a set of rules and manipulate them
- Parameters
rules (iterable of
ReducedRule
) – A list of all the rulesoptim (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[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
- 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[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