Set of transformations for grammpy library.
THIS PACKAGE IS DEPRECATED, USE
grammpy LIBRARY INSTEAD.
Package for transforming grammpy grammars.
Currently only small subset of operations are implement.
Subset of methods for each type of grammar will be stored in separate object (currently only ContextFree is supported).
For each method, you can decide to modify or copy the grammar. Default behaviour is to copy grammar before each modification.
You can disable it for every method by passing
transform_grammar=True as parameter.
Only methods allowing to transform grammar into Chomsky normal form.
Removing of useless symbols
Including removing of unreachable symbols and symbols, thats not generate.
from grammpy_transforms import ContextFree new_g = ContextFree.remove_unreachable_symbols(g) new_g = ContextFree.remove_nongenerating_nonterminals(g) new_g = ContextFree.remove_useless_symbols(g) ContextFree.is_grammar_generating(g)
Epsilon rules elimination
Method create new rules that will replace rules with nonterminal rewritable to epsilon rule. You can also only search for nonterminals, that are in rule with epsilon on the right side.
from grammpy import * from grammpy_transforms import ContextFree class OldRules(Rule): rules = [([A], [B, C]), ([B], [EPS])] ContextFree.find_nonterminals_rewritable_to_epsilon(g) # list of nonterminals new_g = ContextFree.remove_rules_with_epsilon(g) class NewRules(Rule): rules = [([A], [B, C]), ([A], [C])] assert new_g.have_rule(NewRules) is True
Library creating own type of rule, so you can backtrack the changes.
The type is
class CreatedRule(Rule): rule = ([A], [C]) created = new_g.get_rule(CreatedRule) assert created.from_rule.rule == ([A], [B, C]) assert created.replace_index == 0 assert issubclass(created, ContextFree.EpsilonRemovedRule)
Removing of unit rules
As with epsilon rules removing, method for removing unit rules create new ones as so as removing invalid ones. You can transform the grammar or just find reachable symbols.
from grammpy import * from grammpy_transforms import ContextFree class OldRules(Rule): rules = [([A], [B]), ([B], [C]), ([B], ), ([C], )] reach = ContextFree.find_nonterminals_reachable_by_unit_rules(g) # instance of ContextFree.UnitSymbolRechablingResults assert reach.reach(A, B) is True assert reach.reachables(A) == [A, B, C] path = reach.path_rules(B, C) # list of unit rules assert path.rule == ([B], [C]) new_g = ContextFree.remove_unit_rules(g) class NewRules(Rule): rules = [([A], ), ([A], ), ([B], ), ([C], )] assert new_g.have_rule(NewRules) is True
Method creates own type of rule (
ContextFree.ReducedUnitRule) and you can backtrack the tranformations.
class Ato1Rule(Rule): rule=([A], ) created = new_g.get_rule(Ato1Rule) assert created.by_rules.rule == ([A], [B]) assert created.by_rules.rule == ([B], [C]) assert created.end_rule.rule == ([C], )
Transformation to Chomsky normal form
Method transfer grammar into Chomsky normal form.
This operations create a lot of own types to allow easy backtracking of transformations.
Base classes are
ContextFree.ChomskyRule, that are base classes for other.
As nonterminals method use
ContextFree.ChomskyTermNonterminal that represent nonterminal rewritable to terminal (A->a). Nonterminal have property
for_term, where it stores terminal (as Terminal class).
Second class is
ContextFree.ChomskyGroupNonterminal, that represent group of symbols (for example in rule A->BCD will this nonterminal represent CD). This nonterminal have property
group, where it stores list of symbols, that represent.
For rules method create list of classes, where each class have different meaning:
ContextFree.ChomskySplitRule: Represent rule, that was split to contain only two symbols. In property
from_ruleis stored original rule.
ContextFree.ChomskyRestRule: Represent right part after splitting of rule. As previous, in
from_ruleproperty is stored original rule. When splitting, ChomskySplitRule and ChomskyRestRule represent original whole rule:
A->BCDE ==> A->BX and X->CDE.
ContextFree.ChomskyTerminalReplaceRule: This class is used in situations, where rule contains nonterminal with terminal. Rule is transformed into state, where terminal is replace with nonterminal rewritable to that terminal. Class have
from_ruleproperty that stores original rule and
replace_indexproperty, that indicate which terminal were replace.
ContextFree.ChomskyTermRule: It is class for rule, that directly rewrite nonterminal to terminal.
Eliminating of epsilon rules, removing of unit rules and transforming into Chomsky normal form have their inverse operations.
They are implemented on
That functions needs just root nonterminal of parsed tree. They then traverse the parse tree and replace rules created by transformations by their original equivalent.
The operations needs to be perform in opposite order, that transformations occurs.
Because Grammar class split rules, which represents more than two rules,
there is need for algorithm, that replace splitted rule with the original one.
This algorithm is implemented on
InverseCommon class as
splitted_rules static method.
This call must be call as the last one. Also, you dont need to call this, if all of your rules have just single rule defined.
Algorithm is for now implemented only for Context-Free grammars.
In the following release of grammpy library, splitted rules should behave same as their original counterparts. This method will than reflect it and may have empty implementation in the future.
Library provide from version 1.2.0 classes, that helps with parsed tree manipulation and traversing.
Manipulation can replace specific rule, nonterminal or terminal with different one.
The new element will be added into parsed tree and correctly connected to rest of the elements.
from grammpy_transforms import Manipulation # ... parsed = cyk(...) Manipulation.replaceNode(parsed, MyNewNonterminal()) Manipulation.replaceRule(parsed.to_rule, MyNewRule()) # or use type deductions Manipulation.replace(parsed, MyNewNonterminal()) Manipulation.replace(parsed.to_rule, MyNewRule())
Second class is
Traversing. It contains static methods for post order and pre order traversing.
Methods traverse throught nonterminals, terminals and even the rules. If you want to traverse just nonterminals, use the
filter buildin function.
from grammpy_transforms import Traversing # ... Traversing.postOrder(parsed) Traversing.preOrder(parsed)
You can create your own traversing path by calling
traverse static method.
Method accept root of the parsed tree and function accepting current traversing node and callback.
Passed method must call callback with every node you want to traverse.
from grammpy_transforms import Traversing # ... def post_order_traversing(elem, callback): if isinstance(elem, Nonterminal): for ch in elem.to_rule.to_symbols: yield callback(ch) yield ch Traversing.traverse(parsed, post_order_traversing)
Alternatively, you can use
traverseSeparated static method, that call different functions for nonterminals, terminals and rules.
def postOrder(root): def travRule(item, callback): resp = [callback(ch) for ch in item.to_symbols] return functools.reduce(operator.add, resp, ) + [item] def travNonterm(item, callback): return callback(item.to_rule) + [item] def travTerm(item, callback): return [item] return Traversing.traverseSeparated(root, travRule, travNonterm, travTerm)
Class Traverse also provide
(R)ChomskySplitTempRule81 |--(N)NoBracketExpression | `--(R)ChomskySplitRule20 | |--(T)<class 'lambda_cli.terminals.LeftBracket'> | `--(N)ChomskyGroupNonterminal20 | `--(R)ChomskySplitTempRule20 | |--(N)NoBracketExpression | | `--(R)ReducedSplitRules6 | | |--(T)<lambda_cli.terminals.Variable object at 0x060818D0> | | `--(N)ExpressionBody | | `--(R)SplitRules7 | | `--(T)<lambda_cli.terminals.Variable object at 0x060817D0> | `--(T)<class 'lambda_cli.terminals.RightBracket'> `--(T)<class 'lambda_cli.terminals.RightBracket'>
Currently only small subset of operations are implemented.
Library should at least support these operations:
- Transform of grammar into valid LL(k) grammar
- Removing of recursion
- Transformations into another representation (like regular grammar to state machine), but this will be probably in separate package.
Author: Patrik Valkovič
Licence: GNU General Public License v3.0
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size & hash||File type||Python version||Upload date|
|grammpy-transforms-1.2.5.tar.gz (16.9 kB) View hashes||Source||None|