def parse(input_ids,
          rules,
          nonterminals,
          start_idx,
          populate_fn,
          postprocess_fn,
          verbose=False):
  """Run bottom up parser using Trie-based implementation."""
  input_len = len(input_ids)
  input_symbols = tuple(
      [cfg_rule.CFGSymbol(idx, cfg_rule.TERMINAL) for idx in input_ids])

  # Initialize the empty chart.
  chart = Chart(populate_fn, postprocess_fn)

  # Initialize Trie of rules.
  trie_root = TrieNode()
  for rule in rules:
    add_rule_to_trie(trie_root, rule)

  # Populate the chart.
  for span_end in range(1, input_len + 1):
    for span_begin in range(span_end - 1, -1, -1):

      # Map of span_begin to List of SearchState.
      search_map = collections.defaultdict(list)
      search_map[span_begin].append(SearchState([], trie_root))

      # Iterate across every input token in the span range to find rule matches.
      for idx in range(span_begin, span_end):

        # End early if there are no remaining candidate matches.
        if not search_map[idx]:
          continue

        terminal_symbol = input_symbols[idx]

        # Iterate through partial matches.
        while search_map[idx]:
          search_state = search_map[idx].pop()

          # Consider matching terminal.
          new_trie_node = search_state.trie_node.maybe_get_child(
              terminal_symbol)
          if new_trie_node:
            # Found a match for the terminal in the Trie.
            # Add a partial match to search_map with idx incremented by 1 token.
            new_search_state = SearchState(search_state.anchored_nonterminals,
                                           new_trie_node)
            search_map[idx + 1].append(new_search_state)

          # Consider matching non-terminal.
          nonterminal_tuples = chart.get_from_start(idx)
          if len(search_state.anchored_nonterminals) < MAX_NONTERMINALS:
            # Iterate through lower chart entries with a completed sub-tree
            # that starts at the current index.
            for nt_end, nonterminal in nonterminal_tuples:
              nonterminal_symbol = cfg_rule.CFGSymbol(nonterminal,
                                                      cfg_rule.NON_TERMINAL)
              new_trie_node = search_state.trie_node.maybe_get_child(
                  nonterminal_symbol)
              if new_trie_node:
                # Found a match for the non-terminal in the Trie.
                # Add a partial match to search_map with idx set to the end
                # of the sub-tree span.
                new_anchored_nonterminals = search_state.anchored_nonterminals[:]
                new_anchored_nonterminals.append((idx, nt_end, nonterminal))
                search_map[nt_end].append(
                    SearchState(new_anchored_nonterminals, new_trie_node))

      # Loop through search_map for completed matches at span_end.
      for search_state in search_map[span_end]:
        # Get the ParserRule(s) associated with the particular Trie path.
        matched_rules = search_state.trie_node.values
        if not matched_rules:
          continue

        for rule in matched_rules:
          # Given the ParserRule and anchored nonterminal positions, generate
          # new chart entries and add chart.
          if len(search_state.anchored_nonterminals) == 1:
            # Matched rule contains 1 non-terminal.
            for child in chart.get_from_key(
                *search_state.anchored_nonterminals[0]):
              chart.add(span_begin, span_end, rule, [child])
          elif len(search_state.anchored_nonterminals) == 2:
            # Matched rule contains 2 non-terminals.
            for child_0 in chart.get_from_key(
                *search_state.anchored_nonterminals[0]):
              for child_1 in chart.get_from_key(
                  *search_state.anchored_nonterminals[1]):
                chart.add(span_begin, span_end, rule, [child_0, child_1])
          elif len(search_state.anchored_nonterminals) > 2:
            raise ValueError
          else:
            # Matched rule contains 0 non-terminals.
            chart.add(span_begin, span_end, rule, [])

      for nt in nonterminals:
        chart.postprocess(span_begin, span_end, nt)

      if verbose:
        for nt in nonterminals:
          cell = chart.get_from_key(span_begin, span_end, nt)
          if cell:
            print("Populated (%s,%s): %s - %s" %
                  (span_begin, span_end, nt, cell))

  # Return completed parses.
  return chart.get_from_key(0, input_len, start_idx)
Run bottom up parser using Trie-based implementation.
language/compgen/nqg/common/cky/trie_utils.py