Skip to content

Latest commit

 

History

History
255 lines (158 loc) · 14.1 KB

README.md

File metadata and controls

255 lines (158 loc) · 14.1 KB
Raw

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