<reponame>azaat/formal_languages_course
from pyformlang.cfg import CFG, Variable, Terminal, Production
from src.grammar import CFGWrapper


# An extension of pyformlang CFG class for CNF grammars
class GrammarCNF(CFGWrapper):
    def __init__(self,
                 start_symbol=None,
                 productions=None):
        cfg = CFG(
            start_symbol=start_symbol,
            productions=productions
        )
        
        cnf = cfg.to_normal_form()
        # needed for language preservation
        if cfg.generate_epsilon():
            cnf._productions.add(Production(cnf._start_symbol, []))
                        
        self.pair_productions = set()
        for p in cnf._productions:
            if len(p.body) == 2:
                self.pair_productions.add(p)

        super(GrammarCNF, self).__init__(
            start_symbol=cnf._start_symbol,
            productions=cnf._productions
        )

    @staticmethod
    def from_text(text):
        cfg = CFGWrapper.from_text(text)
        return GrammarCNF(
            start_symbol=cfg.start_symbol,
            productions=cfg.productions
        )


    @staticmethod   
    def from_txt(path):
        productions = []
        with open(path, 'r') as f:
            for line in f:
                production = line.split()
                productions.append(
                    production[0] + ' -> ' + ' '.join(production[1:])
                )

        return GrammarCNF.from_text('\n'.join(productions))

    def contains_lex(self, word_terminals) -> bool:
        word_len = len(word_terminals)
        # Empty word case
        if (word_len == 0):
            return self.generate_epsilon()

        cyk_table = [
            [set() for _ in range(word_len)]
            for _ in range(word_len)
        ]

        # Filling the CYK table with initial values
        for i in range(word_len):
            for production in self.productions:
                if (
                        len(production.body) == 1 and
                        production.body[0] == word_terminals[i]
                    ):
                    cyk_table[i][0].add(production.head)

        for length in range(1, word_len):  # length of span
            for start in range(word_len - length):  # start of span
                for split in range(length):
                    left = cyk_table[start][split]
                    right = cyk_table[start + split + 1][length - split - 1]
                    for production in self.productions:
                        if (
                            len(production.body) == 2 and
                            production.body[0] in left and
                            production.body[1] in right
                        ):
                            cyk_table[start][length].add(production.head)

        return self.start_symbol in cyk_table[0][word_len - 1]
        

    # Uses CYK implementation to find out if the word is generated by the grammar
    def contains(self, word) -> bool:
        word_terminals = [Terminal(sym) for sym in word]
        return self.contains_lex(word_terminals)
from pyformlang.cfg import CFG, Variable, Terminal, Production
from src.grammar import CFGWrapper


# An extension of pyformlang CFG class for CNF grammars
class GrammarCNF(CFGWrapper):
    def __init__(self,
                 start_symbol=None,
                 productions=None):
        cfg = CFG(
            start_symbol=start_symbol,
            productions=productions
        )
        
        cnf = cfg.to_normal_form()
        # needed for language preservation
        if cfg.generate_epsilon():
            cnf._productions.add(Production(cnf._start_symbol, []))
                        
        self.pair_productions = set()
        for p in cnf._productions:
            if len(p.body) == 2:
                self.pair_productions.add(p)

        super(GrammarCNF, self).__init__(
            start_symbol=cnf._start_symbol,
            productions=cnf._productions
        )

    @staticmethod
    def from_text(text):
        cfg = CFGWrapper.from_text(text)
        return GrammarCNF(
            start_symbol=cfg.start_symbol,
            productions=cfg.productions
        )


    @staticmethod   
    def from_txt(path):
        productions = []
        with open(path, 'r') as f:
            for line in f:
                production = line.split()
                productions.append(
                    production[0] + ' -> ' + ' '.join(production[1:])
                )

        return GrammarCNF.from_text('\n'.join(productions))

    def contains_lex(self, word_terminals) -> bool:
        word_len = len(word_terminals)
        # Empty word case
        if (word_len == 0):
            return self.generate_epsilon()

        cyk_table = [
            [set() for _ in range(word_len)]
            for _ in range(word_len)
        ]

        # Filling the CYK table with initial values
        for i in range(word_len):
            for production in self.productions:
                if (
                        len(production.body) == 1 and
                        production.body[0] == word_terminals[i]
                    ):
                    cyk_table[i][0].add(production.head)

        for length in range(1, word_len):  # length of span
            for start in range(word_len - length):  # start of span
                for split in range(length):
                    left = cyk_table[start][split]
                    right = cyk_table[start + split + 1][length - split - 1]
                    for production in self.productions:
                        if (
                            len(production.body) == 2 and
                            production.body[0] in left and
                            production.body[1] in right
                        ):
                            cyk_table[start][length].add(production.head)

        return self.start_symbol in cyk_table[0][word_len - 1]
        

    # Uses CYK implementation to find out if the word is generated by the grammar
    def contains(self, word) -> bool:
        word_terminals = [Terminal(sym) for sym in word]
        return self.contains_lex(word_terminals)
# An extension of pyformlang CFG class for CNF grammars # needed for language preservation # Empty word case # Filling the CYK table with initial values # length of span # start of span # Uses CYK implementation to find out if the word is generated by the grammar