Skip to content

Andy-Messer/formal-languages-practice-2

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

Releases

No releases published

Packages

No packages published

Languages