docs: 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