flc_assignment2.py

# from tabulate import tabulate # library to print the table

# function to generate a table to see the behavior of the algorithm
def generate_table(n): 
    table = [] # create empty list for table
    for i in range(n): # create the rows
        row = ['-'] * n
        for j in range(i + 1):
            row[j] = ' '
        table.append(row)
    return table

# cky algorithm
def cky(G, l): 
    n = len(l) # get the length of the string
    table = generate_table(n) # generate the table accoring to the # of characters

    # fill table with the initial productions
    for position, char in enumerate(l): # gets position & char of the string
        for nonTerminal, production in G.items(): # for each NonTerminal -> production | ex: (A, a)
            if char in production: 
                table[position][position] = nonTerminal # set cell value of the diagonal with the NonTerminal [1, 1], [2, 2]
        #print(tabulate(table, tablefmt="fancy_grid")) 

    # combinations of productions in G 
    binary_productions = {}  # a dictionary with the binary productions and their nonterminals 
    for nonTerminal, productions in G.items():  # iterate over each nonterminal and their list of productions 
        for production in productions:  # iterate over each production of each nonTerminal
            if len(production) == 2:  #  production has 2 symbols (binary production)
                binary_productions.setdefault(production, []).append(nonTerminal)  # add (binaryProduction): [nonterminal] if it doesn't exist yet
    """
    binary_productions = {
    ('A', 'B'): ['S'],
    ('B', 'C'): ['S']
    
    }
    
    """

    for substring_length in range(2, n + 1): # iterate over len(substrings) >= 2 in the string
        for substring_start in range(n - substring_length + 1): # go to the possible starting positions of substrings
            for split_position in range(1, substring_length): # iterate over possible positions to split the substring
                # get the nonterminal chars for the 2 substrings:
                first_substring = table[substring_start][substring_start + split_position - 1]
                second_substring = table[substring_start + split_position][substring_start + substring_length - 1]
                #  if both nonterminals exist and the concatenation of them is a key in the binary_productions dictionary
                if first_substring and second_substring  and first_substring + second_substring  in binary_productions:
                    # replacing the entry in the table with the nonTerminal of the binary production
                    table[substring_start][substring_start + substring_length - 1] = binary_productions[first_substring + second_substring][0]
            # printing the table after each iteration (for visualization)
            #print(tabulate(table, tablefmt="fancy_grid"))
    result = 'S' in table[0][-1] # check if S is in the corner of the table after the process
    return result

def main():
    c = int(input(" | Enter the number of grammars to process: "))  # receive how many grammars we're going to process
    for _ in range(c):  # for each grammar, ask
        l = input(" | Enter the number of rules and the number of strings (example: 5 5):" )  # read the line containing the number of production rules and the number of strings to evaluate, e.g., 5 5
        n = [int(i) for i in l.split()]  # convert the numbers into a list of integers -> "3 5" -> l.split -> ["5", "5"] -> int(i)... -> n= [5, 5]
        G = {}  # initialize the dictionary that will store the grammar
        j = 0  # initialize the integer variable that will store the production rules
        while j < n[0]:  # n[0] >> number of G / for each production rule
            l = input("| Enter production rules (example: C SB): ")  # what's to the right of the variables - read the production rule
            l = l.split()  # split the production rule into a list of symbols | e.g., A BA a | ['A', 'BA', 'a']
            G[l[0]] = []  # add an entry for the non terminal in the dictionary G | e.g., G[A] = []
            for i in range(1, len(l)):  # for each terminal symbol in the production rule | e.g., iterates over BA and a
                G[l[0]].append(l[i])  # add the terminal symbol to the corresponding list in G | first adds BA | G[A] = ['BA'] | then adds a | G[A] = ['BA', 'a']
            j += 1
        i = 0
        while i < n[1]:  # for each string to evaluate | 'abb' | n looks like this = [3, 5] | 5 strings
            l = input("| Enter the string to evaluate: ")  # read the string
            ans = cky(G, l)  # call the cky function to check if the string can be generated by the grammar
            if ans:  # if the string can be generated | if the cky function returns true
                print('yes')
            else:
                print('no')
            i += 1


main()