"""
Context Free Grammar Module
===========================
A module containing CFG class, and helper classes for table filling.
    - ProductionRule Class,
    - TableCell Class,
    - CellEntry Class
"""
class CFG:
    """
    Context Free Grammar (CFG) Class
    --------------------------------
    Attributes:
        * vars  (list) : The set of variables in the CFG
        * ters  (list) : The set of terminals generated by the CFG
        * start (str)  : The starting variable for the CFG
        * rules (list) : A list of ProductionRule objects for the CFG
    """
    def __init__(self, vas, tes, start, rules):
        self.vars = vas
        self.ters = tes
        self.start = start
        self.rules = [ProductionRule(rule[0], rule[1]) for rule in rules]

    def genCombinationProducers(self, cellA, cellB):
        """
        The core part of each Cell filling step in the CYK algorithm.
        Get all the possible combinations of entries in cellA and cellB, and
        see which are producable in this grammar.
        If some variable in the grammar produces that combination, create a new
        CellEntry defined by that variable, and give it back pointers
        to those entries A and B it can produce (saving a parse tree)
        """
        entries = list()
        for entryA in cellA.entries:
            for entryB in cellB.entries:
                for producer in self.findProducers(entryA.producerVar, entryB.producerVar):
                    entries.append(CellEntry(producer, entryA, entryB))
        return entries


    def findProducers(self, productA, productB=None):
        """
        A method for finding the Variables that produce the input product(s)
        If only productA is passed, looking for a terminal production rule.
        If both products are passed, looking for a variable production rule.
        """
        producers = list()
        for rule in self.rules:
            if rule.produces(productA, productB):
                producers.append(rule.var)
        return producers


    def generateTable(self, in_string):
        """
        ITERATIVE implementation of the CYK algorithm, using table-filling.
        Generate a table for this CFG on the given input string.
        """
        l = len(in_string)
        # 2d Array repres. a CYK table. Each TableCell will contain a list of entries.
        table = [[TableCell() for i in range(l - j)] for j in range(l)]

        # Fill cells of the first row with variables that can produce the corresp terminal.
        for i in range(l):
            prod = self.findProducers(in_string[i])
            table[0][i].entries.extend([CellEntry(var, None, None, in_string[i]) for var in prod])

        # Fill all remaining cells. Work across the columns on a row, then move to next row.
        # For each cell, try each substring combination that corresponds to that cell.
        for row_ind in range(1, l):
            for col_ind in range(l - row_ind):
                targetCell = table[row_ind][col_ind]
                for perm in range(row_ind):
                    cellA = table[perm][col_ind]
                    cellB = table[row_ind-perm-1][col_ind+perm+1]
                    targetCell.entries.extend(self.genCombinationProducers(cellA, cellB))
        return table


    def checkMembership(self, table):
        """
        Check if this grammar's start state is in the top cell of the table.
        """
        return True if (self.topCell(table).contains(self.start)) else False


    def printRightmostDerivation(self, table):
        """
        Given a table, attempts to print a rightmost derivation for the string
        it describes.
        Iterative method, using stacks.
        """
        e_stack = list()
        t_stack = list()
        # Choose an entry in the topCell that starts on the start variable.
        # May be multiple if the grammar is ambiguous on this string, choose any
        for entry in self.topCell(table).entries:
            if (entry == self.start):
                e_stack.append(entry)
                break
        line = ""
        # Iterate until there are no variables left to generate from.
        while (len(e_stack) > 0):
            # Add the str representation of the current step in the generation
            line += "".join([repr(e) for e in e_stack])
            line += "".join(t_stack) + "\n"
            # Get the rightmost remaining variable to generate next.
            rightmost = e_stack.pop(-1)
            if (rightmost.backTerminal == None):
                e_stack.append(rightmost.backEntryA)
                e_stack.append(rightmost.backEntryB)
            else:
                t_stack.insert(0, rightmost.backTerminal)
        line += "".join((t_stack))
        print(line) if line else print("No derivation")


    def checkAmbiguity(self, table):
        """
        Simple method to check for ambiguity. If there are multiple
        valid parse trees, then there will be multiple entries in the
        table's top cell containing the Start variable.
        """
        derivations = self.topCell(table).entries.count(self.start)
        return (derivations > 1)


    def topCell(self, table):
        """
        Helpful getter method to retrieve the top cell of a table.
        """
        return table[len(table)-1][0]


class ProductionRule:
    """
    Production Rule Class
    ---------------------
    A simple class that represents a Production Rule that complies with CNF.
    Attributes:
        - var (str) : The LHS of the production rule
        - p1  (str) : First product of the rule. May be a variable, or a terminal.
        - p2  (str) : Second product. A variable IFF p1 is a variable, else None.
    """
    def __init__(self, producerVariable, producedTuple):
        self.var = producerVariable
        self.p1 = producedTuple[0]
        self.p2 = producedTuple[1] if (len(producedTuple) > 1) else None

    def produces(self, product1, product2=None):
        """
        Checks if this rule produces the supplied product(s)
        Can be given a pair of variables, or a single terminal, works for both.
        """
        return True if (self.p1==product1 and self.p2==product2) else False


class TableCell:
    """
    Table Cell Class
    ----------------
    Stores a list of CellEntry objects. Each cell in the 2d table array contains
    a single TableCell.
    Attributes:
        - entries (list) : The CellEntry objects within this cell.
    """
    def __init__(self):
        self.entries = list()

    def contains(self, producerVar):
        """
        Checks if any entries in this cell contain a rule with LHS producerVar.
        """
        return (producerVar in self.entries)


class CellEntry:
    """
    Cell Entry Class
    ----------------
    Stores an entry - a producer variable with back pointers to the entries it produces
    in this derivation.
    Attributes:
        - producerVar  (str)       : The variable that can produce the substring for this cell
        - backEntryA   (cellEntry) : The entry that produces the left substring
        - backEntryB   (cellEntry) : The entry that produces the right substring
        - backTerminal (str)       : For entries on the first row. No backentries, prod a term.
    """
    def __init__(self, producerVar, backEntryA=None, backEntryB=None, backTerminal=None):
        self.producerVar = producerVar
        self.backEntryA = backEntryA
        self.backEntryB = backEntryB
        self.backTerminal = backTerminal

    def __repr__(self):
        """
        A Cell Entry is simplisticly represented by its producerVar value.
        """
        return self.producerVar

    def __eq__(self, checkEq):
        """
        A really shallow equality check - only checks if the producer variable
        is the same as the provided string value.
        """
        return (self.producerVar == checkEq)

