Realization of Earley's algorithm

Task

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

1. Earley's algorithm
2. 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.

Description of the algorithm

You can find it in docs/Formal_Languages__Colloquium_2021.pdf

Testing, coverage

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

Summary

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

namespace early_parser::algo

Summary

/Members	Descriptions
class early_parser::algo::Algo	Realization of Earley algorithm.

class early_parser::algo::Algo

Realization of Earley algorithm.

Summary

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

Members

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 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

namespace early_parser::grammar

Summary

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.

Members

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

class early_parser::grammar::Grammar

Section: Work with Grammar.

Realization of Context-free Grammar

Summary

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 !!!

Members

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 !!!

class early_parser::grammar::Grammar::_Iterator

Standard bidirectional Iterator for Grammar.

Summary

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.

Members

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.

class early_parser::algo::Algo::_State

Metaclass that implements a state inside a certain rule

Summary

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

Members

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