def parse(tokens,
          rules,
          node_fn,
          postprocess_cell_fn,
          max_single_nt_applications=1,
          verbose=False):
  """Run bottom up parser.

  Args:
    tokens: List of strings for input (terminals or nonterminals).
    rules: List of QCFGRule instances.
    node_fn: Function with input arguments (span_begin, span_end, rule,
      children) and returns a "node".
    postprocess_cell_fn: Function from a list of "nodes" to "nodes".
    max_single_nt_applications: The maximum number of times a rule where the RHS
      is a single nonterminal symbol can be applied consecutively.
    verbose: Print debug output if True.

  Returns:
    A List of "node" objects for completed parses.
  """
  if verbose:
    print("tokens: %s" % (tokens,))
    print("rules:")
    for rule in rules:
      print(str(rule))

  # Our QCFG grammars always use a single NT symbol.
  nt_idx = 0

  # Convert to ParserRule format.
  converter = cfg_converter.CFGRuleConverter()
  idx_to_rule = {}
  parser_rules = []
  rule_idx = 0

  allowed_terminals = set(tokens)
  for rule in rules:
    if not qcfg_rule.is_allowed(rule.source, allowed_terminals):
      continue
    rhs = _convert_nt(rule.source)
    parser_rule = converter.convert_to_cfg_rule(
        lhs=NT_IDX,
        rhs=rhs,
        rule_idx=rule_idx,
        nonterminal_prefix=NON_TERMINAL_PREFIX)
    parser_rules.append(parser_rule)
    idx_to_rule[rule_idx] = rule
    rule_idx += 1

  for token in tokens:
    if not qcfg_rule.is_nt(token) and token not in converter.terminals_to_ids:
      if verbose:
        print("Input token does not appear in rules: %s" % token)
      return []

  input_symbols = []
  for token in tokens:
    if qcfg_rule.is_nt(token):
      input_symbols.append(cfg_rule.CFGSymbol(nt_idx, cfg_rule.NON_TERMINAL))
    else:
      idx = converter.terminals_to_ids[token]
      input_symbols.append(cfg_rule.CFGSymbol(idx, cfg_rule.TERMINAL))

  # Wrap node_fn to pass original Rule instead of CFGRule.
  def populate_fn(span_begin, span_end, parser_rule, children):
    rule = idx_to_rule[parser_rule.idx]
    node = node_fn(span_begin, span_end, rule, children)
    return [node]

  nonterminals = {nt_idx}
  start_idx = nt_idx

  if verbose:
    print("parser_rules: %s" % parser_rules)

  parses = cfg_parser.parse_symbols(
      input_symbols,
      parser_rules,
      nonterminals, {start_idx},
      populate_fn,
      postprocess_cell_fn,
      max_single_nt_applications=max_single_nt_applications,
      verbose=verbose)

  return parses
Run bottom up parser.

  Args:
    tokens: List of strings for input (terminals or nonterminals).
    rules: List of QCFGRule instances.
    node_fn: Function with input arguments (span_begin, span_end, rule,
      children) and returns a "node".
    postprocess_cell_fn: Function from a list of "nodes" to "nodes".
    max_single_nt_applications: The maximum number of times a rule where the RHS
      is a single nonterminal symbol can be applied consecutively.
    verbose: Print debug output if True.

  Returns:
    A List of "node" objects for completed parses.
  
language/compgen/csl/qcfg/qcfg_parser.py