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.