def induce_rules(examples, config):
  """Return set of induced rules for a given set of examples."""
  # For effeciency, we only run grammar induction a subset of examples based
  # on the sample size specified in the config.
  examples_sample, examples_other = _split_examples(examples, config)

  # Initialize with a rule for each example.
  seed_rules = set()
  for source_str, target_str in examples_sample:
    seed_rules.add(_example_to_rule(source_str, target_str))
  print("Added %s seed rules for examples." % len(seed_rules))

  # Optionally add exact match rules.
  if config.seed_exact_match:
    seed_rules |= exact_match_utils.get_exact_match_rules(examples_sample)
  print("Seed rules after adding exact match rules for sampled examples: %s." %
        len(seed_rules))

  # Iteratively induce rules over the sampled set of examples.
  induced_rules = _induce_rules_for_examples(examples_sample, seed_rules,
                                             config)
  print("Induced %s rules from sample of %s examples." %
        (len(induced_rules), len(examples_sample)))

  # Verify that induced grammar can derive all examples in examples_sample.
  # We use the QCFG parser rather than `derivation_utils` as it is typically
  # faster when we do not need to consider non-terminals in the goal strings,
  # and to verify consistency of the algorithms.
  for source_str, target_str in examples_sample:
    if not qcfg_parser.can_parse(source_str, target_str, induced_rules):
      raise ValueError("Induced rules cannot parse example: (%s, %s)" %
                       (source_str, target_str))

  print("Checking %s remaining examples." % len(examples_other))
  # Add rules for any examples that were not in the original sample and cannot
  # be derived by the induced set of rules.
  if examples_other:
    if config.seed_exact_match:
      induced_rules |= exact_match_utils.get_exact_match_rules(examples_other)
    print("Rules after exact match for remaining examples: %s" %
          len(induced_rules))
    for source_str, target_str in examples_other:
      if not qcfg_parser.can_parse(source_str, target_str, induced_rules):
        induced_rules.add(_example_to_rule(source_str, target_str))
    print("Rules after adding rules for unparsable remaining examples: %s" %
          len(induced_rules))

  return induced_rules
Return set of induced rules for a given set of examples.
language/compgen/nqg/model/induction/induction_utils.py