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.