def cyk(grammar, parse_sequence):
    # type: (Grammar, Iterable[Any]) -> Nonterminal
    """
    Perform CYK algorithm.
    :param grammar: Grammar to use in Chomsky Normal Form.
    :param parse_sequence: Input sequence to parse.
    :return: Instance of root Nonterminal in parsed tree.
    """
    # check start symbol
    if grammar.start is None:
        raise StartSymbolNotSetException()
    # create variables
    parse_sequence = list(parse_sequence)
    input_length = len(parse_sequence)
    index = input_length - 1
    f = Field(input_length)
    # creating mapping for speedup rules searching
    (termmap, rulemap) = _create_mapping(grammar)
    # fill first line with rules directly rewritable to terminal
    f.fill(termmap, parse_sequence)
    # fill rest of fields
    for y in range(1, input_length):
        for x in range(input_length - y):
            positions = f.positions(x, y)
            pairs_of_rules = [(f.rules(pos[0].x, pos[0].y),
                      f.rules(pos[1].x, pos[1].y))
                     for pos in positions]
            rules = set()
            for pair_of_rule in pairs_of_rules:
                for (first_rule, second_rule) in _all_combinations(pair_of_rule):
                    h = hash((first_rule.fromSymbol, second_rule.fromSymbol))
                    if h in rulemap:
                        for r in rulemap[h]: # list of rules
                            rules.add(PlaceItem(r, first_rule, second_rule))
            f.put(x, y, list(rules))
    # Check if is start symol on the bottom of field
    if grammar.start not in [r.fromSymbol for r in f.rules(0, input_length - 1)]:
        raise NotParsedException()
    # Find init symbol and rule
    start = grammar.start()  # type: Nonterminal
    start_rule = [r for r in f.rules(0, input_length - 1) if grammar.start == r.fromSymbol][0]
    # Prepare buffer for proccess
    to_process = list()
    to_process.append({'n': start, 'r': start_rule})
    # Prepare tree
    while len(to_process) > 0:
        working = to_process.pop()
        rule_class = working['r']
        working_nonterm = working['n']  # type: Nonterminal
        # its middle rule - not rewritable to nonterminal
        if isinstance(rule_class, PlaceItem):
            created_rule = rule_class.rule()  # type: Rule
            working_nonterm._set_to_rule(created_rule)
            created_rule._from_symbols.append(working_nonterm)
            for side in rule_class.to_rule:
                symbol = side.fromSymbol()  # type: Nonterminal
                symbol._set_from_rule(created_rule)
                created_rule._to_symbols.append(symbol)
                to_process.append({'n': symbol, 'r': side})
        # it is rule rewritable to nonterminal
        else:
            created_rule = rule_class()  # type: Rule
            working_nonterm._set_to_rule(created_rule)
            created_rule._from_symbols.append(working_nonterm)
            t = Terminal(parse_sequence[index])
            index -= 1
            created_rule._to_symbols.append(t)
            t._set_from_rule(created_rule)
    return start
def cyk ( grammar , parse_sequence ) : if grammar . start is None : raise StartSymbolNotSetException ( ) parse_sequence = list ( parse_sequence ) input_length = len ( parse_sequence ) index = input_length - 1 f = Field ( input_length ) ( termmap , rulemap ) = _create_mapping ( grammar ) f . fill ( termmap , parse_sequence ) for y in range ( 1 , input_length ) : for x in range ( input_length - y ) : positions = f . positions ( x , y ) pairs_of_rules = [ ( f . rules ( pos [ 0 ] . x , pos [ 0 ] . y ) , f . rules ( pos [ 1 ] . x , pos [ 1 ] . y ) ) for pos in positions ] rules = set ( ) for pair_of_rule in pairs_of_rules : for ( first_rule , second_rule ) in _all_combinations ( pair_of_rule ) : h = hash ( ( first_rule . fromSymbol , second_rule . fromSymbol ) ) if h in rulemap : for r in rulemap [ h ] : rules . add ( PlaceItem ( r , first_rule , second_rule ) ) f . put ( x , y , list ( rules ) ) if grammar . start not in [ r . fromSymbol for r in f . rules ( 0 , input_length - 1 ) ] : raise NotParsedException ( ) start = grammar . start ( ) start_rule = [ r for r in f . rules ( 0 , input_length - 1 ) if grammar . start == r . fromSymbol ] [ 0 ] to_process = list ( ) to_process . append ( { 'n' : start , 'r' : start_rule } ) while len ( to_process ) > 0 : working = to_process . pop ( ) rule_class = working [ 'r' ] working_nonterm = working [ 'n' ] if isinstance ( rule_class , PlaceItem ) : created_rule = rule_class . rule ( ) working_nonterm . _set_to_rule ( created_rule ) created_rule . _from_symbols . append ( working_nonterm ) for side in rule_class . to_rule : symbol = side . fromSymbol ( ) symbol . _set_from_rule ( created_rule ) created_rule . _to_symbols . append ( symbol ) to_process . append ( { 'n' : symbol , 'r' : side } ) else : created_rule = rule_class ( ) working_nonterm . _set_to_rule ( created_rule ) created_rule . _from_symbols . append ( working_nonterm ) t = Terminal ( parse_sequence [ index ] ) index -= 1 created_rule . _to_symbols . append ( t ) t . _set_from_rule ( created_rule ) return start
Perform CYK algorithm.
    :param grammar: Grammar to use in Chomsky Normal Form.
    :param parse_sequence: Input sequence to parse.
    :return: Instance of root Nonterminal in parsed tree.