def can_parse(target_string, rules, verbose=False):
  """Returns True if there exists >=1 parse of target_string given rules."""
  tokens = target_string.split(" ")

  # Add a rule for every span in target_string with lhs `ANYTHING`.
  anything_rules = []
  for start_idx in range(len(tokens)):
    for end_idx in range(start_idx + 1, len(tokens) + 1):
      rhs = " ".join(tokens[start_idx:end_idx])
      anything_rules.append(TargetCfgRule(ANYTHING, rhs))

  # Convert tokens to integer IDs.
  terminals_to_ids = {}
  for idx, token in enumerate(set(tokens)):
    terminals_to_ids[token] = idx
  input_ids = [terminals_to_ids[token] for token in tokens]

  # Generate non-terminal IDs.
  nonterminals_to_ids = {}
  nt_idx = 0
  for rule in rules + anything_rules:
    if rule.lhs not in nonterminals_to_ids:
      nonterminals_to_ids[rule.lhs] = nt_idx
      nt_idx += 1
  nonterminals = nonterminals_to_ids.values()
  start_idx = nonterminals_to_ids[ROOT_SYMBOL]

  # Convert rules.
  parser_rules = []
  for rule_idx, rule in enumerate(rules + anything_rules):
    parser_rule = _convert_to_parser_rule(rule, terminals_to_ids,
                                          nonterminals_to_ids, rule_idx)
    if parser_rule:
      parser_rules.append(parser_rule)

  # Run parser.
  parses = cfg_parser.parse(
      input_ids,
      parser_rules,
      nonterminals,
      start_idx,
      _populate_fn,
      _postprocess_fn,
      verbose=verbose)

  if parses:
    return True
  else:
    return False
Returns True if there exists >=1 parse of target_string given rules.
language/compgen/nqg/model/parser/inference/targets/target_grammar.py