MediumNLPnlp-119

CFG Rule Extraction Count

Problem

Count the distinct context-free grammar productions across a list of parse trees given as nested lists.

Each node is [head, child, child, ...] and a production is formatted as 'head -> child1 child2 ...', where a child that is itself a list contributes its head symbol. Return the number of distinct production strings.

Hint

Recursively walk each node, collecting the head symbols of its children into a set.

Test cases

case 1

in: [[["S",["NP",["DT","the"],["NN","cat"]],["VP",["V","sat"]]]]]

expected: 6

case 2

in: [[["S",["NP",["DT","the"],["NN","cat"]],["VP",["V","sat"]]],["S",["NP",["DT","the"],["NN","cat"]],["VP",["V","sat"]]]]]

expected: 6

case 3

in: [[]]

expected: 0

case 4

in: [[["S",["A","a"]]]]

expected: 2

Starter codePython

def cfg_rule_count(trees):
    # Your code here
    pass

4 test cases · run your code against them in the editor