CYK created by Tim_LucaL - https://repl.it/@Tim_LucaL/CYK

cyk.py

from tabulate import tabulate

class CYK:
    def __init__(self, grammar, startstate):
        self.grammar = grammar
        self.startstate = startstate

    def __getValidCombinations(self, left_collection_set, right_collection_set):
        valid_combinations = []
        for num_collection, left_collection in enumerate(left_collection_set):
            right_collection = right_collection_set[num_collection]
            for left_item in left_collection:
                for right_item in right_collection:
                    combination = left_item + right_item
                    for key, value in self.grammar.items():
                        if combination in value:
                            if not key in valid_combinations:
                                valid_combinations.append(key)
        return valid_combinations

    def __getCollectionSets(self, full_table, x_position, x_offset):
        table_segment = []
        y_position = 0
        while x_offset >= 2:
            item_set = full_table[y_position][x_position:x_position+x_offset]
            if x_offset > len(item_set):
                return None
            table_segment.append(item_set)
            x_offset -= 1
            y_position += 1
    
        vertical_combinations = []
        horizontal_combinations = []
        for item in table_segment:
            vertical_combinations.append(item[0])
            horizontal_combinations.append(item[-1])
        return vertical_combinations[::-1], horizontal_combinations
        
    def __generateTable(self, word):
        table = [[]]
        for letter in word:
            valid_states = []
            for key, value in self.grammar.items():
                if letter in value:
                    valid_states.append(key)
            table[0].append(valid_states)
        
        for x_offset in range(2,len(word)+1):
            table.append([])
            for x_position in range(len(word)):
                collection_sets = self.__getCollectionSets(table, x_position, x_offset)
                if collection_sets:
                    table[-1].append(self.__getValidCombinations(*collection_sets))
        
        return table
        
    def checkWord(self, word):
        return self.startstate in self.__generateTable(word)[-1][-1]
        
    def outputTable(self, word):
        table = self.__generateTable(word)
        pretty_table = [
            [
                ",".join(sorted(y)) if y != [] else u"\u2205" for y in x
            ] for x in table
        ]
        
        print(tabulate(pretty_table, list(word), tablefmt="grid"))

main.py

from cyk import CYK

startstate = "S"

grammar_school = {
    startstate:["VaE","VbF"],
    "G":["GG","a","b","VaVb"],
    "E":["GVa","a"],
    "F":["GVb","b"],
    "Va":["a"],
    "Vb":["b"]
}

grammar_yt_vid = {
    startstate:["SA","a"],
    "A":["BS"],
    "B":["BB","BS","b","c"]
}

cyk = CYK(grammar_yt_vid, startstate)

while True:
    word = input("Which word do you want to test?\n")
    print("The word is {}part of the grammar.".format(
        ["not " if not cyk.checkWord(word) else ""][0]
    ))
    if input("Do you want to see the table to your word?\n") in ["y","yes"]:
        cyk.outputTable(word)

requirements.txt

tabulate==0.8.2