Python list to Parse tree

Question

In Python, I have an input of list like following:

[('S', ['NP', 'VP']),
('A', ['V', 'NP']),
('VP', ['V', 'NP']),
('NP', ['DET', 'NP']),
('N', "'mouse'"),
('NP', "'mouse'"),
('DET', "'the'"),
('V', "'saw'"),
('N', "'Ron'"),
('NP', "'Ron'")]

This is the result of the following CYK algorithm:

S -> NP VP
VP -> A NP | V NP
NP -> N N | DET NP | 'chocolate' | 'cat' | 'John' | 'Ron' | 'mouse'
DET -> 'the'
N -> 'chocolate' | 'cat' | 'John' | 'Ron' | 'mouse'
V -> 'saw' | 'bought' | 'ate'
A -> V NP

The string that I want to match with is "Ron saw the mouse".

I want to relate output like this:

(S (NP Ron) (VP (V saw) (NP (DET the) (NP mouse))))

I am not sure how the algorithm should be constructed especially with an ambiguous algorithm which may contain multiple outputs. How should I construct code? Any suggestion what should be a better approach with/without recursion?

UPDATE: I managed to get a single exact parse tree after adding extra parents and child nodes position values with the input list. But my problem doesn't solve with the ambiguous sentence.

Answer 1

The standard way to make a parse tree using the CYK algorithm is to build a new tree node every time you would be storing "true" in the CYK table, and store that node in the table instead. The node should contain pointers to the array elements that produced it: that is, its eventual children.

If you have an ambiguous grammar, you can store sets of nodes in the table instead. The child pointers will then point to these sets of nodes rather than individual nodes. For instance, in the classic ambiguous sentence "I saw a man with a telescope", the root would have a child pointer to a set of two VP nodes: one of which has "with a telescope" modifying the verb, the other with it modifying the noun.

Another alternative is to use an Earley parser (a type of chart parser), and store tree nodes in your Earley items. If you allow Earley items to compare different when they have different tree nodes, you'll end up with entirely separate trees for all the possible parses. (Though be warned that this can lead to exponential runtime in the worst case.)