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

  # Convert rules.
  converter = cfg_converter.CFGRuleConverter()
  parser_rules = []
  for rule_idx, rule in enumerate(rules):
    parser_rule = converter.convert_to_cfg_rule(
        lhs=rule.lhs,
        rhs=rule.rhs.split(" "),
        rule_idx=rule_idx,
        nonterminal_prefix=NON_TERMINAL_PREFIX,
        allowed_terminals=set(tokens),
    )
    if parser_rule:
      parser_rules.append(parser_rule)

  start_idx = converter.nonterminals_to_ids[ROOT_SYMBOL]
  nonterminals = converter.nonterminals_to_ids.values()

  input_symbols = []
  for token in tokens:
    if token.startswith(NON_TERMINAL_PREFIX):
      idx = converter.nonterminals_to_ids[token[len(NON_TERMINAL_PREFIX) :]]
      input_symbols.append(cfg_rule.CFGSymbol(idx, cfg_rule.NON_TERMINAL))
    else:
      if token not in converter.terminals_to_ids:
        return False
      idx = converter.terminals_to_ids[token]
      input_symbols.append(cfg_rule.CFGSymbol(idx, cfg_rule.TERMINAL))

  # Run parser.
  parses = cfg_parser.parse_symbols(
      input_symbols,
      parser_rules,
      nonterminals,
      {start_idx},
      _populate_fn,
      _postprocess_fn,
      verbose=verbose,
      max_single_nt_applications=max_single_nt_applications,
  )

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