docs: def _parse(s, g):
      """Parses sentence 's' using CNF grammar 'g'."""
      # The CYK table. Indexed with a 2-tuple: (start pos, end pos)
      table = defaultdict(set)
      # Top-level structure is similar to the CYK table. Each cell is a dict from
      # rule name to the best (lightest) tree for that rule.
      trees = defaultdict(dict)
      # Populate base case with existing terminal production rules
      for i, w in enumerate(s):
          for terminal, rules in g.terminal_rules.items():
              if match(terminal, w):
                  for rule in rules:
                      table[(i, i)].add(rule)
                      if (rule.lhs not in trees[(i, i)] or
                          rule.weight < trees[(i, i)][rule.lhs].weight):
                          trees[(i, i)][rule.lhs] = RuleNode(rule, [T(w)], weight=rule.weight)
  
      # Iterate over lengths of sub-sentences
      for l in xrange(2, len(s) + 1):
          # Iterate over sub-sentences with the given length
          for i in xrange(len(s) - l + 1):
              # Choose partition of the sub-sentence in [1, l)
              for p in xrange(i + 1, i + l):
                  span1 = (i, p - 1)
                  span2 = (p, i + l - 1)
                  for r1, r2 in itertools.product(table[span1], table[span2]):
                      for rule in g.nonterminal_rules.get((r1.lhs, r2.lhs), []):
                          table[(i, i + l - 1)].add(rule)
                          r1_tree = trees[span1][r1.lhs]
                          r2_tree = trees[span2][r2.lhs]
                          rule_total_weight = rule.weight + r1_tree.weight + r2_tree.weight
                          if (rule.lhs not in trees[(i, i + l - 1)]
                              or rule_total_weight < trees[(i, i + l - 1)][rule.lhs].weight):
                              trees[(i, i + l - 1)][rule.lhs] = RuleNode(rule, [r1_tree, r2_tree], weight=rule_total_weight)
      return table, trees