def sample(parser_rules,
           start_idx,
           rule_values=None,
           max_recursion=1,
           nonterminal_coef=1,
           verbose=False):
  """Sample data from CFG.

  Args:
    parser_rules: A list of CFGRule instances.
    start_idx: Index of non-terminal that is start symbol.
    rule_values: A optional list of rules with 1-1 mapping to parser rules. The
      rule values can be target grammar, QCFG rules, strings, etc. Only used
      when verbose is True for debugging purpose.
    max_recursion: The maximum number of recursion depth of applying CFG rules.
    nonterminal_coef: The scaling coefficient for rules with nonterminals.
    verbose: Print debug logging if True.

  Returns:
    A nested list of CFGRule instances.
  """
  nonterminals_to_rules = collections.defaultdict(list)
  for rule in parser_rules:
    nonterminals_to_rules[rule.lhs].append(rule)

  def expand_nonterminal(nonterminal, recursion=0):
    rules_to_sample = nonterminals_to_rules[nonterminal.idx]

    if recursion == max_recursion:
      # Filter out the rules that have NTs on RHS.
      rules_to_sample_no_nts = [
          rule for rule in nonterminals_to_rules[nonterminal.idx]
          if cfg_rule.get_arity(rule) == 0
      ]
      # If there are no rules for this NT that contain no NTs, then keep
      # recursing. In this case, we may exceed `max_recursion`.
      if rules_to_sample_no_nts:
        rules_to_sample = rules_to_sample_no_nts
    sampled_rule = sample_rule(rules_to_sample,
                               nonterminal_coef=nonterminal_coef)
    if verbose and rule_values is not None:
      print("Recursion %d, Sampled rule: %s" %
            (recursion, rule_values[sampled_rule.idx]))

    output = [sampled_rule]
    for symbol in sampled_rule.rhs:
      if symbol.type == cfg_rule.NON_TERMINAL:
        output.append(expand_nonterminal(symbol, recursion=recursion + 1))
    return output

  start_symbol = cfg_rule.CFGSymbol(idx=start_idx, type=cfg_rule.NON_TERMINAL)
  output = expand_nonterminal(start_symbol, recursion=0)
  return output
Sample data from CFG.

  Args:
    parser_rules: A list of CFGRule instances.
    start_idx: Index of non-terminal that is start symbol.
    rule_values: A optional list of rules with 1-1 mapping to parser rules. The
      rule values can be target grammar, QCFG rules, strings, etc. Only used
      when verbose is True for debugging purpose.
    max_recursion: The maximum number of recursion depth of applying CFG rules.
    nonterminal_coef: The scaling coefficient for rules with nonterminals.
    verbose: Print debug logging if True.

  Returns:
    A nested list of CFGRule instances.
  
language/compgen/csl/cky/cfg_sampler.py