It is necessary to implement the algorithm in the form of an Algo class, which has the following methods:
fit(G: Grammar) ! Algo - preprocessing
predict(word: String) ! Boolean - checking whether a word belongs to the language.
Additionally, it is necessary to implement testing of the built preprocessing. Algorithms for implementation
- Earley's algorithm
- LR(1)-algorithm Since there is no preprocessing in Earley's algorithm, it is necessary to implement the functions:
• Scan(conf: Configuration, letter: char) ! Set• Predict(...)
• Complete(...) - think over the interface in such a way that the result can be read- test.
You can find it in docs/Formal_Languages__Colloquium_2021.pdf
These results are obtained on the basis of branch testing
early_parser/grammar.py have 99% because there are raising exception in _Iterator
If you want to see coverage code, do this commands:
coverage run --branch -m unittest early_parser.test_module
coverage html
Wrote HTML report to htmlcov/index.html
Members | Descriptions |
---|---|
namespace early_parser::algo |
|
namespace early_parser::grammar |
|
class early_parser::grammar::Grammar::_Iterator |
Standard bidirectional Iterator for Grammar. |
class early_parser::algo::Algo::_State |
Metaclass that implements a state inside a certain rule |
/Members | Descriptions |
---|---|
class early_parser::algo::Algo |
Realization of Earley algorithm. |
Realization of Earley algorithm.
Members | Descriptions |
---|---|
public def __init__ (self, Grammar grammar) |
The constructor of Algo |
public bool complete (self,int _id) |
The main complete method |
public bool has_word (self,str word) |
Checks the presence of a word in the grammar |
public bool predict (self,int _id) |
The main predict method |
public def scan (self,int _id,str s) |
The main scan method |
The constructor of Algo
public bool
complete
(self,int _id)
The main complete method
public bool
has_word
(self,str word)
Checks the presence of a word in the grammar param word given word return True if there is return False if there isn't
public bool
predict
(self,int _id)
The main predict method
public def
scan
(self,int _id,str s)
The main scan method
Members | Descriptions |
---|---|
public bool is_non_terminal (str c) |
Checks the symbol for non-terminal param c symbol return: True is non-terminal return: False is terminal. |
public bool is_symbol (str c) |
Checks belonging of the symbol to the alphabet param c symbol return: True is in alphabet return: False not in the alphabet. |
public bool is_valid_rule (str rule) |
Checks validity of rules param rule given rules return True if valid return False if not valid. |
public bool is_valid_single_rule (str rule) |
Checks validity of a separate rule param rule given rule return True if valid return False if not valid. |
public list parse_rules (str rule) |
Section: Work with rules. |
class early_parser::grammar::Grammar |
Section: Work with Grammar. |
public bool
is_non_terminal
(str c)
Checks the symbol for non-terminal param c symbol return: True is non-terminal return: False is terminal.
public bool
is_symbol
(str c)
Checks belonging of the symbol to the alphabet param c symbol return: True is in alphabet return: False not in the alphabet.
public bool
is_valid_rule
(str rule)
Checks validity of rules param rule given rules return True if valid return False if not valid.
public bool
is_valid_single_rule
(str rule)
Checks validity of a separate rule param rule given rule return True if valid return False if not valid.
public list
parse_rules
(str rule)
Section: Work with rules.
Splits several rules written in one line into separate ones param rule given rules return rules list of split rules
Section: Work with Grammar.
Realization of Context-free Grammar
Members | Descriptions |
---|---|
public def __init__ (self,str start) |
Constructor. |
public def __iter__ (self) |
Redefining of method 'iter' by class _Iterator |
public int __len__ (self,str c) |
Outputs size of object param c non-term return size of container. |
public def __repr__ (self) |
This method allow to convert grammar to string !!! This method wasn't tested !!! |
public def __str__ (self) |
This method allow to output grammar to stdout !!! This method wasn't tested !!! |
public bool add_rule (self,str rule) |
Add rule to grammar param rule given rule return True correctly added return False wasn't added. |
public def del_similar_rules (self) |
Delete similar rules from grammar For this uses container - set. |
public def erase_rule (self, _Iterator it) |
Deleting rule by iterator param it iterator return iterator to the next element. |
public def get_start (self) |
Get first nonTerminal in grammar. |
public def input_init (self) |
Input the grammar from stdin !!! This method wasn't tested !!! |
public def
__init__
(self,str start)
Constructor.
public def
__iter__
(self)
Redefining of method 'iter' by class _Iterator
public int
__len__
(self,str c)
Outputs size of object param c non-term return size of container.
public def
__repr__
(self)
This method allow to convert grammar to string !!! This method wasn't tested !!!
public def
__str__
(self)
This method allow to output grammar to stdout !!! This method wasn't tested !!!
public bool
add_rule
(self,str rule)
Add rule to grammar param rule given rule return True correctly added return False wasn't added.
public def
del_similar_rules
(self)
Delete similar rules from grammar For this uses container - set.
public def
erase_rule
(self,
_Iterator
it)
Deleting rule by iterator param it iterator return iterator to the next element.
public def
get_start
(self)
Get first nonTerminal in grammar.
public def
input_init
(self)
Input the grammar from stdin !!! This method wasn't tested !!!
Standard bidirectional Iterator for Grammar.
Members | Descriptions |
---|---|
public def __init__ (self, rules ,c) |
Constructor. |
public def __iter__ (self) |
Realization of iteration in grammar. |
public def __next__ (self) |
Redefining of method 'next'. |
public def get_rule (self) |
Get the rule by iterator. |
public def is_valid (self) |
Checks whether the iterator is valid. |
Constructor.
public def
__iter__
(self)
Realization of iteration in grammar.
public def
__next__
(self)
Redefining of method 'next'.
public def
get_rule
(self)
Get the rule by iterator.
public def
is_valid
(self)
Checks whether the iterator is valid.
Metaclass that implements a state inside a certain rule
Members | Descriptions |
---|---|
public def __eq__ (self,other) |
Redefining the method '==' |
public def __hash__ (self) |
Redefining the hash method |
public def __init__ (self,str rule,int rule_pos,int str_pos) |
The constructor of _State |
public def
__eq__
(self,other)
Redefining the method '=='
public def
__hash__
(self)
Redefining the hash method
public def
__init__
(self,str rule,int rule_pos,int str_pos)
The constructor of _State
Generated by Moxygen